Cryptography - Lecture 12 - Modern Stream Ciphers

1. Modern Stream Ciphers

• stream ciphers process the message bit by bit (as a stream)
• typically have a (pseudo) random stream key
• combined (XOR) with plaintext bit by bit
• randomness of stream key completely destroys any statistically properties in the message
• what could be simpler!!!!

  Ci = Mi XOR StreamKeyi
  

2. Vernam Cipher or One-Time Pad

• probably the most famous stream cipher
• also known as the one-time pad
• invented by Vernam, working for AT&T, in 1917
• simply add bits of message to random key bits
• originally chose random number from a hat, punched onto paper tape
• then combined using XOR with a telegraph message
• is unconditionally secure provided key is truly random
  
  Vernam Cipher

3. Using a Vernam Cipher

• in practise have some issues when using this
• most critically you need as many key bits as message
• can be difficult in practise
• eg can distribute on a mag-tape or CDROM
• have no chaining since the stream key is independent of the message
• hence need to use other methods to verify integrity
• and critically must never ever reuse a stream key
• since if have two messages encrypted by XOR with same key
• can combine these to remove effect of key giving a book cipher

  C1i = M1i XOR StreamKeyi
  C2i = M2i XOR StreamKeyi
  C1i XOR C2i = M1i XOR StreamKeyi XOR
  	M2i XOR StreamKeyi
  	= M1i XOR M2i
  

4. Practical Pseudo-random Stream Ciphers

• given the problems of key distribution for a Vernam Cipher
• suggestion is to generate a keystream from a smaller (base) key
• using some pseudo-random function
• superficially look very attractive
• in practise is extremely difficult to find a good fast pseudo-random function that is cryptographically strong
• that is, one which is unpredictable
• this is still an area of much research
  
  Stream Cipher Using a PRG

5. Stream Ciphers and Pseudo-Random Generators

• when using a Pseudo-Random Generator (PRG)
• the generated stream must be:
  • statistically random (like result of coin tossing)
  • (know part of seq not enough)
• PRG may be controlled just by key influencing:
  • next-state function (output feedback mode)
  • output function (counter mode)
• PRG may be controlled both by data and key:
  • output function (cipher feedback mode)

6. Stream Ciphers and Pseudo-Random Generators

Pseudo-Random Generator

7. Using Block Ciphers as Stream Ciphers

• have already seen block ciphers used as a PRG
• Output Feedback Mode uses a block cipher as a PRG
• with the cipher being the next-state function
• with a null output function

  Ci = Pi XOR Oi
  Oi = DESK1(Oi-1)
  O-1 = IV
  

• also have a Counter Mode
• where internal state is a counter incremented by next-state function
• encrypt this value using block cipher as an output function

  Ci = Pi XOR Oi
  Oi = DESK1(i)
  

8. Using Block Ciphers as Stream Ciphers

• Cipher Feedback Mode has PRG controlled by both data and key
• internal state is derived from ciphertext
• and the block cipher is used as the next state function

  Ci = Pi XOR DESK1 (Ci-1)
  C-1 = IV
  

• all of these work well
• block ciphers make a strong PRG
• BUT want more efficient PRGs than these

9. Linear Feedback Shift Registers (LFSR)

• LFSRs are often proposed for use as a PRG in stream ciphers
• comprise a shift register (of binary bits) of some length
• along with a linear feedback function of some of those bits
• each time a bit is needed, all bits are shifted one place
• the bit bumped out is the bit used as output from the LFSR
• a new bit is formed from the linear feedback function of other bits
• this form is known as the fibonacci configuration
• an alternate galois configuration is easier to code in s/w
• correctly designed they generate a very long sequence before repeating
• the generated sequence is also statistically pretty random
  
  Linear Feedback Shift Register

10. Linear Feedback Shift Registers (LFSR)

• given a suitable sized register
• can use the key to initialise one or both of:
  • the initial state (value) in the shift register
  • the feedback function used
• an n-bit shift register can generate a sequence of 2ⁿ-1 bits
• need to use a primitive polynomial linear function to do this
• for greater security should use dense (not sparse) polynomials
• these are well known for common register sizes (see Number Theory lecture)
• eg. above diagram uses: p(x) = x32+x7+x5+x3+x2+x

11. LFSR Insecurities!

• LFSR's can generate a very large key
• which is why they're often used
• BUT they are insecure - statistically random but predictable
  • given an n bit shift register
  • just 2n bits is enough to completely predict sequence
  • using the well known Berlecamp-Massey algorithm for reconstructing a LFSR from a stream of bits
  • any stream of bits can be approximated by an LFSR
  • (at worst just one big register with the complete stream)
  • in practice can often do much better
• even so, LFSRs do form the basis though of most stream ciphers
• but design attempts to hide the underlying LFSR structure

12. Stream Ciphers Design Criteria

• Rueppel has codified stream ciphers design criteria:
  • long period with no repetitions
  • statistically random
  • large linear complexity (based on size of equiv LFSR)
  • correlation immunity (have tradeoff with linear complexity)
  • confusion (output bits depend on all key bits)
  • diffusion
  • use of highly non-linear boolean functions

