Skip to main content

Facebook's DKIM RSA key should be crackable

If Facebook sends you a mail they will sign it using DKIM. Here are the headers from a mail I received the other day:

DKIM-Signature: v=1; a=rsa-sha1; d=facebookmail.com; s=q1-2009b;
c=relaxed/relaxed;
q=dns/txt; [email protected]; t=1276438946;
h=From:Subject:Date:To:MIME-Version:Content-Type;
bh=Yn52UpOukFZwR3a9mIx7vzTOepw=;
b=RGMm2Lp2Jms1yLuanKsEhSfSLpXQ15Y9RaGb0KgzWfGqcnEFUeQlhazkJXuT0+Nh
3iNqMAfwE6TvLQmiv55YUA==;

The signature itself is the b field (RGMm2Lp2Jms1yLuanKsEhSfSLpXQ15Y9RaGb0KgzWfGqcnEFUeQlhazkJXuT0+Nh
3iNqMAfwE6TvLQmiv55YUA==
). The a field tells you the algorithm used (in this case, it's RSA/SHA1). The d field tells you the domain of the entity that signed the mail, and the s field tells you which key you need to retrieve (q1-2009b).

So, let's go get that key (the q field tells you that this can be retrieved by a DNS TXT query):

$ dig -ttxt q1-2009b._domainkey.facebookmail.com

; <<>> DiG 9.4.3-P3 <<>> -ttxt q1-2009b._domainkey.facebookmail.com
;; global options: printcmd
;; Got answer:
;; ->>HEADER<<- opcode: QUERY, status: NOERROR, id: 19407
;; flags: qr rd ra; QUERY: 1, ANSWER: 1, AUTHORITY: 13, ADDITIONAL: 3

;; QUESTION SECTION:
;q1-2009b._domainkey.facebookmail.com. IN TXT

;; ANSWER SECTION:
q1-2009b._domainkey.facebookmail.com. 434 IN TXT "k=rsa\; t=s\; p=MFwwDQYJKo
ZIhvcNAQEBBQADSwAwSAJBAKrBYvYESXSgiYzKNufh9WG8cktn2yrmdqGs9uz8VL6Mz44
GuX8xJAQjpmPObe6p2vfTMWeztKEudwY6ei7UcZMCAwEAAQ=="

The answer section gives the actual key. It's an RSA public key, so let's turn that into a file that OpenSSL can handle:

-----BEGIN PUBLIC KEY-----
MFwwDQYJKoZIhvcNAQEBBQADSwAwSAJBAKrBYvYESXSgiYzKNufh9WG8cktn2yr
mdqGs9uz8VL6Mz44GuX8xJAQjpmPObe6p2vfTMWeztKEudwY6ei7UcZMCAwEAA
Q==
-----END PUBLIC KEY-----

Feed that file to OpenSSL and we can find out information about it.

$ openssl rsa -noout -text -pubin < facebook.key
Modulus (512 bit):
00:aa:c1:62:f6:04:49:74:a0:89:8c:ca:36:e7:e1:
f5:61:bc:72:4b:67:db:2a:e6:76:a1:ac:f6:ec:fc:
54:be:8c:cf:8e:06:b9:7f:31:24:04:23:a6:63:ce:
6d:ee:a9:da:f7:d3:31:67:b3:b4:a1:2e:77:06:3a:
7a:2e:d4:71:93
Exponent: 65537 (0x10001)

So, Facebook is using an 512-bit RSA key. Wikipedia says: "Keys of 512 bits have been shown to be practically breakable in 1999 when RSA-155 was factored by using several hundred computers and are now factored in a few weeks using common hardware."

Aside: that modulus is a 154 digit number. Good old pexpr can dump it in decimal for you:

$ ./pexpr 0x00aac162f6044974a0898cca36e7e1f561bc724b67db2ae6
76a1acf6ecfc54be8ccf8e06b97f31240423a663ce6deea9daf7d33167b3
b4a12e77063a7a2ed47193

8943186814115303114568660480537979564493722038302983441617064
6773160165001660444316004226000197630872797343250751845439313
40226281950481206150316967621011

Of course, the RSA modulus there is the product of two prime numbers and quite hard to factor. But there are techniques that can be used to break keys like that fairly fast. The General Number Field Sieve is widely used and there's a nice open source implementation called GGNFS for those that want to try.

Some months ago I started an 8 core Mac Pro machine at work on breaking this key. It ran for 70 days non-stop and was close to a break when I had to use the machine for something else.

If I can do that, pretty much anyone can. And those people will be able to forge mail from Facebook. Facebook has a simple solution, of course, just change the key length. And if you are using 512-bit RSA keys in your DKIM implementation, please stop.

PS The owner of a spam botnet could factor keys like that very quickly. Imagine having a few thousand machines that can be used for key factoring.

PPS I actually got interested in breaking DKIM keys when I read about the TI calculator break which was a break of a 512 bit RSA key done in 73 days.

Update: I received mail from Facebook indicating that they are taking this seriously and will switch for 1,024 bit keys.

Comments

Anonymous said…
Wolfram Alpha also does the trick for the hexadecimal-to-decimal conversion :) http://is.gd/cUsXu
Unknown said…
Hi, sometimes when I try to run the

