Understanding Manger’s Padding Oracle Attack on RSA Encryption

The previous article discussed Bleichenbacher’s 1998 attack on RSA encryption, which relies on access to a PKCS#1v15 padding oracle. Just a few years later, in 2001, James Manger published details of a different padding oracle attack on RSA encryption. Manger’s attack is similar to Bleichenbacher’s attack, but relies on a different type of padding oracle. Manger’s paper is shorter and easier to read than Bleichenbacher’s, but even so, understanding the attack may be easier if you read this article first rather than jumping directly into the paper. Further, I explain some points of interest which are not mentioned in the paper.

By the way, if you aren’t familiar with Bleichenbacher’s padding oracle attack, read the previous article before this one (or before reading Manger’s research paper, for that matter).

How does a Manger padding oracle differ from a Bleichenbacher padding oracle?

Bleichenbacher’s attack requires an oracle which tells the attacker whether any attacker-chosen ciphertext decrypts to a plaintext with valid PKCS#1v15 padding. To refresh your memory, this is what PKCS#1v15 padding looks like:

In contrast, Manger’s attack requires an oracle which tells the attacker just one thing: a Manger oracle takes any attacker-chosen ciphertext, decrypts it, and then tells the attacker whether the first (most significant) byte is zero or not.

It might sound like a Manger oracle is “weaker” than a Bleichenbacher oracle, in the sense of providing less information to the attacker. But in fact, a Manger oracle is much more useful to an attacker than a Bleichenbacher oracle; using a Manger oracle, one can crack RSA encryption with far fewer oracle queries. Let’s see how.

What doesn’t change from Bleichenbacher’s attack

In Bleichenbacher’s attack, we multiply the ciphertext by some integer $s^e\text{mod}N$, which multiplies the (unknown) plaintext $m$ by $s\text{mod}N$, and submit the result to the padding oracle. If it returns true, we derive some information about the value of $m$; specifically, we derive a set of ranges $M_i$ which it might be in. The intersection of all sets $M_i$ gives a set $M$, which contains all possible values of $m$ consistent with what the attacker knows so far. When the set $M$ is narrowed down to just one value, then the encryption has been cracked.

All of this applies equally to Manger’s attack, but take note of these differences:

• With Manger’s attack, the set $M$ only ever contains a single, contiguous range of integers. So the code for manipulating that set is much simpler than with Bleichenbacher’s attack.
• In Bleichenbacher’s attack, the attacker only updates $M$ when the padding oracle returns true. But in Manger’s attack, both true and false return values from the oracle enable the attacker to narrow down the possible values of $m$.^[1]
• Manger’s paper calls the multipliers $f$ instead of $s$. It also uses the name $B$ for a number (of the same byte length as the RSA message size) which has 1 in the most-significant byte and 0 in all less-significant bytes; this is 256 times larger than the number which is called $B$ in Bleichenbacher’s paper.

The three stages of Manger’s attack

When starting the attack, we assume that the first byte of the plaintext is zero. (More later on what can be done if that’s not the case.)

In Step 1, we check how many high-order bits in $m$ are zero. With very few oracle queries, this gives rough bounds on $m$, with an upper bound which is less than double the true value of $m$.

Do it like this: Try $f_1=2$; that left-shifts $m$ by one bit position. If the oracle returns true (meaning the high 8 bits of $sm\text{mod}N$ are zero), then the left-shift didn’t push a 1 bit up into the top byte, so the next bit after the top byte must be 0. In that case, try $f_1=4$; that left-shifts $m$ by two bit positions, and tells whether the next bit in $m$ is 0 or not. Continue until the oracle returns false; then you know which bit is the highest-order 1-bit in $m$.

In Step 2, we take advantage of our new knowledge of the highest-order 1-bit in $m$, together with our knowledge of the RSA modulus $N$.

With those two pieces of information, we can calculate a multiplier $f_2$, larger than $f_1$, with these properties: If $m$ is in the highest part of its possible range, $f_{2}m$ will wrap the modulus $N$, but not go so high as to reach $N+B$ and make the oracle return false. But if $m$ is in the lower part of its possible range, $f_{2}m$ will not wrap the modulus $N$, and because $f_2$ is larger than $f_1$, that high-end 1-bit will go into the top byte, and the oracle will return false. The formula is:

$$f_2=\lfloor \frac{n+B}{B}\rfloor \frac{f_1}{2}$$

