8 ms·

Ron was Wrong, Whit is Right

122 points by sew 15y ago

deleted 15y ago
[deleted]
nohat 15y ago
Somewhat disappointing, but not surprising that they did not describe their actual calculation technique for finding the connected primes. It strikes me that there isn't a good excuse for having bad random numbers with the computation power we now have. A simple bitwise addition of various sources of supposedly random numbers is strictly stronger than any subset of its components. So we can combine lots of questionable strong sources and get a very strong source. Generating the primes locally with insufficient independence seems more understandable than that the same primes are used by independent parties. That hints at a more severe problem with random number generation. Regardless, assuming this is confirmed, it is a significant problem that needs to be hunted down.
- a1k0n 15y ago
  It was mentioned in the nytimes article, and in retrospect it's fairly obvious: you use the Euclidean algorithm. If you have n1=p q1 and n2=p q2, so that the prime p is shared between them, then gcd(n1,n2) = p. That only takes a few iterations of bignum modulos to solve.
  - nohat 15y ago
    Ah, I took the 'the straightforward approach would require about ten core-years and would not scale well' to mean they had a more efficient method.
    - a1k0n 15y ago
      Hm, that's possible. A comprehensive search over 4 million pairs would be O(16 trillion) operations, so perhaps they gain something by reusing intermediate steps of the gcd, or something? Good point, I'm not sure. The brute-force solution is still not out of the question for a modestly large map-reduce cluster.
      - notaddicted 15y ago
        Yeah, regarding going ahead with the "naive" search, I'm coming up with a price of 5k to 15k on Amazon EC2 using the cluster compute 8XL instances, and under a month using 10 machines.
        nohat 15y ago
        Considering the potential value of some of those rsa keys, that is a quite minimal investment. This might be an in the wild danger pretty quickly.
        tptacek 15y ago
        The chances of any one key being compromised are very, very low. If this is a pattern of simple software flaws, or something environmental like keys generating during cold start entropy starvation, the likelihood of pulling a truly valuable key out of that soup are even lower: generally (not always, but generally) the more valuable keys are generated using very well known software, and under tight process constraints. So basically you get ~10k random certs that allow you to MITM ~10k random sites. It's not nothing, but criminals have better ways of monetizing attacker effort.
        nohat 15y ago
        A lot does depend on the actual circumstances for the bad RNG. If you had a good method of recognizing the valuable sites (anything involving money or maybe email?) it might be more practical considering a botnet would be just fine for this sort of computation.
grandpa 15y ago
In case it's not obvious to everyone: Ron = Ron Rivest (the R in RSA); Whit = Whitfield Diffie (of Diffie-Hellman).
- locacorten 15y ago
  What a bad choice for a paper title.
  - scott_s 15y ago
    I don't agree. It's short and gets across the main point to the right people. If you don't know the names being referred to, you're probably not the audience for the paper.
    - cperciva 15y ago
      I am the audience for this paper, and I recognized the names. I still had absolutely no clue what the title meant until grandpa pointed it out. I agree with locacorten: Horrible title.
      - tptacek 15y ago
        You can't see "Whit" and immediately know "it's Whit Diffie", or given Whit Diffie expect that "Ron" means "Ron Rivest"? I got it instantly and have way less crypto than you. Or are you saying, "Ron Rivest was wrong, Whitfield Diffie was right" is still a horrible title? The whole paper had the feel of a rump session pub, didn't it?
        dekz 15y ago
        The whole title is horrible because of its not even related to the outcome of the experiment/paper. Ron and Whit are neither both right nor both wrong, nothing in the article even came close to proving such a title. Using bad entropy is wrong. What would be nice to see is the age of the affected certificates graphed in a scatter. It would be interesting to note if there are patterns of grouping. We all read the articles from Peter Goodman et al where he demonstrates horrible entropy [0,0,0,0,0,0,0,0].
