Understanding Bleichenbacher’s CRYPTO’98 Padding Oracle Attack on RSA Encryption

In 1998, Daniel Bleichenbacher published a method for cracking RSA encryption with PKCS#1v15 padding, given access to a “padding oracle”. I learned of this attack via the cryptopals challenges, where it is featured in challenge #47 and #48.

The instructions for the challenge state: “We recommend you just use the raw math from the paper and not spend too much time trying to grok how the math works.” However, I was not able to solve the challenge without understanding “how the math works.” For other software practitioners who want to implement, or at least understand, Bleichenbacher’s chosen-ciphertext RSA attack, this article may serve as a more gentle introduction than jumping directly into the research paper.

Prerequisites first, then the details of the attack will follow:

What is PKCS#1v15 padding?

PKCS #1 is a standard for how to use the RSA algorithm to encrypt data. Version 1.5 was published in 1998.

It specifies the following format for a plaintext data block:^[1]

Note that the padding bytes are at the beginning of the block; this will be important later on.

What is a “padding oracle”?

A padding oracle is anything which lets an attacker know whether an arbitrary ciphertext block decrypts to a correctly padded plaintext block, or not. With PKCS#1v15 padding, this means that the first byte must be zero, the second byte must be 2, and so on, as shown in the above diagram.

Of course, the attacker doesn’t have the decryption key, or they wouldn’t need to bother messing around with a padding oracle. The attacker can make up any ciphertext block they want, give it to the oracle, and the oracle tells them: “yes, after I decrypt that, the padding looks OK”, or “no, it doesn’t”. (For clarity, the padding oracle must have the decryption key, or it couldn’t answer the attacker accurately.)

Again: the padding oracle doesn’t directly tell the attacker what any ciphertext block decrypts to; it just tells the attacker whether the decrypted block has the right padding or not.

The most common type of padding oracle which exists in the real world is a network service which receives encrypted requests from clients and returns a status code or message. To be used as a padding oracle, the service must return a different error code or message for a request which fails because of bad padding, or one which fails for any other reason. At the very least, something about the response must be different between requests with good or bad padding, or it’s not a padding oracle. (…which is a good thing, if you are operating that service! A padding oracle is only useful for people who want to crack someone else’s encryption.)

Because an attacker can only get a very small amount of information by checking a padding oracle once, they will need to check the oracle many, many times, on many different crafted ciphertext blocks, before they can gather enough information to (potentially) crack the encryption.

Refresh my memory on how RSA encryption works, please?

Why, of course! Look up “modular arithmetic” first if you need a refresher on that. Then, here is a highly abbreviated summary of RSA encryption:

1. Find two large primes, and call them p and q. The math for encryption and decryption will be done mod N, where N=pq.
2. Take a fixed number e (the “exponent”); 3 was frequently used in the past, but now 65517 is most common. e and N together are the “public key”.
3. Find a number d which relates in a special way to e and N (see Wikipedia for details). d and N together are the “private key”.
4. To encrypt: c=me (mod N). (c is “ciphertext”, m is “message”. It may seem strange to take a power of a message, but remember that the message can be thought of as a very large binary number, and we can take powers of that number just like any other. By the way, the message m must be a smaller number than N. If it’s too big, it must be broken up into blocks, and then the blocks must be encrypted individually.)
5. To decrypt: m=cd (mod N).

⸻But why does it work out that (me)d=m (mod N)? In other words, why are the encryption and decryption formulas inverses?

I’m not going to delve into that, since it is not the point of this article. But if you are curious, consider learning the basics of group theory. You don’t have to go extremely deep; once you grasp basic group theory, it will become easy to understand why the above equation is true. This textbook is recommended: Contemporary Abstract Algebra, by Joseph Gallian (chapters 1-8 are enough to understand RSA encryption).^[2]

Overview of the attack

In short, to crack an RSA ciphertext c, the attacker must find a series of ciphertext blocks, derived from c, which have correct padding when decrypted (as revealed by the padding oracle). For each such block which is found, the attacker can narrow down the possible values of the original plaintext m. When only one possibility remains, then the attacker knows exactly what m was; the encryption has been cracked.

In a bit more detail:

1. Keep a set of ranges which cover all the possible values of m. Call this set M. Initialize it to cover all correctly padded messages.
2. Find an integer si​ (call it a “multiplier”), where si​m mod N is a correctly padded message. (You will have to submit a number of ciphertexts to the padding oracle, until you find one where the padding oracle returns “true”.)
3. Convert si​ to a new set of ranges Mi​, which includes all the possible values of m for which si​m mod N would be correctly padded.
4. Combine M and Mi​, to make a new set of ranges which may be smaller than both of them: M=intersection(M,Mi​).
5. If the set M includes only one m-value, congratulations. That’s the original message. If not, go back to step 2, find a different value of s which works, and repeat.

If you want to implement this attack, do these things first:

1. Get set up to compute with bignums. For some programming languages, the standard library will include a suitable bignum library. For others, you will have to find one. You only need the most basic operations: addition, subtraction, multiplication, division, remainder after division (“mod”), modular exponentiation, and comparison.^[3]

2. Write some code to manipulate sets of bignum ranges; specifically, to initialize such a set from a list of ranges, to take the union or intersection of such sets, to test if they contain exactly one integer, and to test if they contain exactly one contiguous range. Test your code thoroughly enough to be confident that it works. Tip 1: Beware of the possibility that a set could contain overlapping or adjoining ranges. Either canonicalize the sets after every operation, or carefully ensure that your code works even if the representation of a set is non-canonical. Tip 2: Bleichenbacher’s paper is written in terms of closed ranges; in other words, ranges which include both the lower and upper endpoints. But the code may be simpler if you use half-open ranges, which include the lower endpoint but exclude the upper endpoint.

How can we manipulate a ciphertext to multiply the plaintext by s?

Good question! Indeed, in step 2 we need to find an integer si​, where si​m mod N is correctly padded. But we don’t know what m is (yet), and anyways, our padding oracle takes ciphertexts as input (not plaintexts).

Given that we have c, which is the encryption of m, we need a way to find the encryption of sm (call that cs​), for any candidate value s. If we pass cs​ to the padding oracle, and it returns “true”, then we will know that sm mod N is correctly padded, and that s is a valid multiplier. Then we can proceed to step 3. Here’s the trick:

Remember the formula for RSA encryption:

If we apply the same encryption formula to sm, we get:

In other words, to test whether an candidate integer s is a valid multiplier, multiply the ciphertext c by se (mod N), then pass it to the padding oracle.

How do we convert si​ to a set of intervals which bound the value of the original plaintext?

Remember, the PKCS#1v15 padding scheme requires the first two bytes of the padded message to be 0x00 0x02. Therefore, if the message is interpreted as a big-endian integer, then messages with correct padding will fall in the range (0x2000000…) up to (0x2FFFFFF…).

We need to give those endpoints names. Call the number (0x1000000…) B. Then the range is [2B,3B).^[4]

So the question is: for which values of m, would sm mod N fall into that range?

Definitely, s must be big enough that sm is greater than N; sm needs to be big enough that its remainder after division by N falls into [2B,3B).

Call the number of times that N goes into sm ‘r’ (for “remainder” after division by N). Then:

Although we know the value of s, we don’t know the exact value of m (yet). We just know that sm mod N is correctly padded. So in the above equation, the smallest possible value of sm is:

And the largest possible value of sm is:

So all possible values of m consistent with the fact that s is a valid multiplier are:

We’re making progress! But we don’t know the value of r. We know it must be at least 1 or more, but that’s not saying much. The above inequality doesn’t allow us to find a range of m-values unless we know r.

The breakthrough comes from realizing that we can turn the inequality around and solve it for r. But wait a minute; we don’t know m, so how can we solve for a specific value of r? Well, while we don’t know the exact value of m, we do have the set M which tells us possible values of m. For each range in the set M, we can take its endpoints and feed them into the above inequality to get a range of possible values for r.

Take all the possible r-values which you just derived, and for each one, solve for a new range of possible m-values. Take the union of all those ranges to get the new set Mi​.

That reasoning may seem convoluted, but it’s not circular. Although we are using possible values of m to obtain possible values of r, and then possible values of r to obtain possible values of m, we don’t just get back to where we started. The discovery of each valid multiplier si​ provides new information, and as a result, we do actually get a new and different set of possibilities Mi​, distinct from M. (Hopefully Mi​ is not just a superset of M; every time we set M=intersection(M,Mi​), we hope that the resulting sets become smaller and smaller.)

How do we find s1​, the first value of si​?

The simple way is a linear, brute-force search. Start from the smallest value which could potentially cause sm to wrap around mod N and come back to [2B,3B).

There is a smarter way to do this, which makes the attack faster on average; more on that later.

Once we have sn​, how do we find sn+1​ efficiently?

Reason on the same inequality as we did above:

