发布时间 : 星期日 文章General Model of the SingleKey Meet-in-the-Middle Distinguisher on the Word-Oriented Block Cipher更新完毕开始阅读7836c2348bd63186bdebbce0
GeneralModeloftheSingle-KeyMeet-in-the-MiddleDistinguisher211
3.4TheDistinguisherUsingE?cientTabulation
At[8],Derbezetal.proposedthee?cienttabulationtoreducethememorycomplexityandmadethiskindofattackagainst7-roundAES-128possible.Thenewcomponentofthedistinguisherusingthistechniqueisaspecialtruncateddi?erentialtrail.Withapairofmessagessatisfyingthistrail,wecanreducethememorycomplexityofthedistinguisher.WecallthispairtheT-Srightpair.However,thistechniquedoesn’tworkforalltheSPNblockciphersbecauseitusesthedi?erential-propertyofS.AEShasaspecial4-roundtruncateddi?erentialtrail1→4→16←4←1,sothetwostatesonthebothsidesofthenonlinear-permutationinthethirdroundareallactivewiththeprobabilityequalsto1.However,sincethebranchnumberofthemixcolumnoperation[5]isn’tthemaximum(suchasCryptonandmCrypton),therearemorethan1activecellsbeforethemixcolumnoperation(suchasthe5-roundAESdistin-guisher[8])andsoon,thestatesonthebothsidesofthenon-linearpermutationmayhaveinactivecells.Ifithappens,theinactivecellscantakeallthe2bvaluesratherthan1.Thiswillincreasethememorycomplexity.
Thealgorithmofthedistinguisherusinge?cienttabulationisshowninAppendixA.4.Anexampleofdistinguisherusingthee?cienttabulationandthecomputationprocessofmemorycomplexityconsideringthelimitationareshowninSect.4.3andAppendixA,respectively.Wealsoshowsomeviewpointsonthe4-roundAESdistinguisherstartingfroma2-δ-setandthe5-rounddis-tinguisher[8]inAppendixA.3.
4DistinguishersandAttacksonCryptonandmCrtpton
Inthissection,wedescribeourbasicdistinguishersandthedistinguishersusingthee?cienttabulationonCrypton6[12,13]andmCrypton[14].InSects.4.1and4.2,weintroducethebasicdistinguishersonCryptonandmCrypton.Section4.3givesthedistinguishersonCryptonandmCryptonusingthee?cienttabulation.Thenweintroducetheattackson7-roundCrypton-128andmCrypton-96inAppendixB.
Inthissection,weusethenotationasfollows:x[i]denotethei-thbyte/nibbleofaninternalstate,andx[i,...,j]forbytes/nibblesbetweeni-thandj-th.Inthei-thround,wedenotetheinternalstateafterthekey-additionlayerbyxi,afterthenonlinear-permutationbyyi,afterthebitpermutationbyzi,afterthecolumn-to-rowbywi.4.1
BasicDistinguisheronCrypton
Thefollowingpropositiongivesa4-rounddistinguisheronCrypton.
6
BothV0.5andV1.0sincewedon’tusethepropertyofthekey-schedule.
212L.Linetal.
1
Proposition2.Considertheencryptionofa(1?)δ-set(ofbyte){x0i,xi,...,x255i}throughfourfullCryptonrounds.Foreach(1-)multiset
??0??100255x4[0]⊕x0[0],x[0]⊕x[0],...,x[0]⊕x[0]44444
isfullydeterminedbythefollowing24bytes:
00x0i+1[0,4,8,12],xi+2[0,...,15],xi+3[0,...,3.]
TheproofprocedureisshowninFig.2andthesameastheprocedureof
Sect.3.1.The?rstandsecondroundsaretheformerpart,thethirdroundisthemiddlepartandthelastroundisthelatterpart.
Sincethemultisetsofxi+4[0]aretotallydeterminedby24bytes,itcantakeasmanyas224×8=2192values(outofthe2507.6“theoreticallypossible”values).Asaresult,wetreatthecipherwithwrongkeyguessasarandomfunction,theprobabilitythatarandomvalueisonememberofthe“rightset”is2192?507.6=2?315.6.Itisalmostimpossible.
Fig.2.The4-roundsdistinguisherofCryptonandmCrypton
4.2BasicDistinguisheronmCrypton
SincemCryptonisalightweightblockcipher,thedistinguisheronmCryptonisalittledi?erentfromCrypton.mCryptonusesthe2-δ-settobuildthedistin-guisherandgetsa2-muliset.Thefollowingpropositiongivesa4-rounddistin-guisheronmCrypton.
GeneralModeloftheSingle-KeyMeet-in-the-MiddleDistinguisher213
1255
Proposition3.Considertheencryptionofa2-δ-set{x0i[0,1],xi[0,1],...,xi[0,1]}throughfourfullmCryptonrounds.Foreach2-multiset
??0??100255x4[0,4]⊕x0[0,4],x[0,4]⊕x[0,4],...,x[0,4]⊕x[0,4]44444
isfullydeterminedbythefollowing24nibbles:
00
x0i+1[0,4,8,12],xi+2[0,...,15],xi+3[0,...,3].
TheproofprocedureisshowninFig.2.4.3
DistinguishersonCryptonandmCryptonUsingE?cient
Tabulation
Ifthereexistsa(1-1)rightpairamongtheδ-setofCryptonanda(2-2)rightpairamongthe2-δ-setofmCrypton,wecanreducetherequirementformemory.Proposition4((1-1)rightpairpropertyofCrypton).Ifastatex0ibelongstoarightpairofstatesconformingtothetruncateddi?erentialtrail,thenthemultisetsofΔxi+4[0]obtainsfromtheδ-setconstructedfromx0iasthestandard
89
statecantakeonly2values.Moreprecisely,the24bytesparameterscantakeonly289valuesanddeterminedby10bytes.The10bytesare:
0
Δyi[0],x0i+1[0,4,8,12],Δzi+3[0],yi+3[0,...,3].
TheproofisshowninFig.3andthesameasthemethodinAppendixA.4.Proposition5((2-2)rightpairpropertyofmCrypton).Ifastatex0i
belongstoa(2-2)rightpairofstatesconformingtothetruncateddi?erentialtrail,thenthe2-multisetsofΔxi+4[0,1]obtainsfromthe2-δ-setconstructed
49.44
values.Moreprecisely,the24fromx0iasthestandardstatecantakeonly2
49.44
valuesanddeterminedby12nibbles.The12nibbleparameterstakeonly2
nibblesare:
0
Δyi[0,1],x0i+1[0,4,8,12],Δzi+3[0,1],yi+3[0,...,3].
TheproofprocedureisthesameasthatofCryptonandshowninFig.3.The
numberofpossiblemultisetsis249.44.Thewaytocalculatetheexactnumberof2-multisetsisshowninAppendixA.2.4.4
BasicAttackonCryptonandmCryptonUsingE?cientTabulation
UsingthedistinguisherofSect.4.3,theattackson7-roundCrypton-128andmCrypton-96canbebuilt.ForCrypton,ittakesatimecomplexityof2113,adatacomplexityof2113chosenplaintextsandamemorycomplexityof291.FormCrypton,ittakesatimecomplexityof277,adatacomplexityof249chosen-plaintextsandamemorycomplexityof252.44.
Theattacksaremadeupof2phase:theprecomputationphaseandtheonlinephase.Theonlinephaseisalsomadeupofthreeparts:?ndingtherightpair,creatingandcheckingtheδ-setand?ndingthesecretkey.ThedetailoftheseattacksisshowninAppendixB.
214L.Linetal.
5BasicDistinguisheronLBlock
Wegivea9-rounddistinguisheronLBlock[16]of14guessed-nibblesinFig.4.Wechoosetheactivenibblesatpositions8and9ofR0asthe2-δ-set,andtheactivenibblesatpositions8and9ofR9tobuildthe2-multiset.Theguessed-nibbles(a,b)ofroundiaremarkedbyLi(a,b).
6ConclusionandFurtherWorks
Inthispaper,weproposedthebasicsingle-keymeet-in-the-middledistinguishermodelontheword-orientedblockcipherandshowedthatbuildingabetterdistinguisherisequivalenttoapositiveintegeroptimizationproblem.Thenwegaveaproperalgorithmtosolvethisproblem.Furthermore,weanalyzedthelimitationofthedistinguisherusingthee?cienttabulationandthemethodtosearchthespecialdi?erentialtrailneededinthisdistinguisher.What’smore,weappliedthedistinguishermodeltoCrypton,mCryptonandLBlock.Wegave4-roundbasicdistinguishersonCryptonandmCrypton.Afterthatwegavethedistinguisherswiththee?cienttabulationandusedthesedistinguisherstobuildtheattackson7-roundCrypton-128andmCrypton-96.ForCrypton,theattackcostatimecomplexityof2113,adatacomplexityof2113chosenplaintextandamemorycomplexityof291.FormCrypton,itcostatimecomplexityof277,adatacomplexityof249chosen-plaintextsandamemorycomplexityof252.44.ForLBlock,wegavea9-rounddistinguisherof14guessed-cells.
Theresearchcommunityhasstillalottolearnonthewaytobuildbetterdistinguishersandtherearemanyfutureworkspossible:themodeltobuildbetterdistinguishersofthiskindwithmoreroundsandlessguessed-cells,howtoapplythee?cienttabulationtotheFeistel-SPcipherandgiveaformalproofofsecurityagainstthiskindofdistinguishers.
Acknowledgements.Wewouldliketothanktheanonymousreviewersforprovidingvaluablecomments.TheresearchpresentedinthispaperissupportedbytheNationalBasicResearchProgramofChina(No.2013CB338002)andNationalNaturalScienceFoundationofChina(No.61272476,No.61232009andNo.61202420).
A
A.1
TheNumberofδ-Sets
TheNumberofδ-SetsforCrypton
ForCrypton,sincethebranchnumberofthebitpermutationis4,inFig.3,the?rstcolumnofzimaynotbeallactive.Ifthereisoneinactivebyte,theresultisthatonecolumnofzi+1isinactive.Evenifthej-thbyteofthe?rstcolumnisactive,thej-thcolumnofzi+1mayhaveoneinactivebyte,andviceversa.However,thei-thbyteofxi+2andyi+2mustbebothactiveorinactive.
Ifonebyteatthesamepositionofxi+2andyi+2isinactive,thenthatpositioncantakeallthe256valuesoutoftheaverage256255values[8].