13. Stream Ciphers Based on LFSRs

• general idea is to take several LFSRs of different sizes & feedback polys
• then combine them to try & obscure the underlying LFSRs by:
  • combining outputs of several LFSRs using a non-linear function
  • selecting the output from the LFSRs using a multiplexor
  • controlling the clocking of some LFSRs by another
  • only selecting some of the output bits (decimating the output)
• virtually all of these proposals have identified flaws
• incl. all current mobile phone algorithms are broken
• currently when LFSRs are used, they are re-keyed extremely often:
  • fast enough so attacks will yield little info
  • slow enough for a block cipher to be used to create keying information

14. A5

• A5 is the stream cipher used to encrypt GSM phones
• was protected as a "trade secret"
• but has subsequently been reverse engineered (fully at SCARD'99)
• actually has several variants (A5, A5/1, A5/2)
• all have been broken (A5/2 in Aug99, A5/1 in Apr 2000)
• A5/1 uses 3 LFSR's of 19, 22 and 23 bits using sparse feedback polys
• basic attack has complexity 240
• guess state of LFSR's 1 & 2, try to determine 3 from keystream
• A5/2 is weakened version with clocking from 4th LFSR, easily attacked
• real problem is registers are too small & feedback poly's are sparse

15. SOBER

• a Australian designed (98) stream cipher using an LFSR
• but instead of binary values for x use nicer sized words
• several versions for different word sizes (t8, t16, t32)
• has fast keying, small memory, fast implementation
  • each element is 8, 16 or 32-bits (a Galois polynomial)
  • use XOR and modular polynomial multiplication as operations
  • LFSR is updated using (polynomial) evaluation of

  Sn+17 = 99 x Sn+15 + Sn+4 + 206 x Sn
  

• equivalent to a 136-bit binary shift register, period is 2136-1
• uses a non-linear (integer) function on selected values
• and stutters (decimates) output based on some of output

  Vn = ROTL(Sn+Sn+16) + Sn+1 + Sn+6 + Sn+13
  

16. SOBER

• analysis of original version identified some flaws
• has subsequently been redesigned
• current analysis appears very promising
• extremely efficient implementation in s/w
• SOBER-t16 being considered for new digital mobile phone standards
• see Rose, ACISP98 & FSE99 proceedings for details of design & analyses

17. RC4

• a proprietary cipher created by RSA Data Security Inc
• not an LFSR but rather a more general PRG design
• another Ron Rivest design, simple but effective
• now a widely licenced commercial cipher
• was kept secret, but has been reverse engineered
• ftp:///ftp.dsi.unimi.it/pub/security/crypt/code/rc4.revealed.gz
• turns key into random permutation of 256 8-bit values
• uses that permutation to scamble input info processed a byte at a time

18. RC4 Key Schedule

• basic idea is to start with an array of numbers: 0..255
• and well and truly shuffle this up, controlled by the key
• this array S forms the internal state of the cipher
• given a key k of length l bytes

  i = j = 0
  initialise array S to {0, 1, 2, ..., 255}
  repeat 256 times
      j += S[i] + k[i mod l] (mod 256)
      swap(S[i], S[j])
      increment i
  

19. RC4 Encryption

• to encrypt we continue to shuffle array entries
• and use the sum of the pair we shuffled as the "stream key"
• which then XOR with the next byte of the message

  i = j = 0
  for each message byte
  	i = i + 1 (mod 256)
  	j = j + S[i] (mod 256)
  	swap(S[i], S[j])
  	t = (S[i] + S[j]) (mod 256)
  	C = M XOR S[t] 
  

20. RC4 Security

• is claimed secure against known cryptanalyses
• result is very non-linear
• the first group of outputs correlate with key
• so in practise should discard first 256 outputs
• also, being a stream cipher, should never reuse a key
• also after a few GB, see some values occuring slightly too often
• but none of these really a major practical issue

21. Other Stream Ciphers

• many other proposals have been made
• see Schneier for many descriptions
• nearly all have problems
• the frequency of successful attacks on new stream cipher proposals is very worrying
• great care currently should be taken in selecting any for use
• European Community has a call for new algs, including stream ciphers
• may see major advances similar to those AES has pushed

22. Public Key Based Schemes

• have several schemes based on public key algorithms, eg RSA
• simplest, best, known and most efficient is the "Blum, Blum and Shub" (BBS) generator

  xi+1 = xi2 mod n	and use
  bi the LSB of xi
  where n=p.q, primes p,q=3 mod 4
  

• security rests on difficulty of factoring N
• is unpredictable given any run of bits
• slow, since very large numbers must be used for security
• too slow for cipher use, but good for key generation

23. Summary

• have discussed:
• concept of stream ciphers
• Vernam Cipher or One-time pad
• Using block ciphers to make stream ciphers
• Using PRGs in s stream cipher
• LFSR's
• Ciphers: A5, SOBER, RC4, BBS

24. Exercises