**
Did you know that you can navigate the posts by swiping left and right?
**

#crypto #redteam

Last time we saw how to forge a valid signature by intercepting a signed message, its authentic signature and the length of the key that was used to sign it. Today we’ll see how to decrypt ciphertexts, without knowing the key that was used to encrypt the original plaintext. The only mistake that needs to be made, is for a decryption module to leak whether the padding of the ciphertext that is decrypting, has a valid padding or not! Yes, an innocent looking papercut like this, will make your crypto fall completely apart.

In this case, the decryption module that leaks this information is called the Padding Oracle. The Padding Oracle Attack was initially published by Vaudenay and it’s a side-channel chosen-ciphertext attack that works against the Cipher Block Chaining (CBC) mode and the Public Key Cryptography Standards #7 (PKCS7) padding scheme. Side-channel attacks are those that are based on the implementation of a cryptosystem. Chosen-ciphertext attacks on the other hand, are those that enable the adversary to submit chosen ciphertexts and decrypt them using a cryptosystem. In order to understand how the attack works, we need first to understand how CBC and PKCS7 work.

Encryption and decryption work with Block Ciphers in their core. Imagine the Block Ciphers as black boxes, that get as an input a fixed length key, a fixed length block of plaintext/ciphertext and they spit out the corresponding block of ciphertext/plaintext. Since these blackboxes have a fixed length input, we need to somehow combine them, so we can enable the encryption/decryption of arbitrary sized inputs. This is what Block Cipher Modes are about, with CBC being the most popular among them.

When encrypting a plaintext with a block cipher in CBC mode, then the plaintext input of each block is XOR’ed with the ciphertext output of the previous block cipher. That way the slightest change in the plaintext input, will affect all the following blocks of its block, apart from the block itself. In the case of the first block, then a random block (per encryption) called Initialization Vector is used to XOR the plaintext of the first block before it’s encrypted.

Here’s a visualization of the process:

In order to decrypt a ciphertext that was produced using CBC, you need to XOR the ciphertext of the previous block, with the output of the current block cipher. That way you nullify the encryption’s XOR operation of the previous’ block cipher’s ciphertext:

C_{i - 1} ⊕ P_{i} ⊕ C_{i - 1} →

(C_{i - 1} ⊕ C_{i - 1}) ⊕ P_{i} →

0 ⊕ P_{i} →

P_{i}

We need a padding scheme in order to construct inputs that have a length that is divisible by the block size, since the Block Ciphers operate strictly on blocks.
The PKCS7 padding is simple, the last *N* bytes are padded with the value *N*.
For example the padding of *“Hello, world”*, for a block size of 16 bytes will be four 4s appended at its end:

```
# H e l l o , w
0x48 0x65 0x6c 0x6c 0x6f 0x2c 0x20 0x77
o r l d 4 4 4 4
0x6f 0x72 0x6c 0x64 0x04 0x04 0x04 0x04
```

Now that we know what CBC and PKCS7 are, let’s see the vulnerable Ruby code that encrypts and decrypts data using the Advanced Encryption Standard (AES) block cipher, which operates on blocks of 128 bits (or 16 bytes):

```
require 'openssl'
class PaddingOracle
def encrypt(plaintext)
cipher = OpenSSL::Cipher::AES.new(256, :CBC)
cipher.encrypt
@key = cipher.random_key
iv = cipher.random_iv
ciphertext = cipher.update(plaintext) + cipher.final
return iv + ciphertext
end
def decrypt(ciphertext)
decipher = OpenSSL::Cipher::AES.new(256, :CBC)
decipher.decrypt
decipher.key = @key
decipher.iv = ciphertext[0..15]
# The Oracle will leak if whether the padding is correct or not in the .final method
plaintext = decipher.update(ciphertext[16..(ciphertext.length - 1)]) + decipher.final
# No plaintext returned
end
end
```

