8_StreamCiphers

1、Stream Ciphers 1Stream CiphersStream Ciphers 2Stream CiphersGeneralization of one-time padTrade provable security for practicalityStream cipher is initialized with short key Key is “stretched into long keystreamKeystream is used like a one-time padXOR to encrypt or decryptStream cipher is a keystrea

2、m generatorUsually, keystream is bits, sometimes bytesStream Ciphers 3Stream CipherGeneric view of stream cipherStream Ciphers 4Shift RegistersTraditionally, stream ciphers were based on shift registersToday, a wider variety of designsShift register includesA series of stages each holding one bitA f

3、eedback functionA linear feedback shift register (LFSR) has a linear feedback functionStream Ciphers 5Example (nonlinear) feedback functionf(xi, xi+1, xi+2) = 1 xi xi+2 xi+1xi+2Example (nonlinear) shift registerFirst 3 bits are initial fill: (x0, x1, x2) Shift RegisterStream Ciphers 6LFSRExample of

4、LFSRThen xi+5 = xi xi+2 for all iIf initial fill is (x0,x1,x2,x3,x4) = 01110then (x0,x1,x15,) = 01001Stream Ciphers 7LFSRFor LFSRWe have xi+5 = xi xi+2 for all iLinear feedback functions often written in polynomial form: 1+ x3 + x5Connection polynomial of the LFSRStream Ciphers 8Berlekamp-Massey Alg

5、orithmGiven (part of) a (periodic) sequence, can find shortest LFSR that could generate the sequenceBerlekamp-Massey algorithmOrder N2, where N is length of LFSRIterative algorithmOnly 2N consecutive bits requiredStream Ciphers 9Berlekamp-Massey AlgorithmBinary sequence: s = (s0,s1,s2,sn-1)Linear co

6、mplexity of s is the length of shortest LFSR that can generate sLet L be linear complexity of sThen connection polynomial of s is of formC(x) = c0 + c1x + c2x2 + + cLxLBerlekamp-Massey finds L and C(x)Algorithm on next slide (where d is known as the discrepancy)Stream Ciphers 10Berlekamp-Massey Algo

7、rithmStream Ciphers 11Berlekamp-Massey AlgorithmExample:Stream Ciphers 12Berlekamp-Massey AlgorithmBerlekamp-Massey is efficient way to determine minimal LFSR for sequenceWith known plaintext, keystream bits of stream cipher are exposedWith enough keystream bits, can use Berlekamp-Massey to find ent

8、ire keystream2L bits is enough, where L is linear complexity of the keystreamKeystream must have large linear complexityStream Ciphers 13Cryptographically Strong SequencesA sequence is cryptographically strong if it is a “good keystream“Good relative to some specified criteriaCrypto strong sequence

9、must be unpredictableKnown plaintext exposes part of keystreamTrudy must not be able to determine more of the keystream from a short segmentSmall linear complexity implies predictableDue to Berlekamp-Massey algorithmStream Ciphers 14Crypto Strong SequencesNecessary for a cryptographically strong key

10、stream to have a high linear complexityBut not sufficient!Why? Consider s = (s0,s1,sn-1) = 0001Then s has linear complexity nSmallest shift register for s requires n stagesLargest possible for sequence of period n But s is not cryptographically strongLinear complexity “concentrated in last bitStream

11、 Ciphers 15Linear Complexity ProfileLinear complexity profile is a better measure of cryptographic strengthPlot linear complexity as function of bits processed in Berlekamp-Massey algorithmShould follow n/2 line “closely but irregularlyPlot of sequence s = (s0,s1,sn-1) = 0001 would be 0 until last b

12、it, then jumps to nDoes not follow n/2 line “closely but irregularlyNot a strong sequence (by this definition)Stream Ciphers 16Linear Complexity ProfileA “good linear complexity profileStream Ciphers 17k-error Linear Complexity ProfileAlternative way to measure cryptographically strong sequencesCons

13、ider again s = (s0,s1,sn-1) = 0001 This s has max linear complexity, but it is only 1 bit away from having min linear complexity k-error linear complexity is min complexity of any sequence that is “distance k from s1-error linear complexity of s = 0001 is 0Linear complexity of this sequence is “unst

14、ableStream Ciphers 18k-error Linear Complexity Profilek-error linear complexity profilek-error linear complexity as function of kExample:Not a strong sGood pro follow diagonal “closelyStream Ciphers 19Crypto Strong SequencesLinear complexity must be “largeLinear complexity pro n/2 line “closely but

15、irregularlyk-error linear complexity pro follow diagonal line “closely All of this is necessary but not sufficient for crypto strength!Stream Ciphers 20Shift Register-Based Stream CiphersTwo approaches to LFSR-based stream ciphersOne LFSR with nonlinear combining functionMultiple LFSRs combined via

