CTFZone Quals 2019

December 4, 2019

This is a writeup for OCB2. We start off with access to a socket server but no source. Upon connecting, it generates a session key and nonce for OCB2 encryption. Then it offers the following:

The server also gives a sample (nonce, ciphertext, tag) for the help command. Executing it prints a list of commands, including one called flag. Based on this information, our goal is to encrypt the flag command with the session nonce, the catch being the server won’t do that for us.

It’s pretty clear that the challenge is based on an OCB2 universal forgery attack that was discovered in 2018. Although this challenge won’t require a full understanding of it, you should at least be familiar with the mechanics of OCB2 and what they call the ‘Minimal Example of Forgery’ (Attack 4.1).

My writeup won’t show any code (it’s very messy and frankly unreadable), but I’ll say that the pyOCB library is a good resource for solving the challenge.

P.S. My solution is harder than intended. During the competition, I thought that the server would not decrypt using the session nonce at all (in reality, it only blocks the sample help command). So technically the authors could’ve added that limitation and this would still work :p

Leaking nonce offsets

A major aspect of OCB’s design is its use of an offset sequence: 2L, (2^2)L, …, where L = E(N). Its purpose is to mask the true inputs and outputs of the block cipher in the overall scheme.

By following Attack 4.1 from the paper, we can forge a ciphertext with a single encryption query. More importantly, however, is that its corresponding plaintext is 2L ⊕ len(n). Hence, we can leak 2L by decrypting the forgery and XORing the output with len(n).

Emulating the block cipher

In OCB, the first plaintext block is encrypted as C[1] = E(M[1] ⊕ 2L) ⊕ 2L. Since we know 2L, we can control the block cipher E’s input and learn its corresponding output.

If we want to learn E(X), we can set M[1] = X ⊕ 2L to cancel the inner XOR. Then we compute E(X) = C[1] ⊕ 2L to cancel the outer XOR.

The one caveat is that OCB encrypts the last block of the plaintext (regardless of length) in a different manner. Essentially, it acts like a stream cipher such that we can’t control the block cipher’s input. We can avoid this simply by appending a block of junk data. To summarize the process of learning E(X):

Emulating encryption

From here on, N and L refer to the session nonce and offset specifically. Note that L = E(N), so just compute it using the method described above! Now we can fully emulate OCB encryption with the session nonce.

At this point, I tried encrypting the string flag and sent that as a command — only to have the server respond with an error. It turned out that the help command was 73 characters long, so something else was going on.

Partial decryption

As I mentioned before, OCB encrypts the last block of data like a stream cipher. Thanks to that, we can decrypt it by calculating the pad. In the help command, there are four full blocks and a fifth block of 9 bytes. So, the last block’s pad is E(encode(9) ⊕ (2^5)L).

Using this method, I decrypted the final block to ":"help"}, implying the command was a JSON. I also found that sending {"command":"help"} to the server resulted in a missing token error. Based on that, I guessed that all commands required an additional string of secret data.

The final step

One approach to bypass this secret token is to keep the first four blocks of the help command’s ciphertext. Then, append a new block that changes the JSON value to "flag". The only thing left to consider is the forgery’s tag.

A tag T is computed based on a checksum ∑ and m, the number of blocks in the plaintext. When M[m] is not a full block of data, pad consists of the unused pad bytes.

∑ = M[1] ⊕ ... ⊕ M[m] || pad
T = E(∑ ⊕ 3(2^m)L)

Let M, C, ∑ refer to the help command’s respective values. Similarly, let M', C', ∑' refer to that of our new command.

Instead of computing a new tag, we can try keeping it the same by appending two blocks, M'[5] and M'[6], to the first four from the help command. M'[5] changes the JSON string to flag, while M'[6] calibrates ∑' so that tag calculation remains the same.

T = E(∑ ⊕ 3(2^5)L) = E(∑' ⊕ 3(2^6)L)
∑ ⊕ 3(2^5)L = ∑' ⊕ 3(2^6)L

Note that ∑ and ∑' should not be equal because our new command is 6 blocks long. But ∑ and ∑' use the same first four blocks, so we can cancel that.

M[5] || pad ⊕ 3(2^5)L = M'[5] ⊕ M'[6] ⊕ 3(2^6)L

Our two unknowns are M'[5] and M'[6]. Since the plaintext must also be a valid JSON, they should follow the format below, where the * characters are unknown. The wrapping key-value pair maximizes the chance that they constitue valid JSON syntax.

M'[5] = ":"help","a":"**
M'[6] = **************"}

Fortunately, there are just enough unknowns to cover all 16 bytes; we would have to add another block otherwise. The difference between ∑ and ∑' can be found by XORing all known values together.

3(2^5)L ⊕ 3(2^6)L ⊕ M[4] || pad ⊕ ":"help","a":" || "}

The first 14 bytes go to M’[6] and the last 2 go to M’[5]. Thanks to this, the tag remains the same while C' is different.

C' = C[1..4] || E(M'[5] ⊕ (2^5)L) ⊕ (2^5)L
             || E(M'[6] ⊕ (2^6)L) ⊕ (2^6)L

Although this decrypts successfully, the JSON format does not always accept the * bytes. Even so, I found a valid forgery after only a couple sessions — challenge solved!