First before we can get into the details of the attack, we need an intuition why it works. There's a nice picture hosted on the TLSeminar page illustrating this point:
which basically says that we want to modify the last byte $\color{red}\times$ of the second-to-last block so that the CBC decryption of the last block which has "$\color{blue}?$" as its content yields $\color{green}{\mathtt{0x01}}$ instead. This of course works because CBC decrypts as $\color{green}{M_i}={\color{blue}{D_K(C_i)}}\oplus \color{red}{C_{i-1}}$. Finding the right $\color{red}\times$ is achieved by querying all 256 values to the padding oracle to which you should only get one positive response (when you hit the correct plaintext guess or accidently hit a longer padding).
So now that we know roughly what to do: Namely guess the last yet unknown byte until you get confirmation, let's get into the details.
- Let $i$ by the current plaintext octet counted from the end that we are trying to recover, including padding. Initially, let $i=1$. Further let $G_i$ be the set of potential plaintext octets recovered in iteration $i$.
- Let $c_{k-1}$ be the second to last ciphertext block or if $k=1$ then it corresponds to the IV. Define $c'_{k-1}:= c_{k-1}\oplus (0^{n-8(i-1)}\|g_{i-1}\|\ldots\|g_1)\oplus (0^{n-8i}\|\texttt{i}^{i})$ where $\texttt{i}^i$ is $\texttt{i}$ encoded as one octet repeated $i$ times and the $g_i$ are elements of their respective sets $G_i$ which we currently use.
- For all $g\in\{0,1\}^8$, query the oracle with $c'=c''_{k-1}\|c_k$ where $c''_{k-1}:=c'_{k-1}\oplus (0^{n-8i}\|g_i\|0^{8(i-1)})$, add all $g_i$ for which $P(c''_{k-1})=1$ to $G_i$.
- If $G_i$ contains $0$ or $256$ entries, that is the oracle always responded positive or negative, find the largest $j<i$ for which $G_j$ has more than one entry.
Remove $g_j$ from $G_j$ and set any other element of $G_j$ to be $g_j$.
Note that $j$ may be negative here which then implies that a previously "discarded" ciphertext block needs to be re-added and $j$ be incremented by $n/8$.
This addition of old blocks needs to be repeated until $j$ is positive again.
If $G_i$ fulfilled that special condition, set $i\gets j+1$ otherwise update $i\gets i+1$ and pick any element of $G_i$ as current $g_i$.
- If $8i>n$ set $i\gets 0, k\gets k-1$ discard the last block and return $g_{n/8}\|\ldots\|g_1$ as its contents.
- Go back to 1.
As this is quite the wall of text, here's an UML sequence diagram illustrating the above procedure for the case that the $G_i$ always have size 1:
The idea of the addition of these sets is that indeed we may get unlucky and hit a second-to-last byte of $\texttt{0x02}$ which results in $\texttt{0x02}$ and $\texttt{0x01}$ being accepted by the padding oracle. So instead we take a guess which plaintext guess was right and go back to take another option if needed later, e.g. if we obviously did a bad guess previously due to now always satisfying the oracle.
If the padding oracle enforces a given ciphertext length, we can still recover data, but if the padding is only allowed for up to one block, we can only recover one block or else we can recover at most $255$ bytes if arbitrary length multi-block padding is allowed. For this then we simply don't discard the ciphertext blocks and keep incrementing our $i$ beyond $n/8.$
