Looking for a Boneh and Durfee attack in the wild posted January 2016

A few weeks ago I wrote about testing RSA public keys from the most recent Alexa's top 1 million domains handshake log that you can get on scans.io.

Most public exponents \(e\) were small and so no small private key attack (Boneh and Durfee) should have happened. But I didn't explained why.

Why

The private exponent \(d\) is the inverse of \(e\), that means that \(e * d = 1 \pmod{\varphi(N)}\).

\(\varphi(N)\) is a number almost as big as \(N\) since \(\varphi(N) = (p-1)(q-1)\) in our case. So that our public exponent \(e\) multiplied with something would be equal to \(1\), we would at least need to loop through all the elements of \(\mathbb{Z}_{\varphi(N)}\) at least once.

Or put differently, since \(e > 1 \pmod{\varphi(N)}\), increasing \(e\) over \(\varphi(N)\) will allow us to get a \(1\).

l = 1024
p = random_prime(2^(l/2), lbound= 2^(l/2 - 1))
q = random_prime(2^(l/2), lbound= 2^(l/2 - 1))
N = p * q
phiN = (p-1) * (q-1)
print len(bin(int(phiN / 3))) - 2 # 1024
print len(bin(int(phiN / 10000000))) # 1002

This quick test with Sage shows us that with a small public exponent (like 3, or even 10,000,000), you need to multiply it with a number greater than 1000 bits to reach the end of the group and possibly ending up with a \(1\).

All of this is interesting because in 2000, Boneh and Durfee found out that if the private exponent \(d\) was smaller than a fraction of the modulus \(N\) (the exact bound is \(d < N^{0.292}\)), then the private exponent could be recovered in polynomial time via a lattice attack. What does it mean for the private exponent to be "small" compared to the modulus? Let's get some numbers to get an idea:

print len(bin(N)) - 2 # 1024
print len(bin(int(N^(0.292)))) - 2 # 299

That's right, for a 1024 bits modulus that means that the private exponent \(d\) has to be smaller than 300 bits. This is never going to happen if the public exponent used is too small (note that this doesn't necessarely mean that you should use a small public exponent).

Moar testing

So after testing the University of Michigan · Alexa Top 1 Million HTTPS Handshakes, I decided to tackle a much much larger logfile: the University of Michigan · Full IPv4 HTTPS Handshakes. The first one is 6.3GB uncompressed, the second is 279.93GB. Quite a difference! So the first thing to do was to parse all the public keys in search for greater exponents than 1,000,000 (an arbitrary bound that I could have set higher but, as the results showned, was enough).

I only got 10 public exponents with higher values than this bound! And they were all still relatively small (633951833, 16777259, 1065315695, 2102467769, 41777459, 1073741953, 4294967297, 297612713, 603394037, 171529867).

Here's the code I used to parse the log file:

import sys, json, base64

with open(sys.argv[1]) as ff:
    for line in ff:
        lined = json.loads(line)
        if 'tls' not in lined["data"] or 'server_certificates' not in lined["data"]["tls"].keys() or 'parsed' not in lined["data"]["tls"]["server_certificates"]["certificate"]:
            continue
        server_certificate = lined["data"]["tls"]["server_certificates"]["certificate"]["parsed"]
        public_key = server_certificate["subject_key_info"]
        signature_algorithm = public_key["key_algorithm"]["name"]
        if signature_algorithm == "RSA":
            modulus = base64.b64decode(public_key["rsa_public_key"]["modulus"])
            e = public_key["rsa_public_key"]["exponent"]
            # ignoring small exponent
            if e < 1000000:
                continue
            N = int(modulus.encode('hex'), 16)
            print "[",N,",", e,"]"