Practical Padding Oracle Attacks on RSA

We revise attacks on the RSA cipher based on side-channels that leak partial information about the plaintext. We show how to compute a plaintext when only its parity is leaked. We then describe PKCS#1 v1.5 padding for RSA and we show that the simple leakage of padding errors is enough to recover the whole plaintext, even when it is unpadded or padded under another scheme. This vulnerability is well-known since 1998 but the flawed PKCS#1 v1.5 padding is still broadly in use. We discuss recent optimizations of this padding oracle attack that make it effective on commercially available cryptographic devices. We illustrate through many examples and fragments of code.

Cryptography is a fundamental mechanism for secure computation. It is extremely important in distributed environments when devices need to remotely communicate and perform critical tasks. Cryptographic tokens, smartcards and embedded secure cryptoprocessors are becoming very popular as applications can in principle delegate to them any cryptographic operation. Keys are securely stored in a tamper-resistant chip and cryptography is performed by the cryptographic device so that keys are never exposed.

PKCS#11 is one of the standard API for cryptographic devices. It specifies a multitude of operations and mechanisms that can be performed by a PKCS#11 compliant device. Most of the commercially available cryptographic tokens and smartcards are, in fact, PKCS#11 compliant. The API is very complex and flexible and, quite surprisingly a complete compliance to the standard is likely to make the device flawed. In [BCFS10] we have shown that many commercially available devices are vulnerable to attacks that allow to leak sensitive keys by combining commands in unexpected ways [C03] [DKS08]. In the same paper, we develop a tool named Tookan that automatically builds a model of the analysed device and looks for real attacks. If the device is flawed, it is possible to modify the model in order to experiment with various fixes. This should help manufacturers and end-users to fix or, when possible, configure the devices so that attacks are prevented.

In this article we discuss a different class of attacks that we have recently investigated on PKCS#11 devices [BFKSST12]. We have realized, in fact, that many commercially available devices implement PKCS#1 v1.5 padding which is known to be affected by a side-channel vulnerability since 1998, the year when Bleichenbacher published his attack [B98]. Bleichenbacher’s attack is based on a padding oracle just revealing whether or not a decrypted message is correctly padded according to PKCS#1 v1.5. The attack finds the whole plaintext, even when it is unpadded or padded under another scheme. In the PKCS#11 API, the C_UnwrapKey command allows for importing a key encrypted under another one, e.g., under a RSA public key. In our study, we have shown that many devices return errors that are suitable for implementing the padding oracle attack.

Padding oracle attacks are not the only example of side-channels leaking partial information about the plaintext. In another recent study [FL12] we have investigated attacks that allows to recover bank PINs in a way that is very similar to the Mastermind game: one player (the attacker) makes a guess and the other one (the bank Hardware Security Module device) gives a partial information about its correctness.

We insist that these side-channel attacks are very dangerous and effective on real devices and should be regarded as such by hardware manufacturers and software developers. To prevent the Bleichenbacher attack it is enough to adopt OAEP padding, which is already in the standard and is recommended for all new applications since version v2.1 (2002). It is crucial, however, that PKCS#1 v1.5 and OAEP are not allowed on the same key as Bleichenbacher’s attack is effective even on messages padded under different schemes. The RSA SecureID is the only device among the one we analysed that implements OAEP but unfortunately it does not prevent switching to PKCS#1 v1.5, which makes the attack possible even on OAEP padded ciphertexts.

Our presentation is general and independent of the specific setting. We do not explain or discuss the PKCS#11 API for smartcards and cryptographic tokens. We focus, instead, on padding oracle attacks and we explain the new optimizations proposed in [BFKSST12] that make them very effective on commercially available devices.

More specifically, we start giving simple tools for Playing with RSA. This will be useful to have a practical experience with the RSA cipher and its basic operations. We will discuss, in particular, The multiplicative property of RSA that is fundamental to implement side-channel attacks on the cipher. We will then illustrate A simple parity side-channel. This is a well-known attack in which leaking the parity of the plaintext allows the recovery of the whole plaintext. We will then have a closer look at the PKCS#1 v1.5 padding that will allow us to describe in detail The Bleichenbacher attack. We will conclude by illustrating Practical attacks on cryptographic hardware which are based on new optimizations of the Bleichenbacher attack [BFKSST12].