deleted 15y ago
[deleted]
jalapeno_dude 15y ago
Posting what I said in the other thread: As far as I can tell, this is what they're doing: if two different keys have a factor in common (i.e. A=PQ, B=PR), then you can use Euclid's algorithm (which just requires repeated subtraction, and is thus really easy) to find P (=gcd(A,B)), and then just use division to find Q (=A/P) and R (=B/P) easily. So what the researchers did, apparently, was to gather all the RSA public keys they could find (6 million or so) and then calculate the gcds of all pairs of keys. (Presumably they were slightly more clever than this, but it doesn't really matter--doing this is still vastly easier than factoring even a single public key). Whenever they found a gcd that wasn't equal to 1, they'd cracked (at least) 2 keys. And it turns out that roughly 0.2% of the keys could be cracked in this way (for a total of 12720 1024-bit moduli). As far as I can tell, the problem isn't with RSA itself, but with whatever algorithms are used to pick two random primes to multiply and produce the key (or moduli, whatever)--they don't have high enough entropy and output duplicates ~0.2% of the time.
- cperciva 15y ago
  As far as I can tell, the problem isn't with RSA itself, but with whatever algorithms are used to pick two random primes to multiply and produce the key (or moduli, whatever)... Correct. they don't have high enough entropy and output duplicates ~0.2% of the time. Almost correct: They don't have enough entropy at least 0.2% of the time. These results are consistent with all primes being generated with ~40 bits of entropy -- which would imply that all the keys are broken. Obviously we hope that this is not the case and instead it's just a small subset of primes which were generated with low entropy, but the data do not provide any evidence in either direction.
  - DavidSJ 15y ago
    They do write: the graph of the moduli contained in c distinct certificates consists, in an ideal world, of c disjoint connected components each consisting of two vertices joined by a single edge, for a total of 2c vertices and c edges ... tens of millions of [lab-]generated RSA moduli turned out to behave as expected based on the above assumption. That implies that there is at least one (presumably common) method for generating RSA keys which does not frequently output duplicate primes.
marshray 15y ago
As if it's somehow Ron Rivest's fault that people can't generate random numbers?
- tptacek 15y ago
  "Yes, because his algorithm requires you to get two secure ones, and other public key algorithms don't." Would be the authors' response to that.
  - dekz 15y ago
    And the retort to the author would be the case of the PS3 and ECDSA. Using low entropy PRNGs at all is the _REAL_ problem.
    - tptacek 15y ago
      Are we sure the problem is a low entropy CSPRNG? The problem could be "when bad primes happen to good CSPRNGs". (The paper itself makes the DSA point.)
      - dekz 15y ago
        They do mention that the lower depth results of the tree could be from bad entropy on a CSPRNG. Which is what I'm making my comment from. There may be a potential flaw in an implementation e.g CRT. My comment was in regards to crypto usage in general where the most problematic factor is the misuse of PRNG and seeds. (ECDSA PS3 for example). edit: Article makes points towards a flaw in the CSPRNG and Prime generation.
        tptacek 15y ago
        I don't think I'm being clear. Sorry. Obviously, if unrelated people around the world are at random times coming up with the same (ostensibly) random gigantic prime factors, there is a randomness issue. The point the paper makes is that this isn't necessarily a CSPRNG issue. The issue is not necessarily that people are using rand() to generate primes. It's that to generate factors for RSA, you need more than a CSPRNG: you need a prime number generator that correctly uses the CSPRNG. The paper hypothesizes one very plausible prime number generator that would be insecure even if driven off hardware entropy.
mindslight 15y ago
Utterly simple and completely obvious in retrospect -> game changing. Maybe it's a good idea to tag a public key with the software/version used to create it. Debian fiasco keys are easy to pick out - the entropy was so low that the bad keys can be enumerated. This new attack relies on any small weakness in the distribution of primes, and it seems quite hard to track down responsible versions of software. I wonder how many of these shared factors aren't the actual value of p or q chosen at generation time (primality tests are probabilistic).
- dekz 15y ago
  The responsible version of software are armchair cryptographers or average programmers trying to get things to 'work'. I bet this all results simply using OpenSSL with a SAMPLE to seed a PRNG or a bad seed of 0's. To see if it could potentially be a afflicted version of a toolkit, a scatter plot of dates and frequencies of these shared primes would provide a little more information.
  - mindslight 15y ago
    Bad system entropy is probably causing a lot of the duplicate moduli (complete keys), but not the cases where only one factor is shared. To me, that seems like an implementation weakness skewing the distribution of (probable) primes.
- marshray 15y ago
  > Maybe it's a good idea to tag a public key with the software/version used to create it. I'm a full-disclosure guy at heart, but why would I want to advertise to the attacker my potential weaknesses? Wouldn't I find my own personal selfish security is maximized when I falsify that field when generating my keys?
  - mindslight 15y ago
    Hence the 'maybe'. But what information would actually be leaked by knowing the generation software (assuming it's decoupled from the server software)? It seems if a certain implementation's keys are weak, one could simply try to exploit that over all keys. I don't need to know you're running Debian before I go scanning for those particular weak keys.
tptacek 15y ago
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 affected parties have been notified. 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 confirm the assumption, expecting at worst a very small number of counterexamples and affected owners to be notified. 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 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 certicates, many of the duplications are re-certications 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 different 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 offer marginal security. A large number of the 512-bit ones were certified 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 first 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 profit 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 certicates encountered that contain an ECDSA key (namely, just one), and the small number of certicates 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 findings 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.
tlb 15y ago
Should certificate authorities be checking that any new key they sign doesn't have a common factor in common with any other key they've signed? It would have discovered a few problems much earlier, but it conceivably leaks information when your CSR gets rejected.
- DavidSJ 15y ago
  It would only "leak" information which is already public.

122 points by sew 15y ago

deleted 15y ago

[deleted]

nohat 15y ago

Somewhat disappointing, but not surprising that they did not describe their actual calculation technique for finding the connected primes. It strikes me that there isn't a good excuse for having bad random numbers with the computation power we now have. A simple bitwise addition of various sources of supposedly random numbers is strictly stronger than any subset of its components. So we can combine lots of questionable strong sources and get a very strong source. Generating the primes locally with insufficient independence seems more understandable than that the same primes are used by independent parties. That hints at a more severe problem with random number generation. Regardless, assuming this is confirmed, it is a significant problem that needs to be hunted down.

a1k0n 15y ago
It was mentioned in the nytimes article, and in retrospect it's fairly obvious: you use the Euclidean algorithm. If you have n1=p q1 and n2=p q2, so that the prime p is shared between them, then gcd(n1,n2) = p. That only takes a few iterations of bignum modulos to solve.
- nohat 15y ago
  Ah, I took the 'the straightforward approach would require about ten core-years and would not scale well' to mean they had a more efficient method.
  - a1k0n 15y ago
    Hm, that's possible. A comprehensive search over 4 million pairs would be O(16 trillion) operations, so perhaps they gain something by reusing intermediate steps of the gcd, or something? Good point, I'm not sure. The brute-force solution is still not out of the question for a modestly large map-reduce cluster.
    - notaddicted 15y ago
      Yeah, regarding going ahead with the "naive" search, I'm coming up with a price of 5k to 15k on Amazon EC2 using the cluster compute 8XL instances, and under a month using 10 machines.
      - nohat 15y ago
        Considering the potential value of some of those rsa keys, that is a quite minimal investment. This might be an in the wild danger pretty quickly.
        tptacek 15y ago
        The chances of any one key being compromised are very, very low. If this is a pattern of simple software flaws, or something environmental like keys generating during cold start entropy starvation, the likelihood of pulling a truly valuable key out of that soup are even lower: generally (not always, but generally) the more valuable keys are generated using very well known software, and under tight process constraints. So basically you get ~10k random certs that allow you to MITM ~10k random sites. It's not nothing, but criminals have better ways of monetizing attacker effort.
        nohat 15y ago
        A lot does depend on the actual circumstances for the bad RNG. If you had a good method of recognizing the valuable sites (anything involving money or maybe email?) it might be more practical considering a botnet would be just fine for this sort of computation.

grandpa 15y ago

In case it's not obvious to everyone: Ron = Ron Rivest (the R in RSA); Whit = Whitfield Diffie (of Diffie-Hellman).

locacorten 15y ago
What a bad choice for a paper title.
- scott_s 15y ago
  I don't agree. It's short and gets across the main point to the right people. If you don't know the names being referred to, you're probably not the audience for the paper.
  - cperciva 15y ago
    I am the audience for this paper, and I recognized the names. I still had absolutely no clue what the title meant until grandpa pointed it out. I agree with locacorten: Horrible title.
    - tptacek 15y ago
      You can't see "Whit" and immediately know "it's Whit Diffie", or given Whit Diffie expect that "Ron" means "Ron Rivest"? I got it instantly and have way less crypto than you. Or are you saying, "Ron Rivest was wrong, Whitfield Diffie was right" is still a horrible title? The whole paper had the feel of a rump session pub, didn't it?
      - dekz 15y ago
        The whole title is horrible because of its not even related to the outcome of the experiment/paper. Ron and Whit are neither both right nor both wrong, nothing in the article even came close to proving such a title. Using bad entropy is wrong. What would be nice to see is the age of the affected certificates graphed in a scatter. It would be interesting to note if there are patterns of grouping. We all read the articles from Peter Goodman et al where he demonstrates horrible entropy [0,0,0,0,0,0,0,0].

deleted 15y ago

[deleted]

jalapeno_dude 15y ago

Posting what I said in the other thread: As far as I can tell, this is what they're doing: if two different keys have a factor in common (i.e. A=PQ, B=PR), then you can use Euclid's algorithm (which just requires repeated subtraction, and is thus really easy) to find P (=gcd(A,B)), and then just use division to find Q (=A/P) and R (=B/P) easily. So what the researchers did, apparently, was to gather all the RSA public keys they could find (6 million or so) and then calculate the gcds of all pairs of keys. (Presumably they were slightly more clever than this, but it doesn't really matter--doing this is still vastly easier than factoring even a single public key). Whenever they found a gcd that wasn't equal to 1, they'd cracked (at least) 2 keys. And it turns out that roughly 0.2% of the keys could be cracked in this way (for a total of 12720 1024-bit moduli). As far as I can tell, the problem isn't with RSA itself, but with whatever algorithms are used to pick two random primes to multiply and produce the key (or moduli, whatever)--they don't have high enough entropy and output duplicates ~0.2% of the time.

cperciva 15y ago
As far as I can tell, the problem isn't with RSA itself, but with whatever algorithms are used to pick two random primes to multiply and produce the key (or moduli, whatever)... Correct. they don't have high enough entropy and output duplicates ~0.2% of the time. Almost correct: They don't have enough entropy at least 0.2% of the time. These results are consistent with all primes being generated with ~40 bits of entropy -- which would imply that all the keys are broken. Obviously we hope that this is not the case and instead it's just a small subset of primes which were generated with low entropy, but the data do not provide any evidence in either direction.
- DavidSJ 15y ago
  They do write: the graph of the moduli contained in c distinct certificates consists, in an ideal world, of c disjoint connected components each consisting of two vertices joined by a single edge, for a total of 2c vertices and c edges ... tens of millions of [lab-]generated RSA moduli turned out to behave as expected based on the above assumption. That implies that there is at least one (presumably common) method for generating RSA keys which does not frequently output duplicate primes.

marshray 15y ago

As if it's somehow Ron Rivest's fault that people can't generate random numbers?

tptacek 15y ago
"Yes, because his algorithm requires you to get two secure ones, and other public key algorithms don't." Would be the authors' response to that.
- dekz 15y ago
  And the retort to the author would be the case of the PS3 and ECDSA. Using low entropy PRNGs at all is the _REAL_ problem.
  - tptacek 15y ago
    Are we sure the problem is a low entropy CSPRNG? The problem could be "when bad primes happen to good CSPRNGs". (The paper itself makes the DSA point.)
    - dekz 15y ago
      They do mention that the lower depth results of the tree could be from bad entropy on a CSPRNG. Which is what I'm making my comment from. There may be a potential flaw in an implementation e.g CRT. My comment was in regards to crypto usage in general where the most problematic factor is the misuse of PRNG and seeds. (ECDSA PS3 for example). edit: Article makes points towards a flaw in the CSPRNG and Prime generation.
      - tptacek 15y ago
        I don't think I'm being clear. Sorry. Obviously, if unrelated people around the world are at random times coming up with the same (ostensibly) random gigantic prime factors, there is a randomness issue. The point the paper makes is that this isn't necessarily a CSPRNG issue. The issue is not necessarily that people are using rand() to generate primes. It's that to generate factors for RSA, you need more than a CSPRNG: you need a prime number generator that correctly uses the CSPRNG. The paper hypothesizes one very plausible prime number generator that would be insecure even if driven off hardware entropy.

mindslight 15y ago

Utterly simple and completely obvious in retrospect -> game changing. Maybe it's a good idea to tag a public key with the software/version used to create it. Debian fiasco keys are easy to pick out - the entropy was so low that the bad keys can be enumerated. This new attack relies on any small weakness in the distribution of primes, and it seems quite hard to track down responsible versions of software. I wonder how many of these shared factors aren't the actual value of p or q chosen at generation time (primality tests are probabilistic).

dekz 15y ago
The responsible version of software are armchair cryptographers or average programmers trying to get things to 'work'. I bet this all results simply using OpenSSL with a SAMPLE to seed a PRNG or a bad seed of 0's. To see if it could potentially be a afflicted version of a toolkit, a scatter plot of dates and frequencies of these shared primes would provide a little more information.
- mindslight 15y ago
  Bad system entropy is probably causing a lot of the duplicate moduli (complete keys), but not the cases where only one factor is shared. To me, that seems like an implementation weakness skewing the distribution of (probable) primes.
marshray 15y ago
> Maybe it's a good idea to tag a public key with the software/version used to create it. I'm a full-disclosure guy at heart, but why would I want to advertise to the attacker my potential weaknesses? Wouldn't I find my own personal selfish security is maximized when I falsify that field when generating my keys?
- mindslight 15y ago
  Hence the 'maybe'. But what information would actually be leaked by knowing the generation software (assuming it's decoupled from the server software)? It seems if a certain implementation's keys are weak, one could simply try to exploit that over all keys. I don't need to know you're running Debian before I go scanning for those particular weak keys.

tptacek 15y ago

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 affected parties have been notified. 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 confirm the assumption, expecting at worst a very small number of counterexamples and affected owners to be notified. 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 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 certicates, many of the duplications are re-certications 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 different 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 offer marginal security. A large number of the 512-bit ones were certified 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 first 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 profit 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 certicates encountered that contain an ECDSA key (namely, just one), and the small number of certicates 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 findings 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.

tlb 15y ago

Should certificate authorities be checking that any new key they sign doesn't have a common factor in common with any other key they've signed? It would have discovered a few problems much earlier, but it conceivably leaks information when your CSR gets rejected.

DavidSJ 15y ago
It would only "leak" information which is already public.