SECURITYANDCOMMUNICATIONNETWORKSComm.Networks2016;9:4285–4294Publishedonline7September2016inWileyOnlineLibrary().DOI:10.1002/sec.1606RESEARCHARTICLEAlgebraictechniquesonsearchinglineardiffusionlayersinblockcipherABSTRACTplaysanefficaciousroleinprovidingresistanceagainstthemostwell-knownattacksonblockciphers,suchasdifferentialcryptanalysisandlinearcryptanalysis.Inthispaper,weproposealgebraictechniquesinsearchingpermutationswithmaximalbranchnumber,whichcanbeemployedasthelineardiffusionlayersinblockciphers.Wefocusonpermutationscomposedofsimpleoperationssuchasword-levelXORsandrotations.Somenecessaryconditionsareproposedtofilteroutlinearpermutationsthatcannotachievethemaximalbranchnumber.Withtheseconditions,thesearchingprocessofmaximumpermutationon32-bitwordcanbefinishedin1s,contrasttotheprevioussearchingmethodwhichspentseveraldaysontwocomputers.Whatisthemostimportantisthatitcanbegeneralizedto64-bitwordandshowthatthereisno8-bytewordpermutation,whichisXORof9right-rotationsor11right-rotationswithmaximumbranchnumber.Copyright?2016JohnWiley&Sons,Ltd.KEYWORDSdiffusionlayer;branchnumber;maximalpermutation*CorrespondenceWenyingZhang,No.88EastWenhuaRoad,SchoolofInformationScienceandEngineering,ShandongNormalUniversity,Jinan250014,Shandong,China.E-mail:\hweny\hingzh@INTRODUCTIONBlockciphersareimportantelementarycomponentsinthedesignofmanysymmetriccryptographicschemessuchasencryptionalgorithms,hashfunctions,authenticationschemesandpseudo-randomnumbergenerators[1]andimplementencryptioninbulkdatatrans-mission.Modernblockciphersarecascadesofseveralroundswhereeachroundconsistsofconfusionanddif-fusionlayers[2,3];theconfusionlayerisoftenexploitedasaparallelapplicationofnon-linearsubstitutionboxes(S-boxes)[4,5],whilethediffusionlayerisbuiltfromalineartransformation.Thediffusionlayerisacrypto-permutation;itplaysanimportantroleinprovidingresistanceagainstthemostwell-knownattacksonblockcipherssuchasdifferentialcryptanalysisandlinearcryptanalysis.Theblockciphertakesablockoftheplaintextandthekeyasinputsandadoptsseveralalternatingroundscon-sistingofasubstitutionstagefollowedbyapermutationstagetoproduceeachblockofciphertextoutput.Thenon-mixesthekeybitswiththoseoftheplaintext,creatingShannon’sconfusion[6];itiscomposed

