CCA on PKCS#5 using error feedback

Question

My question is about attacking PKCS#5 with CCA using the error feedback.

What we learnt in class about PKCS#5:

CBC requires padding to whole block boundary PKCS#5: standard padding

• If last plaintext block has 1 byte: pad with $\texttt{07}$ bytes
• If last plaintext block has 2 bytes: pad with $\texttt{06}$ bytes
• If last plaintext block has 7 bytes: pad with $\texttt{01}$ byte
• If last plaintext block has 8 bytes: pad with another block (8 bytes) of $\texttt{08}$.

And:

Decryption process: Apply 'regular' CBC-mode decryption Check padding:

• If padding Ok, remove and return plaintext
• If incorrect, abort with error

Up until now I understand everything. But the last part, describing a CCA attack on PKCS#5 with feedback, is what I can not understand:

Let $(c_1,...,c_8)=F_k(p_1,...,p_8)$ be some ciphertexts.

To find last byte $p_8$: Check which prev block gives Ok decryption

Let $x_8$ be the last byte of a block $X$ giving Ok padding

With high probability, $x_8 \oplus p_8 = \texttt{01}$...

And that's it.

First, I don't get where the IND-test is involved here.

In the test, attacker sends two messages $m_1$,$m_2$ and receives $c'$ which is an encryption of one of them, and has to distinguish which one exactly using the chosen-ciphertext capability, but here we just use the error result, as if the test is ignored.

Now, let's see if I understand that correctly:

$c_1$,...,$c_8$ are the bytes of some ciphertext block we wish to decrypt.

It says that in order to find out $p_8$ we find last block which gives ok on padding - let's assume we found one... this block looks like this: $c'=(c'_1,...,c'_8)$, and I know that the plaintext of $c'$ ends with $\texttt{01}$, or $\texttt{02},\texttt{02}$, etc.. until $\texttt{08},...\texttt{08}$ (8 times).

And now we denote the last byte (decrypted as plaintext) as $x_8$.

Why would $x_8 \oplus p_8$ be $\texttt{01}$ with high probability?

It would be great if someone could enlighten me up, I'm also open for other explanations instead the one I described here.

P.S. Read that question, seems related but I still can't understand how to deduce an answer about my question. Can you explain Bleichenbacher's CCA attack on PKCS#1 v1.5?

Answer 1

Ok, suppose that we have a ciphertext $(c_1, c_2, ..., c_8)$ that we wish to decrypt.

What we start off with is to make a guess for $p_8$, which is the decryption of the last byte of the block. Suppose that we guess that it is 0x07; we then need to validate that guess.

What we do is create a two block message; the second block is the challenge ciphertext block $(c_1, c_2, ..., c_8)$; the first block has 7 random bytes; followed by $0x07 \oplus 0x01 = 0x06$. We then send it to the Oracle for decryption.

Let us recall when CBC mode decryption is; it is $P_i = C_{i-1} \oplus D_k( C_i )$. In the specific case of the last block, what the decryption process will do is first internally decrypt the last ciphertext block $(c_1, c_2, ..., c_8)$, and get the plaintext block $(p_1, p_2, ..., p_8)$; it'll then exclusive or that with the previous ciphertext block; the last byte of that result will be $p_8 \oplus 0x06$ (because we made the last byte of the next-to-last-block 0x06).

Now, if our guess was correct; that is $p_8 = 0x07$, the result of this exclusive-or is $0x07 \oplus 0x06 = 0x01$; a last block with the last byte of 0x01 is valid padding, and so the message will be accepted.

On the other hand, if our guess was not correct, then the result of this exclusive-or is something other than 0x01. Now, it's possible that the result will also look like a valid padding (for example, the last three bytes might be 0x03 0x03 0x03), however that would also involve other bytes (which we set randomly), and so that's unlikely.

So, to actually perform this attack, we would make guesses at $p_8$, and send out ciphertexts to test those guesses. And, once we have determined the likely value of $p_8$, we can start guessing $p_7$ (which works just the same way, except we're targetting the $0x02$ $0x02$ final pattern).

BTW: the Bliechenbacker CCA attack is actually unrelated.