DKIM-Signature: v=1; a=rsa-sha1; d=facebookmail.com; s=q1-2009b;
q=dns/txt; firstname.lastname@example.org; t=1276438946;
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
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-----
-----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):
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
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.