Did you know that you can navigate the posts by swiping left and right?
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:
Ci - 1 ⊕ Pi ⊕ Ci - 1 →
(Ci - 1 ⊕ Ci - 1) ⊕ Pi →
0 ⊕ Pi →
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):
C0 | C1
Now let’s construct a ciphertext C’0 like this:
C’0 = C0 ⊕ 00000001 ⊕ 0000000X
Where X is a byte between 0 and 255. Now let’s submit C’0 | C1 to the Oracle and let’s see what will be computed:
C’0 ⊕ D(C1) →
C0 ⊕ 00000001 ⊕ 0000000X ⊕ (P1 ⊕ C0) →
(C0 ⊕ C0) ⊕ 00000001 ⊕ 0000000X ⊕ P1 →
00000000 ⊕ 00000001 ⊕ 0000000X ⊕ P1 →
00000001 ⊕ 0000000X ⊕ P1
Let’s assume that X is the correct guess of the last byte of P1, what will happen in this case? The last byte of P1 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 P1, 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 C1. Now how can we continue to the next byte? By simply following the same logic for the second last byte of C0, like this:
C’0 = C0 ⊕ 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 | C1 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: