发布时间 : 星期日 文章General Model of the SingleKey Meet-in-the-Middle Distinguisher on the Word-Oriented Block Cipher更新完毕开始阅读7836c2348bd63186bdebbce0
GeneralModeloftheSingle-KeyMeet-in-the-MiddleDistinguisher219
3.Thetwopairsonthebothsidesofthenon-linearpermutationmustbeperfectmatch7.Thenbythedi?erentialpropertyofS[8],wecangetonevalueinaveragefortheactivecellsand2bvaluesfortheinactivecells.
4.Takenthelimitationintoaccount,wecanusetheguessed-cellsandtheretrievedvaluestogettheS-multisetsfromtheT-δ-setandcalculatethememorycomplexity.Ifthememorycomplexityisgreaterthanexhaustivesearch,wegiveupthis(ET,DS)pair.ThegoalofthealgorithmistomaximizerE+rDundertheconditionthatthememorycomplexity(consideringtheguessed-cellsandthelimitationofthiskindofdistinguisher)islessthantheexhaustivesearch.Afterthat,wemakethememorycomplexitytobetheleast.Wecantryallthepossiblecombinationof(rE,rD)and(ET,DS)to?ndthebestdistinguisher.
B
BasicAttacksonCryptonandmCryptonUsingE?cientTabulation
Inthissection,wewillshowthebasicattacksonCryptonandmCryptonusingthedistinguishersinSect.4.3.Theattacksaremadeupof2phases:theprecom-putationphaseandtheonlinephase.Theonlinephaseisalsomadeupofthreeparts:?ndingtherightpair,creatingandcheckingδ-setand?ndingsecretkey.B.1
AttacksonCrypton
1.Precomputationphase.Intheprecomputationphaseoftheattack,webuildalookuptablecontaining289multisetsforΔx5[0]followingthemethodofSect.4.3andAppendixA.1.
Thelookuptableofthe289possiblemultisetsusesabout291128-bitblockstostore[8].Toconstructthetable,wehavetoperform289partialencryptionson256messages,whichweestimateto293encryptions.
2.OnlinePhase.TheattackprocedureisshowninFig.5.Theonlinephaseismadeupofthreeparts:?ndingtherightpair,creatingandcheckingtheδ-setand?ndingthesecretkey.(a)FindingtheRightPair:
i.Weprepareastructureof232plaintextswherethe?rstcolumntakesall232values,andtheremaining12bytesare?xedtosomeconstants.Hence,eachofthe232×(232?1)/2≈263pairswecangeneratesatis?estheplaintextdi?erence.Choose281structuresandgetthecorrespondingciphertext.Amongthe263+81=2144correspondingciphertextpairs,weexpect2144×2?96=248toverifythetruncated-di?erencetrailwhereonlythethirdcolumnhasnon-zerodi?erenceasshowninFig.5.Sinceonlythethirdcolumnoftheciphertexthas
7
Thecellsinthesamepositionmustbebothactiveorinactive.Ifnot,wegiveupthis(ET,DS)pair.
220L.Linetal.
PPARKx0y0z0w0x0y0ARKz0w0NSBPPro.C2RNSBPPro.C2RARKx1w4x1ARKw44 Round Distinguisher4 Round DistinguisherARKx5y5z5w5ARKx5y5z5w5NSBPPro.C2RNSBPPro.C2RARKx6y6z6w6ARKx6y6z6w6NSBPC2RNSBPC2RARKx7y7z7CARKx7y7z7CC2RBPC2RC2RBPC2RInactive cells
Active cells from the encrypt direction
Active cells from the decrypt direction
The cells need to be guessed
Fig.5.The7-roundsbasicattackofCryptonandmCrypton
non-zerodi?erence,byObservation2of[15],wehavethatonlythe?rstrowofy6hasnon-zerodi?erence.Storetheleaving248pairsinahashtable.Thissteprequires281+32=2113chosenplaintextsandtheircorrespondingciphertexts.
ii.Guessthevaluesofk?1[0,...,3],usingtheguessedvaluestoencryptthe?rstcolumnoftheremainingpairstoy0.Afterthebitpermu-tationoperation,wechoosethepairsthathavenon-zerodi?erenceonlyinbyteposition0,thereare248?24=248?24pairsleft.
iii.Guessthevaluesofy6[0,4,8,12].Sincewecanyieldthe?rstcolumn
ofΔy6fromthethirdcolumnofΔz7,wecanusetheguessedval-uestoencryptthe?rstrowoftheremainingpairstoz5.Afterthebitpermutationoperation,wechoosethepairsthathavenon-zerodi?erenceonlyinbyteposition0,thereare224?24=1pairsleft.
(b)CreatingandCheckingtheMultiset:
i.ForeachguessoftheeightbytesmadeinPhase(a)andforthecorrespondingpair,takeoneofthemembersofthepair,denoteitbyP0,and?nditsδ-setusingtheknowledgeofk?1[0,...,3].(Thisisdonebyusingtheknowledgeofk?1[0,...,3],wecanencryptP0tow0,thenXORitwiththe28?1possiblevalueswhicharedi?erent
GeneralModeloftheSingle-KeyMeet-in-the-MiddleDistinguisher221
onlyinbyte0.Decryptthe28?1obtainedvaluethroughround0usingtheknownsubkeybytes.Theresultingplaintextsaretheothermembersoftheδ-set.)
ii.UsingP0asthestandardplaintext,theother255plaintextsaredenotedasP1toP255,andthecorrespondingciphertextsasC0toC255.ByObservation2of[15],knowingtheknowledgeofthethirdcolumnin[C0⊕C0,C1⊕C0,...,C255⊕C0],wecanyieldthe
00112550
knowledgeofthethirdrowof[y6⊕y6,y6⊕y6,...,y6⊕y6].Bythe
00
knowledgeofy6[0,4,8,12],wecanyieldthevaluesofy6[0,4,8,12]
255
[0,4,8,12].Bythelinearityofkeyaddition,column-to-rowtoy6
0⊕andbitpermutation,wecanyieldtheknowledgeofbyte0in[y5
01025500
y5,y5⊕y5,...,y5⊕y5].Guessbyte0ofy5[0],wecanobtainthe
0002550
multiset[x05[0]⊕x5[0],x5[1]⊕x5[0],...,x5[0]⊕x5[0]].
iii.Checkingwhetherthemultisetexistsinthehashtablemadeinthe
PrecomputationPhase.Ifnot,discardtheguessing.
(c)ExhaustiveSearchtheRestoftheKey:Foreachremainingkey
guess,?ndtheremainingkeybytesbyexhaustivesearch.Itisclearthattimecomplexityoftheonlinephaseoftheattackisdominatedbyencrypting2113plaintexts,andhence,thedataandtimecomplexityofthispartis2113.Thememorycomplexityisabout291128-bitblocks,sinceeachmultisetcontainsabout512bits.Thetimecomplexityofthepreprocessingphaseoftheattackisapproximately293encryptions.B.2
AttacksofmCrypton
TheattackprocedureofmCryptonisquitethesameasCryptonandshowninFig.5.
Thetimecomplexityoftheonlinephaseis28×232×240=280one-roundmCryptonencryptions,itequals2777-roundmCryptonencryption.Thedatacomplexityoftheonlinephaseis249.Thememorycomplexityoftheprecompu-tationphaseis252.4464-bitblocks,sinceeachmultisetcontainsabout512bits.
CAlgorithms
Algorithm1.Functionofr1-RoundEncryption
1:functionPROPAGATE(Λ,r1)2:StateSetofsizer1,χ←03:(χ??,Λ)←ONEROUND(Λ)4:fori=1tor1?1do5:StateSet[i?1]←Λ6:(χ??,Λ)←ONEROUND(Λ)7:χ←χ+χ??8:return(StateSet,χ)
??The?rstroundwithoutguessinganycells
??Recordingtheguessed-cells??Thetotalnumberofguessed-cells
222L.Linetal.
Algorithm2.FunctionofPruning
1:functionLOCALPRUNING(StateSet[i],Ω,χ)??StateSet[i]isoneelementof
StateSet2:fork=0ton?1do3:if(StateSet[i][k]isactive)and(Ω[k]isinactive)then4:χ←χ?1??StateSet[i][k]doesn’ta?ectΩ5:if(StateSet[i][k]isinactive)andΩ[k]isactivethen6:Ω[k]←inactive??LocalpruningforΩ7:return(Ω,χ)1:functionENDINGCONDITION(StateSet[i],Ω)2:fork=0ton?1do3:if(StateSet[i][k]=Ω[k]then??Oneisactive,theotherisinactive4:returnfalse5:returntrue??Returntruewhentotallymatch1:functionPRUNING(StateSet,Ω,χ,r1)??r1isnumberofroundoftheformerpart
??Startfromthelastroundsoftheformerpart2:fori=r1?2to0do
(1)
??Gobackoneround3:Ω←A(Ω)
??Localpruning4:(Ω,χ)←LOCALPRUNING(StateSet[i],Ω,χ)
5:ifENDINGCONDITION(StateSet[i],Ω)=truethen6:returnχ7:returnχ
Algorithm3.AProperSolutiontoProblem1
1:functionMINROUNDNUMBER()??TheoutputisMax{r1+r2+r3}ofProblem12:RoundNum←03:RoundNum←RoundNum+1??Attackmoreround4:forallT-δ-setΛdo5:(StateSet,χ)←PROPAGATE(χ,RoundNum)6:forallS-MultisetΩdo7:χ←PRUNING(StateSet,Ω,χ,RoundNum)8:ifχ GeneralModeloftheSingle-KeyMeet-in-the-MiddleDistinguisher223 References 1.Bouillaguet,C.,Derbez,P.,Fouque,P.-A.:Automaticsearchofattacksonround-reducedaesandapplications.In:Rogaway,P.(ed.)CRYPTO2011.LNCS,vol.6841,pp.169–187.Springer,Heidelberg(2011) 2.Cheon,J.H.,Kim,M.J.,Kim,K.,Lee,J.-Y.,Kang,S.W.:Improvedimpossibledi?erentialcryptanalysisofrijndaelandcrypton.In:Kim,K.(ed.)ICISC2001.LNCS,vol.2288,pp.39–49.Springer,Heidelberg(2002) 3.Daemen,J.,Knudsen,L.R.,Rijmen,V.:TheblockcipherSquare.In:Biham,E.(ed.)FSE1997.LNCS,vol.1267,pp.149–165.Springer,Heidelberg(1997) 4.Daemen,J.,Rijmen,V.:Aesproposal:Rijndael.In:FirstAdvancedEncryptionStandard(AES)Conference(1998) 5.Daemen,J.,Rijmen,V.:TheDesignofRijndael:AES-theAdvancedEncryptionStandard.Springer,Berlin(2002)6.Demirci,H.,Sel?cuk,A.A.:Ameet-in-the-middleattackon8-roundAES.In:Nyberg,K.(ed.)FSE2008.LNCS,vol.5086,pp.116–126.Springer,Heidelberg(2008) 7.Derbez,P.,Fouque,P.-A.:ExhaustingDemirci-Sel?cukMeet-in-the-MiddleAttacksAgainstReduced-RoundAES.In:Moriai,S.(ed.)FSE2013.LNCS,vol.2013,pp.541–560.Springer,Heidelberg(2013) 8.Derbez,P.,Fouque,P.-A.,Jean,J.:Improvedkeyrecoveryattacksonreduced-roundAESinthesingle-keysetting.In:Johansson,T.,Nguyen,P.Q.(eds.)EURO-CRYPT2013.LNCS,vol.7881,pp.371–387.Springer,Heidelberg(2013) 9.Dunkelman,O.,Keller,N.,Shamir,A.:Improvedsingle-keyattackson8-roundAES-192andAES-256.In:Abe,M.(ed.)ASIACRYPT2010.LNCS,vol.6477,pp.158–176.Springer,Heidelberg(2010) 10.Fouque,P.-A.,Jean,J.,Peyrin,T.:StructuralevaluationofAESandchosen-key distinguisherof9-roundAES-128.In:Canetti,R.,Garay,J.A.(eds.)CRYPTO2013,PartI.LNCS,vol.8042,pp.183–203.Springer,Heidelberg(2013) 11.Gilbert,H.,Minier,M.:ACollisionsSttackonthe7-RoundsRijndael(2000)12.Lim,C.H.:Crypton:ANew128-bitBlockCipher.NIsTAEsProposal(1998)13.Lim,C.H.:ArevisedversionofCRYPTON-CRYPTONV1.0.In:Knudsen,L.R. (ed.)FSE1999.LNCS,vol.1636,p.31.Springer,Heidelberg(1999) 14.Lim,C.H.,Korkishko,T.:mCrypton–alightweightblockcipherforsecurityof low-costRFIDtagsandsensors.In:Song,J.-S.,Kwon,T.,Yung,M.(eds.)WISA2005.LNCS,vol.3786,pp.243–258.Springer,Heidelberg(2006) 15.Mala,H.,Shakiba,M.,Dakhilalian,M.:Newimpossibledi?erentialattackson reduced-roundcrypton.Comput.Stand.Interface32(4),222–227(2010) 16.Wu,W.,Zhang,L.:LBlock:alightweightblockcipher.In:Lopez,J.,Tsudik,G. (eds.)ACNS2011.LNCS,vol.6715,pp.327–344.Springer,Heidelberg(2011)