General Model of the SingleKey Meet-in-the-Middle Distinguisher on the Word-Oriented Block Cipher

GeneralModeloftheSingle-KeyMeet-in-the-MiddleDistinguisherontheWord-OrientedBlockCipher

LiLin1,2(B),WenlingWu1,YanfengWang1,andLeiZhang1

1

TrustedComputingandInformationAssuranceLaboratory,InstituteofSoftware,

ChineseAcademyofSciences,Beijing100190,China{linli,wwl,wangyanfeng,zhanglei1015}@is.iscas.ac.cn

2

GraduateUniversityofChineseAcademyofSciences,Beijing100190,China

Abstract.Thesingle-keymeet-in-the-middleattackisane?cientattackagainstAES.Themaincomponentofthisattackisadistin-guisher.Inthispaper,weextendthiskindofdistinguishertotheword-orientedblockcipher,suchastheSPNblockcipherandtheFeistel-SPblockcipher.Weproposeageneraldistinguishermodeland?ndthatbuildingabetterdistinguisherisequivalenttoapositiveintegeropti-mizationproblem.Thenwegiveaproperalgorithmtosolvethisprob-lem.Furthermore,weanalysethelimitationofthedistinguisherusingthee?cienttabulationandgiveamethodtosearchthespecialdi?eren-tialtrailweneedinthisdistinguisher.Finally,weapplythedistinguishertoCrypton,mCryptonandLBlock,andgivedistinguisherson4-roundCrypton,4-roundmCryptonand9-roundLBlock.Wealsogive7-roundattacksonCrypton-128andmCrypton-96.Keywords:Single-keyMIMToriented·SPN·Feistel-SPN

·

Geneldistinguishermodel

·

Word-

1Introduction

TheRijndaelblockcipherwasdesignedbyDaemenandRijmenin1997andacceptedastheAES(AdvancedEncryptionStandard).VariousofattackshasbeenproposedagainstAES,thesingle-keymeet-in-the-middleattack1wasane?cientone.Theideaofthisattack?rstcamefromthesquareattack[3],itusedtheδ-settobuildthedistinguisher.Afterthat,GilbertandMinershowedin[11]thatthispropertycouldbeusedmoreprecisetobuildacollisionsattack

cukhadgeneralizedthisideaon7-roundRijndael.AtFSE2008,DemirciandSel?

usingthemeet-in-the-middletechnique[6].Morespeci?cally,theyshowedthatthevalueofeachbyteoftheciphertextcouldbedescribedbyafunctionoftheδ-setparameterizedby258-bitparameters.Thisfunctionwasusedtobuildadistinguisheron4-roundAES.AtASIACRYPT2010,Dunkelman,Kellerand

1

Inthispaper,wecallthiskindofattackthesingle-keymeet-in-the-middleattack.

cSpringerInternationalPublishingSwitzerland2014??

H.-S.LeeandD.-G.Han(Eds.):ICISC2013,LNCS8565,pp.203–223,2014.DOI:10.1007/978-3-319-12160-413

204L.Linetal.

