Breaking Provably Secure Schemes: OCB2

Applied Cryptography

These slides are from a lecture I designed and repeatedly gave in the course on Applied Cryptography at TU Eindhoven.

It was placed as the second lecture in the course, to be given in the same weak as the first one, that was meant to introduce provable security and the random oracle model. The idea here was to first introduce the students to security proofs and show them how they are important, only to then demonstrate on a high-profile example, that proofs can very much still be wrong.

Also note that I gave the lecture in a classroom with a blackboard, where it was far easier to explain some of the more technical things; the recording I provide here did not have that benefit and also lacks tracking of any pointers, making especially the explanation of some of the more technical mathematical aspects less ideal. Still though: This is primarily a slide-show and a lot of information was meant to be passed via the spoken word, so I would generally still reocmmend to view it in slide-show mode with the recording. (I don’t have captions as of now, and given that this is a full hour recording, I won’t make any promises for how soon (if ever) they’ll be available. Sorry.)

Overview

I am only providing the slides for the second lecture here, since the slides for the first lecture are not mine, but Andreas Hülsing’s who was (and is) the responsible professor for the overal course; that said, I understand that this creates the somewhat unfortunate situation that the following slides might assume more previous knowledge than would be ideal, but it is what it is…

Last Time: Proofs are important

Allow quick development of protocols
Focuses cryptanalytic research on fewer targets.
Enforces the use of formal security statements

Today: Proofs are not a silver Bullet

Are the assumptions true?
Are the assumptions used correctly?
Does the proof really say what you think it does?
Is the proof itself correct?

Blockciphers and Modes

Take a key $k \in \mathbb{B}^\lambda$ and a message-block $m \in \mathbb{B}^n$ and return a ciphertext-block $c \in \mathbb{B}^n$ . ( $\mathbb{B} := \{0,1\}$ )

A message is fed into a blockcipher and transformed into a ciphertext; the blockcipher also receives a key that may, but does not have to be of the same length.

“Keyed Permutation” or “PseudoRandom Permutation” (PRP)
If $k$ is unknown, its associated permutation should be indistinguishable from a truly random permutation.

Formal Definition (for Completeness)

PRP-security in the CPA setting:

$\forall \mathcal{A} \in \mathrm{PPT}: \left| \begin{array}{l} \Pr\left[\mathcal{A}^{E_k(\cdot)}(1^\lambda) \Rightarrow 1 \middle|k \leftarrow \mathbb{B}^\lambda\right]\\ -\Pr\left[\mathcal{A}^{\pi(\cdot)}(1^\lambda)\Rightarrow 1\middle|\pi \leftarrow \Pi\right] \end{array} \right| < \mathrm{negl}(\lambda)$

PRP-security in the CCA setting:

$\forall \mathcal{A} \in \mathrm{PPT}: \left| \begin{array}{l} \Pr\left[\mathcal{A}^{E_k(\cdot), D_k(\cdot)}(1^\lambda) \Rightarrow 1 \middle|k \leftarrow \mathbb{B}^\lambda\right]\\ -\Pr\left[\mathcal{A}^{\pi(\cdot), \pi^{-1}(\cdot)}(1^\lambda)\Rightarrow 1\middle|\pi \leftarrow \Pi\right] \end{array} \right| < \mathrm{negl}(\lambda)$

Not an Encryption Scheme! Merely a building-block.

Modes: ECB

Also Tux, but every equal run of four pixels is replaced with a pseudorandom sequence; the image is still highly recognizable however, because large areas that have the same color in the plaintext still look quite flat in the ciphertext. — After Encryption with AES in ECB-mode.

Modes: CTR

An image that seems to purely consist of random noise — But this time encrypted with Counter-Mode

Modes: CTR

a mostly black image with a white gnu in the bottom center — Let’s XOR a gnu on top of the ciphertext

A ciphertext that looks like before — The result still looks random.

Modes: CTR

The same image of Tux as before, but with a clearly recognizable black gnu on his belly. — But once we decrypt…

Modes

Blockciphers are not encryption-schemes!
- If someone tells you “We encrypt everything with AES”, look for penguins.
Secure modes are important and non-trivial!
Confidentiality alone is usually not enough!
- IND-CPA + MAC sometimes works, but we can do much better…

