How to make a security geek feel very old: #Factorisation, #DKIM and @DrZacharyHarris

So this afternoon I got forwarded:

How a Google Headhunter’s E-Mail Unraveled a Massive Net Security Hole

So [Zach Harris] wondered if the e-mail might have been spoofed – something sent from a scammer to appear to come from the search giant. But when Harris examined the e-mail’s header information, it all seemed legitimate.

Then he noticed something strange. Google was using a weak cryptographic key to certify to recipients that its correspondence came from a legitimate Google corporate domain. Anyone who cracked the key could use it to impersonate an e-mail sender from Google, including Google founders Sergey Brin and Larry Page.

The problem lay with the DKIM key (DomainKeys Identified Mail) Google used for its 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 domain in 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.

For security reasons, the DKIM standard calls for using keys that are at least 1,024 bits in length. But Google was using a 512-bit key – which could be easily cracked with a little cloud-computing help.

Harris thought there was no way Google would be so careless, so he concluded it must be a sly recruiting test to see if job applicants would spot the vulnerability.

…well, sure, yeah, ‘course you do. It’s a fun read, but the thing that hit me like a ton of bricks was this:

“A 384-bit key I can factor on my laptop in 24 hours,” he says. “The 512-bit keys I can factor in about 72 hours using Amazon Web Services for $75. And I did do a number of those. Then there are the 768-bit keys. Those are not factorable by a normal person like me with my resources alone. But the government of Iran probably could, or a large group with sufficient computing resources could pull it off.”

I haven’t bothered keeping track, but back in 1999 the first 512-bit challenge key was factored – and it took about 4 months to achieve, the bulk of that in sieving and about a further 10 days of Cray runtime.

It was a world-record back then; for those of you who remember what a MIPS meant, it took about 8000 MIPS-years and wrangling several farms of semi-random machines including several score of workstations and servers at Sun Microsystems.

And now it’s about “75 bucks” on AWS.


Well done Dr Harris for pursuing with such elegance an outcome that was formerly a major project management effort.

And if anyone wants an good estimate of how long it will be before we factor a 1024-bit key, I am reliably informed that the first 1024-bit key will be factored on March 29th 2023, at 12:32pm.

That’s Paul Leyland’s estimate, and he should know.

Leave a Reply

Your email address will not be published. Required fields are marked *