Random Public Crypto Keys Aren’t So Random

Public key cryptography, a system used to secure online traffic, carries a significant flaw, a group of European and American mathematicians and cryptographers has found.

Public key cryptography requires the sender and the receiver of a message to each have a digital key to encrypt and decrypt it, respectively. One of these keys is kept private.

For this to work securely, the keys have to be generated totally at random.

However, the researchers found that some of the keys they found had duplicates, which might perhaps allow the owner of one of the duplicates to hack into the messages of the other.

Except in cases where people had the same key re-signed by a different certification authority, “the problems observed represent security problems, and there really isn’t any acceptable norm for security defects,” Paul Kocher, president and chief scientist of Cryptography Research, told TechNewsWorld.

What the Researchers Discovered

The researchers collected 11.7 million openly accessible public keys from the Web. These contained 6.4 million distinct RSA modules.

RSA is an algorithm for public key cryptography. Users create and then publish the product of two large prime numbers, together with an auxiliary value, as their public key, but keep the prime factors secret.

The team found that 4 percent of 6.6 million distinct X.509 certificates and PGP keys had duplicate RSA modules. Further, 1.1 percent of the moduli were duplicated more than once, with some being duplicated thousands of times.

X.509 is a standard established by the International Telecommunication Union that specifies standard formats for public key certificates, attribute certificates and other things for a public key infrastructure.

This is an example of an X.509 certificate.

PGP, or Pretty Good Privacy, is a data encryption and decryption program that’s used for encrypting emails, files, directors and whole disk partitions, among other things.

The team’s findings were published in a paper it will present at Crypto 2012, the 32nd international cryptology conference, to be held in Santa Barbara, Calif., in August.

What the Findings Mean

“This is a problem that should never occur if systems are properly designed, so it’s evidence of defects in systems that are in day-to-day use,” Cryptography Research’s Kocher remarked. The findings also “give some real statistical evidence about the prevalence of a security issue, which is usually fairly hard to come by.”

However, there’s disagreement over how serious a problem this is.

“The report talks about generally theoretical attacks that may be practical in an exceptionally small set of targeted attack scenarios and would usually require more work than using simple social engineering or other standard surveillance tactics to obtain the desired content,” Randy Abrams, an independent security consultant, told TechNewsWorld.

“Any duplication of keys represents a theoretical threat,” Rob Enderle, principal analyst, Enderle Group, pointed out. However, “the authors did not demonstrate an actual breach, and … it may still be easier for an attacker to use a brute force attack, since determining which keys were duplicated, let alone getting hold of the duplicates, might prove unacceptably difficult.”

Some devices and appliances will need security updates, and “users who rely on SSL security to secure remote login into appliances may want to consider adding another layer of security, like a [virtual private network],” Cryptographic Research’s Kocher said.

Leave a Comment

Please sign in to post or reply to a comment. New users create a free account.

More by Richard Adhikari
More in Cybersecurity

Technewsworld Channels