CHAPTER

5

Cryptography

ZHQMZMGMZMFM

—GJuliusCaesar

KXJEYUREBEZWEHEWRYTUHEYFSKREHEGOYFIWTTTUOLKSYCAJPOBOTEI

ZONTXBYBWTGONEYCUZWRGDSONSXBOUYWRHEBAAHYUSEDQ

—JohnFKennedy

5.1 Introduction

Cryptography is where security engineering meets mathematics. It provides

uswiththetoolsthatunderliemostmodernsecurityprotocols.Itisprobably

the key enabling technology for protecting distributed systems, yet it is

surprisinglyhardtodoright.Aswe’vealreadyseeninChapter3,‘Protocols’,

cryptography has often been used to protect the wrong things, or used to

protecttheminthewrongway.We’llseeplentymoreexampleswhenwestart

lookingindetailatrealapplications.

Unfortunately, the computer security and cryptology communities have

driftedapart over the last 25 years. Security peopledon’t always understand

the available crypto tools, and crypto people don’t always understand the

real-worldproblems.Thereareanumberofreasonsforthis,suchasdifferent

professional backgrounds (computer science versusmathematics) and differ-

ent research funding (governments have tried to promote computer security

research while suppressing cryptography). It reminds me of a story told by

a medical friend. While she was young, she worked for a few years in a

countrywhere,foreconomicreasons,they’dshortenedtheirmedicaldegrees

and concentrated on producing specialists as quickly as possible. One day,

129

130 Chapter5 ■ Cryptography

a patient who’d had both kidneys removed and was awaiting a transplant

neededherdialysisshuntredone.Thesurgeonsentthepatientbackfromthe

theateronthegroundsthattherewasnourinalysisonfile.Itjustdidn’toccur

tohimthatapatientwithnokidneyscouldn’tproduceanyurine.

Just as a doctor needs to understand physiology as well as surgery, so

a security engineer needs to be familiar with cryptology as well as computer

security(andmuchelse).Thischapterisaimedatpeoplewithoutanytraining

in cryptology; cryptologists will find littlein it that they don’t already know.

As I only have a few dozen pages, and a proper exposition of modern cryp-

tographywouldrunintothousands,Iwon’tgointomuchofthemathematics

(there are lots of books that do that; see the end of the chapter for further

reading). I’ll just explain the basic intuitions and constructions that seem

to cause the most confusion. If you have to use cryptography in anything

resemblinganovelway,thenIstronglyrecommendthatyoureadalotmore

about it—and talk to some real experts. The security engineer Paul Kocher

remarked,atakeynotespeechatCrypto2007,thatyoucouldexpecttobreak

any cryptoproductdesignedby‘any company thatdoesn’temploysomeone

inthisroom’.Thereisafairbitoftruthinthat.

Computer security people often ask for non-mathematical definitions of

cryptographic terms. The basic terminology is that cryptography refers to

the science and art of designing ciphers; cryptanalysis to the science and

art of breaking them; while cryptology, often shortened to just crypto, is

thestudyofboth. Theinputtoanencryptionprocessiscommonly calledthe

plaintext, and the outputthe ciphertext. Thereafter,things getsomewhat more

complicated. There are a number of cryptographic primitives—basic building

blocks, such as block ciphers, stream ciphers, and hash functions. Block ciphers

may either have one key for both encryption and decryption, in which case

they’re called shared-key (also secret-key or symmetric), or have separate keys

for encryption and decryption, in which case they’re called public-key or

asymmetric. A digital signature scheme is a special type of asymmetric crypto

primitive.

Intherestofthischapter,Iwillfirstgivesomesimplehistoricalexamplesto

illustratethebasicconcepts.I’llthentrytofine-tunedefinitionsbyintroducing

the random oracle model, which many cryptologists use. Finally, I’ll show how

some of the more important cryptographic algorithms actually work, and

howtheycanbeusedtoprotectdata.

5.2 Historical Background

Suetonius tells us that Julius Caesar enciphered his dispatches by writing

‘D’ for ‘A’, ‘E’ for ‘B’ and so on[1232]. When Augustus Caesar ascended the

throne,hechangedtheimperialciphersystemsothat‘C’wasnowwrittenfor

5.2 HistoricalBackground 131

‘A’,‘D’for‘B’etcetera.Inmodernterminology,wewouldsaythathechanged

the key from ‘D’ to ‘C’. Remarkably, a similar code was used by Bernardo

Provenzano,allegedlythecapoditutticapioftheSicilianmafia,whowrote‘4’

for‘a,‘5’for‘b’andsoon.ThisleddirectlytohiscapturebytheItalianpolice

in2006aftertheyinterceptedanddecipheredsomeofhismessages[1034].

The Arabs generalised this idea to the monoalphabetic substitution, in which

akeywordisusedtopermutethecipheralphabet.Wewillwritetheplaintext

inlowercaseletters,andtheciphertextinuppercase,asshowninFigure5.1:

abcdefghijklmnopqrstuvwxyz

SECURITYABDFGHJKLMNOPQVWXZ

Figure5.1:Monoalphabeticsubstitutioncipher

OYAN RWSGKFR AN AH RHTFANY MSOYRM OYSH SMSEAC NCMAKO;but breaking

ciphers of this kind is a straightforward pencil and paper puzzle, which you

may have done in primary school. The trick is that some letters, and combi-

nations of letters, are much more common than others; in English the most

common letters are e,t,a,i,o,n,s,h,r,d,l,u in that order. Artificial intelligence

researchers have shown some interest in writing programs to solve monoal-

phabeticsubstitutions.Usingletteranddigram(letterpair)frequenciesalone,

they typically succeed with about 600 letters of ciphertext, while smarter

strategiessuchasguessingprobablewordscancutthistoabout150letters.A

humancryptanalystwillusuallyrequiremuchless.

Therearebasicallytwowaystomakeastrongercipher—thestreamcipher

and the block cipher. In the former, you make the encryption rule depend on

a plaintext symbol’s position in the stream of plaintext symbols, while in the

latter you encrypt several plaintext symbols at once in a block. Let’s look at

earlyexamples.

5.2.1 An Early Stream Cipher — The Vigene`re

This early stream cipher is commonly ascribed to the Frenchman Blaise de

Vigene`re, a diplomat who served King Charles IX. It works by adding a key

repeatedly into the plaintext using the convention that ‘A’ = 0, ‘B’ = 1, ... ,

‘Z’=25,andadditioniscarriedoutmodulo26—thatis,iftheresultisgreater

than25,wesubtractasmanymultiplesof26asareneededtobringisintothe

range[0,...,25],thatis,[A,...,Z].Mathematicianswritethisas

C=P+K mod26

So,forexample,whenweaddP(15)toU(20)weget35,whichwereduceto

9bysubtracting26.8correspondstoJ,sotheencryptionofPunderthekeyU

(andofUunderthekeyP)isJ.Sointhisnotation,JuliusCaesar’ssystemuseda

132 Chapter5 ■ Cryptography

fixed key K =D1, while Augustus Caesar’s used K =C and Vigene`re used a

repeating key, also known as a running key. Various means were developed

to dothis additionquickly,including printedtables and, for field use,cipher

wheels. Whatever the implementation technology, the encryption using a

repeatedkeywordforthekeywouldlookasshowninFigure5.2:

Plain tobeornottobethatisthequestion

Key runrunrunrunrunrunrunrunrunrun

Cipher KIOVIEEIGKIOVNURNVJNUVKHVMGZIA

Figure5.2:Vigene`re(polyalphabeticsubstitutioncipher)

Anumberofpeopleappeartohaveworkedouthowtosolvepolyalphabetic

ciphers, from the womaniser Giacomo Casanova to the computing pioneer

CharlesBabbage.Howeverthefirstpublishedsolutionwasin1863byFriedrich

Kasiski,aPrussianinfantryofficer[695].Henoticedthatgivenalongenough

pieceofciphertext,repeatedpatternswillappearatmultiplesofthekeyword

length.

InFigure5.2,forexample,wesee‘KIOV’repeatedafternineletters,and‘NU’

after six. Since three divides both six and nine, we might guess a keyword

of three letters. It follows that ciphertext letters one, four, seven and so on

all enciphered under the same keyletter; so we can use frequency analysis

techniques to guess the most likely values of this letter, and then repeat the

processforthesecondandthirdlettersofthekey.

5.2.2 The One-Time Pad

One way to make a stream cipher of this type proof against attacks is for the

keysequencetobeaslongastheplaintext,andtoneverrepeat.Thiswaspro-

posedbyGilbertVernamduringWorldWar1[676];itseffectisthatgivenany

ciphertext,andanyplaintextofthesamelength,thereisakeywhichdecrypts

the ciphertext to the plaintext. Regardless of the amount of computation that

opponents can do, they are none the wiser, as all possible plaintexts are just

aslikely.Thissystemisknownastheone-timepad.LeoMarks’engagingbook

on cryptography in the Special Operations Executive in World War 2[836]

relates how one-time key material was printed on silk, which agents could

conceal inside their clothing; whenever a key had been used it was torn off

andburnt.

Anexampleshouldexplainallthis.Supposeyouhadinterceptedamessage

from a wartime German agent which you knew started with ‘Heil Hitler’,

and the first ten letters of ciphertext were DGTYI BWPJA. This means that

1modulo23,asthealphabetCaesarusedwroteUasV,JasI,andhadnoW.

5.2 HistoricalBackground 133

the first ten letters of the one-time pad were wclnb tdefj, as shown in

Figure5.3:

Plain heilhitler

Key wclnbtdefj

Cipher DGTYIBWPJA

Figure5.3:Aspy’smessage

Butoncehe’sburntthepieceofsilkwithhiskeymaterial,thespycanclaim

thathe’sactuallyamemberoftheanti-Naziundergroundresistance,andthe

messageactuallysaid‘HangHitler’.Thisisquitepossible,asthekeymaterial

couldjustaseasilyhavebeenwggsb tdefj,asshowninFigure5.4:

Cipher DGTYIBWPJA

Key wggsbtdefj

Plain hanghitler

Figure5.4:Whatthespyclaimedhesaid

Nowwerarelygetanythingfornothingincryptology,andthepriceofthe

perfectsecrecyoftheone-timepadisthatitfailscompletelytoprotectmessage

integrity. Suppose for example that you wanted to get this spy into trouble,

youcouldchangetheciphertexttoDCYTI BWPJA(Figure5.5):

Cipher DCYTIBWPJA

Key wclnbtdefj

Plain hanghitler

Figure5.5:Manipulatingthemessagetoentrapthespy

During the Second World War, Claude Shannon proved that a cipher has

perfect secrecy if and only if there are as many possible keys as possible

plaintexts,andeverykeyisequallylikely;sotheone-timepadistheonlykind

ofsystemwhichoffersperfectsecrecy[1157,1158].

The one-time pad is still used for some diplomatic and intelligence traffic,

butitconsumesasmuchkeymaterialasthereistrafficandthisistooexpensive

for most applications. It’s more common for stream ciphers to use a suitable

pseudorandomnumbergeneratortoexpandashortkeyintoalongkeystream.

Thedataisthenencryptedbyexclusive-or’ingthekeystream,onebitatatime,

with the data. It’s not enough for the keystream to appear ‘‘random’’ in

the sense of passing the standard statistical randomness tests: it must also

havethepropertythatanopponentwhogetshishandsonevenquitealotof

134 Chapter5 ■ Cryptography

keystream bits should not be able to predict any more of them. I’ll formalise

thismoretightlyinthenextsection.

Stream ciphers are commonly used nowadays in hardware applications

where the number of gates has to be minimised to save power. We’ll look

at some actual designs in later chapters, including the A5 algorithm used

to encipher GSM mobile phone traffic (in the chapter on ‘Telecom System

Security’), and the shift register systems used in pay-per-view TV and DVD

CSS (in the chapter on ‘Copyright and Privacy Protection’). However, block

ciphers are more suited for many applications where encryption is done in

software,solet’slookatthemnext.

5.2.3 An Early Block Cipher — Playfair

One of the best-known early block ciphers is the Playfair system. It was

invented in 1854 by Sir Charles Wheatstone, a telegraph pioneer who

also invented the concertina and the Wheatstone bridge. The reason it’s

notcalledtheWheatstonecipheristhathedemonstratedittoBaronPlayfair,

apolitician;PlayfairinturndemonstratedittoPrinceAlbertandtoViscount

Palmerston(laterPrimeMinister),onanapkinafterdinner.

Thiscipherusesa5by5grid,inwhichweplacethealphabet,permutedby

thekeyword,andomittingtheletter‘J’(seeFigure5.6):

P A L M E

R S T O N

B C D F G

H I K Q U

V W X Y Z

Figure5.6:ThePlayfairencipheringtableau

Theplaintextisfirstconditionedbyreplacing‘J’with‘I’whereveritoccurs,

then dividing it into letter pairs, preventing double letters occurring in a

pair by separating them with an ‘x’, and finally adding a ‘z’ if necessary to

complete the last letter pair. The example Playfair wrote on his napkin was

‘LordGranville’sletter’whichbecomes‘lo rd gr an vi lx le sl et te rz’.

Itisthenencipheredtwolettersatatimeusingthefollowingrules:

ifthetwolettersareinthesameroworcolumn,theyarereplacedbythe

succeeding letters. For example, ‘am’ enciphers to ‘LE’

otherwisethetwolettersstandattwoofthecornersofarectanglein

thetable,andwereplacethemwiththelettersattheothertwocornersof

this rectangle. For example, ‘lo’ enciphers to ‘MT’.

5.2 HistoricalBackground 135

Wecannowencipherourspecimentextasfollows:

Plain lo rd gr an vi lx le sl et te rz

Cipher MT TB BN ES WH TL MP TA LN NL NV

Figure5.7:ExampleofPlayfairenciphering

Variants of this cipher were used by the British army as a field cipher in

World War 1, and by the Americans and Germans in World War 2. It’s a

substantial improvement on Vigene`re as the statistics which an analyst can

collectareofdigraphs(letterpairs)ratherthansingleletters,sothedistribution

ismuchflatterandmoreciphertextisneededforanattack.

Again,it’snotenoughfortheoutputofablockciphertojustlookintuitively

‘random’.Playfairciphertextslookrandom;buttheyhavethepropertythatif

youchange asingleletterofaplaintextpair,thenoftenonlyasingleletterof

the ciphertext will change. Thus using the key in Figure 5.7, rd enciphers to

TB while rf enciphers to OB and rg enciphers to NB. One consequence is that

givenenoughciphertext,orafewprobablewords,thetable(oranequivalent

one) can be reconstructed[512]. So we will want the effects of small changes

in a block cipher’s input to diffuse completely through its output: changing

oneinputbitshould,onaverage,causehalfoftheoutputbitstochange.We’ll

tightentheseideasupinthenextsection.

Thesecurityofablockciphercanbegreatlyimprovedbychoosingalonger

block length than two characters. For example, the Data Encryption Standard

(DES), which is widely used in banking, has a block length of 64 bits, which

equatestoeightasciicharactersandtheAdvancedEncryptionStandard(AES),

which is replacing it in many applications, has a block length of twice this. I

discusstheinternaldetailsofDESandAESbelow;forthetimebeing,I’lljust

remark that an eight byte or sixteen byte block size is not enough of itself.

For example, if a bank account number always appears at the same place

in a transaction, then it’s likely to produce the same ciphertext every time a

transactioninvolvingitisencryptedwiththesamekey.

Thismightallowanopponenttocutandpastepartsoftwodifferentcipher-

texts in order to produce a seemingly genuine but unauthorized transaction.

Supposeabadmanworkedforabank’sphonecompany,andcouldintercept

theirtraffic.Ifhemonitoredanencipheredtransactionthatheknewsaid‘‘Pay

IBM $10,000,000’’ he might wire $1,000 to his brother causing the bank com-

puter to insert another transaction saying ‘‘Pay John Smith $1,000’’, intercept

thisinstruction,andmakeupafalseinstructionfromthetwociphertextsthat

decrypted as ‘‘Pay John Smith $10,000,000’’. So unless the cipher block is as

largeasthemessage,theciphertextwillcontainmorethanoneblock andwe

willusuallyneedsomewayofbindingtheblockstogether.

136 Chapter5 ■ Cryptography

5.2.4 One-Way Functions

The third classical type of cipher is the one-way function. This evolved to

protect the integrity and authenticity of messages, which as we’ve seen

is not protected at all by many simple ciphers where it is often easy to

manipulatetheciphertextinsuchawayastocauseapredictablechangeinthe

plaintext.

Aftertheinventionofthetelegraphinthemid-19thcentury,banksrapidly

became its main users and developed systems for transferring money elec-

tronically. Of course, it isn’t the money itself which is ‘wired’ but a payment

instruction,suchas:

‘ToLombardBank,London.Pleasepayfromouraccountwithyouno.1234567890

thesumof£1000toJohnSmithof456ChestertonRoad,whohasanaccountwith

HSBC Bank Cambridge no. 301234 4567890123, and notify him that this was

for ‘‘wedding present from Doreen Smith’’. From First Cowboy Bank of Santa

Barbara,CA,USA.Chargestobepaidbyus.’

Sincetelegraphmessageswererelayedfromoneofficetoanotherbyhuman

operators,itwaspossibleforanoperatortomanipulateapaymentmessage.

In the nineteenth century, banks, telegraph companies and shipping com-

panies developed code books that could not only protect transactions but also

shorten them—which was very important given the costs of international

telegrams at the time. A code book was essentially a block cipher which

mapped words or phrases to fixed-length groups of letters or numbers. So

‘Pleasepayfromouraccountwithyouno.’mightbecome‘AFVCT’.Acompet-

ing technology from the 1920s was rotor machines, mechanical cipher devices

whichproduceaverylongsequenceofpseudorandomnumbersandcombine

them with plaintext to get ciphertext; these were independently invented by

a number of people, many of whom dreamed of making a fortune selling

them to the banking industry. Banks weren’t in general interested, but rotor

machines became the main high-level ciphers used by the combatants in

WorldWar2.

The banks realised that neither mechanical stream ciphers nor code books

protect message authenticity. If, for example, the codeword for ‘1000’ is

‘mauve’andfor‘1,000,000’is‘magenta’,thenthecrookedtelegraphclerkwho

cancomparethecodedtrafficwithknowntransactionsshouldbeabletofigure

thisoutandsubstituteonefortheother.

The critical innovation, for the banks’ purposes, was to use a code book

but to make the coding one-way by adding the code groups together into

a number called a test key. (Modern cryptographers would describe it as a

hash value or message authentication code, terms I’ll define more carefully

later.)

5.2 HistoricalBackground 137

Hereisasimpleexample.Supposethebankhasacodebookwithatableof

numberscorrespondingtopaymentamountsasinFigure5.8:

0 1 2 3 4 5 6 7 8 9

x1000 14 22 40 87 69 93 71 35 06 58

x10,000 73 38 15 46 91 82 00 29 64 57

x100,000 95 70 09 54 82 63 21 47 36 18

x1,000,000 53 77 66 29 40 12 31 05 87 94

Figure5.8:Asimpletestkeysystem

Nowinordertoauthenticateatransactionfor£376,514weaddtogether53

(no millions), 54 (300,000), 29 (70,000) and 71 (6,000). (It’s common to ignore

thelesssignificantdigitsoftheamount.)Thisgivesusatestkeyof207.

Most real systems were more complex than this; they usually had tables

for currency codes, dates and even recipient account numbers. In the better

systems, the code groups were four digits long rather than two, and in order

to make it harder for an attacker to reconstruct the tables, the test keys were

compressed:akeyof‘7549’mightbecome‘23’byaddingthefirstandsecond

digits,andthethirdandfourthdigits,andignoringthecarry.

Thismadesuchtestkeysystemsintoone-wayfunctionsinthatalthoughgiven

knowledgeofthekeyitwaspossibletocomputeatestfromamessage,itwas

not possible to reverse the process and recover a message from a test—the

test just did not contain enough information. Indeed, one-way functions had

beenaroundsinceatleasttheseventeenthcentury.ThescientistRobertHooke

publishedin1678thesortedanagram‘ceiiinosssttuu’andrevealedtwoyears

later that it was derived from ‘Ut tensio sic uis’—‘the force varies as the

tension’, or what we now call Hooke’s law for a spring. (The goal was to

establishpriorityfortheideawhilegivinghimtimetocontinuedevelopingit.)

Test keys are not strong by the standards of modern cryptography. Given

somewherebetweenafewdozenandafewhundredtestedmessages,depend-

ing on the design details, a patient analyst could reconstruct enough of the

tables to forge a transaction. With a few carefully chosen messages inserted

intothebanking systemby anaccomplice,it’seveneasierstill.Butthebanks

got away with it: test keys worked fine from the late nineteenth century

throughthe1980’s.Inseveralyearsworkingasabanksecurityconsultant,and

listening to elderly bank auditors’ tales over lunch, I only ever heard of two

cases of fraud that exploitedit: one external attempt involving cryptanalysis,

whichfailedbecausetheattackerdidn’tunderstandbankprocedures,andone

successful but small fraud involving a crooked staff member. I’ll discuss the

systems which replaced test keys, and the whole issue of how to tie cryp-

tographic authentication mechanisms to procedural protection such as dual

138 Chapter5 ■ Cryptography

control, inthechapteron‘Banking andBookkeeping’.Forthemeantime,test

keysaretheclassicexampleofaone-wayfunctionusedforauthentication.

Laterexamplesincludedfunctionsforapplicationsdiscussedintheprevious

chapters, such as storing passwords in a one-way encrypted password file,

andcomputingaresponsefromachallengeinanauthenticationprotocol.

5.2.5 Asymmetric Primitives

Finally, some modern cryptosystems are asymmetric, in that different keys

areusedforencryptionanddecryption.So,forexample,manypeoplepublish

on their web page a public key with which people can encrypt messages to

send to them; the owner of the web page can then decrypt them using the

correspondingprivatekey.

There are some pre-computer examples of this too; perhaps the best is the

postalservice.Youcansendmeaprivatemessagejustassimplybyaddressing

ittomeanddroppingitintoapostbox.Oncethat’sdone,I’mtheonlyperson

who’ll be able to read it. There are of course many things that can go wrong.

You might get the wrong address for me (whether by error or as a result of

deception);thepolicemightgetawarranttoopenmymail;thelettermightbe

stolenbyadishonestpostman;afraudstermightredirectmymailwithoutmy

knowledge;orathiefmightstealtheletterfrommymailbox.Therearesimilar

thingsthatcangowrongwithpublickeycryptography.Falsepublickeyscan

be inserted into the system, computers can be hacked, people can be coerced

andsoon.We’lllookattheseproblemsinmoredetailinlaterchapters.

Anotherasymmetricapplicationofcryptographyisthedigitalsignature.The

idea here is that I can sign a message using a private signature key and then

anybodycancheckthisusingmypublicsignatureverificationkey.Again,there

are pre-computer analogues in the form of manuscript signatures and seals;

and again, there is a remarkably similar litany of things that can go wrong,

bothwiththeoldwayofdoingthingsandwiththenew.

5.3 The Random Oracle Model

Beforedelvingintothedetaileddesignofmodernciphers,Iwanttotakeafew

pages to refine the definitions of the various types of cipher. (Readers who

are phobic about theoretical computer science should skip this section at a

firstpass;I’veincludeditbecauseabasicgraspoftheterminologyofrandom

oraclesisneededtodeciphermanyrecentresearchpapersoncryptography.)

Therandomoraclemodelseekstoformalizetheideathatacipheris‘good’if,

whenviewedinasuitableway,itisindistinguishablefromarandomfunction

ofacertaintype.Iwillcallacryptographicprimitivepseudorandomifitpasses

all the statistical and other tests which a random function of the appropriate

5.3 TheRandomOracleModel 139

typewouldpass,inwhatevermodelofcomputationweareusing.Ofcourse,

thecryptographicprimitivewillactuallybeanalgorithm,implementedasan

array of gates in hardware or a program in software; but the outputs should

‘lookrandom’inthatthey’reindistinguishablefromasuitablerandomoracle

giventhetypeandthenumberofteststhatourcomputationmodelpermits.

Inthisway,wecanhopetoseparatetheproblemofdesigningciphersfrom

theproblemofusingthemcorrectly.Mathematicianswhodesigncipherscan

provide evidence that their cipher is pseudorandom. Quite separately, a

computer scientist who has designed a cryptographic protocol can try to

prove that it is secure on the assumption that the crypto primitives used

to implement it are pseudorandom. The process isn’t infallible, as we saw

with proofs of protocol correctness. Theorems can have bugs, just like pro-

grams; the problem could be idealized wrongly; and the mathematicians

might be using a different model of computation from the computer scien-

tists. In fact, there is a live debate among crypto researchers about whether

formal models and proofs are valuable[724]. But crypto theory can help us

sharpen our understanding of how ciphers behave and how they can safely

beused.

We can visualize a random oracle as an elf sitting in a black box with a

sourceofphysicalrandomnessandsomemeansofstorage(seeFigure5.9)—

representedinourpicturebythediceandthescroll.Theelfwillacceptinputs

of a certain type, then look in the scroll to see whether this query has ever

been answered before. If so, it will give the answer it finds there; if not,

it will generate an answer at random by throwing the dice. We’ll further

assume that there is some kind of bandwidth limitation—that the elf will

only answer so many queries every second. This ideal will turn out to be

useful as a way of refining our notions of a stream cipher, a hash function,

a block cipher, a public key encryption algorithm and a digital signature

scheme.

Figure5.9:Therandomoracle

140 Chapter5 ■ Cryptography

Finally, we can get a useful simplification of our conceptual model by

notingthatencryptioncanbeusedtoprotectdataacrosstimeaswellasacross

distance. A good example is when we encrypt data before storing it with a

third-partybackupservice,andmaydecryptitlaterifwehavetorecoverfrom

adiskcrash.Inthiscase,weonlyneedasingleencryption/decryptiondevice,

rather than having one at each end of a communications link. For simplicity,

letusassumeitisthissortofapplicationwearemodellinghere.Theusertakes

adiskettetotheciphermachine,typesinakey,issuesaninstruction,andthe

dataget transformedin the appropriateway. A yearlater,she comes back to

getthedatadecryptedandverified.

We shall now look at this model in more detail for various different

cryptographicprimitives.

5.3.1 Random Functions — Hash Functions

The first type of random oracle is the random function. A random function

accepts an input string of any length and outputs a random string of fixed

length, say n bits long. So the elf just has a simple list of inputs and outputs,

which grows steadily as it works. (We’ll ignore any effects of the size of the

scrollandassumethatallqueriesareansweredinconstanttime.)

Random functions are our model for one-way functions, also known as

cryptographic hash functions, which have many practical uses. They were first

used in computer systems for one-way encryption of passwords in the 1960s

and, as I mentioned in the chapter on security protocols, are used today in

a number of authentication systems. They are used to compute checksums

on files in forensic applications: presented with a computer seized from a

suspect, you can compute hash values of the files to identify which files are

alreadyknown(suchassystemfiles)andwhicharenovel(suchasuserdata).

Hash values are also used as a means of checking the integrity of files, as

they will change if a file is corrupted. In messaging applications, hashes are

often known as message digests; given a message M we can pass it through a

pseudorandom function to get a digest, say h(M), which can stand in for the

message in various applications. One example is digital signature: signature

algorithmstendtobeslowifthemessageislong,soit’susuallyconvenientto

signamessagedigestratherthanthemessageitself.

Anotherapplicationistimestamping.Ifwewantevidencethatwepossessed

agivenelectronicdocumentbyacertaindate,wemightsubmitittoanonline

time-stampingservice.However,ifthedocumentisstillsecret—forexample

an invention which we plan to patent, and for which we merely want to

establish a priority date—then we might not send the timestamping service

thewholedocument,butjustthemessagedigest.

5.3 TheRandomOracleModel 141

5.3.1.1 Properties

Thefirstmainpropertyofarandomfunctionisone-wayness.Givenknowledge

ofaninputxwecaneasilycomputethehashvalueh(x),butitisverydifficult

given the hash value h(x) to find a corresponding preimage x if one is not

alreadyknown.(Theelfwillonlypickoutputsforgiveninputs,nottheother

wayround.)Astheoutputisrandom,thebestanattackerwhowantstoinvert

a random function can do is to keep on feeding in more inputs until he gets

lucky.Apseudorandomfunctionwillhavethesameproperties,ortheycould

beusedtodistinguishitfromarandomfunction,contrarytoourdefinition.It

followsthatapseudorandomfunctionwillalsobeaone-wayfunction,provided

thereareenoughpossibleoutputsthattheopponentcan’tfindadesiredtarget

output by chance. This means choosing the output to be an n-bit number

wheretheopponentcan’tdoanythingnear2n computations.

A second property of pseudorandom functions is that the output will not

give any information at all about even part of the input. Thus a one-way

encryption of the value x can be accomplished by concatenating it with a

secret keyk and computing h(x,k). If the hash function isn’t random enough,

though, using it for one-way encryption in this manner is asking for trouble.

A topical example comes from the authentication in GSM mobile phones,

wherea16bytechallengefromthebasestationisconcatenatedwitha16byte

secret key known to the phone into a 32 byte number, and passed through

a hash function to give an 11 byte output[226]. The idea is that the phone

company also knows k and can check this computation, while someone who

eavesdrops on the radio link can only get a number of values of the random

challengexandcorrespondingoutputfromh(x,k).Sotheeavesdroppermust

not be able to get any information about k, or compute h(y,k) for a new

input y. But the one-way function used by many phone companies isn’t one-

way enough, with the result that an eavesdropper who can pretend to be

a base station and send a phone about 150,000 suitable challenges and get

the responses can compute the key. I’ll discuss this failure in more detail in

section20.3.2.

Athirdpropertyofpseudorandomfunctionswithsufficientlylongoutputs

is that it is hard to find collisions, that is, different messages M (cid:1)=M with

1 2

h(M )=h(M ). Unless the opponent can find a shortcut attack (which would

1 2

meanthefunctionwasn’treallypseudorandom)thenthebestwayoffindinga

collisionistocollectalargesetofmessagesM andtheircorrespondinghashes

i

h(M), sort the hashes, and look for a match. If the hash function output is an

i

n-bit number, so that there are 2n possible hash values, then the number of

hashes the enemy will need to compute before he can expect to find a match

will be about the square root of this, namely 2n/2 hashes. This fact is of huge

importanceinsecurityengineering,solet’slookatitmoreclosely.

142 Chapter5 ■ Cryptography

5.3.1.2 The Birthday Theorem

The birthday theorem gets its name from the following problem. A maths

teacherasksatypicalclassof30pupilswhattheythinkistheprobabilitythat

two of them have the same birthday. Most pupils will intuitively think it’s

unlikely, and the maths teacher then asks the pupils to state their birthdays

oneafteranother.Astheresultseemsunlikelytomostpeople,it’salsoknown

asthe‘birthdayparadox’.Theoddsofamatchexceed50%once23pupilshave

beencalled.

The birthday theorem was first invented in the 1930’s to count fish, which

ledtoitsalsobeingknown ascapture-recapture statistics[1123].Supposethere

areNfishinalakeandyoucatchmofthem,ringthemandthrowthemback,

then when you first catch a fish you’ve ringed already, m should be ‘about’

√thesquarerootofN.Theintuitivereasonwhythisholdsisthatonceyouhave

Nsamples,eachcouldp√otentia√llymatchanyoftheothers,sothenumberof

possiblematchesisabout Nx NorN,whichiswhatyouneed2.

Thistheoremhasmanyapplicationsforthesecurityengineer.Forexample,

if we have a biometric system which can authenticate a person’s claim to

identitywithaprobabilityofonlyoneinamillionthattworandomlyselected

subjects will be falsely identified as the same person, this doesn’t mean that

we can use it as a reliable means of identification in a university with a user

population of twenty thousand staff and students. This is because there will

be almost two hundred million possible pairs. In fact, you expect to find the

firstcollision—thefirstpairofpeoplewhocanbemistakenforeachotherby

thesystem—onceyouhavesomewhatoverathousandpeopleenrolled.

Therearesomeapplicationswherecollision-searchattacksaren’taproblem,

such as in challenge-response protocols where an attacker would have to be

abletofindtheanswertothechallengejustissued,andwhereyoucanprevent

challenges repeating. (For example, the challenge might be generated by

encryptingacounter.)Soinidentify-friend-or-foe(IFF)systems,forexample,

commonequipmenthasaresponselengthof48to80bits.

However,thereareotherapplicationsinwhichcollisionsareunacceptable.

In a digital signature application, if it were possible to find collisions with

h(M )=h(M ) but M (cid:1)=M , then a Mafia owned bookstore’s web site might

1 2 1 2

get you to sign a message M saying something like ‘I hereby order a copy

1

ofRubberFetishvolume7for$32.95’andthenpresentthesignaturetogether

with an M saying something like ‘I hereby mortgage my house for $75,000

2

andpleasemakethefundspayabletoMafiaHoldingsInc.,Bermuda’.

Forthisreason,hashfunctionsusedwithdigitalsignatureschemesgenerally

havenlargeenoughtomakethemcollision-free,thatis,that2n/2computations

2More precisely, the probability that m fish chosen randomly from N fish are different is

β=N(N−1)...(N−m+1)/NmwhichisasymptoticallysolvedbyN(cid:3)m2/2log(1/β)[708].

5.3 TheRandomOracleModel 143

are impractical for an opponent. The two most common are MD5, which has

a128-bit outputandwillthus requireat most264 computations tobreak,and

SHA1with a160-bit output and awork factor for thecryptanalyst ofat most

280. However, collision search gives at best an upper bound on the strength

of a hash function, and both these particular functions have turned out to be

disappointing,withcryptanalyticattacksthatI’lldescribelaterinsection5.6.2.

Collisions are easy to find for MD4 and MD5, while for SHA-1 it takes about

260computationstofindacollision—somethingthatabotnetofhalfamillion

machinesshouldbeabletodoinafewdays.

In any case, a pseudorandom function is also often referred to as being

collisionfreeorcollisionintractable.Thisdoesn’tmeanthatcollisionsdon’texist

—they must, as the set of possible inputs is larger than the set of pos-

sible outputs—just that you will never find any of them. The (usually

unstated)assumptionsarethattheoutputmustbelongenough,andthatthe

cryptographicdesignofthehashfunctionmustbesound.

5.3.2 Random Generators — Stream Ciphers

Thesecondbasiccryptographicprimitiveistherandomgenerator,alsoknown

as a keystream generator or stream cipher. This is also a random function, but

unlikeinthehash function caseithas ashort inputand along output.(Ifwe

had a good pseudorandom function whose input and output were a billion

bitslong,andweneverwantedtohandleanyobjectslargerthanthis,wecould

turnitintoahashfunctionbythrowingawayallbutafewhundredbitsofthe

output,andturnitintoastreamcipherbypaddingallbutafewhundredbits

oftheinputwithaconstant.)Attheconceptuallevel,however,it’scommonto

thinkofastreamcipherasarandomoraclewhoseinputlengthisfixedwhile

theoutputisaverylongstreamofbits,knownasthekeystream.

It can be used quite simply to protect the confidentiality of backup data:

we go to the keystream generator, enter a key, get a long file of random bits,

and exclusive-or it with our plaintext data to get ciphertext, which we then

send to our backup contractor. We can think of the elf generating a random

tapeoftherequiredlengtheachtimeheispresentedwithanewkeyasinput,

giving it tous and keepinga copy ofit on his scroll for reference incase he’s

given the same input again. If we need to recover the data, we go back to

thegenerator,enterthesamekey,getthesamelongfileofrandomdata,and

exclusive-oritwithourciphertexttogetourplaintextdataback again.Other

people with access to the keystream generator won’t be able to generate the

samekeystreamunlesstheyknowthekey.

Imentionedtheone-timepad,andShannon’sresultthatacipherhasperfect

secrecyifandonlyifthereareasmanypossiblekeysaspossibleplaintexts,and

every key is equally likely. Such security is called unconditional (or statistical)

security as it doesn’t depend either on the computing power available to the

144 Chapter5 ■ Cryptography

opponent,orontherebeingnofutureadvancesinmathematicswhichprovide

ashortcutattackonthecipher.

One-time pad systems are a veryclose fit for our theoretical model,except

in that they are typically used to secure communications across space rather

than time: there are two communicating parties who have shared a copy of

the randomly-generated keystream in advance. Vernam’s original telegraph

ciphermachineusedpunchedpapertape;amoderndiplomaticsystemmight

useDVDs,shippedinatamper-evidentcontainerinadiplomaticbag.Various

techniques have been used to do the random generation. Marks describes

howSOEagents’silkenkeysweremanufacturedinOxfordbylittleoldladies

shufflingcounters.

One important problem with keystreamgenerators is that we want to pre-

ventthesamekeystreambeingusedmorethanonce,whethertoencryptmore

than one backup tape or to encrypt more than one message sent on a com-

municationschannel.DuringWorldWar2,theamountofRussiandiplomatic

trafficexceededthequantityofone-timetapetheyhaddistributedinadvance

totheirembassies,soitwasreused.Thiswasaseriousblunder.IfM +K =C

1 1

and M +K =C , then the opponent can combine the two ciphertexts to get

2 2

a combination of two messages: C −C =M −M , and if the messages M

1 2 1 2 i

have enough redundancy then they can be recovered. Text messages do in

fact contain enough redundancy for much to be recovered, and in the case

of the Russian traffic this led to the Venona project in which the US and UK

decryptedlargeamounts ofwartimeRussiantrafficafterwardsandbrokeup

anumberofRussianspyrings.Thesayingis:‘Avoidthetwo-timetape!’

Exactlythesameconsiderationholdsforanystreamcipher,andthenormal

engineering practice when using an algorithmic keystream generator is to

haveaseedaswellasakey.Eachtimethecipherisused,wewantittogenerate

a different keystream, so the key supplied to the cipher should be different.

So if the long-term key which two users share is K, they may concatenate it

with a seed which is a message number N (or some other nonce) and then

pass it through a hash function to form a working key h(K,N). This working

keyistheoneactuallyfedtotheciphermachine.Thenoncemaybeaseparate

pre-agreed key, or it may be generated at random and sent along with the

ciphertext. However, the details of key management can be quite tricky, and

the designer has to watch out for attacks in which a principal is tricked into

synchronising on the wrong key. In effect, a protocol has to be designed to

ensurethatbothpartiescansynchroniseontherightworkingkeyeveninthe

presenceofanadversary.

5.3.3 Random Permutations — Block Ciphers

The third type of primitive, and the most important in modern commercial

cryptography, is the block cipher, which we model as a random permutation.

5.3 TheRandomOracleModel 145

Here, the function is invertible, and the input plaintext and the output

ciphertext are of a fixed size. With Playfair, both input and output are two

characters;withDES,they’rebothbitstringsof64bits.Whateverthenumber

of symbols and the underlying alphabet, encryption acts on a block of fixed

length. (So if you want to encrypt a shorter input, you have to pad it as with

thefinal‘z’inourPlayfairexample.)

Wecanvisualizeblockencryptionasfollows.Asbefore,wehaveanelfina

box with dice and a scroll. This has on the left a column of plaintexts and on

the right a column of ciphertexts. When we ask the elf to encrypt a message,

it checks in the left hand column to see if it has a record of it. If not, it uses

the dice to generate a random ciphertext of the appropriate size (and which

doesn’t appear yet in the right hand column of the scroll), and then writes

downtheplaintext/ciphertextpairinthescroll.Ifitdoesfindarecord,itgives

usthecorrespondingciphertextfromtherighthandcolumn.

When asked to decrypt, the elf does the same, but with the function of

thecolumnsreversed:hetakestheinputciphertext,checksit(thistimeonthe

right hand scroll) and if he finds it he gives the message with which it was

previously associated. If not, he generates a message at random (which does

notalreadyappearintheleftcolumn)andnotesitdown.

A block cipher is a keyed family of pseudorandom permutations. For each

key,wehaveasinglepermutationwhichisindependentofalltheothers.We

canthinkofeachkeyascorrespondingtoadifferentscroll.Theintuitiveidea

is that acipher machine should output theciphertextgiventhe plaintextand

the key, and output the plaintext given the ciphertext and the key, but given

onlytheplaintextandtheciphertextitshouldoutputnothing.

We will write a block cipher using the notation established for encryption

inthechapteronprotocols:

C={M}

K

The random permutation model also allows us to define different types of

attackonblockciphers.Inaknownplaintextattack,theopponentisjustgivena

numberofrandomlychoseninputsandoutputsfromtheoraclecorresponding

to a target key. In a chosen plaintext attack, the opponent is allowed to put a

certainnumberofplaintextqueriesandgetthecorrespondingciphertexts.In

a chosen ciphertext attack he gets to make a number of ciphertext queries. In a

chosen plaintext/ciphertext attack he is allowed to make queries of either type.

Finally,inarelatedkeyattackhecanmakequeriesthatwillbeansweredusing

keysrelatedtothetargetkeyK,suchasK+1andK+2.

Ineachcase,theobjectiveoftheattackermaybeeithertodeducetheanswer

to a query he hasn’t already made (a forgery attack), or to recover the key

(unsurprisinglyknownasakeyrecoveryattack).

This precision about attacks is important. When someone discovers a vul-

nerabilityinacryptographicprimitive,itmayormaynotberelevanttoyour

146 Chapter5 ■ Cryptography

application. Often it won’t be, but will have been hyped by the media—so

you will need to be able to explain clearly to your boss and your customers

whyit’snotaproblem.Soyouhavetolookcarefullytofindoutexactlywhat

kind of attack has been found, and what the parameters are. For example,

the first major attack announced on the Data Encryption Standard algorithm

requires 247 chosen plaintexts to recover the key, while the next major attack

improved this to 243 known plaintexts. While these attacks were of great sci-

entific importance, their practical engineering effect was zero, as no practical

systemsmakethatmuchknown(letalonechosen)textavailabletoanattacker.

Suchattacksareoftenreferredtoascertificational.Theycanhaveacommercial

effect, though: the attacks on DES undermined confidence in it and started

movingpeopletootherciphers.Insomeothercases,anattackthatstartedoff

ascertificationalhasbeendevelopedbylaterideasintoanexploit.

Which sort of attacks you should be worried about depends on your

application. With a broadcast entertainment system, for example, a bad man

canbuyadecoder,observealotofmaterialandcompareitwiththeenciphered

broadcastsignal;soaknown-plaintextattackisthemainthreat.Butthereare

surprisingly many applications where chosen-plaintext attacks are possible.

ObviousonesincludeIFF,wheretheenemycansendchallengesofhischoice

to any aircraft in range of one of his radars; and ATMs, where if you allow

customerstochangetheirPINs,anattackercanchangehisPINthrougharange

ofpossiblevaluesandobservetheencipheredequivalentsbywiretappingthe

line from the ATM to the bank. A more traditional example is diplomatic

messaging systems, where it’s been known for a host government to give an

ambassadoramessagetotransmittohiscapitalthat’sbeenspeciallydesigned

to help the local cryptanalysts fill out the missing gaps in the ambassador’s

code book[676]. In general, if the opponent can insert any kind of message

intoyoursystem,it’schosen-plaintextattacksyoushouldworryabout.

The other attacks are more specialized. Chosen plaintext/ciphertext attacks

may be a worry where the threat is a lunchtime attacker: someone who gets

temporary access to some cryptographic equipment while its authorized

user is out. Related-key attacks are a concern where the block cipher is used

as a building block in the construction of a hash function (which we’ll

discussbelow).

5.3.4 Public Key Encryption and Trapdoor One-Way

Permutations

Apublic-keyencryptionalgorithmisaspecialkindofblockcipherinwhichthe

elf will perform the encryption corresponding to a particular key for anyone

whorequestsit,butwilldothedecryptionoperationonlyforthekey’sowner.

Tocontinue withour analogy,theusermightgiveasecretname tothescroll

that only she and the elf know, use the elf’s public one-way function to

5.3 TheRandomOracleModel 147

compute a hash of this secret name, publish the hash, and instruct the elf to

performtheencryptionoperationforanybodywhoquotesthishash.

This means that a principal, say Alice, can publish a key and if Bob wants

to, he can now encrypt a message and send it to her, evenif they have never

met.Allthatisnecessaryisthattheyhaveaccesstotheoracle.Therearesome

more details that have to be taken care of, such as how Alice’s name can be

boundtothekey,andindeedwhetheritmeansanythingtoBob;I’lldealwith

theselater.

A common way of implementing public key encryption is the trapdoor

one-way permutation. This is a computation which anyone can perform, but

whichcanbereversedonlybysomeonewhoknowsatrapdoorsuchasasecret

key.Thismodelislikethe‘one-way function’ modelofacryptographichash

function.Letusstateitformallynonetheless:apublickeyencryptionprimitive

consistsofafunctionwhichgivenarandominputRwillreturntwokeys,KR

(the public encryption key) and

KR−1

(the private decryption key) with the

propertiesthat

1. GivenKR,itisinfeasibletocomputeKR−1 (soit’snotpossibletocom-

pute R either);

2. Thereisanencryptionfunction{...}which, appliedtoamessageM

usingtheencryptionkeyKR,willproduceaciphertextC={M} ;and

KR

3. Thereisadecryptionfunctionwhich,appliedtoaciphertextCusingthe

decryptionkeyKR−1,willproducetheoriginalmessageM={C} KR−1.

Forpracticalpurposes,wewillwanttheoracletobereplicatedatbothends

ofthecommunications channel,andthismeanseitherusingtamper-resistant

hardwareor(morecommonly)implementingitsfunctionsusingmathematics

rather than metal. There are several more demanding models than this, for

exampletoanalyzesecurityinthecasewheretheopponentcangetciphertexts

of his choice decrypted, with the exception of the target ciphertext. But this

willdofornow.

5.3.5 Digital Signatures

The final cryptographic primitive which we’ll define here is the digital sig-

nature.Thebasic ideaisthat asignatureonamessagecanbe createdby only

one person, but checked by anyone. It can thus perform the sort of function

in the electronic world that ordinary signatures do in the world of paper.

Applications include signing software updates, so that a PC can tell that an

updatetoWindowswasreallyproducedbyMicrosoftratherthanbyavillain.

Signatureschemescanbedeterministicorrandomized:inthefirst,computing

a signature on a messagewill always givethe same result and in the second,

it will give a different result. (The latter is more like handwritten signatures;

148 Chapter5 ■ Cryptography

no two are ever alike but the bank has a means of deciding whether a given

specimen is genuine or forged). Also, signature schemes may or may not

support message recovery. If they do, then given the signature, anyone can

recoverthemessageonwhichitwasgenerated;iftheydon’t,thentheverifier

needs to know or guess the message before he can perform the verification.

(Therearefurther,morespecialised,signatureschemessuchasblindsignatures

andthresholdsignaturesbutI’llpostponediscussionofthemfornow.)

Formally, a signature scheme, like public key encryption scheme, has a

keypair generation function which given a random input R will return two

keys, σR (the private signing key) and VR (the public signature verification

key)withthepropertiesthat

1. GiventhepublicsignatureverificationkeyVR,itisinfeasibletocom-

pute the private signing key σR;

2. ThereisadigitalsignaturefunctionwhichgivenamessageManda

privatesignaturekeyσR,willproduceasignatureSig (M);and

σR

3. Thereisasignatureverificationfunctionwhich, giventhesignature

Sig (M)andthepublicsignatureverificationkeyVRwilloutputTRUE

σR

ifthesignaturewascomputedcorrectlywithσRandotherwiseoutput

FALSE.

Wecanmodelasimpledigitalsignaturealgorithmasarandomfunctionthat

reducesanyinputmessagetoaone-wayhashvalueoffixedlength,followed

by a special kind of block cipher in which the elf will perform the operation

inonedirection,knownassignature,foronlyoneprincipal,whileintheother

direction,itwillperformverificationforanybody.

Signatureverificationcantaketwoforms.Inthebasicscheme,theelf(orthe

signatureverificationalgorithm)onlyoutputsTRUEorFALSEdependingon

whether the signatureisgood. Butinaschemewithmessage recovery,anyone

can input a signature and get back the message corresponding to it. In our

elf model, this means that if the elf has seen the signature before, it will give

themessagecorrespondingtoitonthescroll,otherwiseitwillgivearandom

value(andrecordtheinputandtherandomoutputasasignatureandmessage

pair). This is sometimes desirable: when sending short messages over a low

bandwidthchannel,itcansavespaceifonlythesignaturehastobesentrather

than the signature plus the message. An example is in the machine-printed

postage stamps, or indicia, being brought into use in many countries: the

stampmayconsistofa2-dbarcodewithadigitalsignaturemadebythepostal

meter and which contains information such as the value, the date and the

sender’s and recipient’s post codes. We give some more detail about this at

theendofsection14.3.2.

5.4 SymmetricCryptoPrimitives 149

However, in the general case we do not need message recovery, as the

message to be signed may be of arbitrary length and so we will first pass it

through a hash function and then sign the hash value. As hash functions are

one-way, the resulting compound signature scheme does not have message

recovery—although if the underlying signature scheme does, then the hash

ofthemessagecanberecoveredfromthesignature.

5.4 Symmetric Crypto Primitives

Nowthatwehavedefinedthebasiccryptoprimitives,wewilllookunderthe

hoodtoseehowtheycanbeimplementedinpractice.Whilemostexplanations

are gearedtowards graduate mathematics students,the presentationI’ll give

hereisbasedononeI’vedevelopedoverseveralyearswithcomputerscience

students. So I hope it will let the non-mathematician grasp the essentials. In

fact, even at the research level, most of cryptography is as much computer

science as mathematics. Modern attacks on ciphers are put together from

guessingbits,searchingforpatterns,sortingpossibleresults,andsoonrather

thanfromanythingparticularlyhighbrow.

We’llfocusinthissectiononblockciphers,andthenseeinthenextsection

how you can make hash functions and stream ciphers from them, and vice

versa.(Inlaterchapters,we’llalsolookatsomespecial-purposeciphers.)

5.4.1 SP-Networks

Claude Shannon suggested in the 1940’s that strong ciphers could be built

by combining substitution with transposition repeatedly. For example, one

mightaddsomekeymaterialtoablockofinputtext,andthenshufflesubsets

of the input, and continue in this way a number of times. He described the

propertiesofacipherasbeingconfusionanddiffusion—addingunknownkey

values will confuse an attacker about the value of a plaintext symbol, while

diffusion means spreading the plaintext information through the ciphertext.

Blockciphersneeddiffusionaswellasconfusion.

The earliest block ciphers were simple networks which combined sub-

stitution and permutation circuits, and so were called SP-networks[681].

Figure 5.10 shows an SP-network with sixteeninputs, which we can imagine

as the bits of a sixteen-bit number, and two layers of four-bit invertible sub-

stitutionboxes (orS-boxes),eachofwhich canbe visualizedasalookuptable

containingsomepermutationofthenumbers0to15.

Thepointofthisarrangementisthatifweweretoimplementanarbitrary16

bitto16bitfunctionindigitallogic,wewouldneed220 bitsofmemory—one

150 Chapter5 ■ Cryptography

lookuptableof216bitsforeachsingleoutputbit.That’shundredsofthousands

of gates, while a four bit to four bit function takes only 4 x 24 or 64 bits of

memory.Onemighthopethatwithsuitablechoicesofparameters,thefunction

producedbyiteratingthissimplestructurewouldbeindistinguishablefroma

random16bitto16bitfunctiontoanopponentwhodidn’tknowthevalueof

thekey.Thekeymightconsistofsomechoiceofanumberoffour-bitS-boxes,

oritmightbeaddedateachroundtoprovideconfusionandtheresultingtext

fedthroughtheS-boxestoprovidediffusion.

Threethingsneedtobedonetomakesuchadesignsecure:

1. the cipher needs to be ‘‘wide’’ enough

2. it needs to have enough rounds, and

3. the S-boxes need to be suitably chosen.

5.4.1.1 Block Size

First, a block cipher which operated on sixteen bit blocks would have rather

limitedapplicability,asanopponentcouldjustbuildadictionaryofplaintext

andciphertextblocksasheobservedthem.Thebirthdaytheoremtellsusthat

eveniftheinputplaintextswererandom,he’dexpecttofindamatchassoon

as he had seen a little over 28 blocks. So a practical block cipher will usually

dealwithplaintextsandciphertextsof64bits,128bitsorevenmore.Soifwe

are using four-bit to four-but S-boxes, we may have 16 of them (for a 64 bit

blocksize)or32ofthem(fora128bitblocksize).

5.4.1.2 Number of Rounds

Second, we have to have enough rounds. The two rounds in Figure 5.10 are

completely inadequate, as an opponent can deduce the values of the S-boxes

by tweaking input bits in suitable patterns. For example, he could hold the

rightmost 12 bits constant and try tweaking the leftmost four bits, to deduce

the values inthe top left S-box. (The attack is slightlymore complicated than

this,assometimesatweakinaninputbittoanS-boxwon’tproduceachange

in any output bit, so we have to change one of its other inputs and tweak

again.Butimplementingitisstillasimplestudentexercise.)

The number of rounds we require depends on the speed with which data

diffusethroughthecipher.Intheabovesimpleexample,diffusionisveryslow

because each output bit from one round of S-boxes is connected to only one

input bit in the next round. Instead of having a simple permutation of the

wires, it is more efficient to have a linear transformation in which each input

bitinoneroundistheexclusive-orofseveraloutputbitsinthepreviousround.

Ofcourse,iftheblockcipheristobeusedfordecryptionaswellasencryption,

this linear transformation will have to be invertible. We’ll see some concrete

examplesbelowinthesectionsonSerpentandAES.

5.4 SymmetricCryptoPrimitives 151

(cid:1) (cid:1) (cid:1) (cid:1) (cid:1) (cid:1) (cid:1) (cid:1) (cid:1) (cid:1) (cid:1) (cid:1) (cid:1) (cid:1) (cid:1) (cid:1)

S-box S-box S-box S-box

(cid:2)(cid:3) (cid:2)(cid:3) (cid:5)(cid:2)(cid:4) (cid:3) (cid:5)(cid:2)(cid:4) (cid:3)(cid:6) (cid:7)(cid:5)(cid:2)(cid:4) (cid:3)(cid:6) (cid:7)(cid:5)(cid:2) (cid:4) (cid:3)(cid:6) (cid:7)(cid:5)(cid:4)(cid:6) (cid:7)(cid:5)(cid:4)(cid:6) (cid:7)(cid:5)(cid:4)(cid:6) (cid:7)(cid:5) (cid:4)(cid:6) (cid:7)(cid:5)

(cid:4)

(cid:2)(cid:3) (cid:6) (cid:7)(cid:5) (cid:4)(cid:2)(cid:3) (cid:6)(cid:7)(cid:5) (cid:5)(cid:4)(cid:4) (cid:2)(cid:3)(cid:6)(cid:7)(cid:5) (cid:5)(cid:4)(cid:4) (cid:2) (cid:3)(cid:6)(cid:7) (cid:5)(cid:4)(cid:2) (cid:3)(cid:6)(cid:7) (cid:5)(cid:4)(cid:2) (cid:3)(cid:6)(cid:7) (cid:5)(cid:4) (cid:6)(cid:7) (cid:5)(cid:4) (cid:6)(cid:7) (cid:5)(cid:4) (cid:6)(cid:7) (cid:5)

(cid:4)

(cid:6)(cid:7) (cid:5) (cid:4)(cid:3) (cid:2)(cid:6)(cid:7) (cid:5) (cid:4)(cid:3) (cid:2)(cid:5) (cid:4)(cid:3) (cid:2)(cid:5) (cid:4)(cid:3)(cid:2) (cid:3)(cid:2) (cid:3)(cid:2)

(cid:1) (cid:1) (cid:1) (cid:1) (cid:1) (cid:1) (cid:1) (cid:1) (cid:1) (cid:1) (cid:1) (cid:1) (cid:1) (cid:1) (cid:1) (cid:1)

S-box S-box S-box S-box

(cid:1) (cid:1) (cid:1) (cid:1) (cid:1) (cid:1) (cid:1) (cid:1) (cid:1) (cid:1) (cid:1) (cid:1) (cid:1) (cid:1) (cid:1) (cid:1)

Figure5.10:Asimple16-bitSP-networkblockcipher

5.4.1.3 Choice of S-Boxes

The design of the S-boxes also affects the number of rounds required for

security, and studying bad choices gives us our entry into the deeper theory

of block ciphers. Suppose that the S-box were the permutation that maps the

inputs (0,1,2,...,15) to the outputs (5,7,0,2,4,3,1,6,8,10,15,12,9,11,14,13). Then

the most significant bit of the input would come through unchanged as the

mostsignificantbitoftheoutput.IfthesameS-boxwereusedinbothrounds

in the above cipher, then the most significant bit of the input would pass

through to become the most significant bit of the output. This would usually

beabadthing;wecertainlycouldn’tclaimthatourcipherwaspseudorandom.

5.4.1.4 Linear Cryptanalysis

Attacks on real block ciphers are usually harder to spot than in this artificial

example, but they use the same ideas. It might turn out that the S-box had

the property that bit one of the input was equal to bit two plus bit four

oftheoutput;morecommonly,therewillbelinearapproximationstoanS-box

which hold with a certain probability. Linear cryptanalysis[602, 843] proceeds

by collectinganumberofrelationssuchas‘bit2plusbit5oftheinputtothe

first S-box is equal to bit 1 plus bit 8 of the output, with probability 13/16’

and then searching for ways to glue them together into an algebraic relation

between input bits, output bits and key bits that holds with a probability

differentfromonehalf.Ifwecanfindalinearrelationshipthatholdsoverthe

whole cipher with probability p=0.5+1/M, then according to probability

theory we can expect to start recovering keybits once we have about M2

known texts.If the value of M2 for the best linear relationship is greaterthan

the total possible number of known texts (namely 2n where the inputs and

outputsarenbitswide),thenweconsidertheciphertobesecureagainstlinear

cryptanalysis.

152 Chapter5 ■ Cryptography

5.4.1.5 Differential Cryptanalysis

DifferentialCryptanalysis[170,602]issimilarbutisbasedontheprobabilitythat

agivenchangeintheinputtoanS-boxwillgiverisetoacertainchangeinthe

output.Atypicalobservationonan8-bitS-boxmightbethat‘ifweflipinput

bits 2, 3, and 7 at once, then with probability 11/16 the only output bits that

will flip are 0 and 1’. In fact, with any nonlinear Boolean function, tweaking

somecombinationofinputbitswillcausesomecombinationofoutputbitsto

change with a probability different from one half. The analysis procedure is

to look at all possible input difference patterns and look for those values δ,

i

δ such that an input change of δ will produce an output change of δ with

o i o

particularlyhigh(orlow)probability.

Asinlinearcryptanalysis,wethensearchforwaystojointhingsupsothat

an input difference which we can feed into the cipher will produce a known

output difference with a useful probability over a number of rounds. Given

enough chosen inputs, we will see the expected output and be able to make

deductionsaboutthekey.Asinlinearcryptanalysis,it’scommontoconsider

the ciphertobe secureifthenumber oftextsrequiredfor anattack isgreater

than the total possible number of different texts for that key. (We have to be

carefulthoughofpathologicalcases,suchasifyouhadacipherwitha32-bit

block and a 128-bit key with a differential attack whose success probability

givenasinglepairwas2−40.Givenalotoftextunderanumberofkeys,we’d

eventuallysolveforthecurrentkey.)

Thereareaquiteafewvariantsonthesetwothemes.Forexample,insteadof

lookingforhighprobabilitydifferences,wecanlookfordifferencesthatcan’t

happen(orthathappenonlyrarely).Thishasthecharmingnameofimpossible

cryptanalysis, but it is quite definitely possible against many systems[169].

Therearealsovariousspecialisedattacksonparticularciphers.

Block cipher design involves a number of trade-offs. For example, we can

reduce the per-round information leakage, and thus the required number of

rounds,bydesigningtheroundscarefully.However,acomplexdesignmight

beslowinsoftware,orneedalotofgatesinhardware,sousingsimplerounds

but more of them might have been better. Simple rounds may also be easier

to analyze. A prudent designer will also use more rounds than are strictly

necessary to block the attacks known today, in order to give some margin of

safety against improved mathematics in the future. We may be able to show

thatacipherresistsalltheattacksweknowof,butthissayslittleaboutwhether

it will resist the attacks we don’t know of yet. (A general security proof for a

blockcipherwouldappeartoimplyaproofaboutanattacker’scomputational

powers,whichmightentailaresultsuchasP(cid:1)=NPthatwouldrevolutionize

computerscience.)

The point that the security engineer should remember is that block cipher

cryptanalysis is a complex subject about which we have a fairly extensive

theory. Use an off-the-shelf design that has been thoroughly scrutinized

5.4 SymmetricCryptoPrimitives 153

by experts, rather than rolling your own; and if there’s a compelling reason

touseaproprietarycipher(forexample,ifyouwanttouseapatenteddesignto

stop otherpeoplecopying aproduct)thengetitreviewedby experts.Cipher

designisnotanamateursportanymore.

5.4.1.6 Serpent

As a concrete example, the encryption algorithm ‘Serpent’ is an SP-network

withinputandoutputblocksizesof128bits.Theseareprocessedthrough32

rounds,ineachofwhichwefirstadd128bitsofkeymaterial,thenpassthetext

through 32 S-boxes of 4 bits width, and then perform a linear transformation

that takes each output of one round to the inputs of a number of S-boxes

in the next round. Rather than each input bit in one round coming from a

singleoutputbitinthelast,itistheexclusive-orofbetweentwoandsevenof

them.Thismeansthatachangeinaninputbitpropagatesrapidlythroughthe

cipher—aso-calledavalanche effectwhich makesbothlinearanddifferential

attacks harder. After the final round, a further 128 bits of key material

areaddedtogivetheplaintext.The33times128bitsofkeymaterialrequired

arecomputedfromausersuppliedkeyofupto256bits.

This is a real cipher using the structure of Figure5.10, but modified

to be ‘wide’ enough and to have enough rounds. The S-boxes are chosen to

make linear and differential analysis hard; they have fairly tight bounds on

the maximum linear correlation between input and output bits, and on the

maximumeffectoftogglingpatternsofinputbits.Eachofthe32S-boxesina

givenroundisthesame;thismeansthatbit-slicingtechniquescanbeusedto

giveaveryefficientsoftwareimplementationon32-bitprocessors.

ItssimplestructuremakesSerpenteasytoanalyze,anditcanbeshownthat

it withstands all the currently known attacks. A full specification of Serpent

is given in[60] and can be downloaded, together with implementations in a

numberoflanguages,from[61].

5.4.2 The Advanced Encryption Standard (AES)

This discussion has prepared us to describe the Advanced Encryption Stan-

dard, an algorithm alsoknown as Rijndael after its inventors Vincent Rijmen

and Joan Daemen[342]. This algorithm acts on 128-bit blocks and can use a

keyof128,192or256bitsinlength.ItisanSP-network;inordertospecifyit,

weneedtofixtheS-boxes,thelineartransformationbetweentherounds,and

thewayinwhichthekeyisaddedintothecomputation.

AES uses a single S-box which acts on a byte input to give a byte output.

For implementation purposes it can be regarded simply as a lookup table of

256 bytes; it is actually defined by the equation S(x)=M(1/x)+b over the

field GF(28) where M is a suitably chosen matrix and b is a constant. This

constructiongivestightdifferentialandlinearbounds.

154 Chapter5 ■ Cryptography

The linear transformation is based on arranging the 16 bytes of the value

being enciphered in a square and then doing bytewise shuffling and mixing

operations. (AES is descended from an earlier cipher called Square, which

introducedthistechnique.)

Thefirststepinthelineartransformationistheshuffleinwhichthetoprow

of four bytes is left unchanged, while the second row is shifted one place to

the left, the third row by two places and the fourth row by three places. The

second step is a column mixing step in which the four bytes in a column are

mixed using a matrix multiplication. This is illustrated in Figure 5.11 which

shows, asanexample,howachange inthevalueofthethirdbyteinthefirst

column is propagated. The effect of this combination is that a change in the

inputtotheciphercanpotentiallyaffectalloftheoutputafterjusttworounds.

Thekeymaterialisaddedbytebybyteafterthelineartransformation.This

means that 16 bytes of key material are needed per round; they are derived

fromtheusersuppliedkeymaterialbymeansofarecurrencerelation.

Thealgorithmuses10roundswith128-bitkeys,12roundswith192-bitkeys

and14roundswith256-bitkeys.Thesegiveareasonablemarginofsafety;the

best shortcut attacks known at the time of writing (2007) can tackle 7 rounds

for128-bitkeys,and9roundsfor192-and256-bitkeys[16].Thegeneralbelief

in the block cipher community is that even if advances in the state of the art

dopermitattacksonAESwiththefullnumberofrounds,theywillbepurely

certificationalattacksinthattheywillrequireinfeasiblylargenumbersoftexts.

(AES’s margin of safety against attacks that require only feasible numbers of

textsis about 100%.)Although thereisnoproofofsecurity—whether inthe

senseofpseudorandomness,orintheweakersenseofanabsenceofshortcut

attacks of known types—there is now ahigh levelof confidence that AESis

secureforallpracticalpurposes.TheNSAhassince2005approvedAESwith

128-bit keys for protecting information up to SECRET and with 256-bit keys

forTOPSECRET.

. . .

1 1 1

2 2 2

3 3 3

4 4 4

Shift Mix

row column

Figure5.11:TheAESlineartransformation,illustratedbyitseffectonbyte3oftheinput

5.4 SymmetricCryptoPrimitives 155

EvenalthoughIwasanauthorofSerpentwhichwasanunsuccessfulfinalist

in the AES competition (the winner Rijndael got 86 votes, Serpent 59 votes,

Twofish31votes,RC623votesandMARS13votesatthelastAESconference),

and although Serpent was designed to have an even larger security margin

thanRijndael,IrecommendtomyclientsthattheyuseAESwhereageneral-

purpose block cipher is required. I recommend the 256-bit-key version, and

notbecauseIthinkthatthe10roundsofthe128-bit-keyvariantwillbebroken

anytimesoon.Longerkeysarebetterbecausesomekeybitsoftenleakinreal

products, as I’ll discuss at some length in the chapters on tamper-resistance

and emission security. It does not make sense to implement Serpent as well,

‘justincaseAESisbroken’:theriskofafatalerrorinthealgorithmnegotiation

protocol is orders of magnitude greater than the risk that anyone will come

up with a production attack on AES. (We’ll see a number of examples later

where using multiple algorithms, or using an algorithm like DES multiple

times,causedsomethingtobreakhorribly.)

The definitive specification of AES is Federal Information Processing Stan-

dard 197, and its inventors have written a book describing its design in

detail[342].Otherinformation,frombookerratatolinkstoimplementations,

canbefoundontheAESLoungewebpage[16].

One word of warning: the most likely practical attacks on a real imple-

mentation of AESinclude timing analysis and power analysis, both ofwhich

I discuss in Part II in the chapter on emission security. In timing analysis,

the risk is that an opponent observes cache misses and uses them to work

out the key. The latest versions of this attack can extract a key given the

precise measurements of the time taken to do a few hundred cryptographic

operations.Inpoweranalysis,anopponentusesmeasurementsofthecurrent

drawn by the device doing the crypto—think of a bank smartcard that a

customerplacesinaterminalinaMafia-ownedshop.Thetwooverlap;cache

misses cause a device like a smartcard to draw more power—and can also

be observed on remote machines by an opponent who can measure the time

takentoencrypt.Theimplementationdetailsmatter.

5.4.3 Feistel Ciphers

Many block ciphers use a more complex structure, which was invented by

Feistel and his team while they were developing the Mark XII IFF in the late

1950’s and early 1960’s. Feistel then moved to IBM and founded a research

groupwhichproducedtheDataEncryptionStandard,(DES)algorithm,which

isstillthemainstayoffinancialtransactionprocessingsecurity.

AFeistelcipherhastheladderstructureshowninFigure5.12.Theinputis

split up into two blocks, the left half and the right half. A round function f of

1

156 Chapter5 ■ Cryptography

thelefthalfiscomputedandcombinedwiththerighthalfusingexclusive-or

(binaryadditionwithoutcarry),thoughinsomeFeistelciphersadditionwith

carry is also used. (We use the notation ⊕ for exclusive-or.) Then, a function

f of the right half is computed and combined with the left half, and so

2

on. Finally (if the number of rounds is even) the left half and right half are

swapped.

LeftHalf RightHalf

(cid:1)

• (cid:9)

f

(cid:9)⊕

1

(cid:1)

⊕(cid:8)

f

(cid:8) •

2

(cid:1) (cid:1)

...

(cid:1)

⊕(cid:8)

f

(cid:8) •

2k

(cid:4) (cid:5)(cid:4) (cid:5)(cid:4) (cid:5)(cid:4) (cid:5)(cid:4) (cid:5)(cid:4) (cid:5)(cid:4) (cid:5)(cid:4) (cid:5)(cid:4) (cid:5)(cid:4)(cid:5)(cid:4)(cid:5) (cid:4)(cid:5) (cid:4)(cid:5) (cid:4)(cid:5) (cid:4)(cid:5) (cid:4)(cid:5) (cid:4)(cid:5) (cid:4)(cid:5) (cid:4)(cid:5) (cid:4)(cid:5)

(cid:1) (cid:1)

Figure5.12:TheFeistelcipherstructure

5.4 SymmetricCryptoPrimitives 157

A notation which you may see for the Feistel cipher is ψ(f,g,h,...) where

f, g, h, ... are the successive round functions. Under this notation, the above

cipherisψ(f 1,f 2,...f 2k−1,f 2k).ThebasicresultthatenablesustodecryptaFeistel

cipher—andindeedthewholepointofhisdesign—isthat:

ψ−1(f 1,f 2,...,f 2k−1,f 2k)=ψ(f 2k,f 2k−1,...,f 2,f 1)

In other words, to decrypt, we just use the round functions in the reverse

order.Thustheroundfunctionsf donothavetobeinvertible,andtheFeistel

i

structure lets us turn any one-way function into a block cipher. This means

that we are less constrained in trying to choose a round function with good

diffusionand confusion properties,and which also satisfies any other design

constraintssuchascodesize,tablesize,softwarespeed,hardwaregatecount,

andsoon.

5.4.3.1 The Luby-Rackoff Result

The key theoretical result on Feistel ciphers was proved by Mike Luby and

Charlie Rackoff in 1988. They showed that if f were random functions, then

i

ψ(f ,f ,f ) was indistinguishable from a random permutation under chosen

1 2 3

plaintext attack, and this result was soon extended to show that ψ(f ,f ,f ,f )

1 2 3 4

was indistinguishable under chosen plaintext/ciphertext attack—in other

words,itwasapseudorandompermutation.

There are a number of technicalities we omit. In engineering terms, the

effect is that given a really good round function, four rounds of Feistel are

enough. So if we have a hash function in which we have confidence, it is

straightforward to construct a block cipher from it: use four rounds of keyed

hashinaFeistelnetwork.

5.4.3.2 DES

The DES algorithm is widely used in banking, government and embedded

applications. For example, it is the standard in automatic teller machine

networks. It is a Feistel cipher, with a 64-bit block and 56-bit key. Its round

functionoperateson32-bithalfblocksandconsistsofthreeoperations:

first, the block is expanded from 32 bits to 48;

next, 48 bits of round key are mixedin using exclusive-or;

theresultispassedthrougharowofeightS-boxes,eachofwhichtakesa

six-bit input and provides a four-bit output;

finally,thebitsoftheoutputarepermutedaccordingtoafixedpattern.

158 Chapter5 ■ Cryptography

Theeffectoftheexpansion,keymixingandS-boxesisshowninFigure5.13:

Key added

in here

(cid:127) (cid:127) (cid:127) S i – 1 S i S i + 1 (cid:127) (cid:127) (cid:127)

Figure5.13:TheDESroundfunction

Theroundkeysarederivedfromtheuser-suppliedkeybyusingeachuser

key bit in twelve different rounds according to a slightly irregular pattern.

A full specification of DES is given in[936]; code can be found in[1125] or

downloadedfrommanyplacesontheweb.

DESwasintroducedin1974andcausedsomecontroversy.Themosttelling

criticism was that the key is too short. Someone who wants to find a 56 bit

key using brute force, that is by trying all possible keys, will have a total

exhausttimeof256 encryptionsandanaveragesolutiontimeofhalfthat,namely

255 encryptions. Whit Diffie and Martin Hellman argued in 1977 that a DES

keysearch machine could be built with a million chips, each testing a million

keysasecond;asamillionisabout220,thiswouldtakeonaverage215seconds,

or abit over9hours, tofind the key.Theyarguedthat such amachine could

be built for $20 million dollars in 1977[386]. IBM, whose scientists invented

DES,retortedthattheywouldchargetheUSgovernment$200milliontobuild

suchamachine.(Perhapsbothwereright.)

Duringthe1980’s,therewerepersistentrumorsofDESkeysearchmachines

being built by various intelligence agencies, but the first successful public

keysearch attack took place in 1997. In a distributed effort organised over

the net, 14,000 PCs computers took more than four months to find the key

to a challenge. In 1998, the Electronic Frontier Foundation (EFF) built a DES

keysearch machine called Deep Crack for under $250,000 which broke a

DES challenge in 3 days. It contained 1,536 chips run at 40MHz, each chip

containing24searchunitswhicheachtook16cyclestodoatestdecrypt.The

searchratewasthus2.5milliontestdecryptionspersecondpersearchunit,or

60millionkeyspersecondperchip.Thedesignofthecrackerispublicandcan

be foundat[423].By2006, SandeepKumarand colleaguesat theuniversities

of Bochum and Kiel built a machine using 120 FPGAs and costing $10,000,

whichcouldbreakDESin7daysonaverage[755].Amodernbotnetwithhalf

5.4 SymmetricCryptoPrimitives 159

a millionmachines would take a few hours. So the key length of DES is now

definitely inadequate, and banks have for some years been upgrading their

paymentsystems.

AnothercriticismofDESwasthat,sinceIBMkeptitsdesignprinciplessecret

at the request of the US government, perhaps there was a ‘trapdoor’ which

wouldgivethemeasyaccess.However,thedesignprincipleswerepublished

in 1992 after differential cryptanalysis was invented and published[326].

Their story was that IBM had discovered these techniques in 1972, and the

USNationalSecurityAgency(NSA)evenearlier.IBMkeptthedesigndetails

secret at the NSA’s request. We’ll discuss the political aspects of all this

in24.3.9.1.

We now have a fairly thorough analysis of DES. The best known shortcut

attack,thatis,acryptanalyticattackinvolvinglesscomputationthankeysearch,

isalinearattackusing242 knowntexts.DESwouldbesecurewithmorethan

20rounds,butforpractical purposesitssecurityislimitedbyitskeylength.I

don’tknowofanyrealapplicationswhereanattackermightgetholdofeven

240 knowntexts.Sotheknownshortcutattacksarenotanissue.However,its

growing vulnerability to keysearch makes DES unusable in its original form.

IfMoore’slawcontinues,thanby2020itmightbepossibletofindaDESkey

onasinglePCinafewmonths,soevenlow-gradesystemssuchastaximeters

will be vulnerable to brute force-cryptanalysis. As with AES, there are also

attacks based on timing analysis and power analysis, but because of DES’s

structure,thelatteraremoreserious.

The usual way of dealing with the DES keysearch problem is to use

the algorithm multiple times with different keys. Banking networks have

largely moved to triple-DES, a standard since 1999[936]. Triple-DES does an

encryption, then a decryption, and then a further encryption, all done with

independentkeys.Formally:

3DES(k ,k ,k ;M)=DES(k ,DES−1(k ,DES(k ;M)))

0 1 2 2 1 0

Thereasonforthisdesignisthatbysettingthethreekeysequal,onegetsthe

sameresultasasingleDESencryption,thusgivingabackwardscompatibility

mode with legacy equipment. (Some banking systems use two-key triple-DES

which sets k =k ; this gives an intermediate step between single and triple

2 0

DES).NewsystemsnowuseAESasofchoice,butbankingsystemsaredeeply

committedtousingblockcipherswithaneight-byteblocksize,becauseofthe

message formats used in the many protocols by which ATMs, point-of-sale

terminalsandbanknetworkstalktoeachother,andbecauseoftheuseofblock

cipherstogenerateandprotectcustomerPINs(whichIdiscussinChapter10).

Triple DES is a perfectly serviceable block cipher for such purposes for the

foreseeablefuture.

Anotherwayofpreventingkeysearch(andmakingpoweranalysisharder)is

whitening.Inadditiontothe56-bitkey,sayk ,wechoosetwo64-bitwhitening

0

160 Chapter5 ■ Cryptography

keys k and k , xor’ing the first with the plaintext before encryption and the

1 2

secondwiththeoutputoftheencryptiontogettheciphertextafterwards.This

compositecipherisknownasDESX,andisusedintheWin2Kencryptingfile

system.Formally,

DESX(k ,k ,k ;M)=DES(k ;M⊕k )⊕k

0 1 2 0 1 2

It can be shown that, on reasonable assumptions, DESX has the properties

you’d expect; it inherits the differential strength of DES but its resistance to

keysearchisincreasedby theamount ofthewhitening[717].Whitenedblock

ciphersareusedinsomeapplications.

5.5 Modes of Operation

In practice, how you use an encryption algorithm is often more important

thanwhichoneyoupick.Animportantfactoristhe‘modeofoperation’,which

specifies how a block cipher with a fixed block size (8 bytes for DES, 16 for

AES)canbeextendedtoprocessmessagesofarbitrarylength.

There are several standard modes of operation for using a block cipher on

multipleblocks[944].Understandingthem,andchoosingtherightoneforthe

job,isanimportantfactorinusingablockciphersecurely.

5.5.1 Electronic Code Book

In electronic code book (ECB) we just encrypt each succeeding block of

plaintext with our block cipher to get ciphertext, as with the Playfair cipher

I gave above as an example. This is adequate for many simple operations

such as challenge-response and some key management tasks; it’s also used

to encrypt PINs in cash machine systems. However, if we use it to encrypt

redundant data the patterns will show through, letting an opponent deduce

informationabouttheplaintext.Forexample,ifawordprocessingformathas

lotsofstringsofnulls,thentheciphertextwillhavealotofblockswhosevalue

istheencryptionofnullcharactersunderthecurrentkey.

Inone popularcorporateemailsystemfrom thelate1980’s, the encryption

usedwasDESECBwiththekeyderivedfromaneightcharacterpassword.If

youlookedataciphertextgeneratedbythissystem,yousawthatacertainblock

wasfarmorecommonthantheothers—theonecorrespondingtoaplaintext

of nulls. This gave one of the simplest attacks on a fielded DES encryption

system:justencryptanullblock witheachpasswordinadictionaryandsort

theanswers.Youcannowbreakatsightanyciphertextwhosepasswordwas

oneofthoseinyourdictionary.

In addition, using ECB mode to encrypt messages of more than one block

length which have an authenticity requirement—such as bank payment

5.5 ModesofOperation 161

messages—wouldbefoolish,asmessagescouldbesubjecttoacutandsplice

attackalongtheblockboundaries.Forexample,ifabankmessagesaid‘Please

pay account number X the sum Y, and their reference number is Z’ then an

attacker might initiate a payment designed so that some of the digits of X

couldbereplacedwithsomeofthedigitsofZ.

5.5.2 Cipher Block Chaining

Mostcommercialapplicationswhichencryptmorethanoneblockusecipher

block chaining, or CBC, mode. In it, we exclusive-or the previous block of

ciphertexttothecurrentblockofplaintextbeforeencryption(seeFigure5.14).

This mode is effective at disguising any patterns in the plaintext: the

encryption of each block depends on all the previous blocks. The input IV

is an initialization vector, a random number that performs the same function

as a seed in a stream cipher and ensures that stereotyped plaintext message

headerswon’tleakinformationbyencryptingtoidenticalciphertextblocks.

However, an opponent who knows some of the plaintext may be able to

cut and splice a message (or parts of several messages encrypted under the

samekey),sotheintegrityprotectionisnottotal.Infact,ifanerrorisinserted

into the ciphertext, it will affect only two blocks of plaintext on decryption,

so if there isn’t any integrityprotection on the plaintext, an enemy can insert

two-blockgarblesofrandomdataatlocationsofhischoice.

5.5.3 Output Feedback

Outputfeedback(OFB)modeconsistsofrepeatedlyencryptinganinitialvalue

andusingthisasakeystreaminastreamcipherofthekinddiscussedabove.

P P P

1 2 3

(cid:1) (cid:1) (cid:1)

(cid:9)⊕ (cid:9)⊕ (cid:9)⊕

IV

(cid:1) (cid:1) (cid:1)

...

E E E

K K K

• • •

(cid:1) (cid:1) (cid:1)

C C C

1 2 3

Figure5.14:CipherBlockChaining(CBC)mode

162 Chapter5 ■ Cryptography

WritingIVfortheinitializationvectororseed,thei-thblockofkeystreamwill

begivenby

K ={...{{IV} } ...totalofitimes}

i K K

This is one standard way of turning a block cipher into a stream cipher.

ThekeyKisexpandedintoalongstreamofblocksK ofkeystream.Keystream

i

is typically combined with the blocks of a message M using exclusive-or to

i

giveciphertextC =M ⊕K;thisarrangementissometimescalledanadditive

i i i

stream cipher as exclusive-or is just addition module 2 (and some old hand

systemsusedadditionmodulo26).

All additive stream ciphers have an important vulnerability: they fail to

protect message integrity. I mentioned this in the context of the one-time

pad in section5.2.2 above, but it’s important to realise that this doesn’t just

affect‘perfectlysecure’systemsbut‘reallife’streamcipherstoo.Suppose,for

example, that a stream cipher were used to encipher fund transfer messages.

Thesemessagesareveryhighlystructured;youmightknow,forexample,that

bytes37–42containedtheamountofmoneybeingtransferred.Youcouldthen

carry out the following attack. Youcause thedatatrafficfrom alocal bank to

go via your computer, for example by a wiretap. You go into the bank and

send a modest sum (say $500) to an accomplice. The ciphertext C =M ⊕K,

i i i

duly arrives in your machine. You know M for bytes 37–42, so you know

i

K and can easily construct a modified message which instructs the receiving

i

banktopaynot$500but$500,000!Thisisanexampleofanattackindepth;itis

the price not just of the perfect secrecy we get from the one-time pad, but of

muchmorehumblestreamcipherstoo.

5.5.4 Counter Encryption

One possible drawback of feedback modes of block cipher encryption is

latency: feedback modes are hard to parallelize. With CBC, a whole block of

theciphermustbecomputedbetweeneachblockinputandeachblockoutput;

withOFB,wecanprecomputekeystreambutstoringitrequiresmemory.This

canbeinconvenientinveryhighspeedapplications,suchasprotectingtraffic

ongigabitbackbonelinks.There,assiliconischeap,wewouldratherpipeline

ourencryptionchip,sothatitencryptsanewblock(orgeneratesanewblock

ofkeystream)inasfewclockticksaspossible.

Thesimplestsolutionisoftenistogenerateakeystreambyjustencrypting

a counter: K ={IV+i} . As before, this is then added to the plaintext to get

i K

ciphertext(soit’salsovulnerabletoattacksindepth).

Another problem this mode solves when using a 64-bit block cipher such

as triple-DESon a very high speed link is cycle length. An n-bit block cipher

in OFB mode will typically have a cycle length of 2n/2 blocks, after which the

birthdaytheoremwillseetoitthatthekeystreamstartstorepeat.(Oncewe’ve

a little over 232 64-bit values, the odds are that two of them will match.) In

5.5 ModesofOperation 163

CBCmode,too,thebirthdaytheoremensuresthatafterabout2n/2 blocks,we

willstarttoseerepeats.Countermodeencryption,however,hasaguaranteed

cyclelengthof2n ratherthan2n/2.

5.5.5 Cipher Feedback

Cipher feedback, or CFB, mode is another kind of stream cipher. It was

designedtobeself-synchronizing,inthatevenifwegetabursterroranddrop

afewbits,thesystemwillrecoversynchronizationafteroneblocklength.This

is achieved by using our block cipher to encrypt the last n bits of ciphertext,

andthenaddingoneoftheoutputbitstothenextplaintextbit.

Withdecryption,thereverseoperationisperformed,withciphertextfeeding

in from the right in Figure5.15. Thus even if we get a burst error and drop a

few bits, as soon as we’ve received enough ciphertext bits to fill up the shift

register,thesystemwillresynchronize.

Cipher feedback is not much used any more. It was designed for use in

military HF radio links which are vulnerable to fading, in the days when

digitalelectronicswererelativelyexpensive.Nowthatsiliconischeap,people

use dedicated link layer protocols for synchronization and error correction

ratherthantryingtocombinethemwiththecryptography.

5.5.6 Message Authentication Code

Thenextofficialmodeofoperationofablockcipherisnotusedtoencipherdata,

but to protect its integrity and authenticity. This is the message authentication

code, or MAC. To compute a MAC on a message using a block cipher, we

encrypt it using CBC mode and throw away all the output ciphertext blocks

except the last one; this last block is the MAC. (The intermediate results are

keptsecretinordertopreventsplicingattacks.)

(cid:8)

shiftregister

(cid:1)(cid:1)(cid:1)(cid:1)(cid:1)(cid:1)(cid:1)(cid:1)

E

K

(cid:1)

plaintext

(cid:9)⊕ • (cid:9)

ciphertext

Figure5.15:Ciphertextfeedbackmode(CFB)

164 Chapter5 ■ Cryptography

This construction makes the MAC depend on all the plaintext blocks as

well as on the key. It is secure provided the message length is fixed; Mihir

Bellare, Joe Kilian and Philip Rogaway proved that any attack on a MAC

under these circumstances would give an attack on the underlying block

cipher[147].

Ifthemessagelengthisvariable,youhavetoensurethataMACcomputed

on one string can’t be used as the IV for computing a MAC on a different

string,sothatanopponentcan’tcheatbygettingaMAConthecompositionof

thetwostrings.Inordertofixthisproblem,NISThasstandardisedCMAC,in

whichavariantofthekeyisxor-edinbeforethelastencryption[945].(CMAC

isbasedonaproposalbyTetsuIwataandKaoruKurosawa[649].)

There are other possible constructions of MACs: a common one is to use a

hashfunctionwithakey,whichwe’lllookatinmoredetailinsection5.6.2.

5.5.7 Composite Modes of Operation

In applications needing both integrity and privacy, the standard procedure

usedtobetofirstcalculateaMAConthemessageusingonekey,andthenCBC

encrypt it using a different key. (If the same key is used for both encryption

and authentication, then the security of the latter is no longer guaranteed;

cut-and-spliceattacksarestillpossible.)

Recently two further modes of operation have been tackled by NIST that

combine encryption and authentication. The first is CCM, which combines

counter-modeencryptionwithCBC-MACauthentication.Thedangertowatch

forhereisthatthecountervaluesusedinencryptionmustnotcoincidewiththe

initialisationvectorusedintheMAC;thestandardrequiresthattheformatting

functionpreventthis[946].

ThesecondcombinedmodeisGaloisCounterMode(GCM),whichhasjust

been approved at the time of writing (2007). This interesting and innovative

mode is designed to be parallelisable so that it can give high throughput

on fast data links with low cost and low latency. As the implementation is

moderately complex, and the algorithm was approved as this book was in

its final edit, I don’t include the details here, but refer you instead to the

official specification[947]. The telegraphic summary is that the encryption is

performed in a variant of counter mode; the resulting ciphertexts are also

multiplied together with key material and message length information in a

Galois field of 2128 elements to get an authenticator tag. The output is thus

a ciphertext of the same length as the plaintext, plus a tag of typically 128

bits. The tag computation uses a universal hash function which comes from

thetheoryofunconditionally-secureauthenticationcodes;I’lldescribethisin

Chapter13,‘NuclearCommandandControl’.

5.6 HashFunctions 165

BothCCM,andold-fashionedCBCplusCBCMAC,needacompletelynew

MACtobecomputedon thewhole messageifany bit ofitischanged. How-

ever, the GCM mode of operation has an interesting incremental property: a

new authenticator and ciphertext can be calculated with an amount of effort

proportionaltothenumberofbitsthatwerechanged.GCMisaninventionof

DavidMcGrewandJohnViegaofCisco;theirgoalwastocreateanauthenti-

catedencryptionmodethatishighlyparallelisableforuseinhigh-performance

networkhardwareandthatonlyusesoneblockcipheroperationperblockof

plaintext, unlike CCM or the old-fashioned CBC plus CBC-MAC[862]. Now

that GCM has been adopted as a standard, we might expect it to become the

mostcommonmodeofoperationfortheencryptionofbulkcontent.

5.6 Hash Functions

In section5.4.3.1 I showed how the Luby-Rackoff theorem enables us to

construct a block cipher from a hash function. It’s also possible to construct

a hash function from a block cipher. (In fact, we can also construct hash

functionsandblockciphersfromstreamciphers—so,subjecttosomecaveats

I’lldiscussinthenextsection,givenanyoneofthesethreeprimitiveswecan

constructtheothertwo.)

The trick is to feed the message blocks one at a time to the key input of

our block cipher, and use it to update a hash value (which starts off at say

H =0). Inordertomakethis operationnon-invertible,we addfeedforward:

0

the (i−1)st hash value is exclusive or’ed with the output of round i. This is

ourfinalmodeofoperationofablockcipher(Figure5.16).

h i−1

•

(cid:9)

M E

i

⊕(cid:8)

(cid:1)

h

i

Figure5.16:Feedforwardmode(hashfunction)

166 Chapter5 ■ Cryptography

5.6.1 Extra Requirements on the Underlying Cipher

Thebirthdayeffectmakesanotherappearancehere,inthatifahashfunctionh

isbuiltusingannbitblockcipher,itispossibletofindtwomessagesM (cid:1)=M

1 2

with h(M )=h(M ) with about 2n/2 effort (hash slightly more than that many

1 2

messagesM andlookforamatch).Soa64bitblockcipherisnotadequate,as

i

thecost offorging amessagewouldbeoftheorderof232 messages,whichis

quitepractical.A128-bitciphersuchasAESmaybejustaboutadequate,and

infacttheAACScontentprotectionmechanismusedinthenextgenerationof

DVDsuses‘AES-H’,thehashfunctionderivedfromAESinthisway.

The birthday limit is not the only way in which the hash function mode of

operationismoredemandingontheunderlyingblockcipherthanamodesuch

as CBC designedfor confidentiality. A good illustration comes from a cipher

called Treyfer which was designed to encrypt data using as little memory as

possibleinthe8051microcontrollerscommonlyfoundinconsumerelectronics

anddomesticappliances[1371].(Ittakesonly30bytesofROM.)

Treyfer‘scavenges’itsS-boxbyusing256bytesfromtheROM,whichmay

becode,oreven—tomakecommercialcloningriskier—containacopyright

message. At each round, it acts on eight bytes of text with eight bytes of key

byaddingabyteoftexttoabyteofkey,passingitthroughtheS-box,adding

it to the next byte and then rotating the result by one bit (see Figure5.17).

ThisrotationdealswithsomeoftheproblemsthatmightariseiftheS-boxhas

uneven randomness across its bitplanes (for example, if it contains ascii text

P 0 k 0 P 1 k 1 (cid:127) (cid:127) (cid:127)

+

S

+

<<<1

Figure5.17:ThebasiccomponentoftheTreyferblockcipher

5.6 HashFunctions 167

such as a copyright message). Finally, the algorithm makes up for its simple

roundstructureandprobablylessthanidealS-boxbyhavingalargenumber

ofrounds(32).

No attacks are known on Treyfer which prevent its use for confidentiality

andforcomputingMACs.However,thealgorithmdoeshaveaweaknessthat

prevents its use in hash functions. It suffers from a fixed-point attack. Given

any input, there is a fair chance we can find a key which will leave the input

unchanged. We just have to look to see, for each byte of input, whether the

S-box assumes the output which, when added to the byte on the right, has

the effect of rotating it one bit to the right. If such outputs exist for each

oftheinputbytes,thenit’seasytochoosekeyvalueswhichwillleavethedata

unchangedafteroneround,andthusafter32.Theprobabilitythatwecando

this depends on the S-box3. This means that we can easily find collisions if

Treyfer is used as a hash function. In effect, hash functions have to be based

onblockcipherswhichwithstandchosen-keyattacks.

5.6.2 Common Hash Functions and Applications

AlgorithmssimilartoTreyferhavebeenusedinhashfunctionsinkeymanage-

mentprotocolsinsomepay-TVsystems,buttypicallytheyhaveamodification

topreventfixed-pointattacks,suchasaproceduretoaddintheroundnumber

at each round, or to mix up the bits of the key in some way (a key scheduling

algorithm).

Themostcommonlyusedhashfunctionsareallcryptographicallysuspect.

Theyarebasedonvariantsofablockcipherwitha512bitkeyandablocksize

ofeither128or160bits:

MD4hasthreeroundsanda128bithashvalue,andacollisionwas

found for it in 1998 [394];

MD5hasfourroundsanda128bithashvalue,andacollisionwasfound

for it in 2004[1315, 1317];

theUSSecureHashStandardhasfiveroundsanda160bithashvalue,

anditwasshownin2005thatacollisioncanbefoundwithacomputa-

tionaleffortof269 stepsratherthanthe280 thatonewouldhopegivenits

block size[1316].

The block ciphers underlying these hash functions are similar: their round

functionisacomplicatedmixtureoftheregisteroperationsavailableon32bit

processors[1125].

3Curiously,anS-boxwhichisapermutationisalwaysvulnerable,whilearandomlyselected

oneisn’tquitesobad.Inmanycipherdesigns,S-boxeswhicharepermutationsareessentialor

atleastdesirable.Treyferisanexception.

168 Chapter5 ■ Cryptography

MD5wasbrokenbyXiaoyunWangandhercolleaguesin2004[1315,1317];

collisionscannowbefoundeasily,evenbetweenstringscontainingmeaningful

textandadheringtomessageformatssuchasthoseusedfordigitalcertificates.

Wang seriously dented SHA the following year, providing an algorithm that

willfindcollisionsinonly269 steps[1316];andattheCrypto2007conference,

the view was that finding a collision should cost about 260. Volunteers were

being recruited for the task. So it appears that soon a collision will be found

andSHA-1willbedeclared‘broken’.

Atthetimeofwriting,theUSNationalInstituteofStandardsandTechnology

(NIST)recommendsthatpeopleuseextendedblock-sizeversionsofSHA,such

asSHA-256orSHA-512.ThedraftFIPS180-3allows,thoughdiscourages,the

originalSHA;itspecifiesSHA-256andSHA-512,andalsosupports224-bitand

384-bit hashes derivedfrom SHA-256andSHA-512respectivelybychanging

theinitialvaluesandtruncatingtheoutput.TheNSAspecifiestheuseofSHA-

256orSHA-382alongwithAESinitsSuiteBofcryptographicalgorithmsfor

defenseuse.NISTisalsoorganisingacompetitiontofindareplacementhash

functionfamily[949].

Whether a collision-search algorithm that requires months of work on

hundreds of machines (or a few days on a large botnet) will put any given

applicationatriskcanbeacomplexquestion.Ifbanksystemswouldactually

takeamessagecomposedbyacustomersaying‘PayXthesumY’,hashitand

signit,thenaweakhashfunctioncouldindeedbeexploited:abadmancould

find two messages ‘Pay X the sum Y’ and ‘Pay X the sum Z’ that hashed to

the same value, get one signed, and swap it for the other. But bank systems

don’t work like that. They typically use MACs rather than digital signatures

on actual transactions, relying on signatures only in public-key certificates

that bootstrap key-management protocols; and as the public-key certificates

are generated by trusted CAs using fairly constrained algorithms, there isn’t

an opportunity to insert one text of a colliding pair. Instead you’d have to

findacollisionwithanexternally-giventargetvalue,whichisamuchharder

cryptanalytictask.

Hashfunctionshavemanyuses.OneofthemistocomputeMACs.Anaive

methodwouldbetosimplyhashthemessagewithakey:MAC (M)=h(k,M).

k

However the accepted way of doing this, called HMAC, uses an extra step

in which the result of this computation is hashed again. The two hashing

operations are done using variants of the key, derived by exclusive-or’ing

themwithtwodifferentconstants.ThusHMAC (M)=h(k⊕A,h(k⊕B,M)).A

k

isconstructedbyrepeatingthebyte0x36asoftenasnecessary,andBsimilarly

from the byte0x5C.Givenahash function that may beon theweak side,this

is believed to make exploitable collisions harder to find[741]. HMAC is now

FIPS198,beingreplacedbyFIPS198-1.

5.6 HashFunctions 169

Another use of hash functions is to make commitments that are to be

revealed later. For example, I might wish to timestamp a digital document

in order to establish intellectual priority, but not reveal the contents yet. In

thatcase,Icansubmitahashofthedocumenttoacommercialtimestamping

service[572]. Later, when I reveal the document, the fact that its hash was

timestamped at a given time establishes that I had written it by then. Again,

an algorithm that generates colliding pairs doesn’t break this, as you have to

have the pair to hand when you do the timestamp. The moral, I suppose, is

thatengineersshouldbeclearaboutwhetheragivenapplicationneedsahash

functionthat’sstronglycollision-resistant.

But even though there may be few applications where the ability to find

collisionscouldenableabadguytostealrealmoneytoday,theexistenceofa

potentialvulnerabilitycanstillundermineasystem’svalue.In2005,amotorist

accusedofspeedinginSydney,Australia,wasacquittedaftertheNewSouth

WalesRoadsandTrafficAuthorityfailedtofindanexperttotestifythatMD5

was secure. The judge was ‘‘not satisfied beyond reasonable doubt that the

photograph [had] not been altered since it was taken’’ and acquitted the

motorist;thisrulingwasupheldonappealthefollowingyear[964].Soevenif

avulnerabilitydoesn’tpresentanengineeringthreat,itcanstillpresentavery

realcertificationalthreat.

Finally, before we go on to discuss asymmetric cryptography, there are

twoparticularusesofhashfunctionswhichneedmention:keyupdatingand

autokeying.

Key updating means that two or more principals who share a key pass it

through a one-way hash function at agreed times: K

i

=h(K i−1). The point is

that if an attacker compromises one of their systems and steals the key, he

only gets the current key and is unable to decrypt back traffic. The chain of

compromise is broken by the hash function’s one-wayness. This property is

alsoknownasbackwardsecurity.

Autokeying means that two or more principals who share a key hash it

at agreed times with the messages they have exchanged since the last key

change:K+1i=h(K i,M i1,M i2,...).Thepointisthatifanattackercompromises

one of their systems and steals the key, then as soon as they exchange a

message which he doesn’t observe or guess, security will be recovered in

that he can no longer decrypt their traffic. Again, the chain of compromise is

broken. This property is known as forward security. It is used, for example, in

EFT payment terminals in Australia[143, 145]. The use of asymmetriccrypto

allows a slightly stronger form of forward security, namely that as soon as

a compromised terminal exchanges a message with an uncompromised one

whichtheopponentdoesn’tcontrol,thensecuritycanberecoveredevenifthe

messageisinplainsight.I’lldescribehowthistrickworksnext.

170 Chapter5 ■ Cryptography

5.7 Asymmetric Crypto Primitives

Thecommonlyusedbuildingblocksinasymmetriccryptography,thatispublic

keyencryptionanddigitalsignature,arebasedonnumbertheory.I’llgiveonly

abriefoverviewhere,andlookinmoredetailatsomeofthemechanismsused

inPartIIwhereIdiscussapplications.(Ifyoufindthedescriptionassumestoo

much mathematics, I’d suggestyouskip the following twosections and read

upthematerialfromacryptographytextbook.)

Thetechniqueistomakethesecurityofthecipherdependonthedifficultyof

solvingacertainmathematicalproblem.Thetwoproblemswhichareusedin

almostallfieldedsystemsarefactorization(usedinmostcommercialsystems)

anddiscretelogarithm(usedinmanygovernmentsystems).

5.7.1 Cryptography Based on Factoring

Theprimenumbersarethepositivewholenumberswithnoproperdivisors;that

is,theonlynumbersthatdivideaprimenumberare1andthenumberitself.By

definition,1isnotprime;sotheprimesare{2,3,5,7,11,...}.Thefundamental

theoremofarithmeticstatesthateachnaturalnumbergreaterthan1factorsinto

prime numbers in a way that is unique up to the order of the factors. It is

easy to find prime numbers and multiply them together to give a composite

number,butmuchhardertoresolveacompositenumberintoitsfactors.The

largestcompositeproductoftwolargerandomprimestohavebeenfactorized

to date was RSA-200, a 663-bit number (200 decimal digits), factored in 2005.

ThisfactorizationwasdoneonanumberofPCsandtooktheequivalentof75

years’workonasingle2.2GHzmachine.Itispossibleforfactoringtobedone

surreptitiously,perhapsusingabotnet;in2001,whenthestateoftheartwas

factoring 512-bit numbers, such a challenge was set in Simon Singh’s ‘Code

Book’andsolvedbyfiveSwedishstudentsusingseveralhundredcomputers

to which they had access[24]. By 2007, 512-bit factorization had entered into

mainstreamcommerce.From2003,IntuithadprotecteditsQuickenfileswith

strongencryption,butleftabackdoorbasedona512-bitRSAkeysothatthey

couldofferakeyrecoveryservice.Elcomsoftappearstohavefactoredthiskey

andnowoffersacompetingrecoveryproduct.

It is believed that factoring an RSA modulus of 1024 bits would require a

special-purposemachinecostingintherangeof$10–50mandthatwouldtake

ayearforeachfactorization[781];butI’veheardofno-oneseriouslyplanning

tobuildsuchamachine.Manyphysicistshopethataquantumcomputercould

be built that would make it easy to factor even large numbers. So, given that

Moore’s law is slowing down and that quantum computers haven’t arrived

yet, we can summarise the state of the art as follows. 1024-bit products of

tworandomprimesarehardtofactorandcryptographicsystemsthatrelyon

5.7 AsymmetricCryptoPrimitives 171

them are at no immediate risk from low-to-medium budget attackers; NIST

expects them to be secure until 2010, while an extrapolation of the history of

factoring recordssuggeststhefirst factorization willbe publishedin2018. So

risk-averseorganisations that want keystoremainsecurefor many yearsare

alreadyusing2048-bitnumbers.

The algorithm commonly used to do public-key encryption and digital

signatures based on factoring is RSA, named after its inventors Ron Rivest,

AdiShamirandLenAdleman.ItusesFermat’s(little)theorem,whichstatesthat

for all primes p not dividing a, ap−1 ≡1 (mod p) (proof: take the set {1, 2, ...,

p−1}andmultiplyeachofthemmodulopbya,thencancelout(p−1)!each

side).Euler’sfunctionφ(n)isthenumberofpositiveintegerslessthannwith

whichithasnodivisorincommon;soifnistheproductoftwoprimespqthen

φ(n)=(p−1)(q−1)(theproofissimilar).

TheencryptionkeyisamodulusN whichishardtofactor(takeN =pqfor

twolargerandomlychosenprimespandq,sayof1024bitseach)plusapublic

exponentethathasnocommonfactorswitheitherp−1orq−1.Theprivate

keyisthefactorspandq,whicharekeptsecret.WhereMisthemessageand

Cistheciphertext,encryptionisdefinedby

C≡Me (mod N)

Decryptionisthereverseoperation:

√

M≡ e C (mod N)

Who√everknowstheprivatekey—thefactorspandqofN—caneasilycal-

culate e C (mod N).Asφ(N)=(p−1)(q−1)andehasnocommonfactorswith

φ(N),thekey’sownercanfindanumberdsuchthatde≡1 (mod φ(N))—she

finds the√value of d separately modulo p−1 and q−1, and combines the

answers. e C(modN)isnowcomputedasCd (modN),anddecryptionworks

becauseofFermat’stheorem:

Cd ≡{Me}d ≡Med ≡M1+kφ(N) ≡M.Mkφ(N) ≡Mx1≡M (mod N)

Similarly,theownerofaprivatekeycanoperateonamessagewiththisto

produceasignature

Sig (M)≡Md (mod N)

d

andthissignaturecanbeverifiedbyraisingittothepoweremodN (thus,

using e and N as the public signature verification key) and checking that the

messageMisrecovered:

M≡(Sig (M))e (mod N)

d

Neither RSA encryption nor signature is generally safe to use on its own.

The reason is that, as encryption is an algebraic process, it preserves certain

algebraic properties. For example, if we have a relation such as M M =M

1 2 3

172 Chapter5 ■ Cryptography

that holds among plaintexts, then the same relationship will hold among

ciphertexts C C =C and signatures Sig Sig =Sig . This property is known

1 2 3 1 2 3

asamultiplicativehomomorphism;ahomomorphismisafunctionthatpreserves

somemathematicalstructure.ThehomomorphicnatureofrawRSAmeansthat

itdoesn’tmeettherandomoraclemodeldefinitionsofpublickeyencryption

orsignature.

Another problem with public-key encryption is that if the plaintexts are

drawnfromasmallset,suchas‘attack’or‘retreat’,andtheencryptionprocess

is known to the opponent, then he can precompute possible ciphertexts and

recognise them when they appear. Specific algorithms also have specific

vulnerabilities:withRSA,it’sdangeroustouseasmallexponentetoencrypt

the same message to multiple recipients, as this can lead to an algebraic

attack. To stop the guessing attack, the low-exponent attack and attacks

basedonhomomorphism,it’ssensibletoaddinsomerandomness,andsome

redundancy, into a plaintext block before encrypting it. However, there are

goodwaysandbadwaysofdoingthis.

In fact, crypto theoreticians have wrestled for decades to analyze all the

thingsthatcangowrongwithasymmetriccryptography,andtofindwaysto

tidyitup.ShafiGoldwasserandSilvioMicalicameupwithformalmodelsof

probabilisticencryptioninwhichweaddrandomnesstotheencryptionprocess,

andsemanticsecurity,whichmeansthatanattackercannotgetanyinformation

at all about a plaintext M that was encrypted to a ciphertext C, even if he

is allowed to request the decryption of any other ciphertext C(cid:6) not equal

to C[536]. There are a number of constructions that give provable semantic

security,buttheytendtobetooungainlyforpracticaluse.

The common real-world solution is optimal asymmetric encryption padding

(OAEP), where we concatenate the message M with a random nonce N, and

useahashfunctionhtocombinethem:

C =M⊕h(N)

1

C =N⊕h(C )

2 1

Ineffect,thisisatwo-roundFeistelcipherthatuseshasitsroundfunction.

The result, the combination C ,C , is then encrypted with RSA and sent. The

1 2

recipient then computes N as C ⊕h(C ) and recovers M as C ⊕h(N)[148].

2 1 1

(This construction came with a security proof, in which a mistake was sub-

sequently found[1167, 234], sparking a vigorous debate on the value of

mathematicalproofsinsecurityengineering[724].)RSADataSecurity,which

for years licensed the RSA algorithm, developed a number of public-key

cryptographystandards;PKCS#1describesOAEP[672].

With signatures, things are slightly simpler. In general, it’s often enough

to just hash the message before applying the private key: Sig =[h(M)]d

d

(mod N); PKCS #7 describes simple mechanisms for signing a message

5.7 AsymmetricCryptoPrimitives 173

digest[680].However,insomeapplicationsonemightwishtoincludefurther

datainthesignatureblock,suchasatimestamp,orsomerandomnessinorder

tomakeside-channelattacksharder.

Many of the things that have gone wrong with real implementations have

to do with error handling. Some errors can affect cryptographic mechanisms

directly.ThemostspectacularexamplewaswhenDanielBleichenbacherfound

awaytobreaktheRSAimplementationinSSLv3.0bysendingsuitablychosen

ciphertexts to the victim and observing any resulting error messages. If he

can learn from the target whether a given c, when decrypted as cd (mod n),

corresponds to a PKCS #1 message, then he can use this to decrypt or sign

messages[189]. Other attacks have depended on measuring the precise time

taken to decrypt; I’ll discuss these in the chapter on emission security. Yet

others have involved stack overflows, whether by sending the attack code in

as keys, or as padding in poorly-implemented standards. Don’t assume that

theonlyattacksonyourcryptocodewillbedoingcryptanalysis.

5.7.2 Cryptography Based on Discrete Logarithms

WhileRSAisusedinmostwebbrowsersintheSSLprotocol,andintheSSH

protocolcommonlyusedforremotelogintocomputersystems,thereareother

products,andmanygovernmentsystems,whichbasepublickeyoperationson

discrete logarithms. These come in a number of flavors, some using ‘normal’

arithmetic while others use mathematical structures called elliptic curves. I’ll

explainthenormalcase.Theellipticvariantsuseessentiallythesameideabut

theimplementationismorecomplex.

Aprimitiverootmodulopisanumberwhosepowersgenerateallthenonzero

numbers mod p; for example, when working modulo 7 we find that 52 =25

which reduces to 4 (modulo 7), then we can compute 53 as 52×5 or 4×5

whichis20,whichreducesto6(modulo7),andsoon,asinFigure5.18:

51 =5 (mod7)

52 = 25 ≡4 (mod7)

53 ≡ 4x5 ≡6 (mod7)

54 ≡ 6x5 ≡2 (mod7)

55 ≡ 2x5 ≡3 (mod7)

56 ≡ 3x5 ≡1 (mod7)

Figure5.18:Exampleofdiscretelogarithmcalculations

Thus 5 is a primitive root modulo 7. This means that given any y, we can

alwayssolvetheequationy=5x(mod7);xisthencalledthediscretelogarithm

ofymodulo7.Smallexampleslikethiscanbesolvedbyinspection,butfora

largerandom primenumberp, wedonot knowhow todothis computation.

174 Chapter5 ■ Cryptography

Sothemapping f :x→gx (mod p)isaone-way function, withtheadditional

properties that f(x+y)=f(x)f(y) and f(nx)=f(x)n. In other words, it is a

one-way homomorphism. As such, it can be used to construct digital signature

andpublickeyencryptionalgorithms.

5.7.2.1 Public Key Encryption — Diffie Hellman and ElGamal

To understand how discrete logarithms can be used to build a public-key

encryptionalgorithm, bear inmind that we want acryptosystemwhich does

notneedtheuserstostartoffwithasharedsecretkey.Considerthefollowing

‘classical’scenario.

Imagine that Anthony wants to send a secret to Brutus, and the only

communications channel available is an untrustworthy courier (say, a slave

belongingtoCaesar).Anthonycantakethemessage,putitinabox,padlockit,

andgetthecouriertotakeittoBrutus.Brutuscouldthenputhisownpadlock

on it too, and have it taken back to Anthony. He in turn would remove his

padlock,andhaveittakenbacktoBrutus,whowouldnowatlastopenit.

Exactly the same can be done using a suitable encryption function that

commutes, that is, has the property that {{M} KA} KB={{M} KB} KA. Alice

can takethemessageMandencrypt itwithherkeyKA toget{M} KAwhich

shesendstoBob.BobencryptsitagainwithhiskeyKBgetting{{M} KA} KB.

Butthecommutativitypropertymeansthatthisisjust{{M} KB} KA,soAlice

candecryptitusingherkeyKAgetting{M} KB.ShesendsthistoBobandhe

candecryptitwithKB,finallyrecoveringthemessageM.ThekeysKAandKB

mightbelong-termkeysifthismechanismweretobeusedasaconventional

public-keyencryptionsystem,ortheymightbetransientkeysifthegoalwere

toestablishakeywithforwardsecrecy.

Howcanasuitablecommutativeencryptionbeimplemented?Theone-time

paddoescommute,butisnotsuitablehere.SupposeAlicechoosesarandom

key xA and sends Bob M⊕xA while Bob returns M⊕xB and Alice finally

sends him M⊕xA⊕xB, then an attacker can simply exclusive-orthese three

messages together; as X⊕X =0 for all X, the two values of xA and xB both

cancelourleavingasananswertheplaintextM.

The discrete logarithm problem comes to the rescue. If the discrete log

problembasedonaprimitiverootmodulopishard,thenwecanusediscrete

exponentiation as our encryption function. For example, Alice encodes her

message as the primitive root g, chooses a random number xA, calculates

gxA modulo p and sends it, together with p, to Bob. Bob likewise chooses

a random number xB and forms gxAxB modulo p, which he passes back to

Alice.Alicecannowremoveherexponentiation:usingFermat’stheorem,she

calculatesgxB =(gxAxB)(p−xA) (mod p)andsendsittoBob.Bobcannowremove

hisexponentiation,too,andsofinallygetsholdofg.Thesecurityofthisscheme

depends on the difficulty of the discrete logarithm problem. In practice, it is

5.7 AsymmetricCryptoPrimitives 175

trickytoencodeamessagetobeaprimitiveroot;butthereisamuchsimpler

means of achieving the same effect. The first public key encryption scheme

to be published, by Whitfield Diffie and Martin Hellman in 1976, has a fixed

primitiverootgandusesgxAxBmodulopasthekeytoashared-keyencryption

system.ThevaluesxAandxBcanbetheprivatekeysofthetwoparties.

Let’sseehowthismightprovideapublic-keyencryptionsystem.Theprime

p and generator g are common to all users. Alice chooses a secret random

number xA, calculates yA=gxA and publishes it opposite her name in the

companyphonebook.Bobdoesthesame,choosingarandomnumberx and

B

publishingyB=gxB.InordertocommunicatewithBob,AlicefetchesyBfrom

the phone book, forms yBxA which is just gxAxB, and uses this to encrypt the

messagetoBob.Onreceivingit,BoblooksupAlice’spublickeyy andforms

A

yAxB whichisalsoequaltogxAxB,sohecandecrypthermessage.

Slightlymoreworkisneededtoprovideafullsolution.Somecareisneeded

when choosing the parameters p and g; and there are several other details

which depend on whether we want properties such as forward security.

VariantsontheDiffie-HellmanthemeincludetheUSgovernmentkeyexchange

algorithm(KEA)[939],usedinnetworksecurityproductssuchastheFortezza

card, and the so-called Royal Holloway protocol, which is used by the UK

government[76].

Of course, one of the big problems with public-key systems is how to be

sure that you’ve got a genuine copy of the phone book, and that the entry

you’reinterestedinisn’toutofdate.I’lldiscussthatinsection5.7.5.

5.7.2.2 Key Establishment

Mechanismsforprovidingforwardsecurityinsuchprotocolsareofindepen-

dent interest, As before, let the prime p and generator g be common to all

users.Alicechooses arandom numberR ,calculatesgRA andsendsittoBob;

A

Bob does the same, choosing a random number R and sending gRB to Alice;

B

theythenbothformgRARB,whichtheyuseasasessionkey(Figure5.19).

A→B: gRA (mod p)

B→A: gRB (mod p)

A→B: {M}

gRARB

Figure5.19:TheDiffie-Hellmankeyexchangeprotocol

AliceandBobcannowusethesessionkeygRARB toencryptaconversation.

They have managed to create a shared secret ‘out of nothing’. Even if an

opponenthadobtainedfullaccesstoboththeirmachinesbeforethisprotocol

was started,and thusknewalltheirstoredprivatekeys,thenprovidedsome

basic conditions were met (e.g., that their random number generators were

176 Chapter5 ■ Cryptography

not predictable) the opponent could still not eavesdrop on their traffic. This

is the strong version of the forward security property to which I referred in

section5.6.2. The opponent can’t work forward from knowledge of previous

keyswhichhemighthaveobtained.ProvidedthatAliceandBobbothdestroy

thesharedsecretafteruse,theywillalsohavebackwardsecurity:anopponent

who gets access to their equipment subsequently cannot work backward to

breaktheiroldtraffic.

Butthisprotocolhasasmallproblem:althoughAliceandBobendupwith

asessionkey,neitherofthemhasanyideawhotheyshareitwith.

Suppose that in our padlock protocol Caesar had just ordered his slave

to bring the box to him instead, and placed his own padlock on it next to

Anthony’s.TheslavetakestheboxbacktoAnthony,whoremoveshispadlock,

and brings the box back to Caesar who opens it. Caesar can even run two

instancesoftheprotocol,pretendingtoAnthonythathe’sBrutusandtoBrutus

that he’s Anthony. One fix is for Anthony and Brutus to apply their seals to

theirlocks.

With the vanilla Diffie-Hellman protocol, the same idea leads to a mid-

dlepersonattack.CharlieinterceptsAlice’smessagetoBobandrepliestoit;at

the same time, he initiates a key exchange with Bob, pretending to be Alice.

HeendsupwithakeygRARC whichheshareswithAlice,andanotherkeygRBRC

which he shares with Bob. So long as he continues to sit in the middle of the

networkandtranslatethemessagesbetweenthem,theymayhaveahardtime

detecting that their communications are compromised. The usual solution is

toauthenticatetransientkeys,andtherearevariouspossibilities.

Inonesecuretelephoneproduct,thetwoprincipalswouldreadoutaneight

digit hash of the key they had generated and check that they had the same

value before starting to discuss classified matters. A more general solution is

forAliceandBobtosignthemessagesthattheysendtoeachother.

A few other details have to be got right, such as a suitable choice of the

valuespandg.There’ssomenon-trivialmathematicsbehindthis,whichisbest

lefttospecialists.Therearealsomanythingsthatcangowronginimplemen-

tations—examplesbeingsoftwarethatwillgenerateoracceptveryweakkeys

andthusgiveonlytheappearanceofprotection;programsthatleakthekeyby

theamountoftimetheytaketodecrypt;andsoftwarevulnerabilitiesleading

tostackoverflowsandothernasties.Nonspecialistsimplementingpublic-key

cryptography should consult up-to-date standards documents and/or use

properlyaccreditedtoolkits.

5.7.2.3 Digital Signature

Supposethatthebasepandthegeneratorgarepublicvalueschoseninsome

suitable way, and that each user who wishes to sign messages has a private

signing key X and a public signature verification key Y=gX. An ElGamal

5.7 AsymmetricCryptoPrimitives 177

signature scheme works as follows. Choose a message key k at random, and

formr=gk (modp).Nowformthesignaturesusingalinearequationink,r,

the message M and the private key X. There are a number of equations that

willdo;theparticularonethathappenstobeusedinElGamalsignaturesis

rX+sk=M

So s is computed as s=(M−rX)/k; this is done modulo φ(p). When both

sidesarepassedthroughourone-wayhomomorphismf(x)=gxmodpweget:

grXgsk ≡gM

or

Yrrs ≡gM

AnElGamalsignatureonthemessageMconsistsofthevaluesrands,and

therecipientcanverifyitusingtheaboveequation.

Afewmoredetailsneedtobefixeduptogetafunctionaldigitalsignature

scheme.Asbefore,badchoices ofpandgcanweakenthealgorithm.Wewill

also want to hash the message M using a hash function so that we can sign

messagesofarbitrarylength,andsothatanopponentcan’tusethealgorithm’s

algebraic structure to forge signatures on messages that were never signed.

Havingattendedtothesedetailsandappliedoneortwooptimisations,weget

theDigitalSignatureAlgorithm(DSA)whichisaUSstandardandwidelyused

ingovernmentapplications.

DSA(alsoknown as DSS,for DigitalSignatureStandard)assumesaprime

p of typically 1024 bits, a prime q of 160 bits dividing (p−1), an element g of

orderqintheintegersmodulop,asecretsigningkeyxandapublicverification

keyy=gx.ThesignatureonamessageM,Sig (M),is(r,s)where

x

r≡(gk (mod p)) (mod q)

s≡(h(M)−xr)/k (mod q)

ThehashfunctionusedhereisSHA1.

DSAistheclassicexampleofarandomizeddigitalsignatureschemewithout

messagerecovery.Thestandardhaschangedsomewhatwithfastercomputers,

as variants of the algorithm used to factor large numbers can also be used to

computediscretelogarithmsmodulobasesofsimilarsize4.Initiallytheprime

p could be in the range 512–1024 bits, but this was changed to 1023–1024

bits in 2001[941]; the proposed third-generation standard will allow primes

p in the range 1024–3072 bits and q in the range 160–256 bits1[942]. Further

tweakstothestandardarealsoforeseeableafteranewhashfunctionstandard

isadopted.

4Discretelogeffortslagslightlybehind,witharecordsetin2006of440bits.

178 Chapter5 ■ Cryptography

5.7.3 Special Purpose Primitives

Researchers have discovered a large number of public-key and signature

primitives with special properties. Two that have so far appeared in real

productsarethresholdcryptographyandblindsignatures.

Thresholdcryptoisamechanismwherebyasigningkey,oradecryptionkey,

canbesplitupamongnprincipalssothatanykoutofncansignamessage(or

decrypt). For k=n the construction is easy. With RSA, for example, you can

splituptheprivatekeydasd=d +d +...+d .Fork

1 2 n

complex(butnotmuch—youusetheLagrangeinterpolationformula)[382].

Threshold signatures are used in systemswhere a number of serversprocess

transactions independently and vote independently on the outcome; they

couldalsobeusedtoimplementbusinessrulessuchas‘acheckmaybesigned

byanytwoofthesevendirectors’.

Blind signatures are a way of making a signature on a message without

knowing what the messageis.For example,ifwe are using RSA,Ican take a

randomnumberR,formReM(modn),andgiveittothesignerwhocomputes

(ReM)d =R.Md (mod n). When he gives this back to me, I can divide out R

to get the signature Md. Now you might ask why on earth someone would

want to sign a document without knowing its contents, but there are indeed

applications.

Thefirstwasindigitalcash;abankmightwanttobeabletoissueanonymous

payment tokens to customers, and this has been done by getting it to sign

‘digital coins’ without knowing their serial numbers. In such a system, the

bankmightagreetohonourfor$10anystringMwithauniqueserialnumber

andaspecifiedformofredundancy,bearingasignaturethatverifiedascorrect

usingthepublickey(e,n).Theblindsignatureprotocolshowshowacustomer

cangetabanktosignacoinwithoutthebankerknowingitsserialnumber.The

effectisthatthedigitalcashcanbeanonymousforthespender.(Thereareafew

technicaldetailsthatneedtobesortedout,suchashowyoudetectpeoplewho

spendthesamecointwice;butthesearefixable.)Blindsignaturesanddigital

cashwereinventedbyChaum[285],alongwithmuchothersupportingdigital

privacytechnologywhichI’lldiscusslater[284].Theywereusedbrieflyinpilot

projectsforroadtollsintheNetherlandsandforelectronicpursesinBrussels,

but failed to take off on a broader scale because of patent issues and because

neither banks nor governments really want payments to be anonymous: the

anti-money-laundering regulations nowadays restrict anonymous payment

services to rather small amounts. Anonymous digital credentials are now

talked about, for example, in the context of ‘identity management’: the TPM

chiponyourPCmotherboardmightprovesomethingaboutyou(suchasyour

age)withoutactuallyrevealingyourname.

Researchers continue to suggest new applications for specialist public key

mechanisms. A popular candidate is in online elections, which require a

5.7 AsymmetricCryptoPrimitives 179

particular mixture of anonymity and accountability. Voters want to be sure

that their votes have been counted, but it’s also desirable that they should

not be able to prove which way they voted to anybody else;if they can, then

vote-buyingandintimidationbecomeeasier.

5.7.4 Elliptic Curve Cryptography

Finally, discrete logarithms and their analogues exist in many other mathe-

matical structures; thus for example elliptic curve cryptography uses discrete

logarithms on an elliptic curve—a curve given by an equation like y2 =

x3+ax+b. These curves have the property that you can define an addition

operationonthemanduseitforcryptography;thealgebragetsabitcomplex

andageneralbooklikethisisn’ttheplacetosetitout.However,ellipticcurve

cryptosystemsareinterestingfortworeasons.

First, they give versions of the familiar primitivessuch as Diffie-Hellmann

keyexchangeandtheDigitalSignatureAlgorithmthatuselesscomputation,

and also have slightly shorter variables; both can be welcome in constrained

environments such as smartcards and embedded processors. Elliptic curve

cryptography is used,for example,inthe rights-managementmechanisms of

Windows MediaPlayer, and has been adopted as a standard by the NSA for

useindefensesystems.

Second, some elliptic curves have a bilinear pairing which Dan Boneh and

MattFranklinusedtoconstructcryptosystemswhereyourpublickeyisyour

name[207].RecallthatinRSAandDiffie-Hellmann,theuserchosehisprivate

key and then computed a corresponding public key. In a so-called identity-

basedcryptosystem,youchooseyouridentitythengotoacentralauthoritythat

issuesyouwithaprivatekeycorrespondingtothatidentity.Thereisaglobal

public key, with which anyone can encrypt a message to your identity; you

can decrypt this using your private key. Earlier, Adi Shamir had discovered

identity-basedsignatureschemesthatallowyoutosignmessagesusingaprivate

keysothatanyonecanverifythesignatureagainstyourname[1147].Inboth

cases, your private key is computed by the central authority using a system-

wide private key known only to itself. Identity-based primitives could have

interesting implications for specialist systems, but in the context of ordinary

public-key and signature systems they achieve much the same result as the

certificationofpublickeys,whichI’lldiscussnext.

5.7.5 Certification

Now that we can do public-key encryption and digital signature, we need

somemechanismtobinduserstokeys.TheapproachproposedbyDiffieand

Hellmanwhentheyinventeddigitalsignatureswastohaveadirectoryofthe

publickeysofasystem’sauthorizedusers,likeaphonebook.Amorecommon

180 Chapter5 ■ Cryptography

solution,duetoLorenKohnfelder,isforacertificationauthority(CA)tosignthe

users’publicencryptionand/orsignatureverificationkeysgivingcertificates

that contain the user’s name, attributed such as authorizations, and public

keys.TheCAmightberunbythelocalsystemadministrator;oritmightbea

thirdpartyservicesuchasVerisignwhosebusinessistosignpublickeysafter

doingsomeduediligenceaboutwhethertheybelongtotheprincipalsnamed

inthem.

Acertificatemightbedescribedsymbolicallyas

C =Sig (T ,L,A,K ,V ) (5.1)

A KS S A A

where(usingthesamenotationaswithKerberos)T isthecertificate’sstart-

S

ing date and time, L is the length of time for which it is valid, A is the user’s

name, K is her public encryption key, and V is her public signature verifi-

A A

cation key. In this way, only the administrator’s public signature verification

keyneedstobecommunicatedtoallprincipalsinatrustworthymanner.

Certificationishard,forawholelotofreasons.I’lldiscussdifferentaspects

later—naminginChapter6,‘DistributedSystems’,public-keyinfrastructures

inChapter21,‘NetworkAttackandDefense’,andthepolicyaspectsinPartIII.

Here I’ll merely point out that the protocol design aspects are much harder

thantheylook.

Oneofthefirstproposedpublic-keyprotocolswasduetoDorothyDenning

andGiovanniSacco,whoin1982proposedthattwousers,sayAliceandBob,

set up a shared key K as follows. When Alice first wants to communicate

AB

with Bob, she goes to the certification authority and gets current copies of

public key certificates for herself and Bob. She then makes up a key packet

containing a timestamp T , a session key K and a signature, which she

A AB

computesontheseitemsusingherprivatesigningkey.Shethenencryptsthis

wholebundleunderBob’spublickeyandshipsitofftohim.Symbolically,

A→B:C ,C ,{T ,K ,Sig (T ,K )} (5.2)

A B A AB KA A AB KB

In 1994, Mart´ın Abadi and Roger Needham pointed out that this protocol

isfatallyflawed[2].Bob,onreceivingthis message,canmasqueradeas Alice

for as long as Alice’s timestamp T remains valid! To see how, suppose that

A

Bob wants to masquerade as Alice to Charlie. He goes to Sam and gets a

freshcertificateC forCharlie,andthenstripsofftheouterencryption{...}

C KB

from message 3 in the above protocol. He now re-encrypts the signed key

packetT ,K ,Sig (T ,K )withCharlie’spublickey—whichhegetsfrom

A AB KA A AB

C —andmakesupabogusmessage3:

C

B→C:C ,C ,{T ,K ,Sig (T ,K )} (5.3)

A C A AB KA A AB KC

It is quite alarming that such a simple protocol—essentially, a one line

program—should have such a serious flaw remain undetected for so long.

Withanormalprogramofonlyafewlinesofcode,youmightexpecttofinda

5.7 AsymmetricCryptoPrimitives 181

buginitbylookingatitforaminuteortwo.Infact,publickeyprotocolsare

if anything harder to design than protocols that use shared-key encryption,

astheyarepronetosubtleandperniciousmiddlepersonattacks.Thisfurther

motivatestheuseofformalmethodstoprovethatprotocolsarecorrect.

Often,theparticipants’namesaren’tthemostimportantthingstheauthen-

tication mechanism has to establish. In the STU-III secure telephone used by

theUSgovernmentanddefensecontractors,thereisaprotocolforestablishing

transientkeyswithforwardandbackwardsecurity;toexcludemiddleperson

attacks, users have a crypto ignition key, a portable electronic device that they

plugintothephonetoidentifynotjusttheirnames,buttheirsecurityclearance

level. In general, textbooks tend to talk about identification as the main goal

of authentication and key management protocols; but in real life, it’s usually

authorization that matters. This is more complex, as it starts to introduce

assumptions about the applicationinto theprotocol design.(Infact, the NSA

securitymanualemphasisestheimportanceofalwaysknowingwhetherthere

is an uncleared person in the room. The STU-III design is a natural way of

extendingthistoelectroniccommunications.)

Oneseriousweaknessofrelyingonpublic-keycertificatesisthedifficultyof

gettinguserstounderstandalltheirimplicationsandmanagethemproperly,

especiallywheretheyarenotanexactreimplementationofafamiliarmanual

control system[357]. There are many other things that can go wrong with

certification at the level of systems engineering, which I’ll start to look at in

thenextchapter.

5.7.6 The Strength of Asymmetric Cryptographic

Primitives

In order to provide the same level of protection as a symmetric block cipher,

asymmetriccryptographicprimitivesgenerallyrequireatleasttwicetheblock

length. Elliptic curve systems appear to achieve this bound; a 128-bit elliptic

scheme could be about as hard to break as a 64-bit block cipher with a 64-bit

key;andtheonlypublic-keyencryptionschemesusedintheNSA’sSuiteBof

militaryalgorithmsare256-and384-bitellipticcurvesystems.Thecommoner

schemes, based on factoring and discrete log, are less robust because there

are shortcut attack algorithms such as the number field sieve that exploit

the fact that some integers are smooth, that is, they have a large number of

small factors. When I wrote the first editionof this book in 2000, the number

field sieve had been used to attack keys up to 512 bits, a task comparable in

difficulty to keysearch on 56-bit DES keys; by the time I rewrote this chapter

for the second edition in 2007, 64-bit symmetric keys had been brute-forced,

and the 663-bit challenge number RSA-200 had been factored. The advance

in factoring has historically been due about equally to better hardware and

better algorithms. I wrote in 2000 that ‘The current consensus is that private

182 Chapter5 ■ Cryptography

keysforRSAandforstandarddiscretelogsystemsshouldbeatleast1024bits

long, while 2048 bits gives some useful safety margin’; now in 2007, 1024-bit

RSAiswidelybelievedtogiveaboutthesameprotectionas80-bitsymmetric

keys,anddesignersarestartingtomoveto2048bitsforkeysintendedtolast

manyyears.AsImentionedabove,anextrapolationofrecentfactoringresults

suggeststhatitmightbeadecadebeforeweseea1024-bitchallengefactored—

althoughwithMoore’slawstartingtoslowdown,itmighttakemuchlonger.

No-onereallyknows.(HoweverIexpecttosee768-bit RSAfactoredwithina

fewyears.)

There has been much research into quantum computers—devices that per-

form a large number of computations simultaneously using superposed

quantum states. Peter Shor has shown that if a sufficiently large quantum

computer can be built, then both factoring and discrete logarithm compu-

tations will become easy[1165]. So far only very small quantum computers

can be built; factoring 15 is about the state of the art in 2007. Many people

are sceptical about whether the technology can be scaled up to threaten real

systems. But if it does, then asymmetric cryptography may have to change

radically.Soitisfortunatethatmanyofthethingswecurrentlydowithasym-

metricmechanismscanalsobedonewithsymmetricones;mostauthentication

protocolsinusecouldberedesignedtousevariantsonKerberos.

5.8 Summary

Manyciphersfailbecausethey’reusedimproperly,soweneedaclearmodel

of what a cipher does. The random oracle model provides a useful intuition:

weassumethateachnewvaluereturnedbytheencryptionengineisrandom

inthesenseofbeingstatisticallyindependentofallthedifferentoutputsseen

before.

Block ciphers for symmetric key applications can be constructed by the

carefulcombinationofsubstitutionsandpermutations;forasymmetricappli-

cations such as public key encryption and digital signature one uses number

theory.Inbothcases,thereisquitealargebodyofmathematics.Otherkinds

of ciphers—stream ciphers and hash functions—can be constructed from

block ciphers by using them in suitable modes of operation. These have

different error propagation, pattern concealment and integrity protection

properties.

Thebasicpropertiesthatthesecurityengineerneedstounderstandarenot

toodifficulttograsp,thoughtherearemanysubtlethingsthatcangowrong.

In particular, it is surprisingly hard to build systems that are robust even

when components fail (or are encouraged to) and where the cryptographic

mechanisms are well integrated with other measures such as access control

andphysicalsecurity.I’llreturntothisrepeatedlyinlaterchapters.

FurtherReading 183

Research Problems

There are many active threads in cryptography research. Many of them are

where crypto meets a particular branch of mathematics (number theory,

algebraic geometry, complexity theory, combinatorics, graph theory, and

information theory). The empirical end of the business is concerned with

designing primitives for encryption, signature and composite operations,

and which perform reasonably well on available platforms. The two meet

in the study of subjects ranging from cryptanalysis, through the search for

primitivesthatcombineprovablesecuritypropertieswithdecentperformance,

toattacksonpublickeyprotocols.Researchismoredrivenbytheexistingbody

of knowledge than by applications, though there are exceptions: copyright

protection concerns and ‘Trusted Computing’ have been a stimulus in recent

years, as was the US government’s competition in the late 1990s to find an

AdvancedEncryptionStandard.

Thebestwaytogetaflavorofwhat’sgoingonistoreadthelastfewyears’

proceedings of research conferences such as Crypto, Eurocrypt, Asiacrypt,

CHES and Fast Software Encryption—all published by Springer in their

LectureNotesonComputerScienceseries.

Further Reading

The classic papers by Whit Diffie and Martin Hellman[385] and by Ron

Rivest,AdiShamirandLenAdleman[1078]aretheclosesttorequiredreading

in this subject. The most popular introduction is Bruce Schneier’s Applied

Cryptography[1125]whichcoversalotofgroundatalevelanon-mathematician

can understand,but isslightlydated.AlfredMenezes,Paul vanOorshot and

Scott Vanstone’s Handbook of Applied Cryptography[872] is the closest to a

standardreferencebookonthemathematicaldetail.Foranappreciationofthe

recent history of cryptanalysis, try Mark Stamp and Richard Low’s ‘Applied

Cryptanalysis’[1214]:thishasrecentattacksonfieldedcipherssuchasPKZIP,

RC4,CMEAandMD5.

Therearemanymorespecialisedreferences.Thebibleondifferentialcrypt-

analysisisabookbyitsinventorsEliBihamandAdiShamir[170],whileagood

shorttutorialonlinearanddifferentialcryptanalysiswaswrittenbyHoward

Heys[602]. A textbook by Doug Stinson has another detailed explanation of

linear cryptanalysis[1226]; and the modern theory of block ciphers can be

tracedthroughthepapersintheFastSoftwareEncryptionconferenceseries.The

originalbookonmodesofoperationisbyCarlMeyerandSteveMatyas[880].

Neal Koblitzhas agood basicintroduction tothe mathematics behind public

keycryptography[723];andthenumberfieldsieveisdescribedin[780].

184 Chapter5 ■ Cryptography

There’s a shortage of good books on the random oracle model and on

theoretical cryptology in general: all the published texts I’ve seen are very

technical and heavy going. Probably the most regarded source is a book by

OdedGoldreich[535]butthisispitchedatthepostgraduatemathsstudent.A

less thorough but more readableintroduction to randomness and algorithms

isin[564].Currentresearchatthetheoreticalendofcryptologyisfoundatthe

FOCS,STOC,Crypto,EurocryptandAsiacryptconferences.

Four of the simple block cipher modes of operation (ECB, CBC, OFB and

CFB) date back to FIPS-81; their specification was reissued, with CTR mode

added, in 2001 as NIST Special Publication 800-38A[944]. The compound

modesofoperationaredescribedinsubsequentpapersinthatseries.

Thehistoryofcryptologyisfascinating,andsomanyoldproblemskeepon

recurringinmodernguisesthatthesecurityengineershouldbefamiliarwith

it. The standard work is Kahn[676]; there are also compilations of historical

articlesfromCryptologia[363,361,362]aswellasseveralbooksonthehistory

ofcryptologyinWorldWar 2[296,677,836,1336].TheNSAMuseumatFort

George Meade, Md., is also worth a visit, as is the one at Bletchley Park in

England.

Finally,nochapterthatintroducespublickeyencryptionwouldbecomplete

withoutamentionthat,underthenameof‘non-secretencryption,’itwasfirst

discoveredbyJamesEllisinabout1969.However,asEllisworkedforGCHQ

(Britain’s Government Communications Headquarters, the equivalent of the

NSA)hisworkremainedclassified.TheRSAalgorithmwastheninventedby

Clifford Cocks, and also kept secret. This story is told in[427]. One effect of

thesecrecywasthattheirworkwasnotused:althoughitwasmotivatedbythe

expense of Army key distribution, Britain’s Ministry of Defence did not start

buildingelectronickeydistributionsystemsforitsmainnetworksuntil 1992.

Itshouldalsobenotedthattheclassifiedcommunitydidnotpre-inventdigital

signatures;theyremaintheachievementofWhitDiffieandMartinHellman.