Alan Kaminsky • Department of Computer Science • Rochester Institute of Technology • 4572 + 2433 = 7005
 Foundations of Cryptography • CSCI 662-01 • Spring Semester 2018
Course Page

## CSCI 662—Foundations of Cryptography Chapter 2. Stream Ciphers Lecture Notes

Prof. Alan Kaminsky
Rochester Institute of Technology—Department of Computer Science

### Basic Concepts

• 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

### Linear Feedback Shift Register (LFSR)

• m-bit state, initial value Sm−1 . . . S1 S0

• State update function: The modulo-2 sum (XOR) of certain state bits plus a shift

S3 = S1 + S0 (mod 2)
S4 = S2 + S1 (mod 2)
S5 = S3 + S2 (mod 2)

• For each state bit Si there is a feedback coefficient Pi; then:

S3 = P2 S2 + P1 S1 + P0 S0 (mod 2)
S4 = P2 S3 + P1 S2 + P0 S1 (mod 2)
S5 = P2 S4 + P1 S3 + P0 S2 (mod 2)

In this example, P2 = 0, P1 = 1, P0 = 1

• Keystream = sequence of LSBs: S0 S1 S2 S3 S4 S5 . . .

• 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 2m 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

• Example: A 4-bit LFSR, keystream S0 S1 S2 S3 S4 S5 S6 S7 = 1 0 1 0 1 1 1 1

1 = P3 0 + P2 1 + P1 0 + P0 1 (mod 2)
1 = P3 1 + P2 0 + P1 1 + P0 0 (mod 2)
1 = P3 1 + P2 1 + P1 0 + P0 1 (mod 2)
1 = P3 1 + P2 1 + P1 1 + P0 0 (mod 2)

These are 4 linear equations in 4 unknowns which we can solve by Gaussian elimination, or as follows:

1. P2 + P0 = 1 (mod 2)
2. P3 + P1 = 1 (mod 2)
3. P3 + P2 + P0 = 1 (mod 2)
4. P3 + P2 + P1 = 1 (mod 2)
5. Substitute (a) into (c): P3 + 1 = 1 (mod 2): P3 = 0
6. Substitute (e) into (b): 0 + P1 = 1 (mod 2): P1 = 1
7. Substitute (e) and (f) into (d): 0 + P2 + 1 = 1 (mod 2): P2 = 0
8. Substitute (g) into (a): 0 + P0 = 1 (mod 2): P0 = 1

So the feedback coefficients are P3 P2 P1 P0 = 0 0 1 1

• 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

• 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

### Trivium

• ECRYPT Trivium page: http://www.ecrypt.eu.org/stream/e2-trivium.html

• 288-bit circular shift register S

• Initialization
• S1 .. S80 = 80-bit key
• S94 .. S173 = 80-bit initialization vector (IV) = nonce
• S286 .. S288 = 111
• Other bits of S = 0
• Clock S 1152 (= 4×288) times

• Keystream generation
• Initialize S (see above)
• Repeat: Clock S; Zi is the next keystream bit

### Stream Cipher Attack: Cube Attack

• 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 219 time

• Breaks Trivium reduced to 735 initialization rounds in 230 time

• Breaks Trivium reduced to 767 initialization rounds in 245 time

### RC4

• 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)

### Salsa20

• 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 232) -- square
• Bitwise xors -- circle
• Left rotations -- ellipse

 Foundations of Cryptography • CSCI 662-01 • Spring Semester 2018
Course Page
 Alan Kaminsky • Department of Computer Science • Rochester Institute of Technology • 4572 + 2433 = 7005