Cryptopals Set 3 Challenge 17: The CBC padding oracle (Cpp solution)

A proof of concept of the best-known attack on modern block-cipher cryptography, the attack has the name "CBC padding oracle" and it shows how to break and AES Chain Block Cypher (CBC) in the advent of Challenge 17 Set 3 of Cryptopals.

The setup for this proof of concept is the following, the server allows the following interface to the rest of the world:

Function 1: Selects at random one of 10 strings, generates a random AES key (which it should save for all future encryptions), pads the string out to the 16-byte AES block size, and CBC-encrypts it under that key, providing the caller with the ciphertext and the IV (initialization vector).

Function 2: This function should consume the ciphertext produced by the first function, decrypt it, check its padding and return true or false depending on whether the padding is valid.

Padding in cryptography is the byte stuffing so that the size of the plaintext before encryption is a multiple of the block size (normally 128 bits for AES).

It turns out that it’s possible to decrypt the ciphertexts provided by the first function, the decryption here depends on a side-channel leak by the decryption function. The leak is the error message indicating whether the padding is valid or not.

Using D for decryption and E for encryption, the key idea behind this attack is that the decryption of block n is equal to:

D(block n) = E(block n-1) XOR D(block n)

So the last block depends on the n-1 block; if we want to shift the last byte of the last block, we only have to shift that byte in the previous ciphertext block. We do this until we get a valid padding for the last byte of the last block; probabilistically,  it should be padding 0x1, but we can assure you that it is really that padding forcing a change in the previous byte to exclude a false positive as 0x02 | 0x02 in the last two bytes.

When we got a valid padding in the last block, we know that the padding has to be 0x01, so the plaintext decrypted will be = shift XOR 0x01.

We repeat this process for the next byte, forcing a shift in block n-1 in byte 15, now targeting a padding of 0x02, setting already in the last byte a padding of 0x02.

We repeat this process until we get all the bytes of this block, then we erase this block and start the process again. When we only have one block left, if the server gave us the initialization vector (IV), which in this case is true, we can prepend this IV to the last block and repeat the same process until we have the entire ciphertext decoded.

More graphical information about this algorithm can be found on the NCC group web page:
https://research.nccgroup.com/2021/02/17/cryptopals-exploiting-cbc-padding-oracles/

In terms of defense against this kind of attack, stopping to disclose the type of error by the server would only slow down the attacker, as he could still use timing attacks to decide if the error was on the padding or on the mac code, for example.

To really stop the attacker, we should authenticate the ciphertext by switching for example, to Galois/Counter Mode (GCM) or Offset Codebook Mode (OCB) or keeping the CBC but making an authentication with, for example, a Hash-Based Message Authentication mode (HMAC).

More info of this challenge at Cryptopals page:
https://cryptopals.com/sets/3/challenges/17

Source code link:
https://github.com/Photon-einstein/Cryptopals/tree/main/Cryptopals_resolutions/3-Set_3/cryptopals_set_3_problem_17

Diagram Class of the Solution:
https://github.com/Photon-einstein/Cryptopals/blob/main/Cryptopals_resolutions/3-Set_3/cryptopals_set_3_problem_17/Class_diagram.pdf

#cryptography #cpp #cryptopals #aes #cbc #openssl