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. ®
Article source: http://go.theregister.com/feed/www.theregister.co.uk/2012/02/21/rsa_crypto_analysis/
