Cryptography (CSC363): Stream ciphers

Evaluate a cipher's secrecy

A cipher (KG,E,D)(\mathcal{KG}, \mathcal{E}, \mathcal{D}) with message space M\mathcal{M} and ciphertext space C\mathcal{C} is perfectly secret if

m0,m1M,cC:Pr[E(m0)=c]=Pr[E(m1)=c]\forall m_0, m_1 \in \mathcal{M}, c \in \mathcal{C}: \Pr[\mathcal{E}(m_0) = c] = \Pr[\mathcal{E}(m_1) = c]

or, equivalently, if

Pr[M=m0C=c]=Pr[M=m0]\Pr[M = m_0 | C = c] = \Pr[M = m_0]

Example: Shift cipher

The shift cipher is not perfectly secret.

Imagine 2 possible messages:

m0=OKm1=NOm_0 = \text{OK} \newline m_1 = \text{NO}

The ciphertext c=QMc = \text{QM} cannot have been generated by m1m_1, for the amount of shift applied to the letters is different.

One-time pad

The one-time pad is a perfectly secret cipher.

KG{0,1}nE(k,m)=kmD(k,c)=kc\mathcal{KG} \rightarrow \{0, 1\}^n \newline \mathcal{E}(k, m) = k \oplus m \newline \mathcal{D}(k, c) = k \oplus c

where kk is a random key of length nn.

Pros and cons of the one-time pad

ProsCons
Perfect secrecyKey must be as long as the message
Simple and fastKey must be truly random
Key must be shared securely
Key must only be used once

Stream ciphers

A stream cipher is a symmetric key cipher where the plaintext is encrypted using a pseudorandom stream of bit originating from a short seed.

Loading diagram...
E(k,m)=PRG(k)mD(k,c)=PRG(k)c\mathcal{E}(k, m) = \text{PRG}(k) \oplus m \newline \mathcal{D}(k, c) = \text{PRG}(k) \oplus c

Necessity of a nonce

A nonce is a unique value that must be used only once. It must be included in the encryption and decryption processes to prevent replay attacks.

If we only rely on the key, two subsequent encryptions will reveal information about the plaintext.

E(k,m1)=PRG(k)m1=c1E(k,m1)=PRG(k)m2=c2c1c2=m1m2\mathcal{E}(k, m_1) = \text{PRG}(k) \oplus m_1 = c_1 \newline \mathcal{E}(k, m_1) = \text{PRG}(k) \oplus m_2 = c_2 \newline c_1 \oplus c_2 = m_1 \oplus m_2

Adding a nonce

Stream cipher must also consider the nonce in the encryption and decryption processes. The nonce is not secret and can be sent in the clear.

E(k,n,m)=PRG(k,n)mD(k,n,c)=PRG(k,n)c\mathcal{E}(k, n, m) = \text{PRG}(k, n) \oplus m \newline \mathcal{D}(k, n, c) = \text{PRG}(k, n) \oplus c

The combination (key, nonce) must be unique for each encryption request.

Random number generators

True randomness is difficult to achieve for computers. Instead, we rely on pseudorandom generators (PRGs) which expand a short seed into a long pseudorandom sequence of bits.

PRG:{0,1}k{0,1}n\text{PRG}: \{0, 1\}^k \rightarrow \{0, 1\}^n

Characteristics of a good PRG

  • Expansion: the output must be longer than the seed.
  • Indistinguishable: the output must be indistinguishable from true randomness.
  • Efficiency: the output must be generated quickly (polynomial time).
  • Repeatability: the same seed must always produce the same output.
  • Unpredictability: a small change in the seed must produce a completely different output.

Linear feedback shift registers

A linear feedback shift register (LFSR) is a simple PRG that generates a sequence of bits by shifting the bits of a register, producing a bit from the right and introducing a new one from the left.
Can be used to generate a pseudorandom stream of bits.

Loading diagram...

Connection polynomial

Not all bits of the state contribute in generating the next bit. They are determined by the connection polynomial.

For example, the polynomial

x3+x2+1x^3 + x^2 + 1

determines that only bits s3s_3, s2s_2, and s0s_0 participate in generating the next bit.

Loading diagram...

Example: LFSR

Consider the LFSR with polynomial x2+1x^2 + 1 and initial state s=0100s = 0100. What appears at the output after 3 ticks?

Loading diagram...
  1. Output: 00. New state: 10101010
  1. Output: 00. New state: 01010101
  1. Output: 11. New state: 00100010

Period of an LFSR

The sequence of bits generated by a LFSR repeats after a certain number of ticks.

For an ll-bit LFSR, the maximum period is 2l12^l - 1.

The period is determined by the irreducibility of its polynomial C(x)C(x) and the smallest value ll such that C(x)C(x) divides the polynomial xl+1x^l + 1.

LFSR are not secure for cryptographic purposes, as the output can be predicted by just observing the output.