Several months ago I was looking at the proceedings from #days 2010 and read Pascal Junod's slides Open-Source Cryptographic Libraries and Embedded Platforms. In them, he mentioned James Manger's attack on RSA OAEP, a padding scheme first defined in PKCS #1 v2.0. I hadn't heard of it before, and it interested me enough to investigate. (The paper is available via Google or ACM if you're a member.)

The basics of the attack are similar to the Padding Oracle attack in that a small piece of information is exposed via error messages and doing some clever math you can use that to retrieve the plaintext from the ciphertext. After the ciphertext is decrypted, the OAEP decoding process begins. The decrypted plaintext is supposed to fit in one less byte than the maximum size of the ciphertext. If the plaintext does not have a 00 in the highest byte, the ciphertext is considered to have been tampered with and an error is returned. Because of the properties of RSA, you can directly influence the plaintext p by multiplying the ciphertext c by x^e mod n - where e is the exponent from the public key, n the modulus, and x the arbitrary number you want to multiply the plaintext by. This will produce a plaintext p*x mod n after decryption.

Manger's Oracle relies on manipulating the plaintext and detecting when it has overflowed into the highest byte. Using a method reminiscent of binary search, the possible values of the plaintext are narrowed down until only one remains - allowing recovery of the plaintext from the ciphertext. The number of oracle queries needed depends on keysize; for 1024, it's around 1200.

I checked the popular implementations of RSA-OAEP and found none of them vulnerable to Manger's Oracle. OpenSSL specifically protects against it, calling Manger out by name in the comments. BouncyCastle and the .NET implementation were secure because they didn't throw an error if the first byte was non-zero (probably on the assumption that another part of OAEP, the hash, wouldn't match). Libgcrypt didn't implement RSA-OAEP - a patch had been provided a few years ago, but it was never merged... until a few weeks ago when it was committed to trunk.

The new code wasn't actually directly vulnerable - the same error code was returned no matter the type of error that occurred. Regardless, I decided this would be a fun exercise and set about implementing the attack. I got it working; but only after editing the source of libgcrypt to 'cheat', providing my own oracle. I managed to find a mistake in the original paper too, a floor() that should have been a ceil() - detailed in the code linked later.

Since I modified the libgcrypt code to provide an oracle, it was an overly contrived example, but it seemed like it might be possible to exploit it using a timing attack. After measuring and graphing the differences between the two cases, I saw you could determine the error from timing information - so long as you looked at the percentiles over a sufficient number of trials, as shown below. It isn't 100% reliable, but I was able to get a working proof of concept going with just timing information.

Left two box plots show the longer execution time, right two show the shorter.

I've published the code to exploit the oracle in a contrived case, and included the code and steps to demonstrate the timing differential. The code is on github, and as far as I know, this is the only public implementation of Manger's Oracle. (Although apparently it is assigned as homework somewhere...)

"OAEP Padding" is indeed an example of RAS Syndrome

This writeup originally appeared on the Gotham Digital Science blog.

if 1 * 2 < 3:
    print "hello, world!"