Can you explain Bleichenbacher's CCA attack on PKCS#1 v1.5?

Question

I've studied that the Bleichenbacher's CCA attack on PKCS#1 v1.5. is a base to many versions of attacks in the area.

I'm trying to understand that attack, but every explanation I saw starts with the technical details, without giving some overview, so it's hard to follow...

Can you explain it in a simple words before giving the little details?

Answer 1

When encrypting something with RSA, using PKCS#1 v1.5, the data that is to be encrypted is first padded, then the padded value is converted into an integer, and the RSA modular exponentiation (with the public exponent) is applied. Upon decryption, the modular exponentiation (with the private exponent) is applied, and then the padding is removed. The core of Bleichenbacher's attack relies on an oracle: the attack works if there is some system, somewhere, which can tell, given a sequence of bytes of the length of an encrypted message, whether decryption would yield something which has the proper padding format or not.

An example would be a SSL/TLS server. In the initial handshake, at some point, the client is supposed to generate a random key (the "pre-master secret"), encrypt it with the server's public key, and send it. The server decrypts the value, obtains the pre-master secret, and then compute from that pre-master secret the keys used for symmetric encryption of the rest of the connection. Using the standard for guidance, the client sends a ClientKeyExchange (which contains the encrypted pre-master secret), then a ChangeCipherSpec, then Finished; this last message is encrypted with the derived symmetric key and its contents are verified by the server.

If the client sends a random sequence of bytes of the right length to the server instead of a properly encrypted pre-master secret, then the server will, most of the time, respond with an error message telling "I tried to decrypt your ClientKeyExchange contents, but this failed, there was not a proper padding in it". However, by pure chance, it may happen that the random string, after applying the modular exponentiation, yields something which really looks like a pre-master secret with correct padding. In that case, the server will not complain about the ClientKeyExchange, but about the Finished message, which will be incorrectly encrypted.

This is the information the attacker wants: whether the sequence of bytes he sent would, upon decryption, look properly padded or not.

---

Let's see with a bit more technical details. In RSA, let $n$ be the public modulus. Let $M$ be a message to encrypt with $n$ (in the case of SSL, $M$ is the pre-master secret, of length 48 bytes). The PKCS#1 v1.5 padding, for encryption, consists in adding some bytes to the left, so that the total length after padding is equal to that of $n$. For instance, if the server's public key is a 2048-bit RSA key, then $n$ has length 256 bytes, so the padded $M$ should also have length 256 bytes.

A properly padded message $M$ has the following format:

0x00 0x02 [some non-zero bytes] 0x00 [here goes M]

so the sequence of bytes will begin with a byte of value 0, then a byte of value 2, then some bytes which should have random values (but not zero), then a byte of value 0, then $M$ itself. The number of non-zero bytes is adjusted so that the total length is equal to the length of $n$. Upon decryption, the server will look at the first two bytes, and require them to be equal to 0x00 and 0x02, in that order. Then it will scan for the next byte of value 0, thus skipping over all the random non-zero bytes. This way, the padding can be unambiguously removed.

It follows that if the client sends a random string of bytes, then it has probability roughly between $2^{-15}$ and $2^{-17}$ to follow the PKCS#1 padding format (that's the probability that the first two bytes are 0x00 0x02, and that there is at least one byte of value 0 afterwards; exact probability depends on the length and value of $n$).

The attack scenario is the following:

• There is a SSL server, which will send distinct error messages depending on whether a proper PKCS#1 padding was found or not. Alternatively, the two cases could be distinguished through some other information leak (e.g. the server takes longer to respond if the padding was correct).
• The attacker eavesdropped on a connection, and would like to decrypt it. He observed the ClientKeyExchange, so he saw an encrypted message $c$. He knows that $c = m^e \pmod n$ where $e$ is the public exponent, and $m$ is the padded pre-master secret for that connection. He wants to recover $m$, or at least the pre-master secret which is contained in $m$, because that will allow him to compute the symmetric keys used for the connection.

Then the attacker will initiate many connections to the server. For each connection, the attacker generates a value $s$ and sends, as ClientKeyExchange, a value $c' = cs^e \pmod n$. The server decrypts that, and obtains $m' = (cs^e)^d \pmod n$ ($d$ is the private exponent), which is equal to $ms \pmod n$. Most of the time, this $ms$ value will not be properly padded (it will not begin with 0x00 0x02 or will not contain an extra 0x00). However, with a low but non-negligible probability (once every 30000 to 130000 attempts, roughly), luck will have it that the $ms \pmod n$ value looks padded. If that is the case, then the server's behaviour will inform the attacker of that fact. The attacker then learns that, for this value $s$ (the attacker knows it, since he chose it), then $ms \pmod n$ is in a specific range (the range of integers which begin with 0x00 0x02 when encoded in bytes using big-endian convention).

The rest of the attack is trying again, with carefully chosen random values $s$. Each time the server responds with "that was a proper PKCS#1 padding", this gives some information which helps the attacker narrow his guesses on $m$. After a few million connections in all, the attacker learned enough to pinpoint the exact $m$, yielding the pre-master secret.

See the original article for details; once you know how the RSA padding works, the rest is just maths, which are not too hard.

To prevent this attack, SSL servers do not inform the client about padding woes. If decryption fails because of a bad padding, then the server continues with a random pre-master secret (the true failure will then occur when processing the Finished message).

One may note that the specific weakness of the PKCS#1 v1.5 padding (for encryption) is that it is not very redundant; the random bytes are, indeed, random, without any specifically enforced value. This is what allows a sequence of random bytes to be "properly padded" with a small but not negligible probability. Newer versions of PKCS#1 describe a new padding type, called OAEP, which uses hash function to add a lot of internal redundancy, which makes it extremely improbable that a random string matches the padding format. This prevents Bleichenbacher's attack. Unfortunately, SSL still uses PKCS#1 v1.5.