Cryptography (CSC363): Stream ciphers

Evaluate a cipher’s secrecy

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

\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 = m_0 | C = c] = \Pr[M = m_0]

Example: Shift cipher

The shift cipher is not perfectly secret.

Imagine 2 possible messages:

m_0 = \text{OK} \newline m_1 = \text{NO}

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

One-time pad

The one-time pad is a perfectly secret cipher.

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

where $k$ is a random key of length $n$ .

Pros and cons of the one-time pad

Pros	Cons
Perfect secrecy	Key must be as long as the message
Simple and fast	Key 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...

\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.

\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.

\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.

\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

x^3 + x^2 + 1

determines that only bits $s_3$ , $s_2$ , and $s_0$ participate in generating the next bit.

Loading diagram...

Example: LFSR

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

Loading diagram...

Output: $0$ . New state: $1010$

Output: $0$ . New state: $0101$

Output: $1$ . New state: $0010$

Period of an LFSR

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

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

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

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