| Home Page |

| Course Page |

Chapter 2. Stream Ciphers

Lecture Notes

Rochester Institute of Technology—Department of Computer Science

- Stream ciphers encrypt one bit at a time, block ciphers encrypt
*n*bits at a time - Encryption: Ciphertext = plaintext XOR keystream
- Decryption: Plaintext = ciphertext XOR keystream
- Keystream generator
- Keystream must be random
- Even if the plaintext is highly nonrandom, the ciphertext will still be random (proof)

- Key = keystream generator parameter; secret
- Different key gives different keystream

- Known plaintext attack on a stream cipher
- Nonce = keystream generator parameter; not secret
- Same key, different nonce gives different keystream
- Two messages must use different keys and/or different nonces

- Keystream must be unpredictable
- Knowing part of a keystream, an attacker cannot deduce either subsequent keystream bits or the key

- Keystream = true random bits as long as the plaintext
- Upside: Unbreakable
- Downside: Keystreams are large, difficult to generate, and cannot be reused

*m*-bit state, initial value S_{m−1}. . . S_{1}S_{0}- State update function: The modulo-2 sum (XOR) of certain state bits plus a shift
S

_{3}= S_{1}+ S_{0}(mod 2)

S_{4}= S_{2}+ S_{1}(mod 2)

S_{5}= S_{3}+ S_{2}(mod 2) - For each state bit S
_{i}there is a feedback coefficient P_{i}; then:S

_{3}= P_{2}S_{2}+ P_{1}S_{1}+ P_{0}S_{0}(mod 2)

S_{4}= P_{2}S_{3}+ P_{1}S_{2}+ P_{0}S_{1}(mod 2)

S_{5}= P_{2}S_{4}+ P_{1}S_{3}+ P_{0}S_{2}(mod 2)In this example, P

_{2}= 0, P_{1}= 1, P_{0}= 1 - Keystream = sequence of LSBs: S
_{0}S_{1}S_{2}S_{3}S_{4}S_{5}. . . - The keystream bit sequence looks random (if
*m*is big enough) - However, an LFSR keystream generator is easy to attack
- Because the keystream bits are just the LFSR state bits . . .
- If we can get
*m*keystream bits, e.g. by a known plaintext attack . . . - We then know the LFSR state and can generate the rest of the keystream
- Because the LFSR is reversible . . .
- If we can get any
*m*keystream bits . . . - We then know the LFSR state and can run the LFSR backwards to get the previous part of the keystream

- We can attack the LFSR even if the feedback bits are not known
- If we can recover 2
*m*bits of the keystream, e.g. by a known plaintext attack . . . - We can deduce the feedback coefficients
- Then we can run the LFSR backwards and forwards to generate the whole keystream

- If we can recover 2
- Example: A 4-bit LFSR, keystream S
_{0}S_{1}S_{2}S_{3}S_{4}S_{5}S_{6}S_{7}= 1 0 1 0 1 1 1 11 = P

_{3}0 + P_{2}1 + P_{1}0 + P_{0}1 (mod 2)

1 = P_{3}1 + P_{2}0 + P_{1}1 + P_{0}0 (mod 2)

1 = P_{3}1 + P_{2}1 + P_{1}0 + P_{0}1 (mod 2)

1 = P_{3}1 + P_{2}1 + P_{1}1 + P_{0}0 (mod 2)These are 4 linear equations in 4 unknowns which we can solve by Gaussian elimination, or as follows:

- P
_{2}+ P_{0}= 1 (mod 2) - P
_{3}+ P_{1}= 1 (mod 2) - P
_{3}+ P_{2}+ P_{0}= 1 (mod 2) - P
_{3}+ P_{2}+ P_{1}= 1 (mod 2) - Substitute (a) into (c): P
_{3}+ 1 = 1 (mod 2): P_{3}= 0 - Substitute (e) into (b): 0 + P
_{1}= 1 (mod 2): P_{1}= 1 - Substitute (e) and (f) into (d): 0 + P
_{2}+ 1 = 1 (mod 2): P_{2}= 0 - Substitute (g) into (a): 0 + P
_{0}= 1 (mod 2): P_{0}= 1

