8_StreamCiphers

Click to edit Master title style,Click to edit Master text styles,Second level,Third level,Fourth level,Fifth level,Stream Ciphers,*,Click to edit Master title style,Click to edit Master text styles,Second level,Third level,Fourth level,Fifth level,*,Stream Ciphers,1,Stream Ciphers,Stream Ciphers,2,Stream Ciphers,Generalization of one-time pad,Trade provable security for practicality,Stream cipher is initialized with short key,Key is“stretched into long keystream,Keystream is used like a one-time pad,XOR to encrypt or decrypt,Stream cipher is a keystream generator,Usually,keystream is bits,sometimes bytes,Stream Ciphers,3,Stream Cipher,Generic view of stream cipher,Stream Ciphers,4,Shift Registers,Traditionally,stream ciphers were based on shift registers,Today,a wider variety of designs,Shift register includes,A series of stages each holding one bit,A feedback function,A linear feedback shift register(,LFSR,)has a linear feedback function,Stream Ciphers,5,Example(nonlinear)feedback function,f(x,i,x,i+1,x,i+2,)=1,x,i,x,i+2,x,i+1,x,i+2,Example(nonlinear)shift register,First 3 bits are,initial fill,:,(x,0,x,1,x,2,),Shift Register,Stream Ciphers,6,LFSR,Example of LFSR,Then,x,i+5,=x,i,x,i+2,for all i,If initial fill is,(x,0,x,1,x,2,x,3,x,4,)=01110,then,(x,0,x,1,x,15,)=01001,Stream Ciphers,7,LFSR,For LFSR,We have,x,i+5,=x,i,x,i+2,for all i,Linear feedback functions often written in polynomial form:,1+x,3,+x,5,Connection polynomial,of the LFSR,Stream Ciphers,8,Berlekamp-Massey Algorithm,Given(part of)a(periodic)sequence,can find shortest LFSR that could generate the sequence,Berlekamp-Massey algorithm,Order,N,2,where,N,is length of LFSR,Iterative algorithm,Only,2N,consecutive bits required,Stream Ciphers,9,Berlekamp-Massey Algorithm,Binary sequence:,s=(s,0,s,1,s,2,s,n-1,),Linear complexity,of,s,is the length of shortest LFSR that can generate,s,Let L be linear complexity of,s,Then connection polynomial of,s,is of form,C(x)=c,0,+c,1,x+c,2,x,2,+c,L,x,L,Berlekamp-Massey finds L and,C(x),Algorithm on next slide(where,d,is known as the,discrepancy,),Stream Ciphers,10,Berlekamp-Massey Algorithm,Stream Ciphers,11,Berlekamp-Massey Algorithm,Example:,Stream Ciphers,12,Berlekamp-Massey Algorithm,Berlekamp-Massey is efficient way to determine minimal LFSR for sequence,With known plaintext,keystream bits of stream cipher are exposed,With enough keystream bits,can use Berlekamp-Massey to find entire keystream,2,L,bits is enough,where,L,is linear complexity of the keystream,Keystream must have large linear complexity,Stream Ciphers,13,Cryptographically Strong Sequences,A sequence is cryptographically strong if it is a“good keystream,“Good relative to some specified criteria,Crypto strong sequence must be unpredictable,Known plaintext exposes part of keystream,Trudy must not be able to determine more of the keystream from a short segment,Small linear complexity implies predictable,Due to Berlekamp-Massey algorithm,Stream Ciphers,14,Crypto Strong Sequences,Necessary for a cryptographically strong keystream to have a high linear complexity,But not sufficient!,Why?Consider s=(s0,s1,sn-1)=0001,Then s has linear complexity n,Smallest shift register for s requires n stages,Largest possible for sequence of period n,But s is not cryptographically strong,Linear complexity“concentrated in last bit,Stream Ciphers,15,Linear Complexity Profile,Linear complexity profile is a better measure of cryptographic strength,Plot linear complexity as function of bits processed in Berlekamp-Massey algorithm,Should follow n/2 line“closely but irregularly,Plot of sequence s=(s0,s1,sn-1)=0001 would be 0 until last bit,then jumps to n,Does not follow n/2 line“closely but irregularly,Not a strong sequence(by this definition),Stream Ciphers,16,Linear Complexity Profile,A“good linear complexity profile,Stream Ciphers,17,k-error Linear Complexity Profile,Alternative way to measure cryptographically strong sequences,Consider 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 s,1-error linear complexity of s=0001 is 0,Linear complexity of this sequence is“unstable,Stream Ciphers,18,k-error Linear Complexity Profile,k,-error linear complexity profile,k,-error linear complexity as function of,k,Example:,Not a strong s,Good pro follow diagonal“closely,Stream Ciphers,19,Crypto Strong Sequences,Linear complexity must be“large,Linear complexity pro n/2 line“closely but irregularly,k-error linear complexity pro follow diagonal line“closely,All of this is necessary but not sufficient for crypto strength!,Stream Ciphers,20,Shift Register-Based Stream Ciphers,Two approaches to LFSR-based stream ciphers,One LFSR with nonlinear combining function,Multiple LFSRs combined via nonlinear func,In either case,Key is initial fill of LFSRs,Keystream is output of nonlinear combining function,Stream Ciphers,21,Shift Register-Based Str