Slashdot Mirror
How a Google Headhunter's E-Mail Revealed Massive Misuse of DKIM
concealment writes with a tale of how an email sent to a mathematician led to him discovering that dozens of high profile companies were using easily crackable keys to authenticate mail sent from their domains. From the article: "The problem lay with the DKIM key (DomainKeys Identified Mail) Google used for its google.com e-mails. DKIM involves a cryptographic key that domains use to sign e-mail originating from them – or passing through them – to validate to a recipient that the header information on an e-mail is correct and that the correspondence indeed came from the stated domain. When e-mail arrives at its destination, the receiving server can look up the public key through the sender's DNS records and verify the validity of the signature. Harris wasn't interested in the job at Google, but he decided to crack the key and send an e-mail to Google founders Brin and Page, as each other, just to show them that he was onto their game."
If it's easy to misuse, doesn't that make it broken?
No.
If I convince ignorant people that PGP signatures prove that they've actually won $47,325,443 in the Nigerian lottery, and all they need to do is send their account details so I can deposit their winnings, is PGP broken?
This wasn't even a true misuse of DKIM. It was use of a 512 bit key.
Something that many people seem to forget is that the strength of the security should be matched against the risk and costs of being broken. If I'm sending you a message that says "meet me at the corner of 5th and Smith St in five minutes", and it takes someone who intercepts the message an hour to break it, then the encryption has done its job just fine. By the time they break it, we will no longer be at 5h and Smith St, and they will have had no time to set up surveillance.
Given the intended use of DKIM, 512 bits is plenty.
This problem has been reported by the US-CERT (part of the US Department of Homeland Security [Insecurity?]) at http://www.kb.cert.org/vuls/id/268267. See that link for an authoritative report on the meaning of this problem and how to avoid it.
To add more detail to the AC's response.
AES is based on a subsitution-permutation network.
DKIM is based on the RSA signature algorithm which relies on the difficulty of factoring large integers.
Elliptic curve public key cryptography is based on the difficulty of solving a discrete logarithm problem.
The difference in the size of keys between one type of algorithm or another is an expression of the difficulty in solving the underlying problem. Factoring a large integer of X bits (RSA) is relatively easy compared to working through the substitutions and permuations of X bits of AES.
The link below provides a guideline for comparing the key sizes of AES, EC, RSA/DH.
http://www.nsa.gov/business/programs/elliptic_curve.shtml
The DKIM spec itself (RFC6376) says: "Signers MUST use RSA keys of at least 1024 bits for long-lived keys."
It's pretty unequivocal. Google just misconfigured their mailserver.