Choose a target value of r, then use the inequality to find a range of candidate s-values. If you can’t find one that works (and this will definitely happen sometimes), then increment r and try again. Note that the range of possible s-values for r and r+1 may overlap, so to make the attack faster, make sure not to redundantly try the same s-values multiple times. (In other words, keep track of the range of s-values which you searched for the previous value of r, then when you derive the range of possible s-values for the next value of r, trim off any portion which overlaps with the previous range.)

On page 5 (“Step 2.c”), the paper tells you to use the following starting value for ri​:

ri​≥2Nmax(Mi−1​)si−1​−2B​

Notice that the last valid multiplier we found, si−1​, is used to derive the next r-value (ri​), which in turn will give us the next range of s-values to search for si​.

That formula for ri​ is designed so that when we find si​ and derive Mi​ from it, Mi​ will be about ½ the size of Mi−1​. Further, the range of candidate s-values which we derive from ri​ will be quite small; often just a few of them. (Using larger values for ri​ means the number of candidate s-values to search will be greater, but when you find a valid one, the resulting set Mi​ will be smaller. The above formula strikes a good balance and there is little reason to deviate from it.)

Generally, once we find s1​, Bleichenbacher’s attack is very fast. Depending on the particular values of N and m involved, you may find that around 50%-99% of padding oracle queries are used to find s1​.

Going beyond the CRYPTO’98 paper

Bleichenbacher’s paper had three different “search” steps which could be applied during the course of the attack. But it turns out that all of them are subsumed by Step 2.c; don’t bother with Step 2.a or Step 2.b. This will make your code shorter, simpler, and significantly faster.

When you start the attack and are searching for s1​, use r1​≥1.

The paper says that if there is more than one interval in Mi−1​, you should do a linear search for s-values starting from si−1​ + 1 (this is called “Step 2.b”). That situation doesn’t usually arise, but if it does, following Step 2.b is a dumb thing to do, and makes the attack unnecessarily slow. Be smart; instead of Step 2.b, use the Step 2.c formula to derive a target r-value, then derive a range of candidate s-values for each interval in Mi−1​, and search all of those ranges until you find si​. If you don’t find it, then as usual, increment ri​ and try again.^[5]

If you really want to make your Bleichenbacher attack scream, the paper “Efficient Padding Oracle Attacks on Cryptographic Hardware” describes how to use something which they call “trimmers” to reduce the size of M0​ before starting the search for s1​. Here’s a brief explanation of how these “trimmers” work:

Imagine for a moment that the plaintext m is divisible by 4. Take the multiplicative inverse of 4 (mod N); we’ll call it 4−1. If you multiply your ciphertext by (4−1)e mod N, that effectively divides m by 4. If you multiply the ciphertext by (3×4−1)e mod N, that multiplies m by ¾. Pass that ciphertext to the padding oracle; if it tells you that 43​m is correctly padded, then you know m≥38​B; instead of M0​=[2B,3B) you now have M0​=[38​B,3B). A very nice reduction!

Obviously, trying 5/4 would also be a good idea. It might help to lower the upper bound on m from 3B to 512​B.

But how would you know that the plaintext m is divisible by 4? You don’t have to! Just try the trimmers 3/4 and 5/4 as described above; if the padding oracle returns true, then m was divisible by 4 (and you also have tighter bounds on its value). If m isn’t divisible by 4, then the oracle will return false, and you will have wasted 2 oracle queries. But 2 oracle queries isn’t much! Using trimmers can make your attack several times faster on average.

You can try any fraction u/t in the same way, but as t gets bigger, the chances of m being divisible by t will become smaller and smaller. Also, u and t must be coprime (not share any prime factors), or the trimmer won’t work.

Forging RSA signatures with Bleichenbacher

In an earlier section of this article, we reviewed the formula for RSA decryption: m=cd (mod N). It turns out that the formula for calculating an RSA signature is almost the same; hash your message to get h=hash(m), then the signature is s=hd mod N.

Since RSA decryption and signing are essentially the same operation, if we can trick someone into decrypting an arbitrary RSA ciphertext using their private key, we can also trick them into signing arbitrary messages; just take the message which you want them to sign, hash it, and give the victim that hash to “decrypt” as an “RSA ciphertext”.

So a Bleichenbacher attack can be used for more than cracking RSA encryption; it can also be used to forge RSA signatures! And in fact, the inventors of the DROWN attack did this as a proof-of-concept; they actually forged an RSA signature using the private key for one of Facebook’s TLS certificates. (DROWN is a variant of Bleichenbacher’s attack which is tailored to exploit weaknesses in SSL 2.0.)