AE(AD)

Authenticated Encryption (with Associated Data)

Ciphertext does not reveal information about the plaintext
- except for its length
- even with an encryption (and a decryption) oracle
- even if the adversary chooses the nonces

It is impossible to create a valid ciphertext without knowledge of the key
- even with an encryption and a decryption oracle

Essentially IND$-CPA + EU-CMA
- IND$-CPA $\approx$ IND-CPA with adversarially chosen nonces.
- Combined these also imply CCA-security

Formal Definition of Confidentiality

$\begin{align*} &\forall \mathcal{A} \in \mathrm{PPT}:\\ &\left|\begin{array}{l} \Pr\left[\mathcal{A}^{\mathsf{Enc}_K(\cdot,\cdot,\cdot)}(1^\lambda) \Rightarrow 1\middle|K \leftarrow \mathbb{B}^\lambda\right]\\ -\Pr\left[\mathcal{A}^{\$(\cdot,\cdot,\cdot)}(1^\lambda) \Rightarrow 1\right]\\ \end{array}\right|< \mathrm{negl}(\lambda) \end{align*}$

(Every oracle query must use a fresh nonce!)

For CCA-Security add a decryption-oracle. (Thanks to the authenticity it will however answer all fresh queries with ⊥)

Formal Definition of Authenticity

$\begin{align*} &\forall \mathcal{A} \in \mathrm{PPT}:\\ &\Pr\left[\mathsf{Dec}_K(c^*) \neq \bot \middle|\begin{array}{l} K \leftarrow \mathbb{B}^\lambda\\ c^* := \mathcal{A}^{\mathsf{Enc}_K(\cdot,\cdot,\cdot)}(1^\lambda)\\ c^* \notin \{\text{oracle-responses}\} \end{array}\right]< \mathrm{negl}(\lambda) \end{align*}$

(Every oracle query must use a fresh nonce!)

Offset Codebook Mode 2 (OCB2)

Invented by Phil Rogaway
ISO-standard
Little use in standardized internet-protocols due to patents
Nonce instead of random IV
$\approx$ 1 blockcipher application per $n$ bits of message.
Almost no overhead beyond that.

Tweakable Blockcipher

Similar to regular blockciphers, but take an additional tweak.
Indistinguishable from a random permutation per tweak and per key.

Indistinguishability in the CCA setting: $\begin{align*} &\forall \mathcal{A} \in \mathrm{PPT}:\\ &\left| \begin{array}{l} \Pr\left[\mathcal{A}^{E_k(\cdot,\cdot), D_k(\cdot,\cdot)}(1^\lambda) \Rightarrow 1 \middle|k \leftarrow \mathbb{B}^\lambda\right]\\ -\Pr\left[\mathcal{A}^{f(\cdot,\cdot), f^{-1}(\cdot,\cdot)}(1^\lambda)\Rightarrow 1\middle|f \leftarrow \mathsf{PermFam}(\mathcal{T}, n)\right] \end{array} \right| < \mathrm{negl}(\lambda) \end{align*}$

$\mathsf{PermFam}(\mathcal{T}, n)$ samples a random permutation $f(t, \cdot)$ for each $t \in \mathcal{T}$ .

(For just CPA simply remove the decryption-oracles.)

XEX and XE

