8_StreamCiphers

StreamCiphers1StreamCiphersStreamCiphers2StreamCiphersGeneralizationofone-timepadTradeprovablesecurityforpracticalityStreamcipherisinitializedwithshortkeyKeyis“stretched”intolongkeystreamKeystreamisusedlikeaone-timepadoXORtoencryptordecryptStreamcipherisakeystreamgeneratorUsually,keystreamisbits,sometimesbytesStreamCiphers3StreamCipherGenericviewofstreamcipherStreamCiphers4ShiftRegistersTraditionally,streamcipherswerebasedonshiftregistersoToday,awidervarietyofdesignsShiftregisterincludesoAseriesofstageseachholdingonebitoAfeedbackfunctionAlinearfeedbackshiftregister(LFSR)hasalinearfeedbackfunctionStreamCiphers5Example(nonlinear)feedbackfunctionf(xi,xi+1,xi+2)=1xixi+2xi+1xi+2Example(nonlinear)shiftregisterFirst3bitsareinitialfill:(x0,x1,x2)ShiftRegisterStreamCiphers6LFSRExampleofLFSRThenxi+5=xixi+2foralliIfinitialfillis(x0,x1,x2,x3,x4)=01110then(x0,x1,…,x15,…)=0111010100001001…StreamCiphers7LFSRForLFSRWehavexi+5=xixi+2foralliLinearfeedbackfunctionsoftenwritteninpolynomialform:1+x3+x5ConnectionpolynomialoftheLFSRStreamCiphers8Berlekamp-MasseyAlgorithmGiven(partof)a(periodic)sequence,canfindshortestLFSRthatcouldgeneratethesequenceBerlekamp-MasseyalgorithmoOrderN2,whereNislengthofLFSRoIterativealgorithmoOnly2NconsecutivebitsrequiredStreamCiphers9Berlekamp-MasseyAlgorithmBinarysequence:s=(s0,s1,s2,…,sn-1)LinearcomplexityofsisthelengthofshortestLFSRthatcangeneratesLetLbelinearcomplexityofsThenconnectionpolynomialofsisofformC(x)=c0+c1x+c2x2+…+cLxLBerlekamp-MasseyfindsLandC(x)oAlgorithmonnextslide(wheredisknownasthediscrepancy)StreamCiphers10Berlekamp-MasseyAlgorithmStreamCiphers11Berlekamp-MasseyAlgorithmExample:StreamCiphers12Berlekamp-MasseyAlgorithmBerlekamp-MasseyisefficientwaytodetermineminimalLFSRforsequenceWithknownplaintext,keystreambitsofstreamcipherareexposedWithenoughkeystreambits,canuseBerlekamp-Masseytofindentirekeystreamo2Lbitsisenough,whereLislinearcomplexityofthekeystreamKeystreammusthavelargelinearcomplexityStreamCiphers13CryptographicallyStrongSequencesAsequenceiscryptographicallystrongifitisa“good”keystreamo“Good”relativetosomespecifiedcriteriaCryptostrongsequencemustbeunpredictableoKnownplaintextexposespartofkeystreamoTrudymustnotbeabletodeterminemoreofthekeystreamfromashortsegmentSmalllinearcomplexityimpliespredictableoDuetoBerlekamp-MasseyalgorithmStreamCiphers14CryptoStrongSequencesNecessaryforacryptographicallystrongkeystreamtohaveahighlinearcomplexityButnotsufficient!Why?Considers=(s0,s1,…,sn-1)=00…01ThenshaslinearcomplexitynoSmallestshiftregisterforsrequiresnstagesoLargestpossibleforsequenceofperiodnoButsisnotcryptographicallystrongLinearcomplexity“concentrated”inlastbitStreamCiphers15LinearComplexityProfileLinearcomplexityprofileisabettermeasureofcryptographicstrengthPlotlinearcomplexityasfunctionofbitsprocessedinBerlekamp-MasseyalgorithmoShouldfollown/2line“closelybutirregularly”Plotofsequences=(s0,s1,…,sn-1)=00…01wouldbe0untillastbit,thenjumpstonoDoesnotfollown/2line“closelybutirregularly”oNotastrongsequence(bythisdefinition)StreamCiphers16LinearComplexityProfileA“good”linearcomplexityprofileStreamCiphers17k-errorLinearComplexityProfileAlternativewaytomeasurecryptographicallystrongsequencesConsideragains=(s0,s1,…,sn-1)=00…01Thisshasmaxlinearcomplexity,butitisonly1bitawayfromhavingminlinearcomplexityk-errorlinearcomplexityismincomplexityofanysequencethatis“distance”kfroms1-errorlinearcomplexityofs=00…01is0oLinearcomplexityofthissequenceis“unstable”StreamCiphers18k-errorLinearComplexityProfilek-errorlinearcomplexityprofileok-errorlinearcomplexityasfunctionofkExample:oNotastrongsoGoodprofileshouldfollowdiagonal“closely”StreamCiphers19CryptoStrongSequencesLinearcomplexitymustbe“large”Linearcomplexityprofilemustn/2line“closelybutirregularly”k-errorlinearcomplexityprofilemustfollowdiagonalline“closely”Allofthisisnecessarybutnotsufficientforcryptostrength!StreamCiphers20ShiftRegister-BasedStreamCiphersTwoapproachestoLFSR-basedstreamciphersoOneLFSRwithnonlinearcombiningfunctionoMultipleLFSRscombinedvianonlinearfuncIneithercaseoKeyisinitialfillofLFSRsoKeystreamisoutputofnonlinearcombiningfunctionStreamCiphers21ShiftRegister-BasedStreamCiphersLFSR-basedstreamciphero1LFSRwithnonlinearfunctionf(x0,x1,…,xn-1)Keystream:k0,k1,k2,…StreamCiphers22ShiftRegister-BasedStreamCiphersLFSR-basedstreamcipheroMultipleLFSRswithnonlinearfunctionKeystream:k0,k1,k2,…StreamCiphers23ShiftRegister-BasedStreamCiphersSingleLFSRexampleisspecialcaseofmultipleLFSRexampleToconvertsingleLFSRcasetomultipleoLetLFSR0,…LFSRn-1besameasLFSRoInitialfillofLFSR0isinitialfillofLFSRoInitialfillofLFSR1isinitialfillofLFSRsteppedonceoAndsoon…StreamCiphers24CorrelationAttackTrudyobtainssomesegmentofkeystreamfromLFSRstreamcipheroOfthetypeconsideredonpreviousslidesCanassumestreamcipheristhemultipleshiftregistercaseoIfnot,convertittothiscaseByKerckhoffsPrinciple,weassumeshiftregistersandcombiningfunctionknownOnlyunknownisthekeyoThekeyconsistsofLFSRinitialfillsStreamCipher