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 Cipher
? We consider 3 real stream ciphers
? ORYX — weak cipher, uses shift registers,
generates 1 byte/step
? RC4 — strong cipher, widely used but used
poorly in WEP, generates 1 byte/step
? PKZIP — intermediate strength, unusual
mathematical design, generates 1 byte/step
? But first, we discuss shift registers
Shift Registers
? Traditionally, stream ciphers were based
on shift registers
o Today, a wider variety of designs
? Shift register includes
o A series of stages each holding one bit
o A feedback function
? A linear feedback shift register (LFSR)
has a linear feedback function
Berlekamp-Massey Algorithm
? Given (part of) a (periodic) sequence,
can find shortest LFSR that could
generate the sequence
? Berlekamp-Massey algorithm
o Order N2, where N is length of LFSR
o Iterative algorithm
o Only 2N consecutive bits required
Berlekamp-Massey Algorithm
? Binary sequence: s = (s0,s1,s2,…,sn-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) = c0 + c1x + c2x2 + … + cLxL
? Berlekamp-Massey finds L and C(x)
o Algorithm on next slide (where d is known as the
discrepancy)
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
o 2L bits is enough, where L is linear complexity of
the keystream
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 Cipher
? We consider 3 real stream ciphers
? ORYX — weak cipher, uses shift registers,
generates 1 byte/step
? RC4 — strong cipher, widely used but used
poorly in WEP, generates 1 byte/step
? PKZIP — intermediate strength, unusual
mathematical design, generates 1 byte/step
? But first, we discuss shift registers
Shift Registers
? Traditionally, stream ciphers were based
on shift registers
o Today, a wider variety of designs
? Shift register includes
o A series of stages each holding one bit
o A feedback function
? A linear feedback shift register (LFSR)
has a linear feedback function
Berlekamp-Massey Algorithm
? Given (part of) a (periodic) sequence,
can find shortest LFSR that could
generate the sequence
? Berlekamp-Massey algorithm
o Order N2, where N is length of LFSR
o Iterative algorithm
o Only 2N consecutive bits required
Berlekamp-Massey Algorithm
? Binary sequence: s = (s0,s1,s2,…,sn-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) = c0 + c1x + c2x2 + … + cLxL
? Berlekamp-Massey finds L and C(x)
o Algorithm on next slide (where d is known as the
discrepancy)
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
o 2L bits is enough, where L is linear complexity of
the keystream
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 Cipher
? We consider 3 real stream ciphers
? ORYX — weak cipher, uses shift registers,
generates 1 byte/step
? RC4 — strong cipher, widely used but used
poorly in WEP, generates 1 byte/step
? PKZIP — intermediate strength, unusual
mathematical design, generates 1 byte/step
? But first, we discuss shift registers
Shift Registers
? Traditionally, stream ciphers were based
on shift registers
o Today, a wider variety of designs
? Shift register includes
o A series of stages each holding one bit
o A feedback function
? A linear feedback shift register (LFSR)
has a linear feedback function
Berlekamp-Massey Algorithm
? Given (part of) a (periodic) sequence,
can find shortest LFSR that could
generate the sequence
? Berlekamp-Massey algorithm
o Order N2, where N is length of LFSR
o Iterative algorithm
o Only 2N consecutive bits required
Berlekamp-Massey Algorithm
? Binary sequence: s = (s0,s1,s2,…,sn-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) = c0 + c1x + c2x2 + … + cLxL
? Berlekamp-Massey finds L and C(x)
o Algorithm on next slide (where d is known as the
discrepancy)
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
o 2L bits is enough, where L is linear complexity of
the keystream