UPDATE: First the good news: it would seem that large providers and individual server admins have for the most part found and spiked export-grade cipher suites vulnerable to the FREAK attack. The bad news: It would seem it’s even less expensive than first believed to exploit the remaining servers still supporting 512-bit RSA keys.
Researchers from Royal Holloway University in London on Monday published a report that demonstrates how an attacker, with a modest amount of computing power, could spare himself an expensive cloud-computing bill and attack servers still vulnerable to FREAK on the cheap.
When news of the FREAK (Factoring Related Attack on RSA Keys) attack broke on March 3 from researchers at Microsoft and the French National Institute for Research in Computer Science and Control, a number of widely deployed SSL clients, including OpenSSL, were deemed vulnerable. The attack forces a server to downgrade and accept 512-bit keys, which was the U.S. government-approved key strength for export overseas, a leftover artifact thought to be long-ago abandoned by most clients.
“The export-grade RSA ciphers are the remains of a 1980s-vintage effort to weaken cryptography so that intelligence agencies would be able to monitor. This was done badly. So badly, that while the policies were ultimately scrapped, they’re still hurting us today,” cryptographer Matthew Green of Johns Hopkins University explained two weeks ago. “The 512-bit export grade encryption was a compromise between dumb and dumber. In theory it was designed to ensure that the NSA would have the ability to ‘access’ communications, while allegedly providing crypto that was still ‘good enough’ for commercial use. Or if you prefer modern terms, think of it as the original ‘golden master key’.”
The Royal Holloway study included a scan of the IPv4 address space (using the University of Michigan’s ZMap tool) which found 22.7 million hosts supporting TLS, 2.2 million of which offered export-grade 512-bit RSA keys when probed. Original reports from Microsoft and the French researchers put the original number of vulnerable servers at 26 percent, much higher than the 9.7 percent rendered by this most recent scan.
The researchers, Martin R. Albrecht, Davide Papini, Kenneth G. Paterson and Ricardo Villanueva-Polanco, performed a computation using fastgcd software against 1.6 million distinct keys (once duplicates were removed from the original set of 2.2 million supporting the 512-bit keys). In doing so, they were able to factor 90 of the unique RSA moduli (at $100 per), meaning that 90 distinct keys shared moduli, Albrecht said. Because the keys shared moduli, Albrecht said, the factorization was done relatively inexpensively and in less than three minutes on eight 3.3Ghz Xeon core systems, and required less than 2GB of RAM. The researchers said they saved the $9,000 that it would have cost to use cloud-based resources to attack each one directly.
Albrecht said there were also many repeated moduli, including one cluster of 28,394.
“For those keys, we still have to spend $100 dollars, but we can use the result of this computation to break the encryption for all 28,394,” Albrecht said. “These keys were of the form `N_1 = p * q’ and `N_2 = p * q’. If this happens I still need to factor using a not-so-cheap method, but one factorization allows me to do more damage after.”
“In this particular instance, these devices all seem to be consumer/small business level routers from the same manufacturer. The manufacturer simply put the same key on all these devices,” Albrecht told Threatpost, adding that the device may also generate the key from poor randomness.
“When these devices boot up they generate these keys afresh on the device. If these devices do not have sufficient randomness they might produce the same key,” Albrecht said. “Recall that `n = p*q’ is a modulus for RSA where `p’ and `q’ are random primes (with some additional constraints not of relevance here). If your random number generator spits out the same numbers after each boot you’ll generate the same `n’.”
Knowing the value of these primes undercuts any means of security in the encryption, giving an attacker an easy path to cracking the keys and owning traffic emanating from it. The ability to downgrade crypto to 512 bits is an alarming aspect of the FREAK attack, but almost as equally disturbing is the amount of modulus reuse, Albrecht said.
“I only have to factor once to break all traffic using the same modulus. If I already have the factorization because I have access to an affected device I don’t even need to factor,” he said.
This article was updated at noon ET with clarifications throughout.
