Motivation

Recently I read the Trail of Bits Crypto 2019 Takeaways blog post. After studying the reference literature, I wanted to implement the attack described in Iwata's Plaintext Recovery Attack of OCB2* [0]. This blog goes over and discusses the implementation.

From the post:

>The Best Paper award went to the Cryptanalysis of OCB2: Attacks on Authenticity and Confidentiality. This amalgamation of three papers released last fall demonstrates attacks against OCB2, an ISO-standard authenticated encryption scheme, for forging signatures on arbitrary messages and full plaintext recovery. This result is especially shocking because all three versions of OCB have been standardized, and were thought to have airtight security proofs. Fortunately, OCB1 and OCB3 are not vulnerable to this attack because it relies on details specific to how OCB2 applies the XEX* mode of operation.

Likewise, the following passage from the winning paper [1] motivated me:

>For our most relevant attacks we have C code that breaks the OCB2 reference implementation [...]

Background

A block cipher encrypts plaintext in fixed-size \(n\)-bit blocks. For example, \(n = 128\) using AES-128. For plaintext exceeding \(n\) bits, the simplest approach is to partition the plaintext into \(n\)-bit blocks and encrypt them one by one [2]. This method is called the electronic code book (ECB) block cipher mode of operation. In contrast, offset code book 2 (OCB2) is another mode of operation. Precisely, OCB2 [3] is a symmetric-key nonce-based authenticated encryption with associated data (AEAD) block cipher mode. OCB2 appeared at ASIACRYPT 2004 and is standardized(\(\dagger\)) as ISO/IEC 19772:2009.

Algorithms of OCB2

Given a plaintext message (\(M\)), associated data (\(A\)), nonce (\(N\)), and key (\(K\)), the OCB2 encryption function returns a ciphertext (\(C\)) and authentication tag (\(T\)). Vice versa, given a ciphertext, associated data, nonce, and key, the OCB2 decryption function produces plaintext. If the authentication tag is not valid for the ciphertext, associated data, nonce, and key, then the decryption function indicates failure \((\bot)\).

The specifications of the OCB2 encryption and decryption algorithms above are derived from [3]. Note that the details of the parellelizable message authentication code (PMAC) and length functions are not relevant to the attacks.

The goal of OCB2 is that (\(C\)) protects the confidentiality and authenticity of (\(M\)), as well as the authenticity of (\(A\)). Confidentiality can be defined as indistinguishability from random bits. This means an attacker cannot distinguish OCB2 output from an equal amount of random bits. In addition, the authenticity of the cipher refers to the authenticity of ciphertexts [4]. In other words, an attacker is unable to produce valid nonce-ciphertext pairs not already obtained.

OCB2 and AES-128

To build the OCB2 and AES-128 reference implementations:

1. Obtain their source code.

$ wget https://web.cs.ucdavis.edu/~rogaway/ocb/ocb-ref/rijndael-alg-fst.{c,h}
$ wget https://web.cs.ucdavis.edu/~rogaway/ocb/ocb.{c,h}

2. Compile.

$ gcc ocb.c rijndael-alg-fst.c -o ocb

3. Execute. The following is abbreviated test vector output using the reference OCB2 encryption and decryption functions. Note that in this case the additional data is denoted by (H).

$ ./ocb 
...
H : 000102030405060708090A0B0C0D0E0F101112131415161718191A1B1C1D1E1F2021222324252627
M : 000102030405060708090A0B0C0D0E0F101112131415161718191A1B1C1D1E1F2021222324252627
C : F75D6BC8B4DC8D66B836A2B08B32A6369F1CD3C5228D79FD6C267F5F6AA7B231C7DFB9D59951AE9C
T : 65A92715A028ACD4AE6AFF4BFAA0D396
...

Breaking OCB2

On October 2018, Inoue and Minematsu published a fast attack [1] that broke the authenticity of OCB2. In [2], Poettering expanded on the observations and broke the notion of confidentiality using a theoretical approach. By November 2018, in [3], Iwata undermined OCB2 confidentiality by showing a practical plaintext recovery attack. As stated above, [4] is the amalgamation of the papers.

Attacks on Authenticity

In [1, § 4.1] Inoue and Minematsu described four attacks on authenticity. Using an adversarial game between attacker and challenger, in [2, § 3.1 (Fig. 3)] Poettering formalized their minimal attack in relation to an adversary (\(\mathcal{A})\). Summarized below, the game assumes access to encryption (\(\mathcal{E})\) and decryption (\(\mathcal{D)}\) oracles.

