Hi guys in the previous post I discussed the theoretical basis for the vaudenay (or padding oracle attack) , in this one I'm going to share a little script that will help you play around with padding oracles and also manually perform the attack. But first a quick recap!
A padding oracle is a "device" (or for historically correct purposes a stoned virgin trapped in an enclosure) that reports on the correctness of the padding of a piece of cipher-text. We're going to abuse this mechanism in order to decrypt some cipher-text encrypted under a block cipher in CBC mode.
In the previous post we derived an expression that proved we could solve for a byte of plain-text knowing only the cipher-text, here's what it looks like:
In a normal situation you would not get shown the plain-text, I show it here only once the padding is correct because it makes things a little easier to understand, so when you see the plain-text it means somehow the oracle could work with what ever the padding value was.
This is what the oracle replies with when it manages to correctly decrypt some cipher-text, of course you'll notice that there's something off about the cipher text above. Namely, there's a byte missing at [0x00, 0x0f] and the padding has not been removed 0_o. This is because the value we submitted caused final plain-text to have a 0x01 at the end, which is padding scheme talk for 1 byte of padding.
So because the oracle returned a YES for the cipher text value above, we know the following:
which is the value of the padding in the original plain-text (2)! We've just decrypted it without knowing anything about the secret key :).
So continuing the attack, we need to choose values for $c^{'}_{i-1}[15]$ and $c^{'}_{i-1}[16]$ that result in a padding scheme value of 2 meaning we need to end up with 0x02 0x02 in the last block of the final decryption. I've precooked this example and the following cipher text achieves this:
So now we know what the second last byte of the plain-text is, by crunching a couple values:
e' viola! We get another padding value, which is most definitely correct, also corroborating the previous value we decrypted since they should both be 15.
Hopefully this demonstrates this in a good, clear, practical picture :)
Here's the script (feel free to grab it and play around-- that's what she said :):
What is a Padding Oracle?
A padding oracle is a "device" (or for historically correct purposes a stoned virgin trapped in an enclosure) that reports on the correctness of the padding of a piece of cipher-text. We're going to abuse this mechanism in order to decrypt some cipher-text encrypted under a block cipher in CBC mode.
The Theory
In the previous post we derived an expression that proved we could solve for a byte of plain-text knowing only the cipher-text, here's what it looks like:
$p_{i}[j] = k[j] \oplus c_{i -1}[j] \oplus c^{'}_{i-1}[j]$ ...(1)
Where:
- $p_{i}[j]$ is the $j_{th}$ byte of the $i_{th}$ block of plain-text
- $k[j]$ is the $j_{th}$ byte of padding; this value is assumed according to how far into the padding value's we are.
- $c^{'}_{i-1}[j]$ is the $j_{th}$ byte of the $i_{th}$ block of attack controlled cipher text. This is the value we're modifying in order to manipulate the padding value.
- $c_{i-1}[j]$ this is the unmodified value of $c^{'}_{i-1}[j]$, so the original value of the byte we modify.
The script I've whipped up is included at the bottom of this post, you can grab it after running through this post. But lets get started. Here's the cryptographic primitives for the cipher text we are decrypting
- $K = A^{32}$ , the key is simply a string of A's 36 characters long
- $IV = B^{16}$, the initialization vector is a string of B's 16 characters long
- $P = P^{33}$ the plain-text is a string of P's 33 characters long
So the plaintext, once padded looks like this (in raw hex) (2):
(50 is the hex value of the ASCII value of 'P', and '0f' is 15 in hexadecimal since there are 15 characters of padding added to the plain-text)
and encrypting this under AES in CBC mode gives us the following cipher text (3):
00 01 02 03 04 05 06 07 08 09 0a 0b 0c 0d 0e 0f
00 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50
01 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50
02 50 0f 0f 0f 0f 0f 0f 0f 0f 0f 0f 0f 0f 0f 0f 0f
(50 is the hex value of the ASCII value of 'P', and '0f' is 15 in hexadecimal since there are 15 characters of padding added to the plain-text)
and encrypting this under AES in CBC mode gives us the following cipher text (3):
00 01 02 03 04 05 06 07 08 09 0a 0b 0c 0d 0e 0f
00 2d 62 3e c0 89 ff 30 b0 f4 bd 79 bc 55 22 c2 11
01 b5 36 4a 82 1c 52 76 a5 2d 66 27 40 03 98 7e 90
02 7d b9 4c 90 78 c7 0d 11 92 9e 1f 49 92 5b 09 cc
So we need to decrypt this little piece of cipher text, this means we need to apply formula (1), so then:
So lets guess a couple values:
This guessing continues until you stumble across this cipher-text value (4):
and get a response from the Oracle like the following:- $j$ is 16, since we are starting from the last byte.
- $k[16]$ (for the first round) we will decide is 0x1
- $c_{i-1}[16]$ here is 0x90, check out the cipher text above namely the byte at [01,0f]
- $c^{'}_{i-1}[16]$ will assume values in the following set $\{0x0 ... 0xff\}$
So lets guess a couple values:
 |
| Here I guess values from 0x00 to 0x03 just to demonstrate the process |
00 01 02 03 04 05 06 07 08 09 0a 0b 0c 0d 0e 0f
00 2d 62 3e c0 89 ff 30 b0 f4 bd 79 bc 55 22 c2 11
01 b5 36 4a 82 1c 52 76 a5 2d 66 27 40 03 98 7e 9e
02 7d b9 4c 90 78 c7 0d 11 92 9e 1f 49 92 5b 09 cc
 |
| Correct byte guessed for 0x01,0x0f. You'll notice that the cipher-text includes padding but is missing a byte at the end :) |
This is what the oracle replies with when it manages to correctly decrypt some cipher-text, of course you'll notice that there's something off about the cipher text above. Namely, there's a byte missing at [0x00, 0x0f] and the padding has not been removed 0_o. This is because the value we submitted caused final plain-text to have a 0x01 at the end, which is padding scheme talk for 1 byte of padding.
So because the oracle returned a YES for the cipher text value above, we know the following:
- $k[j]$ is 0x01
- $c_{i-1}[j]$ is 0x90
- $c^{'}_{i-1}[j]$ is 0x9e
This means we can work out what $p_{i}[j]$ is! Lets plug this into formula (1). This is what we get:
$p_{i-1}[16] = $ 0x01 $\oplus$ 0x90 $\oplus$ 0x9e = 0xf
which is the value of the padding in the original plain-text (2)! We've just decrypted it without knowing anything about the secret key :).
So continuing the attack, we need to choose values for $c^{'}_{i-1}[15]$ and $c^{'}_{i-1}[16]$ that result in a padding scheme value of 2 meaning we need to end up with 0x02 0x02 in the last block of the final decryption. I've precooked this example and the following cipher text achieves this:
00 01 02 03 04 05 06 07 08 09 0a 0b 0c 0d 0e 0f
00 2d 62 3e c0 89 ff 30 b0 f4 bd 79 bc 55 22 c2 11
01 b5 36 4a 82 1c 52 76 a5 2d 66 27 40 03 98 73 9d
02 7d b9 4c 90 78 c7 0d 11 92 9e 1f 49 92 5b 09 cc
So now we know what the second last byte of the plain-text is, by crunching a couple values:
$p_{i-1}[15] = $ 0x02 $\oplus$ 0x7e $\oplus$ 0x73 $= $ 0xf
e' viola! We get another padding value, which is most definitely correct, also corroborating the previous value we decrypted since they should both be 15.
Hopefully this demonstrates this in a good, clear, practical picture :)
Here's the script (feel free to grab it and play around-- that's what she said :):
Comments
Post a Comment