5.5☆: Applications: Stream Cipher and Symmetric Ratchet

Last updated
Save as PDF

Page ID: 86458

$ \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } $ $ \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} $$\newcommand{\id}{\mathrm{id}}$ $ \newcommand{\Span}{\mathrm{span}}$ $ \newcommand{\kernel}{\mathrm{null}\,}$ $ \newcommand{\range}{\mathrm{range}\,}$ $ \newcommand{\RealPart}{\mathrm{Re}}$ $ \newcommand{\ImaginaryPart}{\mathrm{Im}}$ $ \newcommand{\Argument}{\mathrm{Arg}}$ $ \newcommand{\norm}[1]{\| #1 \|}$ $ \newcommand{\inner}[2]{\langle #1, #2 \rangle}$ $ \newcommand{\Span}{\mathrm{span}}$ $\newcommand{\id}{\mathrm{id}}$ $ \newcommand{\Span}{\mathrm{span}}$ $ \newcommand{\kernel}{\mathrm{null}\,}$ $ \newcommand{\range}{\mathrm{range}\,}$ $ \newcommand{\RealPart}{\mathrm{Re}}$ $ \newcommand{\ImaginaryPart}{\mathrm{Im}}$ $ \newcommand{\Argument}{\mathrm{Arg}}$ $ \newcommand{\norm}[1]{\| #1 \|}$ $ \newcommand{\inner}[2]{\langle #1, #2 \rangle}$ $ \newcommand{\Span}{\mathrm{span}}$$\newcommand{\AA}{\unicode[.8,0]{x212B}}$

The PRG-feedback construction can be generalized in a natural way, by continuing to feed part of $G$ ’s output into $G$ again. The proof works in the same way as for the previous construction $-$ the security of $G$ is applied one at a time to each application of $G$.

Claim 5.7

If $G$ is a secure length-doubling $P R G$, then for any $n$ (polynomial function of $\lambda$ ) the following construction $H_{n}$ is a secure PRG with stretch $n \lambda$ :

The fact that this chain of PRGs can be extended indefinitely gives another useful functionality:

Definition 5.8 (Stream cipher)

A stream cipher is an algorithm $G$ that takes a seed s and length $\ell$ as input, and outputs a string. It should satisfy the following requirements:

$G(s, \ell)$ is a string of length $\ell$.
If $i<j$, then $G(s, i)$ is a prefix of $G(s, j)$.
For each $n$, the function $G(\cdot, n)$ is a secure $P R G$.

Because of the 2 nd rule, you might want to think about a single infinitely long string that is the limit of $G(s, n)$ as $n$ goes to infinity. The finite-length strings $G(s, n)$ are all the prefixes of this infinitely long string.

The PRG-feedback construction can be used to construct a secure stream cipher in the natural way: given seed $s$ and length $\ell$, keep iterating the PRG-feedback main loop until $\ell$ bits have been generated.

Symmetric Ratchet

Suppose Alice & Bob share a symmetric key $k$ and are using a secure messaging app to exchange messages over a long period of time. Later in the course we will see techniques that Alice & Bob could use to securely encrypt many messages using a single key. However, suppose Bob’s device is compromised and an attacker learns $k$. Then the attacker can decrypt all past, present, and future ciphertexts that it saw! Alice & Bob can protect against such a key compromise by using the PRG-feedback stream cipher to constantly "update" their shared key. Suppose they do the following, starting with their shared key $k$ :

They use $k$ to seed a chain of length-doubling PRGs, and both obtain the same stream of pseudorandom keys $t_{1}, t_{2}, \ldots$
They use $t_{i}$ as a key to send/receive the $i$ th message. The details of the encryption are not relevant to this example.
After making a call to the PRG, they erase the $P R G$ input from memory, and only remember the PRG’s output. After using $t_{i}$ to send/receive a message, they also erase it from memory.

This way of using and forgetting a sequence of keys is called a symmetric ratchet.

Construction $5.9$ (Symm Ratchet)

Suppose that an attacker compromises Bob’s device after $n$ ciphertexts have been sent. The only value residing in memory is $s_{n}$, which the attacker learns. Since $G$ is deterministic, the attacker can now compute $t_{n+1}, t_{n+2}, \ldots$ in the usual way and decrypt all future ciphertexts that are sent.

However, we can show that the attacker learns no information about $t_{1}, \ldots, t_{n}$ from $s_{n}$, which implies that the previous ciphertexts remain safe. By compromising the key $s_{n}$, the adversary only compromises the security of future messages, but not past messages. Sometimes this property is called forward secrecy, meaning that messages in the present are protected against a key-compromise that happens in the future.

This construction is called a ratchet, since it is easy to advance the key sequence in the forward direction (from $s_{n}$ to $s_{n+1}$ ) but hard to reverse it (from $s_{n+1}$ to $s_{n}$ ). The exercises explore the problem of explicitly reversing the ratchet, but the more relevant property for us is whether the attacker learns anything about the ciphertexts that were generated before the compromise.

Claim 5.10

If the symmetric ratchet (Construction 5.9) is used with a secure PRG $G$ and an encryption scheme $\sum$ that has uniform ciphertexts (and $\left.\sum . \mathcal{K}=\{0,1\}^{\lambda}\right)$, then the first $n$ ciphertexts are pseudorandom, even to an eavesdropper who compromises the key $s_{n}$.

Proof

We are considering an attack scenario in which $n$ plaintexts are encrypted, and the adversary sees their ciphertexts as well as the ratchet-key $s_{n}$. This situation is captured by the following library:

As we have seen, the shaded box (the process that computes $t_{1}, \ldots, t_{n}$ from $s_{0}$ ) is actually a PRG. Let us rewrite the library in terms of this $\mathrm{PRG} H_{n}$ :

Now, we can apply the PRG security of $H_{n}$ and instead choose $t_{1}, \ldots, t_{n}$ and $s_{n}$ uniformly. This change is indistinguishable, by the security of the PRG. Note that we have not written out the standard explicit steps (factor out the first two lines of ATTACK in terms of $\mathcal{L}_{\text {prg-real }}$, replace with $\mathcal{L}_{\text {prg-rand, }}$, and inline).

At this point, the encryption scheme is being used "as intended" meaning that we generate its keys $t_{i}$ uniformly/indepenendtly, and use each key only for one encryption and nothing else. Formally speaking, this means we can factor out the body of the for-loop in terms of $\mathcal{L}_{\text {ots } \$-r e a l:}$

We can now replace $\mathcal{L}_{\text {ots\$-real with }} \mathcal{L}_{\text {ots\$-rand }}$ and inline the subroutine (without showing the intermediate library). The result is:

This final library is indistinguishable from the first one. As promised, we showed that the attacker cannot distinguish the first $n$ ciphertexts from random values, even when seeing $s_{n}$.

This proof used the uniform-ciphertexts property, but the same logic applies to basically any encryption property you care about - just imagine factoring out the encryption steps in terms of a different library than $\mathcal{L}_{\text {ots\$-real. }}$.

Search

Construction \(5.9\) (Symm Ratchet)

Claim 5.10