My understanding of the encryption attack on a padding oracle is that the attacker has a set of $P_i$'s and $\operatorname{Dec}(C_i)$'s

I understand that by back calculating the attacker can find out $C_{i-1}$'s because we have

$$P_i = \operatorname{Dec}(C_i) \oplus C_{i-1}$$

This way the attacker can find all the $C_{i-1}$'s, but what happens with the very last $C_i$? Since you're starting from the end and going backwards, it looks like the very last $C_i$ wont get calculated, in which case the attacker isn't able to encrypt all of the message...?

EDIT:

So i've run the decryption attack and obtained all the $Dec(C_i)$' for an intercepted ciphertext (so a bunch of blocks of $C_i$'s). and then using that i have calculated a sample $P_i$. I want to generate my own $P_i$ now and encrypt it. So what i've done is i take each block of my sample $P_i$ and XOR that with $Dec(C_{i-1})$ to get a C_i, however, the issue is that the response doesn't seem to be valid. So doesn't $Dec(C_i)$ directly depend on what $C_i$ is being passed into it? The conclusion i've made is that the $Dec(C_i)$ Value changes based on each block of ciphertext that's being fed into it, so the $C_i$'s that i generated using the previous $Dec(C_i)$'s won't be decrypted correctly, because the actual program computes a new set of $Dec(C_i)$'s and based on those my ciphertext isn't correct ... does that make sense? or am i misunderstanding the whole thing.

• Do you have a reference I could look at? How does the attacker obtain $\operatorname{Dec}(C_i)$ for each $P_i$? – bkjvbx Sep 29 '16 at 13:54

I'm assuming you mean CBC mode, and let's say PKCS7 padding. I haven't heard of this attack before, and can't really find any sources (please link if you have one! How would an attacker end up with the $\operatorname{Dec}(C_i)$'s?), but here's one way to generate a valid ciphertext.

If the attacker is okay with 15 garbage bytes at the end of his message, he could do the following:

Send $IV = C_{i-1}$ and a random ciphertext block $C_r$ to the oracle a bunch of times. For a little more than 1 in 256 times, $C_r$ will end up having valid padding (e.g. 0x01 for PKCS7). The attacker can simply add such a block $C_r$ to the end of his ciphertext ($C_1, \dotsc, C_{i-1}$) to get a valid encrypted message, albeit with (usually) 15 garbage bytes at the end of the decrypted, de-padded message.

• Can you look at my edit, i added more information – Ghazal Sep 29 '16 at 17:34
• @Ghazal: Again, which mode of operation are you talking about? If you are talking about CBC, I think you might be misunderstanding how it works. You can't simply use a decrypted block $P_i \oplus C_{i-1}$ of some intercepted $C_i$, XOR it with new plaintext $P_a$, and expect it to resemble ciphertext $C_a$. If this were possible, the encryption scheme would be horribly broken. As far as I know, generating ciphertext for completely new plaintext is impossible using only a padding oracle (though I am by no means an expert on this subject). However, a bitflipping attack could make some changes. – bkjvbx Sep 29 '16 at 18:14
• @bkjvbx you can easily generate any plaintext using a padded oracle attack if you can also modify the IV. If you can't the first block will be garbage, but the rest can be whatever you wish – SztupY Jul 10 '17 at 14:55
• @SztupY Interesting. Can you elaborate? How can one accomplish this using only a padding oracle and possibly some ciphertext? – bkjvbx Jul 11 '17 at 7:05
• @bkjvbx see my answer – SztupY Jul 11 '17 at 8:58

Assuming $C$ is the cyphertext (with $C_1$ the first and $C_n$ the last block) you wish to obtain from the $P$ plaintext you wish to encode using a padding oracle, and you have $n$ blocks, you have to do the following steps:

1. Generate one random block (which can just be a bunch of $0$'s) of bytes. This will be $C_n$, the last cypherblock. You'll see that it doesn't matter what this last block is, as we can use previous blocks to modify the decrypted value to whatever we wish to as that's part of how CBC works.
2. Loop $i$ down from $n \rightarrow 2$

1. Use the padding oracle attack against $C_i$ to obtain $\operatorname{Dec}(C_i)$
2. Next calculate $P_i \oplus \operatorname{Dec}(C_i)$. The result will be $C_{i-1}$.
3. This works because during CBC, the decryption algorithm will calculate $\operatorname{Dec}(C_i) \oplus C_{i-1} == P_i$, which is actually the plaintext we wanted to achieve.
3. For the last block ($i == 1$) everything is the same, but the end result ($C_0$) is actually the $IV$ value. If you do not have access to setting the $IV$, then the first block will decrypt to garbage unfortunately.

Here is a blog post including a tool called PadBuster that can do both decryption and encryption against vulnerable sites, using the mechanism mentioned above.

Here's another post about the mechanism as well