Shamirreducedthenumberofparametersfrom25to24[9].Meanwhile,theydevelopedmanynewideastosolvethememoryproblemsoftheDemirciandSel?ckattacks.Byusingthedi?erentialenumerationtechnique,thenumberofparameterswasreducedlargelyfrom24to16.AtEUROCRYPT2013,Derbez,FouqueandJeandevelopedthee?cienttabulation[8]tofurtherreducethenum-berofparametersfrom16to10whichresultedinalowermemorycomplexity.AtFSE2013,DerbezandFouqueusedtheautomaticsearchtool[1]tobalancethecostoftime,memoryanddataoftheonlinephaseando?-linephase[7].However,thesingle-keymeet-in-the-middleattackisrarelyappliedtoblockciphersexceptAES.Inthispaper,wefocusonthesingle-keymeet-in-the-middledistinguisherwhichplaysanimportantroleinbuildingtheattack.Thiskindofdistinguisherisextendedtotheword-orientedblockcipher,suchastheSPNblockcipherandtheFetstel-SPblockcipher(includingtheGeneralizedFeis-telblockcipher).We?rstde?netheT-δ-setwhichisaspecialsetofstatesandtheS-multisetwhichisamultisetofScells,thenusethesede?nitionstogettheleastspreadT-δ-setwhichhastheleastnumberofactivecellsandtheleastaffected-cell-setwhichisa?ectedbytheleastnumberofactivecells.Afterthat,webuildabasicdistinguishermodelontheSPNblockcipherand?ndthatbuildingabetterdistinguisherisequivalenttoapositiveintegeroptimizationproblem.Thenaproperalgorithmisgiventosolvethisproblem.Furthermore,thisbasicdistinguishermodelisappliedtotheFeistel-SPblockcipherandtheGeneralizedFeistelblockcipher.Moreover,weanalysethelimitationofthedis-tinguisherusingthee?cienttabulation[8]andgiveamethodtosearchthespe-cialdi?erentialtrailneededinthisdistinguisher.WealsoshowsomeviewpointsthatDerbezetaldon’tconsiderin[8]abouttheAESdistinguisherstartedfroma2-δ-setandthe5-roundAESdistinguisher.FinallyweapplythedistinguisherstoCrypton[12,13],mCrypton[14]andLBlock[16].Webuildthe4-rounddis-tinguishersonCryptonandmCrypton,thenusethesedistinguisherstoattack7-roundCrypton-128andmCrypton-96.ForCrypton,ittakesatimecomplexityof2113,adatacomplexityof2113chosenplaintextsandamemorycomplexityof291.FormCrypton,ittakesatimecomplexityof277,adatacomplexityof249chosen-plaintextsandamemorycomplexityof252.44.Andwegivea9-rounddistinguisheronLBlockwith14guessed-nibbles.

Theorganizationofthispaperisasfollows:Sect.2givessomede?nitionsandabasicsingle-keymeet-in-the-middleattackscheme.Section3givesthebasicdistinguishermodelandthemodelusingthee?cienttabulation.InSect.4andSect.5,weapplythedistinguishertoCrypton,mCryptonandLBlock.

2De?nitionsandAttackScheme

Inthissection,we?rstgivethede?nitionsoftheSPNblockcipher,theT-δ-setandtheS-multiset,thenusethesede?nitionstogiveabasicsingle-keymeet-in-the-middleattackscheme.WealsogivethewaytocalculatingthetotalnumberofS-multisetsandthewaytogetthepropervaluesofSandT.Section2.1givesthede?nitionoftheSPNblockcipher.InSect.2.2,wegivethede?nitions

GeneralModeloftheSingle-KeyMeet-in-the-MiddleDistinguisher205

oftheT-δ-setandS-multiset,thewaytocalculatethenumberofS-multisetsandthede?nitionoftheproperparameters.InSect.2.3,wegivethebasicattackscheme.2.1

TheSPNBlockCipher

Tokeepourreasoningasgeneralaspossible,wegiveinthissubsectionagenericdescriptionofSubstitution-PermutationNetwork(SPN)cipher.Oneroundiisitselfcomposedofthreelayers:akeyscheduletransformationlayer(KS)wherewecangetthekeyusedinthisround,ablockcipherpermutationlayer(BC)thatupdatesthecurrentstateoftheblockcipher,akey-additionlayer(AK)wherean-cellround-keyrkiisextractedfromkiandXORedtoxi.

Thesizeofplaintextorciphertextisncells,andthesizeofkeyisnKcells,eachcellconsistofbbits.Astatemeansasetofncellsbeforeorafteroneoper-ation.ThecipherisconsistofRtotalsuccessiveapplicationsofaroundfunction,andwedenotexiandkithesuccessiveinternalstatesoftheencryptionandthekeyschedule,respectively.Thestatex0isinitializedwiththeinputplaintextandk0withtheinputkey.Wecounttheround-numberfrom0.De?nition1(SPNcipher[10]).LetablockcipherEwhoseinternalstateisviewedasann-cellvector,eachcellrepresentingab-bitword,andthekeysched-uleasannK-cellvector.TheblockcipherEiscalledanSPNcipherwhenitsroundfunctionBCismadeupofalinearfunctionPandanon-linearpermu-tationS,withBC=P?S,thelatterapplyingoneordistinctb-bitSboxestoeverycell.

