Stream Ciphers

Symmetric Key Encryption Scheme (SKES)

A SKES consists of:
- M : plaintext space
- C : ciphertext space
- K : key space
- Encryption algorithm E : K x M → C
- Decryption algorithm D : K x C → M

such that:
  D(k, E(k, m)) = m ∀ m ∈ M, k ∈ K
            

Caesar Cipher

Encrypt(m) where m ∈ {A,...,Z}*
  for i = 1,...,|m|
    x ← Encode(m_i)
    y = x + 23 mod 26 (or x -3 mod 26)
    c_i ← Decode(y)
  return c

Decrypt(c) where c ∈ {A,...,Z}*
  for i = 1,...,|c|
    x ← Encode(c_i)
    y = x - 23 mod 26
    m_i ← Decode(y)
  return m
            

Shift Cipher

Key Space
  K = {0,...,25}
  k ← K

Encrypt(k, m) where m ∈ {A,...,Z}*
  for i = 1,...,|m|
    x ← Encode(m_i)
    y ← (x + k) mod 26
    c_i ← Decode(y)
  return c

Decrypt(k, c) where c ∈ {A,...,Z}*
  for i = 1,...,|c|
    x ← Encode(c_i)
    y ← (x - k) mod 26
    m_i ← Decode(y)
  return m
            

Substitution Cipher

Key Space
  K = all permutations of {A,...,Z}

Encrypt(k, m)
  for i = 1,...,|m|
    c_i ← apply permutation k to m_i
  return c

Decrypt(k, c)
  for i = 1,...,|c|
    m_i ← apply inverse permutation k to c_i
  return m
            

Transposition Cipher

Fix a block length B ∈ ℕ
Key Space
  k = all permutations of {1,...,B}

Message and Cipher Space
  M = C = ∪_{i≥0} {A,...,B}^{iB}

Encrypt(k, m)
  for i = 1,...,|m|/B
    x ← ith block of m
    y ← apply permutation k to positions of x
    ith block of c ← y
  return c

Decrypt(k, c)
  for i = 1,...,|c|/B
    x ← ith block of c
    y ← apply inverse permutation k to positions of x
    ith block of m ← y
  return m
            

Vigenère Cipher

Fix a block length B ∈ ℕ
Key Space
  k = {A,...Z}^B

Message and Ciphertext Space
  m = c = ∪_{i≥0} {A,...,Z}^{iB}

Encrypt(k, m)
  for i = 1,...,|m|
    c_i ← m_i + k_{i mod B} mod 26
  return c

Decrypt(k, c)
  for i = 1,...,|c|
    m_i ← c_i - k_{i mod B} mod 26
  return m
            

One-Time Pad (OTP)

#########################
# For plaintext message #
#########################

Fix a message length l ∈ ℕ
Key Space
  K = {A,...Z}^l

Message and Ciphertext Space
  M = C = {A,...,Z}^l

Encrypt(k, m)
  for i = 1,...,l
    c_i ← m_i + k_i mod 26
  return c

Decrypt(k, c)
  for i = 1,...,l
    m_i ← c_i - k_i mod 26
  return m

######################
# For binary message #
######################

Key, Message and Ciphertext Space
  K = M = C = {0,1}^l

Encrypt(k, m) where m ∈ {0,1}^l
  for i = 1,...,l
    c_i ← m_i ⊕ k_i
  return c

Decrypt(k, c) where c ∈ {0,1}^l
  for i = 1,...,l
    m_i ← c_i ⊕ k_i
  return m
            

A5

# Uses three LFSRs whose output is then combined.
# Three LFSRs are irregularly clocked.
  - Overall the output is non-linear
# Each LFSR has a clocking bit.
  - Each LFSR is clocked (i.e. updated using Update function) if its own "clocking bit" is in majority agreement with the clocking bits of the other LFSRs.
# The key length is 64 bits which define the state vector for each LFSR
  x: 19 bits (x0,x1,...,x18)
  y: 22 bits (y0,y1,...,y21)
  z: 23 bits (z0,z1,...,z22)

At each step:
  m = maj(x8,y10,z10) # check major clocking bits

  if x8 == m:
    t = x13 ⊕ x16 ⊕ x17 ⊕ x18
    x_i = x_i-1 for i=1,...,18
    x0 = t
  if y10 == m:
    t = y20 ⊕ y21
    y_i = y_i-1 for i=1,...,21
    y0 = t
  if z10 == m:
    t = z7 ⊕ z20 ⊕ z21 ⊕ z22
    z_i = z_i-1 for i=1,...,22
    z0 = t

  keystream bit is x18 ⊕ y21 ⊕ z22
            

RC4

RC4 is a stream cipher that uses a variable-length key to generate a pseudorandom stream of bits, which is then XORed with the plaintext to create the ciphertext.
Extremely simple, fast and accepts variable key length, but not recommended for use today.

# RC4 has two components:
  - Key scheduling algorithm (Initialize)
  - Keystream generator (Update&Output)

Initialize(K = K[0], K[1], ..., K[d-1])
// K[i], K'[i], S[i] are 8-bit integers
for i=0,...,255:
  S[i] ← i
  K'[i] ← K[i mod d]
j ← 0
for i=0,...,255
  j ← (K'[i]+S[i]+j) mod 256
  swap(S[i],S[j])
return S // 256-byte array S[0],S[1],...,S[255] is a 'random looking' permutation of {0,1,...,255} generated by the secret key K.

Update&Output(S=S[0],S[1],...,S[255])
  i ← (i+1) mod 256
  j ← (S[i]+j) mod 256
  swap(S[i],S[j])
  t ← (S[i]+S[j]) mod 256
  return S[t] 
            

Salsa20

Salsa20 is a stream cipher designed to be secure and fast. It operates by processing a 512-bit key and producing a pseudorandom output stream.

Initialize:
  Load the key, nonce, and counter into the 4x4 array of 32-bits state.

Update&Output
  1. Make a copy of the initial state
  2. Do following operations 10 times:
    - Apply the quarter-round function to each column of the state
    - Apply the quarter-round function to each row of the state
  3. XOR the current state with the copy of the initial state
  4. Output the result as the keystream
            

Initial State: 4x4 array of 32-bit words

Salsa20 Quarter Round Function