This paper has as much social science commentary as math. Things I found interesting or amusing:
pg2 (last graf into pg3)
Publication of results undermining the security of live keys is uncommon and inappropriate, unless all aff ected parties have been noti fied. In the present case, observing the above phenomena on lab-generated test data would not be convincing and would not work either: tens of millions of thus generated RSA moduli turned out to behave as expected based on the above assumption. Therefore limited to live data, our intention was to con firm the assumption, expecting at worst a very small number of counterexamples and aff ected owners to be notifi ed. The quagmire of vulnerabilities that we waded into, makes it infeasible to properly inform everyone involved...
"Of course when we generate keys ourselves they work fine. We have no idea why there are so many collisions in the real world, and there are so many plausible suspects we don't even know where to start notifying people.
pg3 (last graf)
As was the case with the Debian OpenSSL vulnerability, we believe that publication is preferable to attempts to cover up weaknesses. There is a risk, but people desiring to exploit the current situation will have to redo our work, both the data collection and the calculation, as we have put our data under custody. We hope that people who know how to do the computation quickly will show good judgment.
Translated: "On the scale of crypto attacks this is so easy to do that just talking about it discloses the attack; please don't be dicks about that."
pg 5
... Except for eight times e = 1 and two even e-values among the PGP RSA keys ...
!!!
... Two e-values were found that, due to their size and random appearance, may correspond to a short secret exponent (we have not investigated this).
Looking at the owners with shared n-values among the relevant set of 266 729 X.509 certi cates, many of the duplications are re-certi cations or other types of unsuspicious recycling of the same key material by its supposedly legal owner. It also becomes clear that any single owner may come in many di fferent guises. On the other hand, there are also many instances where an n-value is shared among seemingly unrelated owners. Distinguishing intentionally shared keys from other duplications (which are prone to fraud) is not straightforward, and is not facilitated by the volume of data we are dealing with (as 266 729 cases have to be considered). We leave it as a subject for further investigation into this "fuzzy" recognition problem to come up with good insights, useful information, and reliable counts.
Translation: "This is not the only WTF we found in the survey."
pg 7
Although 512-bit and 768-bit RSA moduli were factored in 1999 and 2009, respectively, 1.6% of the n-values have 512 bits (with 0.01% of size 384 and smallest size 374 occurring once) and 0.8% of size 768. Those moduli are weak, but still o ffer marginal security. A large number of the 512-bit ones were certifi ed after the year 2000 and even until a few years ago. With 73.9% the most common size is 1024 bits, followed by 2048 bits with 21.7%. Sizes 3072, 4096, and 8192 contribute 0.04%, 1.5%, and 0.01%, respectively. The largest size is 16384 bits, of which there are 181 (0.003%).
Most certs have 1024 bit keys, but there are still semirecent 512 bit certs out there.
pg 8
Generation of a regular RSA modulus consists of finding two random prime numbers. This must be done in such a way that these primes were not selected by anyone else before. The probability not to regenerate a prime is commensurate with the security level if NIST's recommendation is followed to use a random seed of bit-length twice the intended security level. Clearly, this recommendation is not always followed.
The nut graf of the paper, right?
footnote:
Much larger datasets can be handled without trouble. We chose not to describe the details of our calculation or how well it scales (sapienti sat). On a 1.8GHz i7 processor the straightforward approach would require about ten core-years and would not scale well. Inclusion of the p and q-values from Section 4 and the primes from related to the Debian OpenSSL vulnerability did not produce additional results.
Sapienti sat: "a word to the wise", which I take to mean, if you understand basic RSA attacks, this stuff is pretty straightforward. Notable: the Debian OpenSSL CSPRNG bug didn't seem to contribute to this finding.
pg 9
Irrespective of the way primes are selected (additive/sieving methods or methods using fresh random bits for each attempted prime selection), a variety of obvious scenarios is conceivable where poor initial seeding may lead to mishaps, with duplicate keys a consequence if no "fresh" local entropy is used at all. If the latter is used, the outcome may be worse: for instance, a not-properly-random fi rst choice may be prime right away (the probability that this happens is inversely proportional to the length of the prime, and thus non-negligible) and miss its chance to profi t from local entropy to become unique. But local entropy may lead to a second prime that is unique, and thus a vulnerable modulus.
To me the most interesting graf: here's a story about how generating a random prime is tricky even when you have a reliable source of random bits. You write a prime generator that taps entropy only after each guess. If your first guess is prime, you never tap entropy at all; you generate "correct" but insecure results.
Then, yadda dadda I skipped all the stuff about DSA and ElGamal except:
The only interesting fact we can report about ECDSA is the surprisingly small number of certi cates encountered that contain an ECDSA key (namely, just one), and the small number of certi cates signed by ECDSA (one self-signed and a handful of RSA keys).
Yay for progress!
pg 13
The lack of sophistication of our methods and fi ndings make it hard for us to believe that what we have presented is new, in particular to agencies and parties that are known for their curiosity in such matters. It may shed new light on NIST's 1991 decision to adopt DSA as digital signature standard as opposed to RSA, back then a "public controversy"; but note the well-known nonce-randomness concerns for ElGamal and (EC)DSA and what happens if the nonce is not properly used.
OH SNAP, NSA. This is so easy even YOU could figure it out.
Regarding nonce-randomness: this is what happened to Sony; if nonces to DSA are predictable, the whole algorithm falls.
The remaining connected
component is the most intriguing - or suspicious - as it is a complete graph on nine vertices
(K9): nine primes, each of whose
9C2 = 36 pairwise products occurs as n-value.
There's an RSA key generator out there which randomly picks two primes from a set of 9.
I'd love to know if the author of that generator knew that that's what (s)he was doing.
That is, I like the idea of someone trying to be a bit too clever and accidentally borking their code due to their unfamiliarity with math rather more than I like the idea of that kind of negligence.
Of course, who's to say that a single generator isn't responsible for more than one connected component of the graph...?
> OH SNAP, NSA. This is so easy even YOU could figure it out.
For what it's worth, my impression of that text was not as much about whether they could figure it out, but that they pretty much must have at this point given how simple it was. I don't think they were dissing the capabilities of the NSA, but simply trying to provide insight on the likelihood that this was included in them, and they concluded it almost certainly was.
I'm sure you're right, but the premise I was (facetiously) working from is that the NSA would ordinarily be presumed to have figured something out regardless of the level of sophistication involved in the attack.
Ah. We academics are sticklers about novelty and we try and pin down what is and isn't. We also maintain the conceit that most of our published ideas are. As far as most of us are concerned, our ideas are probably novel unless published elsewhere. These types of things are notable exceptions.
Which reminds me of a conversation I was having the other day which noted that there's not much fear of the NSA scooping you as a researcher because they don't really like publishing things they find useful. :)
It's just our weird and somewhat arrogant perspective, I think. :)
pg2 (last graf into pg3)
Publication of results undermining the security of live keys is uncommon and inappropriate, unless all aff ected parties have been noti fied. In the present case, observing the above phenomena on lab-generated test data would not be convincing and would not work either: tens of millions of thus generated RSA moduli turned out to behave as expected based on the above assumption. Therefore limited to live data, our intention was to con firm the assumption, expecting at worst a very small number of counterexamples and aff ected owners to be notifi ed. The quagmire of vulnerabilities that we waded into, makes it infeasible to properly inform everyone involved...
"Of course when we generate keys ourselves they work fine. We have no idea why there are so many collisions in the real world, and there are so many plausible suspects we don't even know where to start notifying people.
pg3 (last graf)
As was the case with the Debian OpenSSL vulnerability, we believe that publication is preferable to attempts to cover up weaknesses. There is a risk, but people desiring to exploit the current situation will have to redo our work, both the data collection and the calculation, as we have put our data under custody. We hope that people who know how to do the computation quickly will show good judgment.
Translated: "On the scale of crypto attacks this is so easy to do that just talking about it discloses the attack; please don't be dicks about that."
pg 5
... Except for eight times e = 1 and two even e-values among the PGP RSA keys ...
!!!
... Two e-values were found that, due to their size and random appearance, may correspond to a short secret exponent (we have not investigated this).
Good reference: Boneh at http://www.ams.org/notices/199902/boneh.pdf --- under "Elementary attacks"
pg 6
Looking at the owners with shared n-values among the relevant set of 266 729 X.509 certi cates, many of the duplications are re-certi cations or other types of unsuspicious recycling of the same key material by its supposedly legal owner. It also becomes clear that any single owner may come in many di fferent guises. On the other hand, there are also many instances where an n-value is shared among seemingly unrelated owners. Distinguishing intentionally shared keys from other duplications (which are prone to fraud) is not straightforward, and is not facilitated by the volume of data we are dealing with (as 266 729 cases have to be considered). We leave it as a subject for further investigation into this "fuzzy" recognition problem to come up with good insights, useful information, and reliable counts.
Translation: "This is not the only WTF we found in the survey."
pg 7
Although 512-bit and 768-bit RSA moduli were factored in 1999 and 2009, respectively, 1.6% of the n-values have 512 bits (with 0.01% of size 384 and smallest size 374 occurring once) and 0.8% of size 768. Those moduli are weak, but still o ffer marginal security. A large number of the 512-bit ones were certifi ed after the year 2000 and even until a few years ago. With 73.9% the most common size is 1024 bits, followed by 2048 bits with 21.7%. Sizes 3072, 4096, and 8192 contribute 0.04%, 1.5%, and 0.01%, respectively. The largest size is 16384 bits, of which there are 181 (0.003%).
Most certs have 1024 bit keys, but there are still semirecent 512 bit certs out there.
pg 8
Generation of a regular RSA modulus consists of finding two random prime numbers. This must be done in such a way that these primes were not selected by anyone else before. The probability not to regenerate a prime is commensurate with the security level if NIST's recommendation is followed to use a random seed of bit-length twice the intended security level. Clearly, this recommendation is not always followed.
The nut graf of the paper, right?
footnote:
Much larger datasets can be handled without trouble. We chose not to describe the details of our calculation or how well it scales (sapienti sat). On a 1.8GHz i7 processor the straightforward approach would require about ten core-years and would not scale well. Inclusion of the p and q-values from Section 4 and the primes from related to the Debian OpenSSL vulnerability did not produce additional results.
Sapienti sat: "a word to the wise", which I take to mean, if you understand basic RSA attacks, this stuff is pretty straightforward. Notable: the Debian OpenSSL CSPRNG bug didn't seem to contribute to this finding.
pg 9
Irrespective of the way primes are selected (additive/sieving methods or methods using fresh random bits for each attempted prime selection), a variety of obvious scenarios is conceivable where poor initial seeding may lead to mishaps, with duplicate keys a consequence if no "fresh" local entropy is used at all. If the latter is used, the outcome may be worse: for instance, a not-properly-random fi rst choice may be prime right away (the probability that this happens is inversely proportional to the length of the prime, and thus non-negligible) and miss its chance to profi t from local entropy to become unique. But local entropy may lead to a second prime that is unique, and thus a vulnerable modulus.
To me the most interesting graf: here's a story about how generating a random prime is tricky even when you have a reliable source of random bits. You write a prime generator that taps entropy only after each guess. If your first guess is prime, you never tap entropy at all; you generate "correct" but insecure results.
Then, yadda dadda I skipped all the stuff about DSA and ElGamal except:
The only interesting fact we can report about ECDSA is the surprisingly small number of certi cates encountered that contain an ECDSA key (namely, just one), and the small number of certi cates signed by ECDSA (one self-signed and a handful of RSA keys).
Yay for progress!
pg 13
The lack of sophistication of our methods and fi ndings make it hard for us to believe that what we have presented is new, in particular to agencies and parties that are known for their curiosity in such matters. It may shed new light on NIST's 1991 decision to adopt DSA as digital signature standard as opposed to RSA, back then a "public controversy"; but note the well-known nonce-randomness concerns for ElGamal and (EC)DSA and what happens if the nonce is not properly used.
OH SNAP, NSA. This is so easy even YOU could figure it out.
Regarding nonce-randomness: this is what happened to Sony; if nonces to DSA are predictable, the whole algorithm falls.