So the feedback coefficients are P

_{3}P_{2}P_{1}P_{0}= 0 0 1 1 - P
- The ease of attack is due to two reasons:
- The feedback bit is a
*linear*function of the state bits - The keystream bits are equal to the state bits

- The feedback bit is a
- Some real stream ciphers do use feedback shift registers, but . . .
- The feedback bit is a
*nonlinear*function of the state bits - The keystream bits are some function of the state bits, not the state bits themselves

- The feedback bit is a

- We'll look at three:
- Trivium
- RC4
- Salsa20

- The European Network of Excellence for Cryptography (ECRYPT) ran the eSTREAM Project to identify new stream ciphers, concluded in 2008
- ECRYPT web site: http://www.ecrypt.eu.org/
- eSTREAM web site: http://www.ecrypt.eu.org/stream/

- ECRYPT Trivium page: http://www.ecrypt.eu.org/stream/e2-trivium.html
- 288-bit circular shift register S
- Initialization
- S
_{1}.. S_{80}= 80-bit key - S
_{94}.. S_{173}= 80-bit initialization vector (IV) = nonce - S
_{286}.. S_{288}= 111 - Other bits of S = 0
- Clock S 1152 (= 4×288) times

- S
- Keystream generation
- Initialize S (see above)
- Repeat: Clock S; Z
_{i}is the next keystream bit

- I. Dinur and A. Shamir. Cube attacks on tweakable black box polynomials. Cryptology ePrint Archive Report 2008/385, January 26, 2009. http://eprint.iacr.org/2008/385/
- Breaks Trivium reduced to 672 initialization rounds in 2
^{19}time - Breaks Trivium reduced to 735 initialization rounds in 2
^{30}time - Breaks Trivium reduced to 767 initialization rounds in 2
^{45}time

- Invented by Ron Rivest in 1987
- Algorithm had been a trade secret; revealed on the Internet in 1994
- "RC4" is a trademark and cannot be used to refer to an implementation of the algorithm

- The Wikipedia description is pretty good: http://en.wikipedia.org/wiki/Rc4
- Key: 8 to 2,048 bits; nonce: none
- Simple and fast, hence widely used; for example, in:
- Wired Equivalent Privacy (WEP), the original security scheme for wireless Ethernet (now obsolete)
- Wi-Fi Protected Access (WPA), the current security scheme for wireless Ethernet
- BitTorrent protocol encryption
- Secure Sockets Layer (SSL) (optional), used by HTTPS for secure web sites
- Encrypted PDF files

- But too easy to attack (see Wikipedia article)

- ECRYPT Salsa20 page: http://www.ecrypt.eu.org/stream/e2-salsa20.html
- 128-bit or 256-bit key
- 64-bit nonce (IV)
- Salsa20 generates a keystream in 16-word chunks (1 word = 32 bits)
- Keystream chunk i = Salsa20(key,nonce,i), i = 0, 1, 2, . . .

- Salsa20 operates on a 16-word state, organized as a 4-by-4-word matrix
x0 x1 x2 x3 x4 x5 x6 x7 x8 x9 x10 x11 x12 x13 x14 x15

- For a 128-bit key, the state is initialized as follows:
0x61707865 key_0 key_1 key_2 key_3 0x3120646e nonce_0 nonce_1 counter_0 counter_1 0x79622d36 key_0 key_1 key_2 key_3 0x6b206574

- Then we apply 10 iterations of this round function to the state:
For round = 1 to 10 do: // columnround quarterround(x0, x4, x8, x12) quarterround(x5, x9, x13,x1 ) quarterround(x10,x14,x2, x6 ) quarterround(x15,x3, x7, x11) // rowround quarterround(x0, x1, x2, x3 ) quarterround(x5, x6, x7, x4 ) quarterround(x10,x11,x8, x9 ) quarterround(x15,x12,x13,x14)

- The quarterround function updates one row or one column of the state in place
- The sum of the initial state and the final state gives the keystream chunk

- The quarterround function is built from:
- Additions (mod 2
^{32}) -- square - Bitwise xors -- circle
- Left rotations -- ellipse

- Additions (mod 2

| Course Page |

| Home Page |