ofS-boxesworkinginparallelonsmallchunksofthestate.Thissubstitutionmustbeone-to-one,toensureinvertibil-ity(hencedecryption).AsecureS-boxhasthepropertythatchangingoneinputbitwillchangeabouthalfoftheoutputbitsonaverage,thatisknownasthestrictavalanchecriterion;thatis,ithasthepropertythateachoutputbitwilldependoneveryinputbit.Thediffusionlayerthendissipatesredundancies,creatingdiffusion.Adiffusionlayerisapermutationofalltheinputbitsofroundfunction:ittakestheoutputsofalltheS-boxesofoneround,permutesthebitsandfeedsthemintotheS-boxesofthenextround.AgooddiffusionlayerhasthepropertythattheoutputbitsofanyS-boxaredistributedtoasmanyS-boxinputsaspossible[7].Diffusionlayercorrespondstoaninvertiblematrixonfinitefield.Inthispaper,wefocusonthepropertiesandtheevaluationsofdiffusionlayer.Thebranchnumberofadiffusionlayerisdefinedastheminimumvalueofthesumofthenumberofthenonzerobytesofinputandoutput[8].Ahighbranchnumberimpliesthatchangingasinglebyteoftheinputwillchangetheoutputalot,whichisexactlywhatoneexpectsforagooddiffusionlayer[9].Copyright?2016JohnWiley&Sons,Ltd. 4285W.W.ZhangandW.ZhangAlgebraictechniquesonsearchinglineardiffusionlayersPAGE4287PAGE4287SecurityComm.Networks2016;9:4285–4294?2016JohnWiley&Sons,Ltd.DOI:10.1002/secW.W.ZhangandW.ZhangAlgebraictechniquesonsearchinglineardiffusionlayersPAGE4286PAGE4286SecurityComm.Networks2016;9:4285–4294?2016JohnWiley&Sons,Ltd.Thegoalofadesigneristomaximizebranchnumber,diffusingthenon-linearpropertiesoftheS-boxesfastertothesubsequentroundsofthecipher.Thefasterthisnon-linearityspreads,thefewerofroundsthecipherrequirestobecomesecureagainstlinearanddifferentialattacks.Thelargerthebranchnumberis,themoreplaintextsareneededinthecryptanalysis,andthehigherthedatacomplexityusedintheattackis,themoresecurethecryptosystemwillbe.Therefore,inthedesigningstrategyofacryptosystem,adoptinglineartransformationwiththemaximalbranchnumberisanessentialcriterion.¤Ithasbeenshownthatthemaximalbranchnumberofalineartransformationofkwordsisk+1,anddiffu-sionlayerswithmaximalbranchnumbercanbeachievedbyusingMaximumDistanceSeparable(MDS)matri-ces[10,11].However,MDSmatricescannotbesparseandusuallyhavealargedescription,inducingcostlysoft-ware/hardwareimplementations[12,13].So,constructingdiffusionlayerswithhighlyefficientimplementationsisachallengefordesigners.Andconstructingmaximalpermu-tationwithasfewoperationsaspossibleisimperative[14].Technically,amaximalpermutationisatransformationthatdoesnotmaketwodifferent2n-tuplesoftheforminnormorebytes.Thatis,ifxy,then(x,f(x))and(y,f(y))coincideinupton–1bytes.¤x2TheRelatedWork.Theconstructionofpermutationwithgivenbranchnumberhasattractedmuchattentionfromcryptanalyticdesigner.In[15],theauthorsinvesti-gatetherequirementsofthelinearfunctionstoachievethemaximalbranchnumberfortheproposed44wordsdif-fusionlayer.Theauthorsof[16]givetheexhaustivesearchformaximumpermutationwithfiveleft-rotationsandfourXORsonZ32andsuggestthatthefunctionemployedinSM4isuniqueintermsofequivalence.In[17],BonWookKoo,HwanSeokJangandJungHwanSongconstructax2xx1616involutionbinarymatrixofbranchnumber8andestimatethesecurityofa128-bitSPNblockcipherwhichusesthematrixasadiffusionlayerinaroundfunction.Theyalsodescribehowtoconstructa3232binarymatrixofbranchnumber10,whichisaimedatenhancingthesecurityofAES-256likeblockcipherin[18].In[19],Cuiconstructsakindofinvertiblebinarymatriceswithsize8andlargestbranchnumberandproposesakindofmatriceswithequaldifferentialbranchnumberandlinearbranchnumber.Somepropertiesofaclassoflineartrans-formationsbasedoncyclic-shiftandXORoperationsarepresentedin[20].xxOurContributions.Inthispaper,weconsiderthesearchingmethodofpermutationswithmaximalbranchnumber.Thesearchingmethodtransfersthecalculationofaseriesofdeterminantsintothemagnitudecomparisonsofri,i=1,2,3,4,5.Weproposeaveryefficientnewmethodtofiltercandidatelinearper-mutationsthatcannotachievethemaximalbranchnumber,whichisbasedonthefundamentalpropertiesofbooleanmatrixes.Wearegoingtoelaborateontheconditionsforalinearpermutationtobemaximalusingthenecessarycon-ditionsforabooleanmatrixtobesingularbycreatingsome