If the oracle returns false, chop down the upper bound on $m$ accordingly, and calculate a new value of $f_2$, which (again) is just big enough so that values of $m$ in the higher part of its possible range will wrap the modulus $N$ but not go as high as $N+B$ (so the oracle will return true). And again, values of $m$ in the lower part of its possible range will not cause $f_{2}m$ to wrap the modulus $N$, and the oracle will return false. Repeat until the oracle returns true.

For each iteration of this procedure, the new value of $f_2$ is the old one plus $f_1/2$.

After Step 2, we now have a multiplier $f_2$ which maps $M$ into the range $[N,N+B)$, meaning $M=[\lceil \frac{N}{f_2}\rceil ,\lfloor \frac{N+B}{f_2}\rfloor )$. Depending on the value of $N$, that upper bound may be around 1.005 times the lower bound. That’s a big improvement from where we were after Step 1, where the upper bound was roughly double the lower bound.

In Step 3, we systematically chop $M$ down by around half with each successive oracle query.

In Step 1, $f_{1}m$ would not wrap the modulus $N$ at all. In Step 2, $f_{2}m$ would wrap the modulus $N$ either 0 or 1 times. But now in Step 3, we will use larger multiplier values $f_3$, which will wrap the modulus $N$ multiple times. However, we will choose $f_3$ so that we are sure of exactly how many times $N$ goes into $f_{3}m$.

Further, we will make $f_3$ just big enough so that around half of the possible values of $m$ will be less than $iN+B$, and the other half greater (or equal). The formulas are:

$$\begin{array}{rl}{f}_{approx}& =\lfloor \frac{2B}{\text{size}(M)}\rfloor \\ i& =\lfloor \frac{f_{approx}\cdot m_{min}}{N}\rfloor \\ f_3& =\lceil \frac{iN}{m_{min}}\rceil \end{array}$$

Repeat Step 3 until $M$ is narrowed down to a single value.

Note that there is a mistake in Step 3.5b of Manger’s paper; it says to use the floor function when updating $m_{max}$. That would be OK if $m_{max}$ was an inclusive bound (though the bound would not always be as tight as possible), but Step 3.1 clearly shows it’s intended to be an exclusive bound. For an exclusive bound, using the floor function is wrong and can cause the attack to fail.

Comments on the three stages

Take note of why Manger’s Step 1 wouldn’t work with a Bleichenbacher oracle; since a PKCS#1v15-padded message starts with 0x00 0x02, multiplying such a message by 2 and submitting it to a Bleichenbacher oracle would be useless. The high bytes of $sm$ would be 0x00 0x04 or 0x00 0x05, and the oracle would definitely return false. To get any information at all out of a Bleichenbacher oracle, you must use a multiplier big enough to make 0x00 0x02 wrap the modulus $N$. But because that starting multiplier is so large, only a tiny fraction of the possible values of $m$ will land in the target region, where the Bleichenbacher oracle has a chance of returning true. That causes the Bleichenbacher attack to use many oracle queries when searching for $s_1$.

In Manger’s Step 1, each oracle query gives 1 bit of information on the plaintext $m$. Again, in Step 3, each query gives close to 1 bit of information. So could we skip Step 2, where each query gives us much less information than that? No; Step 3 only works when the range of possible values $M$ is small enough, and Step 2 narrows it down just enough for Step 3 to work.

The total number of oracle queries required for Manger’s attack is about 10% more than the number of bits in the plaintext. This is far, far less than a Bleichenbacher attack.

A toy example of Manger’s attack

Was my description of the three stages clear enough? If not, maybe a concrete example (using unrealistically small numbers for intelligibility) will help.

Pick two 12-bit primes to start:

p = 205320632069208120832087208920992111211321292131213721412143215321612179220322072213222122372239224322512267226922732281228722932297230923112333233923412347235123572371237723812383238923932399241124172423243724412447245924672473247725032521253125392543254925512557257925912593260926172621263326472657265926632671267726832687268926932699270727112713271927292731274127492753276727772789279127972801280328192833283728432851285728612879288728972903290929172927293929532957296329692971299930013011301930233037304130493061306730793083308931093119312131373163316731693181318731913203320932173221322932513253325732593271329933013307331333193323332933313343334733593361337133733389339134073413343334493457346134633467346934913499351135173527352935333539354135473557355935713581358335933607361336173623363136373643365936713673367736913697370137093719372737333739376137673769377937933797380338213823383338473851385338633877388138893907391139173919392339293931394339473967398940014003400740134019402140274049405140574073407940914093
q = 205320632069208120832087208920992111211321292131213721412143215321612179220322072213222122372239224322512267226922732281228722932297230923112333233923412347235123572371237723812383238923932399241124172423243724412447245924672473247725032521253125392543254925512557257925912593260926172621263326472657265926632671267726832687268926932699270727112713271927292731274127492753276727772789279127972801280328192833283728432851285728612879288728972903290929172927293929532957296329692971299930013011301930233037304130493061306730793083308931093119312131373163316731693181318731913203320932173221322932513253325732593271329933013307331333193323332933313343334733593361337133733389339134073413343334493457346134633467346934913499351135173527352935333539354135473557355935713581358335933607361336173623363136373643365936713673367736913697370137093719372737333739376137673769377937933797380338213823383338473851385338633877388138893907391139173919392339293931394339473967398940014003400740134019402140274049405140574073407940914093

