See the code in its entirety here.
This code exploits a "padding oracle" in order to decrypt a ciphertext encrypted with AES-128 in CBC mode.
The oracle decrypts a ciphertext and then determines if the resulting plaintext has valid PKCS#7 padding. This may seem innocent, but because an attacker can provide arbitrary text to the oracle, it can actually provide sufficient information to decrypt a ciphertext without knowledge of the key.
Each block of ciphertext is first decrypted with the key, then XORed with the preceding block of ciphertext (except the first block, which is XORed with the initialization vector) to produce the corresponding plaintext block.
This yields an intermediate block that exists between the decryption and XOR step for each block:
decrypt(ciphertext_block, key) = intermediate_block
This intermediate block is of interest because:
previous_ciphertext_block XOR intermediate_block = plaintext_block
Thus, if the value of intermediate_block is known, then it's possible to calculate the plaintext.
The value of intermediate_block is not normally exposed, but it turns out that a padding oracle can be used to do just that.
Consider a 2-block long ciphertext. The first block is some arbitrary text under our control. We'll manipulate this block to decrypt the second block byte-by-byte.
When this 2-block ciphertext is passed to the oracle, each block is decrypted separately. The decryption of the first block is irrelevant; we're interested in the steps involved in decrypting the second block:
intermediate_block = decrypt(second_block, key)
plaintext_block = intermediate_block XOR controlled_block
Notice that intermediate_block is XORed with the block we control. This means we can modify the value of controlled_block to produce different plaintext_block values.
To determine the value of the intermediate block, we rely on the fact that in order for PKCS#7 padding to be valid, the value of each padding byte is predictable. For example, a 13-byte plaintext will be padded with "\x03\x03\x03".
What would it suggest if we passed the oracle a 2-block ciphertext as described above and it returned true?
-
We know the value of the padding bytes in the plaintext (because PKCS#7 padding is predictable)
-
We can calculate the value of the corresponding bytes in
intermediate_blockdue to the inverse nature of the XOR operation. We know thatplaintext_block[i] = intermediate_block[i] XOR controlled_block[i]so...
intermediate_block[i] = plaintext_block[i] XOR controlled_block[i]
Recall that plaintext_block is calculated by XORing corresponding bytes from intermediate_block and controlled_block.
So for the padding oracle to return true, controlled_block[i] needs to be a value, such that when XORed with intermediate_block[i], the operation yields a valid padding byte.
Consider this 2-block ciphertext controlled_block || target_block where target_block is the block to decrypt.
To calculate the last byte of target_block, we need to discover what value for controlled_block[15] would make the corresponding byte of the plaintext be a valid padding byte.
We control controlled_block, so we can use trial and error to change the value of controlled_block[15] until the padding oracle indicates that the padding is valid. We'll try all ASCII characters.
Once the padding oracle returns true, we can use the value of controlled_block[15] to calculate the value of intermediate_block[15] as described above.
for b := 0; b <= 256; b++ {
controlled_block[15] = byte(b)
// Append the targeted block to controlled, so that it is the second block
// of our feigned ciphertext. The intermediate block created during the
// decryption step for the target block will be XORed with the block we control.
controlled := append(controlled, target_block...)
valid, _ := crypto.CbcPadingOracle(controlled_block, iv)
if valid {
intermediate_block[15] = paddingByte ^ controlled_block[15]
break
}
}Once we know the value of intermediate_block[15], we have all the necessary information for calculating plaintext_block[15].
We then do the exact operation that would take place within a CBC decrypt function if we had access to the key. We XOR intermediate_block with the block from the original ciphertext that precedes the target block.
plaintext_block[15] = intermediate_block[15] ^ previous_block[15]
So far we've only calculated the last byte of the target block. Calculating the other bytes is nearly the same as solving the first: cycle through all possible bytes for the targeted byte in the controlled block, append the target block to the controlled block, pass that to the oracle, and if the oracle returns true, then we've found the right byte.
For every byte except the last byte of target_block, the resulting plaintext will require multiple bytes of valid padding in order for the oracle to return true.
Let's say we want to decrypt the 14th byte of target_block. That means in order for the oracle to reveal any useful information about that byte, the decrypted text must end with 3 bytes of valid padding.
The first of the three bytes is the target byte, so to calculate it, we'll cycle through all of the possible characters exactly like before.
Figuring out the last two padding bytes is quite simple. At this point, we'll have already determined the value of intermediate_block[14] and intermediate_block[15], so we can easily find the last two bytes of controlled_block with that information. In this case, paddingLen = 3.
for j := 1; j < paddingLen; j++ {
controlled[i+j] = paddingByte ^ intermediate[i+j]
}We repeat this process for every byte in the block, using an increasing number of padding bytes until target_block[0] is the target and we need to calculate 16 bytes of padding.
Repeat for each block.
* Note, in a realistic situation, the IV is unknown to the attacker, so the attacker wouldn't be able to decrypt the first block of the ciphertext. My implementation incorporates the IV for the sake of demonstration.