8.3: Security of OFB Mode

Last updated
Save as PDF

Page ID: 7385

$ \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}}$

In this section we will prove that OFB mode has pseudorandom ciphertexts (when the blocklength is blen $=\lambda$ bits). OFB encryption and decryption both use the forward direction of $F$, so OFB provides security even when $F$ is not invertible. Therefore we will prove security assuming $F$ is simply a PRF.

Claim 8.5

OFB mode (Construction 8.4) has CPA$ security, if its underlying block cipher $F$ is a secure PRF with parameters in $=$ out $=\lambda$

Proof

The general structure of the proof is very similar to the proof used for the PRF-based encryption scheme in the previous chapter (Construction 7.4). This is no coincidence: if OFB mode is restricted to plaintexts of a single block, we obtain exactly Construction 7.4!

The idea is that each ciphertext block (apart from the IV) is computed as $c_{i}:=r \oplus m_{i}$. By the one-time pad rule, it suffices to show that the $r$ values are independently pseudorandom. Each $r$ value is the result of a call to the PRF. These PRF outputs will be independently pseudorandom only if all of the inputs to the PRF are distinct. In OFB mode, we use the output $r$ of a previous PRF call as input to the next, so it is highly unlikely that this PRF output $r$ matches a past PRF-input value. To argue this more precisely, the proof includes hybrids in which $r$ is chosen without replacement (before changing $r$ back to uniform sampling).

The formal sequence of hybrid libraries is given below:

	The starting point is $\mathcal{L}_{\text {cpa\$-real }}^{\text {OFB }}$, shown here with the details of OFB filled in.
	The statements pertaining to the PRF $F$ have been factored out in terms of $\mathcal{L}_{\mathrm{prf-real}}^{F} \cdot$.
	$\mathcal{L}_{\text {prf-real }}^{F}$ has been replaced by $\mathcal{L}_{\text {prf-rand }}^{F}$. By the PRF security of $F$ the change is indistinguishable.

Next, all of the statements that involve sampling values for the variable $r$ are factored out in terms of the $\mathcal{L}_{\text {samp-L }}$ library from Lemma 4.11:

$\mathcal{L}_{\text {samp-L }}$ is then replaced by $\mathcal{L}_{\text {samp-R. By Lemma }} 4.11$, this change is indistinguishable:

Arguments to LOOKUP are never repeated in this hybrid, so the middle library can be significantly simplified:

Next, $\mathcal{L}_{\text {samp-R}}$ is then replaced by $\mathcal{L}_{\text {samp-L. By Lemma }} 4.11$, this change is indistinguishable:

Subroutine calls to LOOKUP and SAMP are inlined:

Finally, the one-time pad rule is applied within the for-loop (omitting some common steps). Note that in the previous hybrid, each value of $r$ is used only once as a one-time pad. The $i=0$ case has also been absorbed into the for-loop. The result is $\mathcal{L}_{\text {cpa\$-rand }}^{\text {OFB }}$, since OFB encrypts plaintexts of $\ell$ blocks into $\ell+1$ blocks.

The sequence of hybrids shows that $\mathcal{L}_{\text {cpa\$-real }}^{\text {OFB }} \approx \mathcal{L}_{\text {cpa\$-rand }}^{\text {OFB }}$, and so OFB mode has pseudorandom ciphertexts.

We proved the claim assuming $F$ is a PRF only, since OFB mode does not require $F$ to be invertible. Since we assume a PRF with parameters in $=$ out $=\lambda$, the PRP switching lemma (Lemma 6.7) shows that OFB is secure also when $F$ is a PRP with blocklength $n=\lambda$.

	The starting point is \(\mathcal{L}_{\text {cpa\$-real }}^{\text {OFB }}\), shown here with the details of OFB filled in.
	The statements pertaining to the PRF \(F\) have been factored out in terms of \(\mathcal{L}_{\mathrm{prf-real}}^{F} \cdot\).
	\(\mathcal{L}_{\text {prf-real }}^{F}\) has been replaced by \(\mathcal{L}_{\text {prf-rand }}^{F}\). By the PRF security of \(F\) the change is indistinguishable.