Comprehending padding oracle exploits

In week 4 of the excellent online cryptography course taught by Professor Dan Boneh, the topics included various attacks, including one called the padding oracle exploit.

To reinforce the material, the homework for week 4 included a practical question involving padding oracle exploits: a hypothetical web server request log was provided, containing evidence of an actual padding oracle attack.

In the request log, there were recorded the systematic requests that the attacker made of the web server, together with the web server's responses (HTTP 403 if the padding was wrong, HTTP 404 if the padding was correct).

The task posed by the question was: given this evidence, decrypt the original message!

As I worked through the problem, I kept getting the wrong answer, and finally realized my essential mistake: I thought that, once the attacker had brute-forced a single byte of the message by finding the corresponding IV byte that made the pad value correct, that the attacker had learned the corresponding byte of the plaintext.

But that is wrong, what the attacker has learned at this point is the corresponding byte of the decrypted ciphertext, which must then be XOR'd with the previous block's ciphertext (or the actual Initialization Value if this is the first block) in order to find the actual plaintext.

So I was finding the intermediate values correctly, but then there was one more step, to XOR them with the correct values from the originally captured ciphertext, to recover the plaintext.

While working my way through this, I came across this quite nice writeup by Brian Holyfield of Gotham Digital Science: Automated Padding Oracle Attacks With PadBuster.

If you are studying padding oracle attacks, and are looking for a clear description of how they work, with nice diagrams and examples, give Holyfield's article a try and see if it makes the technique a bit more clear.