'Predictably random' public keys can be cracked - crypto boffins

Battling researchers argue over whether you should panic

The Essential Guide to IT Transformation

Analysis Cryptography researchers have discovered flaws in the key generation that underpins the security of important cryptography protocols, including SSL.

Two teams of researchers working on the problem have identified the same weak key-generation problems. However, the two teams differ in their assessment of how widespread the problem is – and crucially which systems are affected. One group reckons the problem affects web servers while the second reckons it is almost completely confined to embedded devices.

EFF group: It could lead to server-impersonation attacks

An audit of the public keys used to protect HTTPS connections, based on digital certificate data from the Electronic Frontier Foundation's SSL Observatory project, found that tens of thousands of cryptography keys offer "effectively no security" due to weak random-number generation algorithms.

Poor random-number generation algorithms led to shared prime factors in key generation. As a result, keys generated using the RSA 1024-bit modulus, the worst affected scheme, were only 99.8 per cent secure. Such a figure would be considered very good in most circumstances, but not in this context because it means two out of every 1,000 of these RSA public keys are insecure.

The weakness creates all manner of problems, as the researchers explain.

The consequences of these vulnerabilities are extremely serious. In all cases, a weak key would allow an eavesdropper on the network to learn confidential information, such as passwords or the content of messages, exchanged with a vulnerable server.

Secondly, unless servers were configured to use perfect forward secrecy, sophisticated attackers could extract passwords and data from stored copies of previous encrypted sessions. Thirdly, attackers could use man-in-the-middle or server impersonation attacks to inject malicious data into encrypted sessions.

The researchers, led by Arjen Lenstra of Ecole Polytechnique Federale de Lausanne, are working with the EFF to notify operators of servers affected by the vulnerability, urging them to switch to new keys as soon as possible. The group will also be discussing its findings with Certificate Authorities and browser vendors.

The team used a 2,400-year-old Euclidean algorithm to look for cases where prime factors were unexpectedly shared by multiple visible public keys, as well as keys that were unexpectedly shared by multiple certificates – which are much easier to spot. The security of algorithms relies on the computational difficulty of factoring the product of two very large prime numbers. This security is seriously undermined if the prime factors used are not random.

The study focused on looking at RSA (the cryptosystem behind TLS, which is used to secure HTTPS transmissions) and ElGamal (the most common class of cryptosystem behind PGP).

Michigan group: It just affects embedded devices

Another set of security researchers working on the same problem were able to remotely compromise a higher percentage: about 0.4 per cent of all the public keys used for SSL web site security. They said: "The keys we were able to compromise were generated incorrectly – using predictable 'random' numbers that were sometimes repeated."

The group - Zakir Durumeric, Eric Wustrow, Alex Halderman, and Nadia Heninger of the University of Michigan - were able to develop a tool that could factor these keys and give them the private keys to all the hosts vulnerable to this attack on the internet in only a few hours.

The Michigan group reckons the problem largely affects network devices, rather than web servers, and is certainly no reason to avoid taking advantage of the cost and convenience benefits brought by e-commerce, as they explain in a blog post on Freedom to Tinker.

There's no need to panic as this problem mainly affects various kinds of embedded devices such as routers and VPN devices, not full-blown web servers. (It's certainly not, as suggested in the New York Times, any reason to have diminished confidence in the security of web-based commerce.)

Unfortunately, we've found vulnerable devices from nearly every major manufacturer and we suspect that more than 200,000 devices, representing 4.1% of the SSL keys in our dataset, were generated with poor entropy. Any weak keys found to be generated by a device suggests that the entire class of devices may be vulnerable upon further analysis.

Almost all of the vulnerable keys were generated by and are used to secure embedded hardware devices such as routers and firewalls, not to secure popular web sites such as your bank or email provider. Only one of the factorable SSL keys was signed by a trusted certificate authority and it has already expired.

The US researchers are in the process of informing equipment manufacturers about the potential problem while they put the finishing touches to an upcoming paper on the subject. ®

Build a business case: developing custom apps

More from The Register

next story
14 antivirus apps found to have security problems
Vendors just don't care, says researcher, after finding basic boo-boos in security software
'Things' on the Internet-of-things have 25 vulnerabilities apiece
Leaking sprinklers, overheated thermostats and picked locks all online
iWallet: No BONKING PLEASE, we're Apple
BLE-ding iPhones, not NFC bonkers, will drive trend - marketeers
Only '3% of web servers in top corps' fully fixed after Heartbleed snafu
Just slapping a patched OpenSSL on a machine ain't going to cut it, we're told
Multipath TCP speeds up the internet so much that security breaks
Black Hat research says proposed protocol will bork network probes, flummox firewalls
How long is too long to wait for a security fix?
Synology finally patches OpenSSL bugs in Trevor's NAS
Israel's Iron Dome missile tech stolen by Chinese hackers
Corporate raiders Comment Crew fingered for attacks
Fiendishly complex password app extension ships for iOS 8
Just slip it in, won't hurt a bit, 1Password makers urge devs
Tor attack nodes RIPPED MASKS off users for 6 MONTHS
Traffic confirmation attack bared users' privates - but to whom?
prev story


Implementing global e-invoicing with guaranteed legal certainty
Explaining the role local tax compliance plays in successful supply chain management and e-business and how leading global brands are addressing this.
Boost IT visibility and business value
How building a great service catalog relieves pressure points and demonstrates the value of IT service management.
Why and how to choose the right cloud vendor
The benefits of cloud-based storage in your processes. Eliminate onsite, disk-based backup and archiving in favor of cloud-based data protection.
The Essential Guide to IT Transformation
ServiceNow discusses three IT transformations that can help CIO's automate IT services to transform IT and the enterprise.
Maximize storage efficiency across the enterprise
The HP StoreOnce backup solution offers highly flexible, centrally managed, and highly efficient data protection for any enterprise.