4003-482-01/4005-705-01 Cryptography
Chapter 2. Stream Ciphers
Lecture Notes

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

One-Time Pad

• 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 S_m−1 . . . S₁ S₀

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

  

  S₃ = S₁ + S₀ (mod 2)
  S₄ = S₂ + S₁ (mod 2)
  S₅ = S₃ + S₂ (mod 2)

• For each state bit S_i there is a feedback coefficient P_i; then:

  S₃ = P₂ S₂ + P₁ S₁ + P₀ S₀ (mod 2)
  S₄ = P₂ S₃ + P₁ S₂ + P₀ S₁ (mod 2)
  S₅ = P₂ S₄ + P₁ S₃ + P₀ S₂ (mod 2)

  In this example, P₂ = 0, P₁ = 1, P₀ = 1

• Keystream = sequence of LSBs: S₀ S₁ S₂ S₃ S₄ S₅ . . .

• If we can recover 2m bits of the keystream (e.g. a known plaintext attack), we can deduce the feedback coefficients and break the cipher, so an LFSR keystream generator is not cryptographically secure

• Example: A 4-bit LFSR, keystream S₀ S₁ S₂ S₃ S₄ S₅ S₆ S₇ = 1 0 1 0 1 1 1 1

  1 = P₃ 0 + P₂ 1 + P₁ 0 + P₀ 1 (mod 2)
  1 = P₃ 1 + P₂ 0 + P₁ 1 + P₀ 0 (mod 2)
  1 = P₃ 1 + P₂ 1 + P₁ 0 + P₀ 1 (mod 2)
  1 = P₃ 1 + P₂ 1 + P₁ 1 + P₀ 0 (mod 2)

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

  1. P₂ + P₀ = 1 (mod 2)
  2. P₃ + P₁ = 1 (mod 2)
  3. P₃ + P₂ + P₀ = 1 (mod 2)
  4. P₃ + P₂ + P₁ = 1 (mod 2)
  5. Substitute (a) into (c): P₃ + 1 = 1 (mod 2): P₃ = 0
  6. Substitute (e) into (b): 0 + P₁ = 1 (mod 2): P₁ = 1
  7. Substitute (e) and (f) into (d): 0 + P₂ + 1 = 1 (mod 2): P₂ = 0
  8. Substitute (g) into (a): 0 + P₀ = 1 (mod 2): P₀ = 1

  So the feedback coefficients are P₃ P₂ P₁ P₀ = 0 0 1 1

Real Stream Ciphers

• We'll look at three:
  • RC4
  • Trivium
  • 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/

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)

Trivium

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

  

• 288-bit circular shift register S

• Initialization
  • S₁ .. S₈₀ = 80-bit key
  • S₉₄ .. S₁₇₃ = 80-bit initialization vector (IV) = nonce
  • S₂₈₆ .. S₂₈₈ = 111
  • Other bits of S = 0
  • Clock S 1152 (= 4×288) times

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

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 final state gives the keystream chunk

• The quarterround function is built from:
  • Additions (mod 2³²) -- square
  • Bitwise xors -- circle
  • Left rotations -- ellipse

    

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 2¹⁹ time

• Breaks Trivium reduced to 735 initialization rounds in 2³⁰ time

• Breaks Trivium reduced to 767 initialization rounds in 2⁴⁵ time

Cryptography • 4003-482-01/4005-705-01 • Spring Quarter 2013

Course Page

Alan Kaminsky • Department of Computer Science • Rochester Institute of Technology • 4486 + 2220 = 6706

Home Page

Copyright © 2012 Alan Kaminsky. All rights reserved. Last updated 19-Mar-2012. Please send comments to ark­@­cs.rit.edu.