Today: Stream Ciphers, Monday. March 9th, 2015

• Stream ciphers
  • Definitions
  • RC4 and Spritz
  • ChaCha
    • Dan Bernstein

PRNGS

If you remember the One-time pad (OTP), we had a message m of length n and a pad p of length n and we computed the ciphertext c by computing c = m \xor p for all n bits.

However, it's very hard to come up with the pad.

TODO: transmitting a secert as long as the message is equivalent to transmitting the message

        pseudo-random generator G

                   ----- 
    key or seed -> | G | -> pad
                   -----
        {0,1}^n             {0,1}^l(n)
                             l(n) > n

Definition: G is a pseudo-random generator (PRG) if no adversary can distinguish between a string x drawn randomly from {0,1}^l(n) (ideal situation) and the output of the program G(s), where s <- {0,1}^n with probability better than 1/2 + negl(n)

• Remember negl(n) is a function that goes to zero faster than any inverse polynomial function of n

Stream ciphers

Stream cipher is a PRG

• but has a long-term K from short-term key (nonce)

May be counter based:

        -----
        | i | <- + 1
        -----
          |
         \ /
          .
        -----
    k ->| G |
        -----
          |
         \ /
          .
        Output 
         pad

May be state based:

               <-----------------------\
        ---------                       \
        | state |    next state fn f    |
        ---------                       |
                \-----------------------/
            |
           \ /          initial state
            .           is the key K
        ---------
        |   G   |
        ---------
            |
           \ /
            .
        output bytes

Spritz - A spongy RC4-like stream cipher

RC4

• Was a 1987 design.
• Works for any set of N bytes: Z_n = {0, 1, ..., N-1} (All math is mod N). Default N = 256
• State consists of
  • Two mod N pointers i and j
  • a permutation S of Z_n
• one of the purpose of designing RC4 was for it to have a lot of state so that you couldn't build a chip that can store it
• Key Setup Algorithm initializes S from key K
• PRG updates state and generate output

RC4-PRG:

RC4_PRG():
    i = i + 1               // update state
    j = j + S[i]
    Swap(S[i], S[j])
    z = S[S[i]+S[j]]        // generate output
    return z

• Heuristically designed
• No proof of security here
• Note this is an invertible function, so this is not good because given a state, an attacker could trace back and figure out previous states, ultimately leading to the key
  • Fortunately, it's hard to get the state

RC4-KSA (key K = L values on N bits (|k| = L bytes when N = 256)):

RC4_KSA(k):
    S[0 ... N-1] = [0 ... N-1]
    j = 0
    for i = 0; to N-1:
        j = j + S[i] + K[i mod L]
        Swap(S[i], S[j])
    i = j = 0

Vulnerabilities:

• Key-dependent biases of initial output
• Key collisions (producing same internal state) is possible
• Key recovery possible from known internal state
• Related-key attacks (WEP)
• State recovery from known output (feasible?)
  • i.e. given a million bytes of output, can your recover the internal state?
  • so far doesn't seem feasible
• Output biases => distinguishers

Spritz

• Design started after CRYTPO2013 (Really after AlFarden, ..., and Schuldt, USENIX 2013)
• Design retained the RC4 style (a few registers plus a permutation S)
• Goal is to minimize statistical vulnerabilities
• Redo key setup entirely
  • Expand API to have "spongy" interface
  • TODO: Absorb entropy?
• Design for Spritz did a computer-aided search w/ statistic testing to find a good function G

Code:

SPRITZ_PRG():
    i = i + w
    j = k + S[j + S[i]]
    k = i + k + S[j]
    Swap(S[i], S[j])
    z = S[j + S[i + S[z+k]]]
    return z

• w is always relatively prime to N
• z is used as feedback (see line before return z)

Initialization:

• S is the identity permutation
• i = j = k = 0
• z = 0
• "Number of nibbles absorbed" var. a set to 0
• Step size w is initialized to 1

Code:

SQUEEZE(r):
    if a > 0:
        SHUFFLE()
    P = new array of size r
    for v = 0 to r-1
        p[v] = SPRITZ_PRG
    return p

ENCRYPT(k, m):
    KEYSETUP(K)
    C = M + SQUEEZE(M.length)
    return C
KEYSETUP(k):
    InitializeState()
    ABSORB(k)

• Absorb takes an arbitrary sequence of k bytes as input

Spritz can also be used as a hash function!

ChaCha

• Recently picked-up by Google as a replacement for RC4 in OpenSSL

• Nice and simple designs

      --------------
     |512 bit state |
      --------------
           |
           | <-----
           |      |
        ChaCha|   |
           |      |
          ---     |
         | + |-----
          ---
           |
          \ /
           .
  

State is 4 x 4 x 32 bit matrix, each cell indexed from 0, ..., 15

c | c | c | c  constant 128bit
-- --- --- --
k | k | k | k  key 256bit
-- --- --- -- 
k | k | k | k
-- --- --- --
n | n | n | n  nonce counter 128bit

It's called ChaCha20 because it has 20 rounds, broken up into quarter rounds (QRs).

This is a style of design called ARX design: Additions, Rotations and XOR

• nice to use ARX because operations are constant time and you do not tend to be vulnerable to timing or side channel attacks

Code:

QR(a,b,c,d):
    a += b; d ^= a; d <<<= 16
    c += d; b ^= c; b <<<= 12
    a += b; d ^= a; d <<<= 8
    c += d; b ^= c; b <<<= 7

You can imagine applying this to a column of this matrix.

Round 1:
QR(0, 4, 8, 12)   # the first column
QR(1, 5, 9, 13)   
QR(2, 6, 10, 14)
QR(3, 7, 11, 15)

Round 2
QR(0, 5, 10, 15)  # the main diagonal
QR(1, 6, 11, 12)  # just above the main diagonal
QR(2, 7, 8, 13)
QR(3, 4, 9, 14)

Round 1 and round 2 are a double round

ChaCha20 has 10 double rounds