The call to the *final* method in the decryption above, will also check if the padding of the result plaintext is valid, before removing it.
If the padding is not valid, then a *OpenSSL::Cipher::CipherError* will be thrown and this information will leak to the caller.
As a result, this is the information that we will use in order to use the *decrypt* method as the Padding Oracle.
By submitting ciphertexts that we construct to the Oracle, we’ll manage to recover the plaintext, without knowing the key that was used to encrypt the ciphertext that we intercepted.

Let’s imagine that we intercepted the following ciphertext that has the length of two blocks (32 bytes):

C_{0} | C_{1}

Now let’s construct a ciphertext C’_{0} like this:

C’_{0} = C_{0} ⊕ 00000001 ⊕ 0000000X

Where *X* is a byte between 0 and 255.
Now let’s submit C’_{0} | C_{1} to the Oracle and let’s see what will be computed:

C’_{0} ⊕ D(C_{1}) →

C_{0} ⊕ 00000001 ⊕ 0000000X ⊕ (P_{1} ⊕ C_{0}) →

(C_{0} ⊕ C_{0}) ⊕ 00000001 ⊕ 0000000X ⊕ P_{1} →

00000000 ⊕ 00000001 ⊕ 0000000X ⊕ P_{1} →

00000001 ⊕ 0000000X ⊕ P_{1}

Let’s assume that *X* is the correct guess of the last byte of P_{1}, what will happen in this case?
The last byte of P_{1} will be nullified by the XOR operation and 1 will end up in the end plaintext.
Then the end plaintext will be a valid PKCS7 padding and the Oracle will not throw.
On the other hand, if *X* doesn’t match the last byte of P_{1}, then the padding of the computed plaintext will not be valid, and the Oracle will throw!

By trying all the possible values of *X*, we will successfully recover the last byte of C_{1}.
Now how can we continue to the next byte?
By simply following the same logic for the second last byte of C_{0}, like this:

C’_{0} = C_{0} ⊕ 00000022 ⊕ 000000YX

Where *Y* is again a value between 0 and 255 and *X* is the byte that we recovered earlier.
Now by submitting C’_{0} | C_{1} to the Oracle, we’ll get the same behavior as before and at some point guess the correct value of *Y*.
Like this we can continue and recover all the bytes of the block and of course this can be applied for every block of the ciphertext, except the first one.
But, the first block is the Initialization Vector so we don’t even need to recover it

Here is the Ruby code that intercepts a ciphertext and then performs the attack on the *PaddingOracle* that we saw earlier:

```
plaintext = 'This is a top secret message!!!'
oracle = PaddingOracle.new()
ciphertext = oracle.encrypt(plaintext)
recovered_plaintext = ''
to = ciphertext.length - 1
from = to - 31
while from >= 0
target_blocks = ciphertext[from..to]
i = 15
padding = 0x01
recovered_block = ''
while i >= 0
# For each byte of the block
for c in 0x00..0xff
# For each possible byte value
chosen_ciphertext = target_blocks.dup
# Set the bytes that we have already recovered in the block
j = recovered_block.length - 1
ii = 15
while j >= 0
chosen_ciphertext[ii] = (chosen_ciphertext.bytes[ii] ^ recovered_block.bytes[j] ^ padding).chr
j -= 1
ii -= 1
end
# Guess the i-th byte of the block
chosen_ciphertext[i] = (chosen_ciphertext.bytes[i] ^ c ^ padding).chr
begin
# Ask the Oracle
oracle.decrypt(chosen_ciphertext)
# The Oracle said Yes, move to the next byte
recovered_block = c.chr + recovered_block
next
rescue OpenSSL::Cipher::CipherError
# The Oracle said No, try the next possible value of the byte
end
end
i -= 1
padding += 0x01
end
recovered_plaintext = recovered_block + recovered_plaintext
# Move to the next block
from -= 16
to -= 16
end
puts recovered_plaintext
# This is a top secret message!!!
```

Here is the full source code:

Happy decrypting!