RSA and small exponents

Strong cryptography, including RSA, is a vital component of modern life. However, it's very easy to get wrong, nullifying some or all of the security provided. In this post we'll go over one possible issue, motivated by a puzzle given at a conference I attended recently.

This January my employer was good enough to send me to USENIX's Enigma conference. The talks were generally excellent (albeit a bit high-level and non-technical) and the conference was well worth going to; watch them here. But rather that write about the conference in detail or go over a particular talk, I'd rather talk about a clever puzzle that came up.

The problem

Signs at the event pointed attendees to a particular URL for information about a surprise secret speaker on the last day of the conference. I had some free time, so I checked it out, and found a cute little crypto puzzle.

Unfortunately the puzzle seems to have been removed, but I did save off a copy. Inside, there are two files, message.enc and public_key.pem:

enigma files

So we have a message encrypted with 2048-bit RSA, and the public key used to encrypt it. Unfortunately, we need the private key to decrypt... right?

The only slightly odd thing here is that the exponent used to encrypt the message is 3. This is fairly unusual; according to a 2012 survey, the exponent 65537 is used in nearly 99% of cases, and . It is entirely possible to securely use other exponents (including 3) with RSA, but it points us towards one particular attack on the cryptosystem.

The attack

Let's take a minute to briefly go over how RSA encryption works.

One party chooses a public exponent \(e\) and generates a public modulus \(N\) and a private exponent \(d\). They then publish the public components \(e\) and \(N\). Whenever someone wants to send them a message \(m\), they can encrypt it by computing \(M = m^e \bmod N\) and send that instead. The recipient can then compute \(M^d \bmod N = m^{ed} \bmod N = m\) to retrieve the original message.

So, when the public exponent is 3, the encrypted message is \(m^3 \bmod N\). And, if the original message is very short, it's possible that \(m^3 < N\), and we can recover the original message simply by taking the cube root of the encrypted version!

Let's start writing some code to try this out. I used Python, since I'm familiar with it and it has packages for everything complicated, but pretty much any modern language should be fine.

First, read in the public key (using PyCrypto) and message:

from Crypto.PublicKey import RSA

with open('public_key.pem', 'rb') as f:  
    public_key = RSA.importKey(f.read()).n

with open('message.enc', 'rb') as f:  
    message = int.from_bytes(f.read(), byteorder='big')

Unfortunately, Python doesn't have great support for non-integral powers of large integers -- it starts by trying to convert them to floats, which doesn't work very well with 256-bit numbers. So I put together a quick implementation that uses Newton's method:

def cube_root(n):  
    guess, previous = n, 0
    while abs(guess - previous) > 1:
        previous = guess
        guess = guess - (guess // 3) + (n // (3 * pow(guess, 2)))

    while pow(guess, 3) > n:
        guess -= 1

    return guess

Since the message was presumably intended to be read by humans, it seems a safe assumption that it will be boring ASCII text. Python 3 supplies a convenient function for turning an integer into a byte sequence; here's a wrapper that uses the right parameters for our use case:

def to_bytes(n):  
    return n.to_bytes((n.bit_length() // 8) + 1, byteorder='big')

Great! Now, if we try this out, we get:

>>> print(to_bytes(cube_root(message)))
b'\x04\x83\xfa\xc6\xe0&L\x12\xb3\x01/!\xd4\x1f\t\xfc\x82f\x98\xcb\x8b\x04\xd4\x08\xac\xf8=\xaaZW\xc6\xddD1j\x16~\x98\x02\xc2N\xa4n\xf4\x06\r\x14S\x82\xc6\xfd\x07F\x12Z\xf0\xce\xeap\x80\xe0\x15\x05\x8b_\x903\x03\xd7\xbf\xd8\\\xdc&\xce\xa6 \xa5n\xc7\xe9\x1d\xc6mD\xeb'  

... hmm. It looks like this isn't the easiest-possible case after all. In retrospect, we should have expected this: it's not terribly likely that a small message would encrypt to be exactly 256 bytes long.

The next idea is that maybe the encrypted message \(m^3\) isn't strictly less than the modulus, but is instead slightly larger? More precisely, \(M = m^3\bmod N\), so \(M + kN = m^3\) for some integer \(k\). What if this \(k\) is small?

One more small function implements this. To determine whether we've found the right \(k\), we again assume that the plaintext is printable ASCII, so no byte's value will be 128 or larger.

def try_multiple(k):  
    message_guess = cube_root(message + k * modulus)
    message_bytes = to_bytes(message_guess)

    if max(message_bytes) < 128:
        print(stringify(message_bytes))
        return True
    else:
        return False

k = 0  
while not try_multiple(k):  
    k += 1

Put it all together, run it, and less than 30 seconds later:

b'Ron Rivest will be giving a short talk at 9am, Wednesday January 27th 2016 @enigmaconf'  

Awesome!

The mitigation

"But wait," you think. "RSA is supposed to be secure! But we just decrypted a message, without the private key, in under a minute!"

That's right! Everyone panic!

... not really. We were only able to decrypt this message because it was short and it used a small exponent. If either of these didn't hold, it would have taken infeasibly long to decrypt. For example, in this case the modulus multiple \(k = 3192\); if the exponent had been the usual 65537 instead of 3, \(k\) is on the order of \(2^{21970}\), and this brute-force method would have taken (almost literally) forever.

Making the message longer without changing the exponent can also fix the issue. There are several standardized methods for turning a short message (this one is 86 bytes) into one that is full-length (256 bytes). This has the effect of making \(m^3\) much, much larger, which again makes the brute-force attack infeasible.

In short, this is an easy attack to defend against, but this mistakes that allow it to work are easy to make as well. If this story has a moral, it's the standard one in cryptography: Don't implement your own crypto unless you know exactly what you're doing.