发布时间 : 星期日 文章General Model of the SingleKey Meet-in-the-Middle Distinguisher on the Word-Oriented Block Cipher更新完毕开始阅读7836c2348bd63186bdebbce0
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.