HTTPS-crippling FREAK attacks become cheaper and easier to carry out

There's more bad news surrounding the HTTPS-crippling FREAK vulnerability that came to light two weeks ago. A recently completed scan of the Internet revealed 10 percent of servers that support the underlying transport layer security protocol remain susceptible. Even worse, many of these laggards contain an additional weakness that drastically drives down exploitation costs, in the most extreme cases to just pennies per server.

As Ars reported almost two weeks ago, so-called FREAK attacks—short for Factoring attack on RSA-EXPORT Keys—are possible when an end user with a vulnerable device connects to an HTTPS-protected website configured to use a weak, 512-bit encryption key. Previously, it took about seven hours and $100 in cloud-computing fees to break such a key. The attack worked by painstakingly analyzing the 512-bit modulus of a vulnerable RSA key pair to discover the two underlying prime numbers that produced it. Attackers had to factor the key of each vulnerable website they wanted to exploit. The work and cost required made it hard to exploit the weakness in mass numbers. Meanwhile, the number of servers that stopped using weak 512-bit keys in the days following the FREAK disclosure acted as a further disincentive for would-be attackers.

Now comes word of an easier, less costly exploit. An Internet scan carried out one week after FREAK came to light has turned up evidence suggesting the weakness may not be so difficult to exploit after all. Of the 22.7 million servers found to support TLS encryption, 2.2 million—or 9.7 percent of them—continued to offer the export-grade 512-bit keys. More troubling still, the team of researchers from Royal Holloway University of London found large clusters of repeated moduli inside the keys' mathematical DNA. In the most extreme case, a single 512-bit modulus appeared 28,394 times in the survey, meaning there were that many servers using precisely the same underlying prime numbers that, when multiplied together, produced the common modulus. Spending $100 and seven hours, then, would allow attackers to spoof as many as 28,394 sites or devices or to decrypt their TLS-protected traffic. That breaks down to about three cents per server or device.

Two additional moduli appeared more than 1,000 times each, and a total of 1,176 moduli were seen 100 times or more each. In all, the researchers uncovered a whopping 664,336 duplicate moduli out of the 2.2 million TLS servers configured to work with 512-bit keys.

Here we go again

It's not the first time researchers have uncovered RSA keys deemed cryptographically worthless because one or both of their underlying prime numbers are used by at least one other key. In early 2012, a team of mathematicians found that an astonishing four out of every 1,000 1024-bit keys available on the Internet were defective after subjecting their moduli to an algorithm first postulated more than 2,000 years ago by the Greek mathematician Euclid. In 2013, a similar fatal flaw was uncovered in Taiwan's secure digital ID system.

Even when small, the number of defective keys is troubling because shared primes should never, ever be found in the wild. That's because the number of possible primes available for even a weak 512-bit key, according to cryptographer Justin Troutman, is 2²⁴⁸—vastly more than the 2⁶² estimated grains of sand on earth, but less than the 2²⁶⁶ atoms in the known universe. (The number of available primes is orders of magnitude greater for keys of 1024 or 2048 bits.) If all these primes are properly mixed up and evenly distributed the way they're supposed to be during a properly executed key generation, no two primes should ever be picked twice.

By definition, a prime is a number greater than one that has no positive divisors other than one and itself. A modulus is defined as the product of the two underlying prime numbers. In a nutshell, the security of RSA-based cryptography comes down to this: while it's easy to multiply the two prime numbers, it's nearly impossible for someone with only the modulus to identify its two underlying prime numbers. The reuse of prime numbers or entire moduli uncovered by the Royal Holloway researchers completely undermines this promise. The 664,336 duplicate moduli they found means websites that use them are vulnerable to low-cost attacks that can completely bypass the benefits of TLS encryption.

Even when discarding the duplicate moduli, the researchers were able to factor 90 of the remaining keys by subjecting them to the same Euclid-postulated algorithm mentioned earlier in this post. The formula worked by computing the greatest common divisor of all moduli to uncover those that use a common prime. To speed up the process, the researchers borrowed a software previously devised by a team led by computer scientist Nadia Heninger and an algorithm devised by cryptographer Dan Bernstein. The enhancements allowed the Royal Halloway researchers to carry out the 90 factorizations in less than three minutes on a computer running eight 3.3Ghz Xeon cores and less than 2GB of RAM. The technique is a good example of how attacks only get better with time, since the original FREAK attack would have required considerably more overhead.

"The computation took less than three minutes on an 8-core system, saving the $9,000 that a cloud computation would have cost if each modulus had been attacked directly," the researchers wrote. "We consider this to be a good return on an investment for a Friday afternoon's work."