That gives us the modulus $N=pq=9341921$; $\varphi (N)=(p-1)(q-1)=9335700$. How would 1990349 do as private exponent $d$? (If you don’t like it, suit yourself; click here and I’ll switch it up.) That would mean the public exponent $e=1111049$.

Now give me an 16-bit unsigned integer as message $m$: . Encode that message in 24 bits (big-endian), and the top byte will be zero; just what we need for Manger’s attack. $B$ is 65536, and the RSA ciphertext is $c=2661993$.

OK, now forget that you already know $d$ and $\varphi (N)$. Also forget that $N$ is so small that it could be factored in microseconds. But, fortuituously, there is a Manger oracle which will gladly decrypt chosen ciphertexts for you and check their leading byte. For fun, we’ll visualize the Manger oracle as a fuzzy creature named Marley.

All we know to start is $M=[0,65536)$. In the 16-bit value $m$, we will call the least significant bit $b_0$, and the most significant bit $b_{15}$.

Step 1:

Find out how many high-end bits of the 16-bit value $m$ are zero.

Step 2:

Use multipliers no greater than $\lfloor \frac{m_{max}}{N+B}\rfloor$ to reduce the size of $M$ until $\frac{m_{max}}{m_{min}}\le \frac{N+B}{N}$.

Step 3:

Use larger multipliers to cut the remaining range of possibilities in half with each query.

If you like, try tweaking some of the above parameters and see how the resulting trace of attack steps changes.

How Manger’s attack relates to OAEP padding

The research paper in which Manger published his attack was entitled “A Chosen Ciphertext Attack on RSA Optimal Asymmetric Encryption Padding (OAEP) as Standardized in PKCS #1 v2.0”. Much of the paper talks about the OAEP padding scheme (which I’ll describe in a moment). So it may seem strange that I’ve described the entire attack without referring to OAEP yet. Here is why:

Manger’s attack really has nothing to do with OAEP padding. It’s a chosen-ciphertext attack which relies on being able to find out whether the top byte of an RSA plaintext is zero or not; no more, no less.