We introduce RSA giving some simple tools to “play” with it. The only thing we need to recall of RSA is that encryption E(m) and decryption D(y) are defined as exponentiation modulo a big n (at least 1024 bits), respectively using the public e and the private d exponent. Encryption and decryption are such that such that D(E(m)) = m.

The OpenSSL toolkit provides very flexible command line tools to perform cryptographic operations. Let us generate a real 1024 bit RSA key-pair using the genrsa command:
[OpenSSL provides an individual manpage for each command. For example, man genrsa shows the manpage of genrsa command.]

The key has been saved into file named key (option -out). You can see that the encryption exponent e is set to the constant 65537, i.e., 0x10001. This is a standard way to make encryption faster: smaller exponents allows for faster exponentiation. Let us have a closer look at the generated key using the pkey command with -text option, which prints in plain text the various key components.

In particular, we see the modulus and the private exponent. Let us try to encrypt a small sample plaintext (a single byte 0x01) using rsautl, with no padding (option -raw). Option -inkey specifies the file key containing the public exponent and the modulus. We save the ciphertext in file enc01 (option -out).

Interestingly, we get an error: OpenSSL refuses to encrypt one single byte with no padding. in -raw mode we have to provide all the 1024/8 = 128 bytes of the plaintext: in other words, we have to manually pad the plaintext. We use perl to pad 0x01 with 127 0x00 bytes:

The obtained ciphertext is a 128 byte (1024 bits) long binary file that we can inspect with hexdump:

Mh, this is annoying: the ciphertext is the same as the plaintext! Well, E(m) is m^e mod n = 1⁶⁵⁵³⁷ mod n = 1 so, in fact, the encryption of 0x01 is 0x01. This is a simple example showing that a 0x00 padding is not a good idea.

Even if we would never use in practice 0x00 padding let us stick to it for a moment. We encrypt 0x02 to see if we get a more interesting ciphertext:

This looks more like what we had in mind thinking of a ciphertext.

We now show that it is very simple to encrypt under RSA using python, as it provides a simple native support for very long integers. We exploit translate and int to directly convert the OpenSSL RSA modulus into a number.

Very simple! We have encrypted 0x02 under the public exponent e = 0x10001 by just rising it to e modulo n, written (m ** e) % n. The result is the same we obtained with OpenSSL (the ending “L” stands for long).

Before illustrating padding oracle attacks we give a simple example of side-channel in which a single bit of the plaintext is revealed: its parity. It is well-known that leaking the parity of an RSA encrypted message allows the recovery of the whole message (see, for example, [S06]). This fact is sometimes regarded as a good property of the cipher: if there is no way to compute the plaintext we are also guaranteed that it is not even possible to just compute the parity bit of the plaintext (as otherwise we would use the attack to reconstruct the whole message).

We describe the attack step-by-step. Consider the following ciphertext:

We can check the parity of the plaintext calling our EEGGs parity oracle:

We thus know that the (unknown) plaintext m ends-up with a 0 bit. Now, think of multiplying m by 2, modulo n. If m < n/2 we have that 2m mod n = 2m which is even. If instead m > n/2 we obtain that 2m mod n = 2m - n, which is odd given that n is always odd (since it is the picked as the product of two large primes). The following table summarizes:

Thus, if we multiply the ciphertext by the encryption of 2 and we call the parity oracle on the obtained ciphertext we discover whether the plaintext is in the first or second half of the interval [0,n-1]. For example, picking a toy modulus n = 21:

This sound promising as it (almost) halves the number of possible candidates for m.

If we multiply by 4 we obtain four cases:

Looking at the parity of 4m mod n we thus discover whether it belongs to first/third or second/fourth quarter interval.

It is easy to generalize this argument to 2ⁱ m mod n for the i-th step. This is enough to implement a binary search: at each step we split the interval of possible plaintexts in two and we then descend into the correct one depending on the parity, which is disclosed by the oracle. The following python program finds the plaintext. We use decimal for arbitrary precision floats which makes it easy to split intervals in two without approximation errors.

When we run it, after about half a minute (be patient as it calls the EEGGs oracle 1023 times) we obtain:

This is an example of a PKCS#1 v1.5 padded ciphertext that we will discuss deeply in the next section. Let us have a quick look at it. It is composed of different parts:

Mh, the plaintext really looks an ASCII message. Converting bytes into ASCII we obtain the following message:

We have seen an example of PKCS#1 v1.5 padded plaintext. Let us revise this padding scheme more in detail. A padded message is composed of different parts:

The first two constant bytes (0x00, 0x02) identify the scheme. Then we have at least 8 non-zero random bytes of padding followed by a 0x00 separator. The actual message follows. The whole padded message must fit the key size exactly. For example, for a 1024-bit key it must be 128 bytes. This is achieved by inserting a sufficient number of random bytes.

We have seen an example in the previous section. Let us show another simple one. Suppose we want to encrypt the message hello world!, i.e., the 12 bytes 68656c6c6f20776f726c6421. Suppose the key is 1024 bits. Thus we need to add 128 - 12 - 3 = 113 bytes of random padding obtaining something of the form:

It is interesting to see what happens when a padded message is decrypted.

Let us do a few experiments to see how this works in practice. We have already seen that option -raw tells OpenSSL not to pad the plaintext. This allows us to manually pad and encrypt it. We then decrypt the ciphertext without the -raw option which by default uses PKCS#1 v1.5. We see that the message is correctly decrypted.

Let us now break the padding. We first change the second byte from 0x02 to 0x03:

As expected it returns an error: block type is not 02.

Let us see what happens, instead, if we insert a 0x00 in the second of the 8 bytes of padding:

This time we get bad pad byte count as the non-zero padding is required to be at least 8 bytes long.

Let us finally put a 0x00 in the ninth byte of the padding:

This does not break the padding. What follows the 0x00 byte we have inserted (which is interpreted as a separator) is returned as the plaintext. So we get a 128 - 11 = 117 byte long garbage message ending with "hello world!".

It should now be fairly clear how PKCS#1 v1.5 works and we can now see how to implement an attack exploiting a padding oracle.

In A simple parity side-channel we have seen how to exploit the multiplicative property of RSA to break a ciphertext, once the parity of the plaintext is leaked. Leaking one bit allows for discovering all the remaining ones. The algorithm is optimal as it builds an almost perfectly balanced search tree. Each parity leakage allows for splitting the interval of possible plaintexts in two sub-interval whose size differs at most by one.

Bleichenbacher’s attack [B98] is similar in the spirit but is based on a rather different side-channel that we will call padding oracle. The attack works whenever a PKCS#1 v1.5 padding error is returned, telling that the decrypted message is not conforming to the padding scheme. We have seen a few examples in the previous section. The attack, in fact, exploits the cases in which the padding is accepted, as these reveal that the first two bytes are 0x00 and 0x02.

If we let k be the size in bits of the RSA modulus and B = 2^(k-16) we have that 1024-bits long numbers starting with 0x0002 are the ones in the interval [2B,3B-1].

As for the simple parity side-channel, we exploit the multiplicative property of RSA to restrict this interval and converge to just one candidate. This is, however, not as simple as in the parity example.

Since the attack can take hundred thousands of steps it is useful to work directly on the plaintexts and simulate the padding oracle by simply checking whether or not the given plaintext is correctly padded. In this way we never perform encryption and decryption operations making the (simulated) attack extremely fast.

We illustrate the attack step by step, giving numerical example.

Assume for the moment that we want to break a ciphertext whose plaintext is known to be correctly padded. In Breaking unpadded ciphertexts we will see how to drop this assumption. Let m₀ note this correctly padded plaintext. We know it belongs to interval [2B,3B-1].

In a paper that will appear this August at CRYPTO 2012 [BFKSST12], we have studied optimizations of Bleichenbacher’s attack that make it very effective even on relatively slow hardware such as smartcards and USB crypto tokens. We briefly revise these improvements.

We have revised attacks on RSA which are based on side-channels that leak partial information about the plaintext. In particular, we have illustrated that PKCS#1 v1.5 padding is vulnerable to a powerful attack that discloses the plaintext once the (in)correctness of padding is notified to the users. In a recent paper, we have shown that these attacks are effective on real, commercially available devices. We recommend manufacturers and software developers to take these attacks very seriously as they can break the security of the system.

PKCS#11, the standard API for cryptographic devices, still includes PKCS#1 v1.5 as a possible padding scheme, while it has been suggested long ago to switch to OAEP padding for new applications and never allow the two schemes to be used on the same key, as in the case of RSA SecureID. We hope that our results will convince editors to reconsider the inclusion of PKCS#1 v1.5 in the new version of PKCS#11.