onri,i=1,2,3,4,5.Becauseitisbriefenoughtodiscusstheoperationwithlessvariables,weinvestigatetherequirementsoflinearpermutationsonZ32,whichcon-sistofsimplelinearoperationssuchasshift,rotationandXORandachievethemaximalbranchnumberfirstly.Themostimportantofallisthatwecanextendthesemethodsto88wordsdiffusionlayersandshowthatthereisno2xx88permutationwhichisXORof9right-rotationsor11right-rotationswithmaximumbranchnumber.FortheXORof13right-rotationsbecauseofthelargequantityofcomputing,wehavecarriedoutadealofrandomsearch-whichachievedthemaximumbranchnumber9.Hence,weassumethatthereisnopermutationwhichisXORofright-rotationsandachievesthemaximumbranchnumber9.Webelievetheproposedmethodcouldbearathersimplestrategyforsearchingadiffusionlayerwithmaximalbranchnumberandwillbepracticalandenlighteninginfuturedesignsofcryptographicalgorithms.2xxThesubsequentpartofthispaperisorganizedasfol-lows.InSection2,wedescribethebranchnumbersbysystemoflinearequationsandgivesomenecessarycon-ditionsthatalinearmapwithmaximumbranchnumbershouldsatisfy.InSection3,wegivetheexperimentalresults.InSection4,weshowthenonexistenceofthex88linearmapswhichisXORof9right-rotationsor11right-rotationswithmaximumbranchnumber.Finally,conclusionsaredrawninSection5.xBACKGROUNDANDPRELIMINARIESOriginalintentionofthisresearchAmaximalpermutationwithcertaindiffusionpropertieshaveremarkableapplicationsincryptography.MaximalpermutationswereappliedinmanyblockcipherssuchasSquare,LED,SHARK,AES,TwofishandthestreamcipherMUGIaswellasthecryptographichashfunctionsWhirlpoolandSHA-2.Therearesomestandardapplica-tionsthatemploythesehashfunctionsandblockcipherslikeauthentication,messageintegrity(usinganHMAC(HashedMAC)),messagefingerprinting,datacorruptiondetection,cryptographicprotocols,anddigitalsignatureefficiency[21].In[22],theauthorspresentedanewcipherPRIDEdedicatedfor8-bitmicro-controllersthatofferscompetitiveperformancebecauseoftheirnewtechniquesforfindinglinearlayers.WLANAuthenticationandPrivacyInfrastructureistheChinesenationalstandardforWirelessLocalAreaNetworksproducts,whichiswidelyusedinChineseindustries.SMS4istheblockcipherusedintheWLANAuthenticationandPrivacyInfrastructurestandard.ItwaspublishedbyChinesegovernmentinJanuary2006.Sinceitsintroduction,theSMS4cipherhasattractedmuchatten-tionfromcryptanalyticresearchers[16,23,24],becauseofitssimplicityanditsauthorityinChina.In2012,SMS4wasrenamedasSM4,inaccordancewiththeothertwoChinesenationalstandardsellipticcurvepublickeycryp-tographicalgorithmsSM2andthecryptographichashalgorithmSM3.TheoverallstructureofSM4is32-roundunbalancedFeistelnetwork.TheencryptionprocedureofSM4isdescribedinthefollowing.LetZ2betheGaloisfieldoftwoelements,thatis,Z2=GF(2)={0,1},X0,X1,X2,X3,Y0,Y1,Y2,Y3Z2.DenoteZ2.Denote(X0,X1,X2,X3),(Y0,Y1,Y2,Y3)2Z2as

