Was Ron really wrong?

In 2012, Lentra et al. published an article provocatively titled "Ron was wrong, Whit is right".  It researched and questioned the strength of RSA encryption keys, importantly, the security of the “trap door” one way function of the use of large prime number.

Was Ron really wrong? Let's analyse Lenstra et al's paper.

Lenstra et al collected random cryptographic public keys and performed sanity checks to assess whether, indeed, unique random keys were generated each time.  The authors concluded that Diffie-Hellman keys were more secure than RSA algorithm ones.

When developing a RSA public key there should be two random large and unique prime numbers.  The research uncovered there is collision, however, whereby keys were identical or partially not unique.  However, this was only a very small percent: 12,720 out of 4,700,000 (0.27%) so the number of common public prime numbered keys could be argued as rare.  Nonetheless, the commonalities are not surprising given the computer systems generating random keys may be working on a pseudorandom code which does not truly generate random numbers.  Further, developers are not adhering to good design practices so compromising on security for efficiency.  The risk is these duplications are susceptible to fraud; thus, will generate similar keys.  This makes it possible for an attacker (if they go to the same lengths are researchers in the article) to find and use a victim’s key (say, Bob) which will have enough cryptographic similarities to decrypt another person’s data (say, Alice).

The authors did also uncover furthers duplicates found in the ElGamal and RSA keys than Holz et al.  Thus, for an attacker to compromise Diffie-Helman is still possible given they would need to find only one prime number, albeit may take longer which is a good security mechanism.

"…publication of results undermining the security of live keys is uncommon and inappropriate, unless all affected parties have been notified."

There are few publications of results undermining security flaws which the authors highlighted, whether it is based on live or, especially, test data.  This can be because of the fear of adverse publicity.  The article encouraged the constant peer-review as technologies change and sharing of results, even if it is bad news, as this can only benefit the security of the different protocols.

"…not to regenerate a prime is commensurate with the security level if NIST’s recommendation."
A main finding of the article is the common occurrence of primes; this could be solved if developers were not complacent at following guidelines/standards in this area.  Rules should be followed more rigorously at every stage (from beginning to end); and security should be implemented in RSA and ElGamal as thousands did not.

"…adequate contact information limited our options."

A lesson from this is for organisations that develop RSA or Diffie-Hellman to ensure they keep their contact details up-to-date as, in this instance, when the authors tried to contact developers they found some details were non-existent or out-dated.  As stated, publication could risk exposing weakness but should be a preference to raise the awareness.  For attackers, they would still have a lot of work to take advantage of weaknesses, some of the techniques would be too cumbersome for them.

The essential finding is that a surprising percentage of RSA moduli surveyed were the same, or had primes on common.  Given the size of RSA moduli, this should not be happening and suggests flaws in the ways that RSA primes are being generated.  The main lesson here is that secure key generation for all cryptosystems is crucial. This is arguably particularly so for public-key cryptosystems where the complexity of key generation seems to lend itself to the implementation of poor practice.