The cost and time required to break 512-bit RSA encryption keys has plummeted to an all-time low of just $75 and four hours using a recently published recipe that even computing novices can follow. But despite the ease and low cost, reliance on the weak keys to secure e-mails, secure-shell transactions, and other sensitive communications remains alarmingly high.
The technique, which uses Amazon's EC2 cloud computing service, is described in a paper published last week titled Factoring as a Service. It's the latest in a 16-year progression of attacks that have grown ever faster and cheaper. When 512-bit RSA keys were first factored in 1999, it took a supercomputer and hundreds of other computers seven months to carry out. Thanks to the edicts of Moore's Law—which holds that computing power doubles every 18 months or so—the factorization attack required just seven hours and $100 in March, when "FREAK," a then newly disclosed attack on HTTPS-protected websites with 512-bit keys, came to light.
In the seven months since FREAK's debut, websites have largely jettisoned the 1990s era cipher suite that made them susceptible to the factorization attack. And that was a good thing since the factorization attack made it easy to obtain the secret key needed to cryptographically impersonate the webserver or to decipher encrypted traffic passing between the server and end users. But e-mail servers, by contrast, remain woefully less protected. According to the authors of last week's paper, the RSA_EXPORT cipher suite is used by an estimated 30.8 percent of e-mail services using the SMTP protocol, 13 percent of POP3S servers. and 12.6 percent of IMAP-based e-mail services.
"The RSA_EXPORT support for mail protocols is certainly the most alarming," Nadia Heninger, one of six researchers at the University of Pennsylvania to co-write the report, told Ars. "It seems that the word got out to maintainers to update their cipher suites for HTTPS after the FREAK attack, but not for their mail servers."
The RSA_EXPORT cipher suite is a remnant from Clinton administration laws that restricted the export of software using strong encryption. Even after the laws were no longer in effect, many software providers failed to remove functions that made it trivial for attackers to force servers to use 512-bit keys. But amazingly, even in cases where the antiquated cipher suite isn't in use, a surprising number of servers still use the weak 512-bit keys, not just for e-mail but for a variety of other extremely sensitive purposes.
Long tail of short keys
Some 10,000 servers that use the DNSSEC specification to cryptographically protect domain name system records against tampering rely on a 512-bit key, the researchers estimate. The number of 512-bit keys used to remotely access servers and computers with the SSH protocol was 508, and the number of DomainKeys Identified Mail (DKIM) keys used to prevent e-mail spoofing was 108, or almost one percent of those found online. The weak DKIM keys are significant given the massive amount of awareness they received three years ago.
A full seven percent of HTTPS-protected websites use 512-bit keys, too. Those sites are already wide open to attack since 512-bit HTTPS certificates must be self-signed rather than backed by a browser-trusted certificate authority. That means it was already trivial for man-in-the-middle attackers to swap out the existing self-signed certificate with a fraudulent one. But being able to obtain the private key of the existing certificate offers attackers a greater array of choices, including stealth.
The researchers concluded that despite widespread awareness that 512-bit keys are highly susceptible to breaking, the message still hasn't adequately sunk in with many administrators. The researchers wrote:
512-bit RSA has been known to be insecure for at least fifteen years, but common knowledge of precisely how insecure has perhaps not kept pace with modern technology. We build a system capable of factoring a 512-bit RSA key reliably in under four hours. We then measure the impact of such a system by surveying the incidence of 512-bit RSA in our modern cryptographic infrastructure, and find a long tail of too-short public keys and export-grade cipher suites still in use in the wild. These numbers illustrate the challenges of keeping an aging Internet infrastructure up to date with even decades-old advances in cryptanalysis.
Now, these lax administrators may soon run out of time. With the new hack-by-numbers template and the ultra-low cost and time requirements for factoring 512-bit keys, it's only a matter of time until they're cloned and used in in-the-wild attacks.
)
