Understanding Bleichenbacher's CRYPTO'98 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 the math involved. 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 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 $\text{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=m^e(\text{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=c^d(\text{mod}N)$.

⸻But why does it work out that $(m^e{)}^d=m(\text{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 the principle of 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 $s$ (call it a “multiplier”), where $sm\text{mod}N$ is a correctly padded message.
3. Convert $s$ to a new set of ranges $M_{new}$, which includes all the possible values of $m$ for which $sm\text{mod}N$ would be correctly padded.
4. Combine $M$ and $M_{new}$, to make a new set of ranges which may be smaller than both of them: $M=\text{intersection}(M,M_{new})$
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.

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 is 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 $s$, where $sm\text{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 $c_s$), for any candidate value of $s$. If we pass $c_s$ to the padding oracle, and it returns “true”, then we will know that $sm\text{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 $s^e\text{mod}N$, then pass it to the padding oracle.

How do we convert $s$ 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)$.^[3]

So the question is: for which values of $m$, would $sm\text{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\text{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 $M_{new}$.

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 $s$ provides new information, and as a result, we do actually get a new and different set of possibilities $M_{new}$, distinct from $M$. (Hopefully $M_{new}$ is not just a superset of $M$; every time we set $M=\text{intersection}(M,M_{new})$, we hope that the resulting sets become smaller and smaller.)

How do we find $s_1$, the first value of $s$?

Just do a linear, brute-force search. Save yourself a few CPU cycles by starting from the smallest value which could potentially cause $sm$ to wrap around $\text{mod}N$ and come back to $[2B,3B)$.

Once we have $s_n$, how do we find $s_{n+1}$ efficiently?

On page 5 (“Step 2.c”), the paper describes a procedure for taking a range from $M$, and using it to narrow down the search for more $s$-values. It’s based on the same inequality as the reasoning above:

Use the ranges in $M$ to find possible values of $r$ in that inequality; then use those values of $r$ to constrain the possible values of $s$. The paper states that this method should be used when there is only one contiguous range in $M$.

This method is far more efficient than doing a brute-force search over all integers to find $s$-values. It’s not just that you find new $s$-values more quickly; for some reason which I don’t understand, it seems that $s$-values found using this strategy tend to narrow down the size of $M$ very effectively.

I did actually try implementing Bleichenbacher’s attack without this search strategy, just doing an incrementing linear search over all integers. That code found lots of $s$-values, but the resulting sets $M_{new}$ seemed random, and the smaller $M$ became, the longer it took to find another set $M_{new}$ which would actually help to reduce the size of $M$. As a result, cracking an encrypted message took approximately forever (or at least, longer than I was willing to wait).

One more tip

If you are implementing Bleicherbacher’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.

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] The notation $[2B,3B)$ indicates that the range includes $2B$ but excludes $3B$; this is called a “half-open” range. ⏎