How does a padding oracle attack work?

Question

I am unsure of how a padding oracle attack works.

What I am not getting is how changing one bit at one time allows one to exploit(get keys) ASP.NET machines.

Can anyone explain this?

Answer 1

Definitions / Introduction

We define (this is solely for our example):

• $enc()$ and $dec()$ as the encryption and decryption function using CBC mode, with a constant key. any block cipher will do
• $\oplus$ is the XOR operation.
• $n$ the amount of plain text blocks.
• the length of a block in bytes is $16$ (i.e. 128 bit).
• $m_1$ through $m_n$ the plain text blocks.
• $c_0$ through $c_n$ the cipher text blocks, whereas
• $c_0$ is the Initialization Vector (i.e. we have one more block here!).
• for each block, a second index points to the byte, i.e. $m_{1,0}$ is the very first byte of our plain text.
• $x_1$ through $x_n$ are the intermediate decryption values, after $dec()$ and before XOR.
• the single equal sign $=$ is used for assignments, the double equal sign $==$ for comparisons.

To explain what $x$ means, here's the CBC decryption formula again. For each encrypted block $c_i$, we determine $m_i$ by:

$m_i$ = $x_{i} \oplus c_{i-1}$,(and the value $dec(c_0)$ is also named $x_0$)

For the very first block, we use the IV as follows:

$m_0$ = $dec(c_0) \oplus iv$

I recommend taking a quick glance at these images for decryption and encryption (It's not gonna hurt to read the whole Wikipedia Article too).

Scenario

For this attack we need a so called padding oracle, e.g. a web application. This padding oracle accepts arbitrary cipher texts and gives different messages about whether the plain text is invalid or the decryption has failed.

Let's imagine this padding:

For all plain texts the last block is padded to a length of 16 bytes as follows, the end.\xFF\xFF\xFF\xFF\xFF\xFF\xFF\x08. If the last block is 15 bytes long, the padding is simply \x01. If the last block is 16 bytes long, that is if the length of the message is a multiple of 16, then a block of 15 arbitrary values followed by \x10 is appended. This means, the last block is always filled with zero to fifteen \xFF bytes up to the last one, which gives the length of our padding.

After decryption, one might now read the very last byte and cut off the given amount of bytes at the end. A value equals 0 and above 16 is invalid and returns a padding error.

We define the Oracle as follows:

$$ O(c) = \left\{ \begin{array}{l l} 0 & \quad \text{if $c$ has a valid padding and }\\ & \quad \text{decryption yields a well-formed plain text} \\ 1 & \quad \text{if the padding was valid, but the plain text}\\ & \quad \text{was not well-formed (contained \xFF)} \\ 2 & \quad \text{if $c$ has an invalid padding}\\ \end{array} \right. $$

The web application expects plaintext as XML (or JSON or whatever) and will report a different error, when parsing fails. For our simplified scenario, let's just say there exists an evil character the plain text (after removing the padding) must not contain, e.g. \xFF

The attack

For this attack to work you need a valid ciphertext $c$, it is not required to know the correct plaintext value $m$.

We will start decrypting block by block, byte by byte. We start with the very first block and it's last byte.

Let's take the very first two cipher text blocks $c_0c_1$, and send them to the oracle. Since $c_0$ is just the IV, the oracle gets the first block (16 bytes) of plain text. Now, this depends on the value but it's pretty likely that the padding will be wrong, so you'll get a padding error.

Now by XORing the value $j$ from \x00 through \xFF to the very last byte of your $c_0c_1$ block you will get a total set of 256 different results. These results, let's call them $\tilde{C}_j$, make up cipher texts with the last byte in all possible values from \x00to \xFF - randomly distributed though. Sending all of them to the oracle will yield 16 for which $O(\tilde{C}_j) < 2$. This means, that the last byte decrypted to valid bytes like \x01 through \x10. Of these 16 values for $j$, one must correspond to the plain text byte \x10. Bitwise comparison will help you notice, that they all have the very same fifth bit (counting from the right, where the rightmost is 1), except one. The exception results to the one that corresponds to 0x10. Let's memorize this $j$-value as $s$.

Whatever value $s$ has, we can XOR it with \x11, which will then result to the plain text \x01. We now have a block with a valid \x01 padding. (Oh, btw. $s \oplus j$ is the last plain text byte for $c_1$)

Now that we have a block with a valid \x01 padding, we have 15 more bytes to find. We know that whenever we have an invalid byte \xFF in the plain text, the web application will stop and say so. So for now, we can go through each byte and find the plain text as following:

let $c$ be the current block and $p$ the plain text result
for $i$ from 1 to 8 (each byte in the block):
$\quad$ for $j$ from 0 to 255 (all ascii values):
$\quad$ $\quad$ $\hat{c}_{i,j} = c_0c_1...(c_i \oplus j)...c_n$
$\quad$ $\quad$ if $O(\hat{c}_{i,j}) == 1$:
$\quad$ $\quad$ $\quad$ $p_i = j \oplus 0xFF$

Repeat this procedure with block pairs $c_1c_2$, $c_2c_3$, ...

Disclaimer

This is a simplified example and I tried to highlight all simplifications where made. I am by no means a crypto expert and my knowledge is limited. If you find any unmentioned simplifications or plain mistakes, please comment/edit :) I can highly recommend reading a good explanation of the XML Encryption padding oracle in this blog. The paper about the attack is a pretty good read too: Breaking XML Encryption

TODO: This post is lacking a good explanation on why the CBC scheme is malleable and I wouldn't mind if there was a good graph to include.

Answer 2

All the details have been published in the paper from the 2011 IEEE Symposium on Security and Privacy: Cryptography in the Web: The Case of Cryptographic Design Flaws in ASP.NET