openssl rsa -text -pubin -in pub.key

command, I'll get an error:

unable to load Public Key
5936:error:0906D064:PEM routines:PEM_read_bio:bad base64 decode:/SourceCache/OpenSSL098/OpenSSL098-32/src/crypto/pem/pem_lib.c:765:


which I can sometimes make go away by adding line breaks to the public key string.
Is there a proper format for that file?
Thanks for the great post.
Unknown said…
Good analysis. A quick, unscientific study of a few other domains showed all to be using 1024 bit keys, but it might be worth a more thorough look.

The other countermeasure, of course, is to rotate the keys from time to time. If one were concerned about the computational load from signing with a longer key, this might be the preferred approach. The selector name "q1-2009b" suggests that this might have been their intent, although the data I have imply strongly that they have only been signing using this key since they began signing with DKIM about October 1, 2009.
Unknown said…
I have done an analysis of key lengths being used for DKIM signatures. Details at http://blogs.cisco.com/security/comments/key_lengths_for_dkim_signatures/#more

Summary: Lots of domains are using 512-bit keys, and need to either use longer keys or rotate them periodically.
Manish! said…
Good to see that Fb is taking this seriously.

Thanks!
Danny said…
So, did you ever continue the factorization where you left off?
Quentin said…
Your blog got a mention in the comments of http://www.wired.com/threatlevel/2012/10/dkim-vulnerability-widespread/all/

Popular posts from this blog

Your last name contains invalid characters

My last name is "Graham-Cumming". But here's a typical form response when I enter it:


Does the web site have any idea how rude it is to claim that my last name contains invalid characters? Clearly not. What they actually meant is: our web site will not accept that hyphen in your last name. But do they say that? No, of course not. They decide to shove in my face the claim that there's something wrong with my name.

There's nothing wrong with my name, just as there's nothing wrong with someone whose first name is Jean-Marie, or someone whose last name is O'Reilly.

What is wrong is that way this is being handled. If the system can't cope with non-letters and spaces it needs to say that. How about the following error message:

Our system is unable to process last names that contain non-letters, please replace them with spaces.

Don't blame me for having a last name that your system doesn't like, whose fault is that? Saying "Your last name …

All the symmetrical watch faces (and code to generate them)

If you ever look at pictures of clocks and watches in advertising they are set to roughly 10:10 which is meant to be the most attractive (smiling!) position for the hands. They are actually set to 10:09.14 if the hands are truly symmetrical. CC BY 2.0image by Shinji
I wanted to know what all the possible symmetrical watch faces are and so I wrote some code using Processing. Here's the output (there's one watch face missing, 00:00 or 12:00, because it's very boring):



The key to writing this is to figure out the relationship between the hour and minute hands when the watch face is symmetrical. In an hour the minute hand moves through 360° and the hour hand moves through 30° (12 hours are shown on the watch face and 360/12 = 30).
The core loop inside the program is this:   for (int h = 0; h <= 12; h++) {
    float m = (360-30*float(h))*2/13;
    int s = round(60*(m-floor(m)));
    int col = h%6;
    int row = floor(h/6);
    draw_clock((r+f)*(2*col+1), (r+f)*(row*2+1), r, h, floor(m…

Importing an existing SSL key/certificate pair into a Java keystore

I'm writing this blog post in case anyone else has to Google that. In Java 6 keytool has been improved so that it now becomes possible to import an existing key and certificate (say one you generated outside of the Java world) into a keystore.

You need: Java 6 and openssl.

1. Suppose you have a certificate and key in PEM format. The key is named host.key and the certificate host.crt.

2. The first step is to convert them into a single PKCS12 file using the command: openssl pkcs12 -export -in host.crt -inkey host.key > host.p12. You will be asked for various passwords (the password to access the key (if set) and then the password for the PKCS12 file being created).

3. Then import the PKCS12 file into a keystore using the command: keytool -importkeystore -srckeystore host.p12 -destkeystore host.jks -srcstoretype pkcs12. You now have a keystore named host.jks containing the certificate/key you need.

For the sake of completeness here's the output of a full session I performe…