There is one obstacle which such an attacker must overcome: the desired signature (or “plaintext”) will not usually happen to be PKCS#1v15-padded. But the Bleichenbacher attack, as described above, assumes that the plaintext is within [2B,3B). So what is a forger to do?

This: Follow Step 1 (on page 4) of Bleichenbacher’s paper. It describes how to use RSA blinding to find a variant plaintext which is PKCS#1v15-padded. After the attack succeeds, don’t forget to remove the RSA blinding as described in Step 4 (on page 5). Finding the right blinding value s0​ will require around 216 extra oracle queries, so the attack will be a bit slower.

Not all padding oracles are created equal

Bleichenbacher’s attack exploits the fact that PKCS#1v15-padded messages fall in the interval [2B,3B). But actually, that is not the only requirement for valid PKCS#1v15 padding. Look at this diagram again:

Notice that bytes 3-10 must be non-zero. Further, there needs to be a zero byte somewhere after that. Because there can be 8 or more padding bytes, the zero byte can be anywhere, right up to the end of the message.

The chances of a random message having no zero bytes in positions 3-10 is (256255​)8≈0.969. The chances of having a zero byte somewhere after that depend on the length of the message; for a 96-byte message, it’s 1−(256255​)86≈0.285.

That means if your padding oracle checks all the rules for PKCS#1v15 padding, even if sm mod N falls in [2B,3B), the chances are high that the padding oracle will return false anyways (because the plaintext randomly happens to violate one of the other PKCS#1v15 padding rules).

The higher the chances are of such spurious false returns, the more s-values an attacker will have to search to find each successive si​. This makes the attack slower. But the algorithm for the attack doesn’t change. (The number of s-values which could potentially work is enormous, so even if 90% are spuriously rejected, there will still be plenty of others which an attacker can use to crack the encryption.)

One more tip

If you are implementing Bleichenbacher’s attack, remember that the inequalities in the paper are expressed in terms of real number division, but your bignum library probably gives you truncating integer division. The difference can and will throw endpoints (especially upper endpoints) out by one and cause your attack code to fail.

Reason carefully on those inequalities to avoid this.

Lessons?

• Don’t create padding oracles.
• More generally, don’t give attackers information; avoid even subtle leaks of information in error messages and so on.
• Don’t use PKCS#1v15 padding.
• More generally, don’t use outdated cryptosystems which are known to be crackable.
• Avoid using RSA encryption.^[6]
• If you do use RSA encryption, don’t use the same private key for both encryption and signing.

Thanks for reading! If you want to learn more about this attack, this is a good time to dive into the original research paper. Or if you haven’t done it before, step up to the plate and take on cryptopals challenge #47 and #48.

[1] The RFC says this padding format is only for “public key operations”; that essentially means “for encryption, but not for signing”. ⏎

[2] If you want to order a copy, it doesn’t necessarily need to be the newest edition. Personally, I learned from the 8th edition of Contemporary Abstract Algebra. The newest edition may be several times more expensive than the previous one. ⏎

[3] In a later section of this article, an optimization called “trimming” will be explained which requires finding multiplicative inverses in a group of integers under modular multiplication, so if you plan to use that optimization, your bignum library should also be able to find modular inverses. If you are using Golang, math/big implements this operation under the name ModInverse. In Python 3.8+, you can get the modular inverse of x mod N with pow(x, -1, N). ⏎

[4] The notation [2B,3B) indicates that the range includes 2B but excludes 3B; this is called a “half-open” range. ⏎

[5] If you read other articles on Bleichenbacher’s attack, you may see references to optimizations called “skipping holes” and “parallel threads”. But both of these are subsumed by the simplified version of the attack which I describe above, where Step 2.a and Step 2.b are not used. If you start the attack using Step 2.c, but with r1​≥1 (instead of using the usual Step 2.c formula for ri​), you automatically benefit from the “skipping holes” optimization. And if you apply Step 2.c in the way I describe above when M contains more than one contiguous range, then you also benefit from the “parallel threads” optimization. ⏎

[6] Although Bleichenbacher’s attack was discovered in 1998, real-world systems which are vulnerable to the attack have been found again and again since then. Security researchers have repeatedly found new types of padding oracle which can be used to mount the attack; see the ROBOT attack paper for an outstanding example. Nor is Bleichenbacher’s attack the only attack which has proved effective against RSA encryption. See this article on Trail of Bits. ⏎