RSA keys not as random as they should be
A team of cryptographic experts has analysed more than 10 million public keys and discovered serious problems in some of the X509 certificates it collected. This is because some keys were far less random than they should have been – more than 12,000 were easily crackable.
Of the 6,185,372 X.509 certificates analysed, the researchers found 266,729 public keys in which moduli were reused. The modulus is the core component of a public key – if it is the same, then the secret key matches. In one extreme case, the same modulus was found 16,489 times. This means that each of the owners of the 16,489 certificates could spoof or spy on each of the other 16,488. The researchers note that it is not unusual to recycle keys when, for example, extending a certificate, but a significant number of these keys belong to entirely independent owners.
The researchers then went one step further and determined the greatest common divisor (GCD) of the moduli collected using the Euclidian algorithm. This is a lot of work, as it requires each modulus to be combined with each of the other moduli, but possible, and if two moduli with a GCD greater than one are found, they are both effectively cracked, since the prime number factoring problem which underlies RSA encryption is then essentially solved. The researchers were able to find such GCDs with 12,720 of their (1024-bit) RSA keys. Where possible, the researchers have notified the owners of the affected keys.
Interestingly, this problem was not found when the team analysed 5 million OpenPGP keys. Marcus Brinkmann of g10 Code (the company behind GnuPG) has told The H's associates at heise Security that the few redundant OpenPGP keys appear to be being deliberately recycled. Alternative cryptographic algorithms based on the Diffie-Hellman protocol, such as (EC)DSA and ElGamal, are not affected by this issue – hence the paper's title Ron was wrong, Whit is right. This refers to Ron Rivest, the R in RSA, which displaced the key exchange protocol developed by Whitfield Diffie and Martin Hellman.
Both the moduli and the prime factors used during key generation should be randomly selected so that they are not duplicated. If this is occurring with this level of frequency, it indicates that there is a problem in the way the random numbers are being generated, as explained in The H Security article on the OpenSSL fiasco at Debian, "Good numbers, bad numbers".
According to Nadia Heninger, who has been carrying out similar research, the poor quality prime factors are probably being generated by routers, VPN gateways and other embedded devices which use OpenSSL without having an adequate source of random numbers for key generation. This means that the risk posed by these redundant keys is significantly less than it might otherwise be, with Heninger reassuring her readers that "the key for your bank's web site is probably safe". Nonetheless, the significance of this research should not be underestimated. "This paper makes a significant contribution to quality control of actual security of cryptographic implementations," suggests GPG developer Brinkmann. The researchers' work would, for example, have detected the Debian OpenSSL problem.