Previously, we explored how to forge a legitimate signature by intercepting a signed message, its authentic signature, and the length of the key used to sign it. Today, we’ll discuss how to decrypt ciphertexts without having knowledge of the key used to encrypt the original plaintext. All that is required to achieve this is for a decryption module to reveal whether the padding of the ciphertext being decrypted has valid padding or not. This seemingly innocuous vulnerability is known as the Padding Oracle Attack and can completely compromise your cryptographic security.
The Padding Oracle, in this case, is the decryption module responsible for leaking the aforementioned information. This attack was initially introduced by Vaudenay and is categorized as a side-channel chosen-ciphertext attack that targets the Cipher Block Chaining (CBC) mode and the Public Key Cryptography Standards #7 (PKCS7) padding scheme. Side-channel attacks exploit vulnerabilities that are present in the implementation of a cryptosystem, whereas chosen-ciphertext attacks allow the attacker to submit chosen ciphertexts and decrypt them using a cryptosystem. In order to understand how this attack works, we must first understand how CBC and PKCS7 operate.
Encryption and decryption are primarily based on Block Ciphers. These ciphers can be thought of as black boxes that take in a fixed-length key and a fixed-length block of plaintext/ciphertext as input and produce the corresponding block of ciphertext/plaintext. However, since these black boxes have fixed-length inputs, we need to find a way to combine them to enable the encryption/decryption of inputs of arbitrary size. This is where Block Cipher Modes come in, with CBC being the most widely used mode.
When using a block cipher in CBC mode to encrypt plaintext, the plaintext input of each block is XOR-ed with the ciphertext output of the previous block cipher. This process ensures that even the slightest modification in the plaintext input will affect all the subsequent blocks except for the block itself. In the case of the first block, a random block, called an Initialization Vector (IV), is XOR-ed with the plaintext of the first block before it’s encrypted.
To help visualize this process, consider the following illustration:
To decrypt a ciphertext that was generated using CBC, you must XOR the output of the current block cipher with the ciphertext of the previous block. This step essentially cancels out the encryption’s XOR operation of the previous block cipher’s ciphertext:
Ci - 1 ⊕ Pi ⊕ Ci - 1 →
(Ci - 1 ⊕ Ci - 1) ⊕ Pi →
0 ⊕ Pi →
A padding scheme is necessary to construct inputs that are evenly divisible by the block size, since Block Ciphers operate exclusively on fixed-size blocks. The PKCS7 padding scheme is straightforward: the last N bytes are padded with the value N. For instance, suppose we wish to pad the string “Hello, world” with a block size of 16 bytes; in that case, four 4s will be added to the end of the string as padding:
# 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 understand what CBC and PKCS7 are, let’s examine some 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), and that is vulnerable to the Padding Oracle Attack:
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
In the decryption process described above, the final method call verifies the validity of the resulting plaintext’s padding before removing it. If the padding is invalid, an
OpenSSL::Cipher::CipherError will be thrown and this information will be leaked to the caller. This information can be used to exploit the decrypt method as a Padding Oracle. By constructing ciphertexts and submitting them to the Oracle, we can recover the plaintext without having knowledge of the encryption key used to encrypt the intercepted ciphertext.
Suppose we have intercepted a ciphertext of length two blocks, or 32 bytes:
C0 | C1
Next, we will construct a ciphertext, denoted as C’0, using the following method:
C’0 = C0 ⊕ 00000001 ⊕ 0000000X
|Here, X is a byte value ranging from 0 to 255. We will now submit C’0||C1 to the Oracle and observe the output:|
C’0 ⊕ D(C1) →
C0 ⊕ 00000001 ⊕ 0000000X ⊕ (P1 ⊕ C0) →
(C0 ⊕ C0) ⊕ 00000001 ⊕ 0000000X ⊕ P1 →
00000000 ⊕ 00000001 ⊕ 0000000X ⊕ P1 →
00000001 ⊕ 0000000X ⊕ P1
Suppose that we have correctly guessed the value of the last byte of P1 as X. In this case, the XOR operation will nullify the last byte of P1, and append the value 1 to the plaintext, resulting in a valid PKCS7 padding. As a result, the Oracle will not throw an error.
However, if our guess for X is incorrect, the computed plaintext will not have a valid padding, and the Oracle will throw an error.
We can successfully recover the last byte of C1 by trying all possible values of X. To proceed to the next byte, we can apply the same logic to the second-last byte of C0 as follows:
C’0 = C0 ⊕ 00000022 ⊕ 000000YX
|We can repeat the same process for the second-last byte of C0, denoted as Y, where Y can take a value between 0 and 255, and X is the byte that we have previously recovered. Submitting C’0||C1 to the Oracle will give us the same behavior as before, eventually leading to the correct guess for Y. By following this approach, we can recover all the bytes of the block. This process can be applied to every block of the ciphertext, except the first one, which is the Initialization Vector and therefore does not need to be recovered.|
Here is the Ruby code that intercepts a ciphertext and performs the Padding Oracle attack that we discussed 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!!!
You can find the complete source code here.