The EMD Mode of Operation (A Tweaked, Wide-Blocksi

TheEMDModeofOperation(ATweaked,Wide-Blocksize,StrongPRP)PhillipRogaway∗26September2002AbstractWedescribeablock-ciphermodeofoperation,EMD,thatbuildsastrongpseudorandomper-mutation(PRP)onnmbits(m≥2)outofastrongPRPonnbits(i.e.,ablockcipher).TheconstructedPRPisalsotweaked(inthesenseof[10]):todeterminethenm-bitciphertextblockC=ETK(P)oneprovides,besidesthekeyKandthenm-bitplaintextblockP,ann-bittweakT.Themodeuses2mblock-ciphercallsandnoothercomplexorcomputationallyexpensivesteps(suchasuniversalhashing).Encryptionanddecryptionareidenticalexceptthatencryptionusestheforwarddirectionoftheunderlyingblockcipheranddecryptionusesthebackwardsdirection.WesuggestthatEMDprovidesanattractivesolutiontothedisk-sectorencryptionproblem,whereonewantstoencipherthecontentsofannm-bitdisksectorinawaythatdependsonthesectorindexandissecureagainstchosen-plaintext/chosen-ciphertextattack.Keywords:block-cipherusage,cryptographicstandards,diskencryption,EMDmode,modesofoperation,provablesecurity,symmetricencryption.Note(addedFeb2003):themodesinthispaperarewrongThemodesdescribedinthisnotearewrong:therearesimpleattacksthatdistinguishEMD/EMEoraclesandtheirinversesfromarandompermutationanditsinverse.TheproofinthispaperforEMDhasabuginthefinalcaseanalysisinAppendixA.3.TheattackswerefoundbyAntoineJoux,“CryptanalysisoftheEMDModeofOperation”,toappearatEurocrypt2003.Thisnotewasnotpublishedanywhere,andmyfirstinclinationwastowithdrawitfromePrintaswell.ButthatwouldleaveJouxwithaEurocryptpaperattackingaschemethatisdescribednowhere.Thisseemedundesirable.SoI’mgoingtoleavethisbuggymanuscriptuponePrint,unchangedapartfromthisnote,atleastforawhile.Anewversionofthispaper,“ATweakableEncipheringMode”,hasbeenwrittenandwillbedistributedsoon.ThepaperisjointwithShaiHalevi.InthenewpaperShaiandIfixthebuggymodeanditsproof.∗DepartmentofComputerScience,UniversityofCalifornia,Davis,California,95616,USA;andDepartmentofCom-puterScience,FacultyofScience,ChiangMaiUniversity,50200Thailand.E-mail:[e-mail]∼rogaway/1IntroductionMotivation.Supposeyouwanttoenciphereach512-bytesectoronadisk.AplaintextdisksectorPhavingindexTistobereplacedbyaciphertextdisksectorC=ETK(P)whereKisasecretkey.ItisnecessarythatChavethesamelengthasP;ablockcipherE,andnotasemantically-secureencryptionscheme,iswhatwewant.Butblock-cipherE,withablocksizeof512bytes,shouldbebuiltastandardblock-cipherEthathas,say,16-byteblocks.Howshouldthisbedone?Theattack-modelenvisagesachosen-plaintext/chosen-ciphertextattack:theadversarycanlearntheciphertextCforanyplaintextPand“tweak”Tthatitchooses,anditcanlearntheplaintextPforanyciphertextCandtweakT.Anychangeinaplaintextshouldgiveacompletelyunpredictableciphertext,andanychangeintheciphertextshouldgiveacompletelyunpredictableplaintext.Identicalplaintextswithdifferenttweaksshouldencrypttounrelatedciphertexts,andidenticalciphertextswithdifferenttweaksshoulddecrypttounrelatedplaintexts.Slightlymoreformally,wewantastrong,tweaked,pseudorandompermutation(PRP):forarandomkeyK,eachpermutationETKanditsinverseDTKshouldbeindistinguishablefromrandompermutationΠTanditsinverse`T.Conventionalmodes,likeCBCwithanIVofT,don’tsolvethisproblem.Theycan’tbytheirverystructure:thefirstblockofciphertextdoesn’tevendependonalloftheblocksofplaintext.ThemostreasonableknownapproachtoconstructthedesiredkindofobjectistofollowNaorandReingold[15,16],whogiveageneralmethodforturningablockcipherintoalong-blocksizeblock-cipher.Theirpaperswereourstartingpoint.EMDMode.Inthispaperweproposeanewmodeofoperation,EMDmode.GivenablockcipherE:K×{0,1}n→{0,1}nandanumberm≥2,EMDmodeprovidesatweakedblock-cipherE=EMD[E,m]=EMD-EwhereE:K×{0,1}n×{0,1}nm→{0,1}nm.Wecallntheblocklength(anditisalsothetweaklengthinourconstruction)andnmisthesectorlength(inbits)andmistheblockspersector.Asatweakedblock-cipher,eachETK(·)=E(K,T,·)ispermutationon{0,1}nm.WedenotetheinverseofthispermutationbyDTK.EMDhasthefollowingcharacteristics:(1)Itusesexactly2mblock-ciphercalls.(2)Itusesnoothercostlyoperations(inparticular,EMDusesnouniversalhashing).(3)ItusesjusttheonekeyKfortheunderlyingblockcipher—noadditionalkeymaterialisneeded.(4)EncryptionbyEusesonlytheforwarddirectionoftheblockcipherE,whiledecryptionbyDusesonlythebackwarddirectionoftheblockcipher,D=E−1.(5)Themodeiscompletelysymmetric:encryptionisidenticaltodecryptionexceptforusingDinplaceofE.(6)Themodeisascache-efficientasonecanhopeforinastrongPRP.(7)Themethodissimpletounderstandandeasytoimplement.TheabovesetofcharacteristicsmakeEMD-EattractiveinbothhardwareandsoftwareaslongasEis.WeemphasizethatEMDdoesnotchangetheinternalsofanycryptographicprimitive;thattheinclusionofatweakTaddsconsiderableversatilityandeaseofcorrectuse;andthatthemodeisfullyspecified—therearenomissingpieces(likeauniversalhashfunction)lefttofillin.Thename“EMD”ismeanttosuggestEncrypt–Mask–Decrypt.Namely,toencipherwithEMDoneencryptstheplaintextPtoformanintermediatevaluePPP;thenonecomputesamaskMASKfromPPPandthetweakTandxorsMASKwithPPPtogiveanintermediatevalueCCC;finally,onedecryptsCCCtoformtheciphertextC.Forapreview,seeFigu