16、nonlinear funcIn either caseKey is initial fill of LFSRsKeystream is output of nonlinear combining functionStream Ciphers 21Shift Register-Based Stream CiphersLFSR-based stream cipher1 LFSR with nonlinear function f(x0,x1,xn-1)Keystream: k0,k1,k2,Stream Ciphers 22Shift Register-Based Stream CiphersL

17、FSR-based stream cipherMultiple LFSRs with nonlinear functionKeystream: k0,k1,k2,Stream Ciphers 23Shift Register-Based Stream CiphersSingle LFSR example is special case of multiple LFSR exampleTo convert single LFSR case to multipleLet LFSR0,LFSRn-1 be same as LFSRInitial fill of LFSR0 is initial fi

18、ll of LFSRInitial fill of LFSR1 is initial fill of LFSR stepped onceAnd so onStream Ciphers 24Correlation AttackTrudy obtains some segment of keystream from LFSR stream cipherOf the type considered on previous slidesCan assume stream cipher is the multiple shift register caseIf not, convert it to th

19、is caseBy Kerckhoffs Principle, we assume shift registers and combining function knownOnly unknown is the keyThe key consists of LFSR initial fillsStream Ciphers 25Correlation AttackTrudy wants to recover LFSR initial fillsShe knows all connection polynomials and nonlinear combining functionShe also

20、 knows N keystream bits, k0,k1,kN-1Sometimes possible to determine initial fills of the LFSRs independentlyBy correlating each LFSR output to keystreamA classic divide and conquer attackStream Ciphers 26Correlation AttackFor example, suppose keystream generator is of the form:And f(x,y,z) = xy yz zN

21、ote that key is 12 bits, initial fillsStream Ciphers 27Correlation AttackFor stream cipher on previous slideSuppose initial fills areX = 011, Y = 0101, Z = 11100 xi011100101110010111001011yi010110010001111010110010zi111000110111010100001001ki111100100110010110001011bits i = 0,1,2,23Stream Ciphers 28

22、Correlation AttackConsider truth table for combining function: f(x,y,z) = xy yz zEasy to show thatf(x,y,z) = x with probability 3/4f(x,y,z) = z with probability 3/4Trudy can use this to recover initial fills from known keystreamStream Ciphers 29Correlation AttackTrudy sees keystream in tableTrudy wa

23、nts to find initial fillsShe guesses X = 111, generates first 24 bits of putative X, compares to kiki111100100110010110001011xi111001011100101110010111Trudy finds 12 out of 24 matchesAs expected in random caseStream Ciphers 30Correlation AttackNow suppose Trudy guesses correct fill, X = 011First 24

24、bits of X (and keystream)ki111100100110010110001011xi011100101110010111001011Trudy finds 21 out of 24 matchesExpect 3/4 matches in causal caseTrudy has found initial fill of XStream Ciphers 31Correlation AttackHow much work is this attack?The X,Y,Z fills are 3,4,5 bits, respectivelyWe need to try ab

25、out half of the initial fills before we find XThen we try about half of the fills for YThen about half of Z fillsWork is 22 + 23 + 24 25Exhaustive key search work is 211Stream Ciphers 32Correlation AttackWork factor in generalSuppose n LFSRsOf lengths N0,N1,Nn-1Correlation attack work isWork for exh

26、austive key search isStream Ciphers 33ConclusionsKeystreams must be cryptographically strongCrucial property: unpredictableLots of theory available for LFSRsBerlekamp-Massey algorithmNice mathematical theory existsLFSRs can be used to make stream ciphersLFSR-based stream ciphers must be correlation

27、immuneDepends on properties of function fRecent ProgressEarly days: LFRS based stream ciphers2000 NESSIE2004 eSTREAMStream Ciphers 34NESSIE Stream Cipher SubmissionsNone recommendedBMGL too slow, small internal state time/memory tradeoff attackLeviathan - distinguishing attackLILI-128 attack O(271)S

28、NOW distinguishing attackSOBER-t16 distinguishing attackSOBER-t32 distinguishing attackBoth Sober algorithms thought to be subject to side channel analysisECRYPTs eStream Contest3rd round of evaluations finished, winners selected4 for software, 4 for hardwareIn third round of evaluations 16 candidat

29、es3+ years from time of call for proposals to final reportoriginally November 2004 to January 2008Just endedECRYPT: European Network of Excellence for Cryptology eStream OverviewCategorieskey length of 128 bits and an IV length of 64 and/or 128 bitskey length of 80 bits and an IV length of 32 and/or

30、 64 bitsSeparate software and hardware categories within eachEvaluationSecurityFree of licensing requirements Performance, range of environmentsCommittee is only collecting submissions. Evaluations are done by the general cryptographic community.eStream EvaluationSecurity CriteriaAny key-recovery attack should be at least as difficu