The game above constructs an example of an unauthentic, yet valid ciphertext \(C'\). Note that \(C' \ne C \) because they have different lengths. See steps (2) and (5) above. Thus, a successful forgery is implied if the ciphertext is accepted by the decryption oracle. In fact, Inoue and Minematsu show in [5, § 4.1] that \(T'\) is always accepted as valid. In the context of the adversarial game, \(Adv^{int}(\mathcal{A}) = 1\). In other words, the adversary breaks authenticity with probability \(1\) and a nonce-ciphertext pair that the adversary did not possess is obtained.

The following is output from Inoue and Minematsu's implementation found within the appendices of [1].

Test for minimal attack 
Encryption query:
 Nonce: 000102030405060708090A0B0C0D0E0F
 Plaintext: 0000000000000000000000000000008000000000000000000000000000000000
 AD: 
 Ciphertext: 713F06475FB9F34089FFC8DAAE1C370CCD6E6EB9ED7E4B79046246B2923F8B35
 Tag: 89B544765C609A07D81D62148CD21E4D
Decryption query (forgery):
 Forged Nonce (the same as encryption): 000102030405060708090A0B0C0D0E0F
 Forged AD (empty): 
 Forged Ciphertext: 713F06475FB9F34089FFC8DAAE1C378C
 Forged Tag: CD6E6EB9ED7E4B79046246B2923F8B35
Tags match: 1.
 Forged Plaintext: 9FDFC45BC1A1458F12F034265483C57C

Here, the decryption oracle also reveals the block \(L=E(N)\) and the forged plaintext \(M' = 2L \oplus len(0^n)\). OCB2 treats blocks in the domain \(\mathcal{M} = \{0,1\}^n\) of its block cipher as a finite field. Each block is a polynomial over the field \(GF(2^{128})\). To derive \(L\), note that \(E(N) = L = (M' \oplus len(0^n))/2\). To divide \((M' \oplus len(0^n))\) by \(2\) multiply it by the inverse of the monomial \(2X \in GF(2^{128})\).

The pair (\(N\),\(L\)) is an internal block cipher input-output mapping. At least three additional input-output pairs can be gathered. Note that these mappings don't leak under normal circumstances. The knowledge of \(L\) is leveraged to undermine OCB2 confidentiality.

Attacks on Confidentiality

In [6], Poettering extends the results of Inoue and Minematsu, and shows that OCB2 also admits a distinguishing attack. Thus, in the formal indistinguishability chosen ciphertext attack (IND-CCA) settings, OCB2 does not achieve the confidentiality or privacy notion. In the first version of [6, § 4], Poettering notes that it remains an open question if the approach can also be used to attack OCB2 implementations in real-world environments.

Iwata Plaintext Recovery Attack of OCB2

Iwata showed in [0] that confidentiality is also broken in a practical sense and arbitrary ciphertexts can be decrypted. The crux of the attack is the block-swapping technique introduced by Inoue and Minematsu in [5, § 4.3]. Originally, in the context of an advanced forgery attack, Poettering notes that the technique was first used for plaintext recovery by Iwata. Both Iwata and Poettering seem to have independently discovered plaintext recovery attacks of OCB2. The difference between their technique is the way the adversary learns \(L\).

In the following pseudo code, the attacker's goal is to recover \(M^*\). Note that it also follows the same security model as [0], assumes at least \(m=3\) blocks of plaintext, and access to encryption and decryption oracles. Finally, let \((C^{*},T^{*})\) be the encryption of \((N^*,A^*,M^*)\).

Implementation

The implementation was based on the code supplied in [5] and can be found on Github. While it's straightforward, the reader is encouraged to review it. One function worth noting multiplies a block by the inverse of the monomial \(2X \in GF(2^{128})\). To implement this, we shift the block's representative coefficient vector of bits to the right by \(1\). Polynomials are represented using the block type. Each block is \(16\) bytes or \(128\) bits. The function is presented here for convenience.

void GF2128DivideByTwo(block A, block B) { // A = B*2^{-1} 

 uint8_t bottom_right = B[15] & 1; /* low bit of A */

 A[0] = (B[0] >> 1) ^ (bottom_right * 0x80);

 uint8_t i;
 for (i = 0; i < 15; i++) {
   A[i+1] = (B[i+1] >> 1) | (B[i] << 7);
 }

 if(bottom_right) {
  A[15] ^= 0x43; 
 }
}

Instructions to apply the attack implementation are:

1. Obtain an implementation of the pseudocode above.

$ git clone https://gist.github.com/HAITI/50fb494e449531e51c172aa8e24a9cf3

2. Obtain the reference implementations and apply deltas to OCB2 exposing some internal functions.

$ cd 50fb494e449531e51c172aa8e24a9cf3/ 
$ wget https://web.cs.ucdavis.edu/~rogaway/ocb/ocb-ref/rijndael-alg-fst.{c,h}
$ wget https://web.cs.ucdavis.edu/~rogaway/ocb/ocb.{c,h}
$ patch < ocb.c.patch
$ patch < ocb.h.patch 

3. Compile.

$ gcc -Wall ocb.c rijndael-alg-fst.c OCB2Attack.c -o OCB2Attack 

4. Execute Iwata's attack using "SIXTEENBYTESHERE" as the key (K).

$ ./OCB2Attack 1 "SIXTEENBYTESHERE"
N*: F92B7D06100AD46203B990314628A28F
M*: 414141414141414141414141414141414242424242424242424242424242424243434343434343434343434343434343
Encryption Oracle
N*: F92B7D06100AD46203B990314628A28F
C*: 4C410A19DF0A0FCB5F1106946B80CEB3CEE86E9146ADC69282CA5B34B255C4317EF27F2CF5E4EF702AE740D51DC8D31F
T*: 553CA97C7AA0558CEDE15122C910D87B
Iwata Plaintext Recovery Attack
Inoue Minematsu Minimal Attack
N: 23EE09B7C678B5CE01A2F2315AB97C41
M: 0000000000000000000000000000008000000000000000000000000000000000
Encryption Oracle
C: B34D61A888966251FB16A772764F5F81D38F1949785B20465917DC23E0EA191B
T: B714E61ED1288D2D106A0A9D17E2A9DF
N': 23EE09B7C678B5CE01A2F2315AB97C41
C': B34D61A888966251FB16A772764F5F01
T': D38F1949785B20465917DC23E0EA191B
Decryption Oracle
M': B4AC4F0A0CE15B0526274F8596B1DA9F
C': B34D61A888966251FB16A772764F5F81D38F1949785B20465917DC23E0EA191B
Recover L
N'': 69589E1419C2B60A4C4E9F0B2D63B439
L'': D38F1949785B20465917DC23E0EA191B
M'': 5E354F94E0BC94EEB196287687FC903E00000000000000000000000000000000
Encryption Oracle
Recover L*
C'': DE0CB9261F981E130FFA9E02DB545F3D0B35E2EBF12CC320380DD81122038F27
L*: 79128BB4EF2E5E9FBDD526451A806D8C
C*[1]: 4C410A19DF0A0FCB5F1106946B80CEB3
C*[2]: CEE86E9146ADC69282CA5B34B255C431
C*[3]: 7EF27F2CF5E4EF702AE740D51DC8D31F
C$[i]: 7EF27F2CF5E4EF702AE740D51DC8D31F
C$[j]: D887572B244801D30E348EAAED54A99E
C$[k]: 5A2E33A3BDEFC88AD3EFD30A3481A31C
C$: D887572B244801D30E348EAAED54A99E5A2E33A3BDEFC88AD3EFD30A3481A31C7EF27F2CF5E4EF702AE740D51DC8D31F
Decryption Oracle
M$: 542D7BF820A78503CEBC97DC1D432FED572E78FB23A48600CDBF94DF1E402CEE43434343434343434343434343434343
! M*[1]: 41414141414141414141414141414141
! M*[2]: 42424242424242424242424242424242
! M*[3]: 43434343434343434343434343434343
$ 

References

[0] 2018 Iwata Plaintext Recovery Attack of OCB2*

[1] 2019 Inoue et. al. Cryptanalysis of OCB2: Attacks on Authenticity and Confidentiality

[2] 2001 Menezes et. al. Handbook of Applied Cryptography

[3] 2009 Rogaway Efficient Instantiations of Tweakable Blockciphers and Refinements to Modes OCB and PMAC

[4] 2014 Krovetz-Rogaway RFC 7253: The OCB Authenticated-Encryption Algorithm

[5] 2018 Inoue-Minematsu Cryptanalysis of OCB2

[6] 2018 Poettering Breaking the confidentiality of OCB2