TheSPNcipherconsideredhereneedstohavethefollowingproperties:alloperationsarebasedoncells;ifweknowtheinputdi?erences,wecangettheoutputdi?erencesafterthelinearfunction,andviceversa.2.2

De?nitions

In[4],Daemenetal?rstproposedthede?nitionofδ-set.Afterthat,δ-setwasusedintheattacksonAESandotherciphers.Intheformersingle-keymeet-in-the-middleattacks[6–9,11],theattackersusethestatestructurethatthereisonlyoneactivebyteinthe?rstroundofthedistinguishertoattackAES.However,weshouldchoosetwoormoreall-activecellsforthelightweightblockcipherorotherkindsoftheSPNciphers.

De?nition2(T-δ-set).LetaT-δ-setbeasetof2T×bstatesthatarealldi?er-entinTcells(theall-activecells)2andallequalintheothercells(theinactivecells),wherebisthenumberofbitsinacellandT≤n.

In[9],Dunkelman,KellerandShamirintroducedthemultisetandusethedi?erencesinsteadoftherealvaluestoreducethenumberofguessed-cells(cells

2

All-activecell:takeallthevaluesofthiscellonce.Theactivecell:theprobabilitythatthedi?erenceisn’tzeroisgreaterthan0.

206L.Linetal.

needtobeguessed).However,theyonlyconsiderthemultisetofonecell.WeshouldconsiderthemultisetoftwoormorecellsforlightweightblockciphersorotherkindsoftheSPNciphers.

De?nition3(S-Multiset).AnS-multisetisanunorderedsetinwhichele-mentscanoccurmanytimes,andeveryelementoftheS-multisetconsistsofScells,S≤n.

Next,wewillshowthenumberofpossibleS-multisets3

Proposition1(NumberofS-Multisets).IfoneS-multisethas2T×bele-ments,thesizeofeachelementisScells,thenthenumberofpossibleS-multisets??T×b+2S×b?1??

.is22S×b?1ThechosenofSandThaveagreatin?uenceonthedistinguisher.Wegive

themethodtochoosethepropernumberofSandTasfollows:

De?nition4(ProperParameters).Thede?nitionoftheproperparameters

??T×b+2S×b?1??

isasfollows:wechoosetheintegerparametersSandTsatisfythat22S×b?1

????T×bS×b

2+2?1

anditssubset??2nK×b.ItmeansthatwehaveasetWofsize2S×b?1

W??ofsize2nK×b.IfwerandomlychooseanelementfromW,theprobabilitythatitisalsofromW??isalmostzero,wecall(T,S)theproperparameters(S≤n,T≤n).密钥空间大小2.3

AttackScheme

Inthissection,wepresentauni?edviewofthesingle-keymeet-in-the-middleattack,whereRroundsoftheblockciphercanbesplitintothreeconsecutivepartsofr1,r,andr2.

ThegeneralattackusesthreesuccessivestepsasshowninFig.1:Precomputationphase

1.Supposewehavebuiltanr-rounddistinguisherfromaT-δ-settoanS-multisetbyguessingsomeinternalcells,webuildalookuptableTcontainingallthepossibleS-multisets;Onlinephase

2.WeneedtoidentifyaT-δ-setintheonlinephase(forthedistinguisherusingthee?cienttabulation,theT-δ-setneedtocontainapairofmessagesveri-fyingthedesireddi?erentialtrail);

3.Finally,wepartiallydecrypttheassociatedT-δ-setthroughthelastr2roundsandcheckwhetheritbelongstoT.Fromthestatementabove,ifwewanttomakethiskindofattackmoree?cient,adistinguisherwithmoreroundsandlesscellstobeguessedneedtobebuilt.Sointhispaper,wefocusonthedistinguisher.

SincethesizeofTislessthan2nK×b,forthewrongkeyguess,theproperparameterscanguaranteetheS-multisetwegetintheonlinephasenottobeoneofT.

3

Wereferto[8]thenumberofcellsnSweneedtostoreanS-multiset.