Experts: RSA weak keys flaw restricted to network devices
Primal fear
Customer Success Testimonial: Recovery is Everything
Analysis Flaws in the way some of EMC's RSA security division encryption keys are generated are down to a weakness in generating random numbers that's restricted to network devices rather than digital certificates on websites, according to both RSA and cryptographic researchers.
After analysing 7.1 million keys, cryptography researchers found that 27,000 (or 0.03 per cent) of them were improperly generated, offering “no security at all”. The finding was based on an audit of public keys used to protect HTTPS connections, using data from the Electronic Frontier Foundation's SSL Observatory project, led by Arjen Lenstra of Ecole Polytechnique Federale de Lausanne (EPFL). The team used a 2,400-year-old Euclidean algorithm to look for cases where prime factors were unexpectedly shared by multiple public keys.
The team published a paper, Ron Was Wrong, Whit Was Right , outlining their analysis and (disputed) conclusions.
A strong random number generator, properly seeded with adequate entropy, is used to generate two primes from which digital keys based on RSA are derived. Strong random number generation underpins the security of public key cryptography.
The finding from the EPFL team might suggest that the security of digital certificates on e-commerce websites was at risk, but this is not the case, according to a second group of security researchers working on the same problem.
The other group carried out a deeper analysis that tracked down the root cause of the problem: poor random number generation in embedded devices. The second team, from the University of Michigan and UC San Diego, were able to compromise a higher percentage: 0.4 per cent of digital keys. "Predictable 'random' numbers were sometimes repeated," the researchers said, leading to the creation of weak keys.
However these weak keys were almost entirely restricted to embedded devices: "firewalls, routers, VPN devices, remote server administration devices, printers, projectors, and VOIP phones" from over 30 manufacturers.
Such devices typically have fewer sources of randomness than general purpose computers. This factor, together with starting off with weak entropy, lies at the heart of the problem. Only one of the factorable SSL keys by the Michigan team was signed by a trusted certificate authority – and that had already expired.
In an update to its original statement, the EPFL team accepted this more limited diagnosis of the problem with weak keys.
"It seems the scope of the problem with respect to keys associated with X.509 certificates is limited primarily to certificates that exist for embedded devices such as routers, firewalls, and VPN devices. The small number of vulnerable, valid CA-signed certificates have already been identified and the relevant parties have been notified."
RSA speaks
In a statement, RSA said the problems uncovered by the EPFL team were down to poor implementation of random number generation rather than flaws in the RSA algorithm itself, which remains secure. RSA accepts the EPFL's teams findings but disputes its conclusions.
On February 14, 2012, a research paper was submitted for publication stating that an alleged flaw has been found in the RSA encryption algorithm. Our analysis confirms to us that the data does not point to a flaw in the algorithm, but instead points to the importance of proper implementation, especially regarding the exploding number of embedded devices that are connected to the internet today. We welcome this form of research into security technologies in general, as it contributes to better overall security for everyone. The RSA algorithm has withstood such scrutiny for decades from multiple sources. But good cryptography, including RSA’s, depends on proper implementation. True random number generation underpins nearly all cryptographic algorithms and protocols, and must be performed with care to protect against the weakening of well-designed cryptography. Our analysis of the data points to the need for better care in implementation, generally tied to embedded devices. We see no fundamental flaw in the algorithm itself, and urge all cryptography users to ensure good implementation and best practices are followed.
In a blog post, Sam Curry of RSA expanded on these points and compared random number generation to a key ingredient in a dish prepared by a restaurant. If the ingredients are poor, he argued, then the result will be unpalatable – no matter how good the chef (encryption scheme) might be.
Independent security researcher Dan Kaminsky praised the EPFL team for its analysis but faulted its conclusions.
In a lengthy blog post, Kaminsky explains that the weak random number generation bug is a problem for networking kit, rather than digital certificates on websites.
"The 'weak RSA moduli' bug is almost (and possibly) exclusively found within certificates that were already insecure (ie, expired, or not signed by a valid CA)," Kaminsky argues. "This attack almost certainly affects not a single production website."
Noted cryptographer Jon Callas looked at all public keys ever signed by Entrust, finding none of them had reused RSA primes.
Experts from encryption firm Voltage Security said that the weak key issues is down to device manufacturers implementing RSA encryption in a non-standards-compliant manner. If the standards had been followed, then these weak keys would not be out there, the firm said.
"Cryptographic algorithms are almost never the root cause of security problems - at least those that are not 'in the basement' proprietary algorithms," said Terence Spies, CTO of Voltage Security. "Correct implementation of any security technology is crucial, and has proven to be quite difficult."
A useful FAQ on the practical implications of the RSA key research has been put together in a post on Kaspersky Labs' Threatpost blog here. ®
COMMENTS
What do you mean, RSA package?
In context, RSA is an algorithm, one widely taught (like, highschool math masterclasses), well-known, available. RSA-the-company was founded by the same people that cooked up the algorithm, but that doesn't mean each implementation has their hand in it, or even their blessing. This spat isn't nearly as connected to them as, say, the break-in that compromised their remote login security keyfobs.
Generally you'd want a *good* source of random numbers, and a PRNG almost by definition disqualifies itself (the "pseudo" bit), though with all sorts of clever tricks it is possible to get something less awfully bad than the old "rand()" found in historical libcs, where you need to discard the lower 12 bits to get something vaguely usable even for, say, games. Modern unices, say, will "gather entropy", possibly even keep it across reboots, and provide a reasonable source of random numbers, possibly with hardware assistance if available. You pretty much need OS support (drivers) for that last bit. Some programs bring their own random number generators, especially if the OS isn't known to provide good support.
The problem with these embedded devices is that at first start-up, they haven't been running very long and as such the random numbers they generate then aren't very good at all, even if your PRNG isn't unreasonable. And that's the point at which these certificates tend to be generated.
So, who's responsible? The embedded system designers, basically. Could chalk it down to an oversight, and an object lesson in how tiny details can wreak havoc upon an otherwise perfectly good plan, especially when crypto is involved. This sort of thing is exactly why random numbers are important.
Real "production" web sites don't have expired certificates then?
Funny, I do see them from time to time. Briefly (no thanks).
Is it?
Only because the state of the device at that point is in an almost entirely predictable state, indeed (near-)identical to others of the same make and model, or merely type. Should the thing come with a decent hardware random number generator, then suddenly they're fine, really.
If the device doesn't, then make sure you generate any and all certificates elsewhere, with a better RNG, before installing them. Otherwise it still doesn't matter a whit how they're signed. Recall that even when paying for a certificate you end up generating the private key yourself.
IT infrastructure monitoring strategies
What you need to know about cloud backup
Agentless Backup is Not a Myth
Top 10 SIEM implementer’s checklist
Customer Success Testimonial: Recovery is Everything
