A blog post that appeared last Friday, observed that Facebook is signing their mail with DomainKeys Identified Mail (DKIM) using a 512-bit RSA key. The author went on to analyze the security of doing so as compared with a longer key, and concluded that a determined attacker could probably factor the public key quickly enough to be useful in sending falsified messages purporting to be from Facebook. The blogger, John Graham-Cumming, said:
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.
One question that comes to mind is how many other domains are using 512-bit keys? It’s hard to answer this question directly because one needs to know the “selector” (key name which is included in the signature) to look up the key, but some of the data Cisco has collected on DKIM metrics gives an approximation. The methodology is a bit indirect because we don’t collect the selector name for successful verifications (only for failures), but since we usually get a smattering of verification failures for domains sending us messages, we can use that data to infer the selector names they use.
Here is the breakdown of key lengths by number of domains:
As you can see, Facebook is far from being alone in using a 512-bit key; about a third of domains do so. Facebook is an important domain, however, since users are accustomed to clicking on links (such as friend requests) received in Facebook mail messages, making them good targets for phishing attacks. There isn’t an objective way to characterize which domains would be good vehicles for phishing, but one proxy for that might be to look at the number of messages received from a given domain. Weighted by the number of messages successfully verified we have the following:
This information shows that there are some substantial senders of email that are using 512-bit keys, and relatively fewer are using large keys. It is computationally easier to sign messages with shorter keys, and some domains may do so to minimize the possibility that their mail signers will become compute-bound. One thing to bear in mind is that DKIM signatures are short-lived, so keys may be rotated relatively easily. Domains that want to use 512-bit keys should rotate their keys relatively often. Shorter keys should not be used; the DKIM specification does not require that shorter keys be supported by verifiers.
Of course, there are a great many domains, including many that might be considered “important” in terms of the potential for spoofing abuse, that do not sign with DKIM at all. This concern about key lengths should be interpreted by those domains as a sign of the importance of email authentication.