The connection with OAEP comes in because careless implementations of OAEP may (potentially) leak information on whether the top plaintext byte is zero. In other words, the nature of OAEP creates danger of exposing a Manger oracle to attackers. But it is certainly possible for RSA implementations not using OAEP to expose a Manger oracle. In fact, the authors of the paper “The 9 Lives of Bleichenbacher’s CAT” found Manger oracles in four different TLS libraries (including OpenSSL), none of which were using OAEP. (Rather, they were using PKCS#1v15 padding for RSA messages.)

Nonetheless, this article wouldn’t be complete without a brief overview of OAEP. Let’s do that now.

OAEP in brief

Here’s a slightly simplified diagram. Note that the overall bit length is the same as the RSA modulus $N$. The symbol ⨁ represents XOR.

Take note of these features:

• The leading 0x00 byte ensures that the integer value of an OAEP-padded message will never be larger than the RSA modulus $N$.
• As with PKCS#1v15, some random bytes are included. This makes the encryption non-deterministic; if you encrypt the same data twice, then the resulting ciphertexts will be different. So attackers can’t simply compare ciphertexts to see if you are sending the same data more than once. It also defends against various other attacks, including the RSA broadcast attack featured in Cryptopals #40.
• The random seed is used to derive a “data mask” which scrambles the entire lower part of the padded message.
• The scrambled lower part is then used to derive a “seed mask” which scrambles the random seed.
• The purpose of the scrambling is to destroy RSA malleability, from the perspective of the data payload which is recovered after reversing the OAEP padding.

Was the last point confusing? I thought so. Let me break it down:

RSA encryption is “malleable”, in that you can multiply an RSA ciphertext by (for example) $2^e$, and the corresponding plaintext will be multiplied by 2. That property is the basis for both Bleichenbacher’s and Manger’s attacks. Of course, the same is true of an OAEP-padded RSA ciphertext/plaintext. You can multiply an OAEP-padded ciphertext by $2^e$, and the OAEP-padded plaintext will be multiplied by 2. But, after the OAEP padding is removed, including reversing the seed mask, reversing the data mask, and pulling out the payload bytes (shown as “DATA…” in the above diagram), those payload bytes will not simply by multiplied by 2. They will be completely and irreversibly scrambled.

That is a big part of what OAEP padding is all about. It means that even if you create a service which (ignoring all good judgement) uses RSA encryption to protect confidential data, and even if your service carelessly exposes an oracle on the format of those “DATA…” bytes, attackers can’t mount adaptive chosen-ciphertext attacks^[2] against you.

The one fly in the ointment, the bruise on the apple, the hair in the soup, the ugly blotch on this otherwise rosy picture, is that RSA malleability still does apply to an OAEP-padded message before the OAEP padding is reversed. That is what makes Manger’s attack possible against RSA-OAEP, if the implementation is not careful to defend against it.

Manger’s attack against non-OAEP plaintexts

Manger’s paper doesn’t describe how to use his attack against messages which don’t start with a zero byte. But it’s easy; just use the same idea as Step 1 of Bleichenbacher’s attack. Generate a random RSA blinding value $r$, and use it to blind the target ciphertext:

$$c_b=c{r}^e\text{mod}N$$

Submit that to the oracle to see whether the blinded plaintext starts with a zero byte or not. If it doesn’t, try again until you find a blinding value which works. Use Manger’s attack to decrypt the blinded ciphertext $c_b$, then remove the blinding:

$$m=m_b{r}^{-1}\text{mod}N$$

Just as for Bleichenbacher’s attack, with this trick, Manger’s attack can be used to forge RSA signatures.

One more point about using Manger’s attack against non-OAEP messages; if the plaintext is a relatively small number (many high-order bytes are zero), then Step 3 sometimes gets stuck in an infinite loop. This is because when $m$ is small and the range $M$ is also very small, it can happen that multiplying by $f_3$ maps the entire range $[m_{min},m_{max})$ to one side of $N+B$; then the oracle always returns the same value, regardless of where $m$ actually is in that range, and Step 3 becomes unable to trim the size of $M$ down further. This can be avoided by validating $f_3$ and fiddling with it when necessary; another solution is to do a brute-force search of $M$ once it gets very small, rather than using oracle queries to run $M$ all the way down to a single value. (This doesn’t happen with OAEP-padded messages; no wonder Manger didn’t mention it in his paper.)

Generalizing the idea of a Manger oracle

Manger’s attack is described in terms of an oracle which reveals whether the first byte (8 bits) of an RSA plaintext is zero. This is because of the property of OAEP padding whereby the first byte of the plaintext is expected to be zero. But there is nothing magic about “8 bits”; if an RSA implementation exposed an oracle revealing whether the first 7 bits were zero, or whether the first 9 bits were zero, it could still be exploited with Manger’s attack. Just adjust the value of $B$ accordingly; $B$ should be the smallest number with a single 1-bit in the region checked by the oracle.

If the oracle only reveals whether one bit (the most-significant bit) is zero or not, Manger’s attack needs some adjustment. Also, if the RSA modulus $N$ is unusually small, such that there is only a single bit in the region checked by the oracle which isn’t also greater than the modulus, the same problem arises. Section 3.2 of Manger’s paper briefly describes how this situation affects his attack, but doesn’t develop an adjusted algorithm in detail.

The ideas behind Manger’s attack can also be adapted to an oracle which reveals whether $m$ falls in some interval $[0,B)$, where $B$ is not a power of 2, and is smaller than $N/2$. Actually, very little changes about the Manger attack algorithm in that case.

Lessons?

• Really, please don’t use RSA encryption. Please?

[1] This might seem like an obvious deficiency in Bleichenbacher’s attack, but it’s not. A Bleichenbacher oracle is expected to return false most of the time, so there is very little marginal information gain which an attacker could possibly derive from a false return. Further, as explained in the previous article, a Bleichenbacher oracle may return false for various reasons, irrespective of whether $sm\text{mod}N$ is in the “target” range $[2B,3B)$ or not. In contrast, in Manger’s attack, there is usually around a 50% chance of getting back either true or false from the padding oracle, so the attacker can derive close to one bit of information from each oracle query. And Manger oracles return true if and only if $fm\text{mod}N$ is inside the target range $[0,B)$. ⏎

[2] If you don’t know the term “adaptive chosen-ciphertext attack”, think of it as “attacks roughly like Bleichenbacher’s or Manger’s”. ⏎