Let $\alpha_1,\dots,\alpha_k \in \mathbb{F}_{2^n}^{\times}$ be primitive elements.
Let 𝕀:=𝕀1×…×𝕀k\mathbb{I} := \mathbb{I}_1 \times\dots\times\mathbb{I}_k with 𝕀i⊂ℤ\mathbb{I}_i \subset \mathbb{Z} so that:
- ∄(i1,…,ik),(i′1,…,i′k)∈𝕀\nexists (i_1,\dots,i_k) ,(i'_1,\dots,i'_k) \in \mathbb{I} so that:
  - $(i_1,\dots,i_k) \neq (i'_1,\dots,i'_k)$ and $\prod_{j=1}^{k} \alpha_j^{i_j} = \prod_{j=1}^{k} \alpha_j^{i'_j}$

let $N \in \mathbb{B}^n$ be a Nonce.
Compute $L := \mathsf{Enc}_k(N)$
Compute $\Delta := L \cdot \alpha_1^{i_1} \cdot \dots \cdot \alpha_k^{i_k}$

Define $\mathsf{XE.Enc}_k(m, N, i) := \mathsf{Enc}_k(\Delta \oplus m)$
Define $\mathsf{XE.Dec}_k(c, N, i) := \Delta \oplus \mathsf{Dec}_k(c)$

Define $\mathsf{XEX.Enc}_k(m, N, i) := \Delta \oplus \mathsf{Enc}_k(\Delta \oplus m)$
Define $\mathsf{XEX.Dec}_k(c, N, i) := \Delta \oplus \mathsf{Dec}_k(\Delta \oplus c)$

OCB2

Proof

Large difference between protocol and security game

→ “Game Hopping”

XE is a CPA-secure tweakable blockcipher

$\mathcal{A}$ always gets access to an (encryption-) oracle. The specific oracle is replaced multiple times:

Game 1: XE with actual blockcipher
Game 2: XE with a truly random permutation
Game 3: XE with a truly random function
Game 4: Truly random function
Game 5: Truly random permutation per tweak

Let $p_i$ be the probability that $\mathcal{A}$ outputs 1 in game $i$ .

Goal: $|p_5 - p_1| < \mathrm{negl}(\lambda)$

From XE[Blockcipher] to XE[Random Permutation]

Claim: $|p_2 - p_1| \leq \mathsf{Adv}_E^{\mathrm{PRP}}(t', 2q)$

Replace all computations of the blockcipher with calls to the PRP-oracle.
If the PRP-challenger presents us the real blockcipher, this is identical to game 1.
If it presents the truly random permutation, this is identical to game 2.
If the CPA-attacker changes its behaviour between these to game, we can use that to distinguish between them.

⇒ $|p_2 - p_1|$ is bounded by the achievable advantage over the security of $E$ in the PRP-game!

From XE[Random Permutation] to XE[Random Function]

Claim: $|p_3-p_2| \leq \frac{2q^2}{2^n}$

Only different if a collision occurs
Outputs are truly random.
With $2q$ calls and blocksize of $n$ bits the probability for a collision is at most $\frac{1}{2} \cdot \frac{2q(2q-1)}{2^n} \leq \frac{2q^2}{2^n}$

⇒ Since the number of oracle queries ( $2q$ ) is at most polynomial whereas $2^n$ is exponential in the security parameter, this is negligible.

From XE[Random Function] to Random Function

Then a miracle occurs…

It provides us with $|p_4-p_3| \leq \frac{2q^2}{2^n}$

From Random Function to Random Permutation

Claim: $|p_5-p_4| \leq \frac{0.5q^2}{2^n}$

Like second hop, just the other way around.

Putting it all together.

$\begin{align*} |p_5-p_1| &\leq |p_5-p_4| + |p_4-p_3| + |p_3-p_2| + |p_2-p_1|\\ &\leq \frac{2q^2}{2^n} + \frac{2q^2}{2^n} + \frac{0.5q^2}{2^n} + \mathsf{Adv}_E^{\mathrm{PRP}}(t', 2q)\\ &= \frac{4.5q^2}{2^n} + \mathsf{Adv}_E^{\mathrm{PRP}}(t', 2q) \end{align*}$

⇒ Since both of these are by assumption negligible, XE with a secure blockcipher provides a secure tweakable blockcipher in CPA settings.

XEX and XEX*

The proof for XEX is similar

Proof by analogy is fraud. - Bjarne Stroustrup

XEX* provides the adversary with an encryption and a decryption oracle.
- Add $b \in \mathbb{B}$ to the tweak
- If $b = 0$ , use XE for CPA-security otherwise XEX for CCA-security
- forbidden to query both $(0, N, T)$ and $(1, N, T)$
- forbidden to query decryptions with $b = 0$ .

XEX*

Game 1: XEX* with regular blockcipher: $p_1 := \Pr\left[\mathcal{A}^{\mathsf{Enc}_K(\cdot,\cdot), \mathsf{Dec}_K(\cdot,\cdot)}(1^\lambda) \Rightarrow 1\middle|K \leftarrow \mathbb{B}^\lambda\right]$
Game 2: XEX* with random permutation: $p_2 := \Pr\left[\mathcal{A}^{\widetilde{\pi}(\cdot,\cdot), \widetilde{\pi}^{-1}(\cdot,\cdot)}(1^\lambda) \Rightarrow 1\middle|\pi \leftarrow \mathsf{Perm}(n)\right]$
Game 3: Random Answers: $p_3 := \Pr\left[\mathcal{A}^{\$(\cdot,\cdot), \$(\cdot,\cdot)}(1^\lambda) \Rightarrow 1\right]$
Game 4: Random permutation per tag: $p_4 := \Pr\left[\mathcal{A}^{f(\cdot,\cdot), f^{-1}(\cdot,\cdot)}(1^\lambda) \Rightarrow 1\middle|f \leftarrow \mathsf{PermFam}(\mathcal{T}, n)\right]$

Hop 1 is pretty much the same as it was with XE, same for Hop 3. Hop 2 is much more complicated and interested students should just read the original paper.

Security of OCB2

Confidentiality

From the original paper:

During the adversary’s attack it asks a sequence of queries $(N^1,M^1),\dots,(N^q, M^q)$ where the $N^i$ -values are distinct. Since the $N^i$ -values are distinct each $\pi_i^N$ and $\widetilde{\pi}_i^N$ that gets used gets used exactly once. We are thus applying a number of independent random permutations each to a single point. The image of a single point under a random permutation is uniform, so the output is perfectly uniform. That is all that is needed to ensure that an adversary has no advantage to distinguish the output from random bits.

Authenticity

More complicated, but similar idea.

Attacking OCB

Akiko Inoue and Kazuhiko Minematsu Enter the Stage

Let $M := \mathrm{len}(0^n) || m_2$ , with $|m_2| = n$ , $A := \epsilon$ , $N$ arbitrary

Use encryption-oracle with $(N, A, M)$ . Receive $C[1] || C[2] || T$

Let $N' := N$ , $A' := A = \epsilon$ , $C' := C[1] \oplus \mathrm{len}(0^n)$ and $T' := M[2] \oplus C[2]$ .

Present $(N', A', C', T')$ to the challenger.

Does this really Work?

$\begin{align*} C[1] &= 2L \oplus E(2L \oplus \mathrm{len}(0^n))\\ C[2] &= M[2] \oplus \mathrm{Pad}\\ &= M[2] \oplus E(2^2L\oplus\mathrm{len}(0^n)) \end{align*}$

$\begin{align*} & C' &= C[1] \oplus \mathrm{len}(0^n)\\ & T' &= M[2] \oplus C[2] \end{align*}$

$\begin{align*} M' &= C' \oplus \mathrm{Pad}'\\ &= C' \oplus E(2L \oplus \mathrm{len}(0^n))\\ &= C[1] \oplus \mathrm{len}(0^n) \oplus E(2L \oplus \mathrm{len}(0^n))\\ &= 2L \oplus E(2L \oplus \mathrm{len}(0^n)) \oplus \mathrm{len}(0^n) \oplus E(2L \oplus \mathrm{len}(0^n))\\ &= 2L \oplus \mathrm{len}(0^n) \end{align*}$

$\begin{align*} T^*&=E(2\cdot3L \oplus \Sigma')\\ &= E(2\cdot3L \oplus M')\\ &= E(2\cdot3L \oplus 2L \oplus \mathrm{len}(0^n))\\ &= E(2^2L \oplus \mathrm{len}(0^n))\\ &= \mathrm{Pad} = M[2] \oplus C[2] = T' \end{align*}$

Preliminary Summary

This is a valid forgery containing a never requested plaintext!

⇒ OCB2 is not a secure authenticated encryption scheme!

What went wrong?

“But there was a proof that it is secure!”

“Since the $N^i$ -values are distinct each $\pi_i^N$ and $\widetilde{\pi}_i^N$ that gets used gets used exactly once.”

“forbidden to query both $(0, N, T)$ and $(1, N, T)$ ”

⇒ Argument was to hand-wavey!

Longer Messages

The first $m-2$ Blocks only xor the checksum with a known value.
Let $C'[m-1] = \sum_{i=1}^{m-2} M[i] \oplus C[m-1] \oplus \mathrm{len}(M[m])$
Let $C'[i] := C[i]$ for $i < m-1$ .
Let $T' = M[m] \oplus C[m]$

Similar workout as before, just more complicated.

Distinguishing attacks

IND-CCA was the result of IND$-CPA + authenticity
It turns out that there is a simple attack

Clark Kent vs Superman: Slightly different looks, still the same person.

⇒ OCB2 is not IND-CCA secure!

Attacks only ever get better: Universal Forgeries

Extract $L$
Compute random input-output-pairs for the blockcipher
Compute specific input-output-pairs for the blockcipher
Compute the ciphertext using the regular algorithm.

⇒ Perfect universal forgeries with at most three oracle-queries!

And better: Plaintext Recovery

Extract $L^*$ with encryption oracle from previous attack
pick random $j, k < m$ .
$C'[j] := C^*[k] \oplus 2^kL^* \oplus 2^jL^*$
$C'[k] := C^*[j] \oplus 2^kL^* \oplus 2^jL^*$
$C'[i] := C^*[i]$ for $i \notin \{j, k\}$
Perform decryption-query with $C'$ .

Profit.

⇒ Full plaintext extraction!

History of the Attacks

OCB2 was widely believed to be secure.

Akiko Inoue and Kazuhiko Minematsu find a small crack that allowed a first attack.
- Published on 26. 10. 2018 → ia.cr/2018/1040

Bertram Poettering discovers universal forgeries
- Published on 8. 11. 2018 → ia.cr/2018/1087

Tetsu Iwata discovers plaintext-recovery
- Published on 11. 11. 2018 → ia.cr/2018/1090

Joined paper (ia.cr/2019/311) wins best paper award at CRYPTO 2019

Conclusions

Even published proofs can be wrong. Always be sceptical!

Hand-wavy arguments can easily be wrong in subtle ways!

Unnecessary complexity (XE vs XEX) is your enemy!

A small cut can turn into a gaping wound very quickly!

Computer Verifiable Proofs

Probably the way to go in the future.
Still no silver bullet, things can and do go wrong there as well.

References

Papers

Rogaway: Efficient Instantiations of Tweakable Blockciphers and Reﬁinements to Modes OCB and PMAC, 2004
Inoue, Iwata, Minematsu, Poettering: Cryptanalysis of OCB2: Attacks on Authenticity and Confidentiality, 2019

Images

Tux: Larry Ewing using GIMP (via)
GNU: CC-SA Aurelio A. Heckert (via)
Jumping Hare: CC-BY-SA by Tim Felce (via)
Flying Gull: Public Domain by unknown author (via)
Bjarne Stroustrup: CC-BY-SA by Julia Kryuchkova (via)
Broken Hand: CC-BY-SA by M.M.Minderhoud (via)
Knights: Monty Python and the Holy Grail (via)
Superman: Warner Bros (via)

Settings

Overview

Last Time: Proofs are important

Today: Proofs are not a silver Bullet

Blockciphers and Modes

Formal Definition (for Completeness)

Modes: ECB

Modes: CTR

Modes: CTR

Modes: CTR

Modes

AE(AD)

Formal Definition of Confidentiality

Formal Definition of Authenticity

Offset Codebook Mode 2 (OCB2)

Tweakable Blockcipher

XEX and XE

XEX and XE

OCB2

Proof

XE is a CPA-secure tweakable blockcipher

From XE[Blockcipher] to XE[Random Permutation]

From XE[Random Permutation] to XE[Random Function]

From XE[Random Function] to Random Function

From Random Function to Random Permutation

Putting it all together.

XEX and XEX*

XEX*

Security of OCB2

Confidentiality

Authenticity

Attacking OCB

Akiko Inoue and Kazuhiko Minematsu Enter the Stage

Does this really Work?

Preliminary Summary

What went wrong?

Longer Messages

Distinguishing attacks

Attacks only ever get better: Universal Forgeries

And better: Plaintext Recovery

History of the Attacks

Conclusions

Computer Verifiable Proofs

References

Papers

Images