ˇ(F)=minx¤0{W(x)+W(F(x))}三Itisapparentthatˇ(F)5,becausewhentheinputhasonenonzerobyte,theoutputhasatmostfournonzerobytes.Asarule,thelargerthebranchnumberis,thebetteritsdiffusioneffects.Thefunctionwhoseˇ(F)reachesthemaximum5iscalledtobeofmaximal.Inanotherword,FachievesthemaximalbranchnumberorFhasthemaximal三branchbranchnumbe.orF(x)=(xnr1)?(xnr2)?(xnthe128bitsplaintextPandthe128bitsciphertextC,respectively.TheencryptionprocedureofSM4isasfollows:Xi+4=Xi?L(S(Xi+1?Xi+2?Xi+3?RKi)) (1)22fori=0,1,:::,31.WhereRKi Z32areroundkeys.Thenon-lineartransformationSappliesthesame8x8S-boxfourtimesinparalleltoan32-bitinput,anditisdefinedasfollows:B=(b0,b1,b2,b3)=(Sbox(a0),Sbox(a1),Sbox(a2),Sbox(a3)).22ThediffusiontransformationLisasimplelinearfunc-?? ? tionwhoseinputistheoutputoftransformationS.ItisdefinedasL(B)=B(Bn2)(Bn10)(Bn18)(Bn24).Fordetails,pleasereferto?? ? 2Moresurprisingly,Listheonlyandthemosteffi-cientlineartransformationonZ32withmaximalbranch2number!Thisisthehighlightofthedesign.Themaxi-malbranchnumberenhancesthesecurityofSM4,whichprovidesamaximallowerboundonthenumberofactiveS-boxesthroughoutthediffusionlayerforresistingdiffer-entialandlinearattacks.AnewkeytechnicalproblemoftheSM4designergroup.Recently,inordertoimprovetheencodingeffi-ciencyandbuildanexcellentlightweightsoftwarecipher,theSM4designergrouphasbeentryingtoextendtheblocksizeofSM4from128to256,stillwithitsprimarymodel.22Thatistheplaintextis(X0,X1,X2,X3)(Z64)4,and222theencryptionprocedureisthatinEquation(1).Buttheyencounterwithaproblemonhowtoconstructapermu-tationonZ64withmaximalbranchnumber9,consisting2ofsimplelinearoperationssuchascyclicshiftandXOR,whichisasubstitutionforL.Thisistheoriginalintentionofthisresearch.DefinitionsandnotionsInordertodescribethephenomenonthattheminimumofthenonzerobytesofinputandoutputtobethemaximumoftheroundfunctionintheblockcipher,theconceptofbranchnumberoftransformationwasintroducedasfol-lows.Inthefollowingsections,letx2Z32andy2Z64be

r3),1bitinputdifferenceleadstoatmost3bitsoutput? difference;hence,thebranchnumbercannotreach5.ForanylineartransformationF(x)=(xnr1)(xnr? ?(xnr3)(xnr4),wehaveF32(x)=0;hence,Fisnot?apermutation.Therefore,theleastnumberofleft-rotationsis5andfourXORstoobtainamaximalpermutation.ThebranchnumberofthelinearpermutationadoptedinSM4reachesthemaximum5;wecanverifythisbyalge-braicdeducing.Thisisnotthetopicthemeofthisarticle;wewillignorethat.Themostimportantissueishowcanweobtainallthemaximallineartransformationswith5left-rotationsand4XORs?Becausethereisexactlyonerowbyteincludingtwori,withoutthelossofgenerality,weassumethatthefirstbyteincludesr1,r2,whichresultsfromthefollowingproperty.i=1Poperty1([16]).LetF(x,1,,rk)=?k(xnri).Foreachvalueof(r1,,rk),thebranchnumberofF(x,r1,,rk)n8,F(x,r1,,rk)n16andF(x,r1,,rk)n24areallequaltothebranchnumberofF(x,r1,,rk).i=1Property1indicatesthattheoutputofeachofthethreefunctionsisjustabyte,permutationoftheoutputofF(x,r1,,rk),sothebranchnumberisunchanged.三 三 三 三 三 三 AccordingtoProperty1,we三 三 三 三 三 三 r1<r27,8r315,16r423,24r531.2Thecommonapproachtoconstructmaximalpermuta-tionistodoexhaustivesearchonZ32.Theauthorsof[16]givetheexhaustivesearchformaximumpermutationwith225left-rotationsand4XORsonZ32;theysearchlineartransformationfromallthe14336transformationswhichisoftheformasfollows:2i=1三F(x)=?5(xnri) where0r1<r27,8r315,16r423,24三i=1三r531.Thequantityoftheirsearchingisenormousthatitspentseveraldaysontwocomputers.Inthefollowing,weproposesomealgebraictechniquestoreducethedatacomplexityfrom14336to4.Andtheverificationofthetwoin4whichbranchnumbersarenot5canbefinished2binaryvectors.WedenoteF(x

2Z32

bymanualcomputation.)asalinearfunctionon22andG(y)asalinearfunctiononZ64,222Definition1([16]).Forx Z32,letW(x)bethebyte-weightfunction,thatis,thenumberofnonzerobytes.The22branchnumberofafunctionF:Z32!Z32isdefinedby

TheoverviewofmaximalpermutationToachievethebranchnumber5requiresthatwhentheinputhasonenonzerobyte,eachofthefouroutputbytesishasexactlytwononzerobytes,theasfollows:

2 2outputhasatleastthreenonzerobytes,thatistosaythattheoutputcannothavetwo0bytes.Whentheinputhasthreenonzerobytes,theoutputhasatleasttwononzerobytes,sothattheoutputcannothavethree0bytes.BecauseF(x)isapermutation,whentheinputhasfournonzerobytes,theoutputcannotbe0,thatis,ithasatleastonenonzero

xr2??xr5=0<xr1+1?xr2+1??xr5+1=<r1+7 r+7 r+7? ? : ?x2 r1+7 r+7 r+7? ?

(3)byte.Inthelinearpermutation,onlyall-zerovectorcanbetransformedto0.Thebranchnumberstandsforthebalancebetweeninputbytesandoutputbytes;hence,wedrawacircleasFigure1toshowthepositionsofri,1三i三5andthe

Forinstance,forL1(x)=x(xo4)(xo12)?(xo19)(xo24),theBooleancoefficientmatrixofthelinearsystemofequations(Equation3)indicatesthatthefirstbyteequalsto0is(M1,M2,M3,M4),where?harmonyoftheirdistance.Inordertoachievethemaxi-mum,therisshouldsatisfyseriesofconditions,justlikeeachofthenumbersonthecompass;theyrepresentthefundamentalharmoniousprinciplesofreality.Theyalsoshowthatthearrangementofriisorganizedbasedontheinternalcycles.Inordertodescribetheequationsinthecustommatrix,andforconvenienceofcalculations,westudytheformofright-rotation.Becauseright-rotationisthemirrorinjec-tionofleft-rotation,thiswillnotaffecttherightnessoftheresult.ThefollowingTableIlistseachbitofxori,i=wheretheithrowiscorrespondingtoxori.ofTableIisthejjthbitofF(x,r1, forapermutationwithbranchnumber5,ifthesecondtothefourthbytesof

M1=

100010000 0 B00010001CBB00010001C00000100@ 00000100@ 0 0 00010000B B 00000100M3= ,M3= ,M4B10000001C B00001000C

,M2

000010000 0 B00000001CBB00000001C@ =,@ =,01000000010000000 0 10000000B B 00100000B00010000Ctheinputareallzerosexceptthatthefirstbyteisnonzero,theoutputbytesareallnonzero.Letussupposetothecon-trarythatthefirstbyteoftheoutputis0,wewillobtainthefollowingequations:

01000000@@ 00010000

10000100@@ 00100001followingsections,A,B,C,D,E,F,Grepresentmatrixesoforder8.(4)Equation(3)isaboutthefirstoutputbytetobe0.Ifthesecondbyteis0,weobtainthefollowinglinearsystemofequations:(4):xr1+9?:xr1+9?xr2+9?<x1+8?x2+8??x5+8=r1+15

??xr5+15=0Figure1.Therelationsofridepictedbyacircle.

ThevariablesinEquation(4)areexactlytherightshiftof1byteofthevariablesinEquation(3).Hence,ifthecoefficientofEquation(3)isdenotedbytheblockmatrix(ABCD),thecoefficientofEquation(4)willbetheblockmatrix(DABC).Andthecoefficientmatrixoftheequationforthatthethirdbyteoftheoutputis0istherightshiftof(DABC),thatis,(CDAB).Thecoefficientmatrixoftheequationofthatfourthbyteoftheoutputis0istherightshiftof(BCDA).Let ofeachbitofxori,i=1,,5. r1 xr1 xr1+7 xr1+8 xr1+15 xr1+16 xr1+23 xr1+24 xr1+31r2 xr2 xr2+7 xr2+8 xr2+15 xr2+16 xr2+23 xr2+24 xr2+31r3 xr3 xr3+7 xr3+8 xr3+15 xr3+16 xr3+23 xr3+24 xr3+31r4 xr4 xr4+7 xr4+8 xr4+15 xr4+16 xr4+23 xr4+24 xr4+31r5 xr5 xr5+7 xr5+8 xr5+15 xr5+16 xr5+23 xr5+24 xr5+31B @ ABCB @ M= CDAB (5)BCDA 三thenthecoefficientmatrixfortheequationssystemofs(s4)bytesoftheinputare0and4–sbytesoftheoutputare0isaminoroforder4–sofM.Forexam-ple,whenthefirsttwooutputbytesare0,thecoefficientmatrixfortheequationssystemofthethirdbyteand 三are0isCD.WecallA,B,C,DtheBCsub-matrixofM.LinearpermutationF(x)inEquation(2)withcoefficientmatrixMismaximum,ifandonlyif,everysquaresub-matrixformedfromrowsandcolumnsofMisnonsingular.THENON-MAXIMALAPPROACHESInthissection,wewillgivesomenon-maximalpermu-tationfilteringmethodsbasedontransformingthecal-culationofaseriesofdeterminantsintothemagnitudecomparisonsoftheshiftrotationnumbersri,i=1,,5.Depictionofall-zerorowinasub-matrix三Whenthesecondtothefourthbytesoftheinputareall0,theoutputbecomesthelinearfunctionofthebitsinthefirstbyte.AndthecoefficientmatrixofthesystemlinearequationisequaltoA.Asx=0istheonlysolutiontoAx=0,thedeterminantofAisnot0[26],especiallyAhasnozerorows.Ifthedistanceofthetwoadjacentriisgreaterthan8,therewillbezerorowsinamatrix,andAissingular;hence,thebranchnumberislessthan5.There-fore,thedistanceofr5andr1isnotmorethan8,thatis,r1+32–r58.Ifthesecondbyteisnonzeroandtheotherbytesareallzero,theoutputbecomesthelinearfunctionofthebitsofthesecondbyte.AndthecoefficientmatrixofthecorrespondingsystemoflinearequationisequaltoB三andsoforth.Thereforer3–r2三8,otherwisewhenr3goesoutofthesecondbyte,andr2hasnotreachedthesecond三 byte,andBwouldhavearowwithzeros.Bythesameway,–r38,r5–r48.Then,weobtainasystemofinequalitiesinri,i=1,2,3,4,三 8

describeamatrixwithequaltworowsaccordingtori.Weonlygivethedescriptionthatthesecondrowtotheeighthrowshouldnotequaltothefirstrow.ThefirstrowofBis 001(the(r3–8)th)00.Ifthereisanother beingequaltothefirstrow,thenthe1inthatrowistherightshiftofr2;hence,theamountofzerosnexttotherighthandofr2isnolessthan15–r3,andtheamountofzerosnexttothelefthandofr2whichisr2–r1–1isnolessthanr3–8.Onlyinthecasethatr3–r2<8canr3runintothematrixB.ItisthesameforCandD.Then,we乏 obtainthefollowingconstraintconditionsfordiscardingthecandidateri,i=1,,乏 Ifr3–r2<8andr2–r1–1 r3–8andr3–r2–1 15–r3thendiscard.乏 Ifr4–r3<8andr3–r2–1 r4–16andr4–r3–1 23–r4乏 乏 Ifr5–r4<8andr4–r3–1 r5–24andr5–r4–1 31–r5乏 3.3.Depictionofthreerowswith0XORBythefollowingexample,wewillexplainhowtherisbehaveinthecasethatthesumofthreerowsofamatrixis? ? ? ForthepermutationL2(x)=(x1)(xo6)(xo14)(xo17)(xo25),thecoefficientmatrixfortheequationthatfirstbyteoftheoutputis0? ? ? B E F GB 01000010000000100100000001000000B 0010000100000001B B 000100001000000010010000B 00001000010000000100100000001000@0000001000010000@000000100001000000010010000000100000000100001000000010010000000110000000100001000000010010000000EagleeyesmightnoticethatthesumofthreerowsofGequalsto0.Nowwemakeafurtherinvestigationonthebehaviorsofrithataccountsforthisphenomenon:三Theamountofzerosonthelefthandofr4isnolessthantheelementsbetweenr3andr2,hencer4–r3r3–r2+1,whichcanbeseenfromthesecondcoloredrowandthethirdcoloredrowintheforegoingmatrix.三Theamountofzerosontherighthandofr4isnolessr3r2 r5r4 rr5r4 r132–r58

(6)

thantheelementsbetweenr4andr3,sothatr5–r4三r3–r2+1,whichcanbeseenfromthefirstcoloredrowandthesecondcoloredrow.Theunique1inthefirstcoloredrowisr4,andtheright1inthesecondcoloredrowisr4.Theleft1in3.2.DepictionoftwoequalrowsBecausethedeterminantofeachsubmatrixisnonzero,thereisnotworowsequal.Nowweconsiderhowto

thesecondrowisr3,andtheunique1inthethirdcoloredrowisr3.Becauser3istheonlyelementinthethirdrow,r3andr4willbeinthesamerowwith8components,whichisnottheeighthrowofmatrix.Thedistanceofthetwoislessthan7,thatis,r4–r3<7.Becauser3istheonlyelementinthethirdrow,r4willdisappearwithinsixsteps,r4>16.Inconclusion,weobtainthefollowingconstraintconditions.Ifr3r2+1r2r1Andr4r3r2r11Andr3–r2<7Andr3>8Thendiscard.Ifr4–r31三r3–r2andr5r4三r3r21andr4–r3<7andr4>16thendiscard.Ifr5r4+1r4r3andr132–r5r4r31and

3.5.TherelationshipbetweentworowsinMInthissubsection,wewillshowhowtoexpressthecon-ditionthatanytworowsoftheorder2minorofMshouldnotbeequaltoeachotherinareversiblematrix.Whentwobytesoftheinputare0,anytwobytesoftheoutputcannotbe0simultaneously.Otherwise,thebranchnumberislessthan5.Asfor4(x)=x?(xo4)?(x12)?(xo20)?(xo24),thematrixofthatthefirsttwobytesofL4(x)areequalto0isasfollows:r5–r4<7andr5>24thendiscard.conditionsfordiscardingthecandi-ri,i=1,,5canbeobtainsimilarlyfromthesecond3.4.Threegapsofdistance8Inthissection,weconsiderthefactorsthattriplegroupsofthedistancesofriandri+1are8.ifr3–r2=8,r4–r3=8,r5–r4=8, wewillobtainC=DinEquation(4).Whenthefirstandthesecondbytesoftheinputare0,letthethirdandfourthbyteoftheinputbenonzero.Weconsiderthevalueofthelast16outputbits.Thecoefficientmatrixoftheequation is CC.Addthefirstrowofblockmatrixtothesec- B ondrow,andthenwewillobtain C C.BecauseB+C0 r3–8=r4–16,16–r3=24–r4,theamountof0onthetwosideofr3isequaltothatofr4.Asaresult,thefirstrowofBisequaltothefirstrowofC,andtheninthrowofmatrixCCwillbeazerovector,andthe B+C0onbooleanvariablesx17,tion.tion.Thatis,whentheinputhastwo0bytes,theoutputalsohastwo0bytes;hence,thebranchnumberisatmost4,

A B C DB 0 1000100000001000B 0 01000100000001000000010001000000B 0010001000000010B 0001000100000001000000010001000000001000100000001000000010001000@ 0000010001000000@ 0000001000100000001000000010001000000001000100000001000000010001B D A BB 10000000100010000000100000001000B 010000000100010000000100B 00100000001000100000001000000010B 0001000000010001B 10001000000010001000000010000000@ 0100010000000100@ 0010001000000010001000000010000000010001000000010001000000010000B into eight B into eight DDABC? ? ? thepermutationisnon-maximal.Asanexample,consider=x(xo1)(xo8)(xo16)(xo24),thecoefficientsmatrixoftheequationthatfirst? ? ? outputis0isasthefollowing.Itcanbeseenthatthematrix0)hasmanyzerorows.Hence,weobtainthefollowingconstraintconditions:Ifr3–r2=8andr4–r3=8andr5–r4=8orr4–r3=8,r5–r4=8andr1+32–r5=8thendiscardthesetofri,i=1,2,3,4,5.B A B CB 11000000100000001000000010000000B 011000000100000001000000B 00110000001000000010000000100000B 0001100000010000B 00001100000010000000100000001000@ 0000011000000100@ 0000001100000010000000100000001000000001100000010000000100000001

II0I0II0@ 0II0@ I0II0I0I ,whereIistheidentitymatrixoforder4II0II0I0 and0whichdenotesthematrixzerooforder4. AB hastworowsequal;hence,itissingular.AsaDAresult,theinputwiththelastbyteis0w