During padding oracle attack (CBC), how is first byte of plaintext block is obtained?

Question

Imagine conducting a padding oracle attack against CBC mode with 16-byte length blocks, and PKCS#5 used for padding.

You start, as always, revealing the last byte of plaintext. Then you iteratively move backward and reach the first byte of last plaintext block. At this stage, you already spoofed the padding with 15 bytes, which values are 0x0f.

• So, how do you reveal the first byte of a block, since you’re out of padding length?

• Does PKCS#5 allow you to pad 16 bytes with 0x10 value?

• Or, these things are up to the implementation of padding used in a specific application?

Answer 1

Does PKCS#5 allow you to pad 16 bytes with 0x10 value?

No, but that's because PKCS#5 only specifies padding for DES, and that has an 8 byte block size. Even PKCS#5 itself refers to PKCS#7 when it comes to padding AES. More information about the differences here.

Now for the real answer. PKCS#7 padding, which is identical to PKCS#5 but allows any block size, requires 16 times the 0x10 byte value as padding:

For such algorithms, the method shall be to pad the input at the trailing end with $k - (l \bmod k)$ octets all having value $k - (l \bmod k)$, where $l$ is the length of the input.

Here $k$ is the block size of the block cipher in bytes, for instance AES with a block size of 16 bytes. Now obviously if $l$ is a multiple of 16 then then a full block of padding is added (as $l \bmod k$ would evalulate to zero and therefore only $k$, i.e. 16 would be left).

The reason for this is simple: imagine that a plaintext message that is a multiple of the block size ends with a valid padding pattern. Then the unpadding would remove that part of the message. By always performing padding the unpadding can be performed regardless of the contents and size of the message (i.e. allowing any message to be decrypted correctly).

Answer 2

So, how do you reveal the first byte of a block, since you’re out of padding length?

We are are not out of padding length. However,

• PKCS#5 (rfc 2898) is defined for 8-byte blocks i.e. for 64 block size like DES, and
• PKCS#7 (rfc2315) is defined up to 256-byte blocks that covers AES, too.

Therefore, for 16-byte blocks, let assume we are using PKCS#7.

The padding for 16 byte blocks contains values from $\texttt{0x01}$ to $\texttt{0x10}$. The value $\texttt{0x10}$ is used if message size is a multiple of the block size.

Once you determined that the padding is $\texttt{0x0F}$, then you continue to look for the next case and asking the oracle for padding $\texttt{0x10}$. Now ask for various values for the first byte ?

?,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10

Once the server not sending back you the padding error, you determined the first byte. $$(D(C_2) \oplus C') \gg 15 = \texttt{0x10}$$

Actually, this is how the message bytes are revealed in padding oracle attacks.

Does PKCS#5 allow you to pad 16 bytes with 0x10 value?

NO, as stated above. It is PKCS#7 that allows padding blocks larger than 8 bytes and up to 256 bytes.

If the message size is multiple of 16 bytes, then a new block is added with 16 $\texttt{0x10}$ values. If a new block is not added this can cause a problem while removing the padding. For example; what if the last byte is $\texttt{0x01}$

$$\texttt{xxxxxxxxxxxxxxx1}$$

then one byte of the message is lost.

Or, these things are up to the implementation of padding used in a specific application?

The padding oracle first described by the Serge Vaudenay; Security Flaws Induced by CBC Padding Applications to SSL, IPSEC, WTLS and years later applied to many times;

1. 2012 Steam Breaking Steam Client Cryptography
2. 2013 Lucky Thirteen attack
3. 2014 POODLE
4. 2016 Yet Another Padding Oracle in OpenSSL CBC Ciphersuites,

Padding oracle is a mixture of protocol and implementation flaws. The padding oracle attack leaks information about the secret data and the attackers is able to use it with crafted invalid inputs. The result of the attack is the break of the confidentiality of not only the last block but the whole message.

A good protocol will use a MAC in encrypt-then-MAC paradigm[*]. Before the decrypting, the server will first check the MAC tag. If there is an error, it will return an incorrect tag. This will only leak information about ciphertext. A bad protocol will do this in the wrong order and may suffer from leaking information about plaintext as in padding oracle attack.

We call the CBC an archaic mode. Good mitigation is getting rid of CBC mode at all like it is removed from TLS 1.3. In TLS 1.3 there are only 5 cipher suites and all of them authenticated encryption modes;

• TLS_AES_256_GCM_SHA384
• TLS_CHACHA20_POLY1305_SHA256
• TLS_AES_128_GCM_SHA256
• TLS_AES_128_CCM_8_SHA256
• TLS_AES_128_CCM_SHA256

---

[*] Should we MAC-then-encrypt or encrypt-then-MAC? for more detail