[deleted]
I take it you didn't read to the end :)
[deleted]
Flaw found in online encryption method
11–20 of 37 posts
Re: Flaw found in online encryption method
#12This is not about some new vulnerability. It is a survey of collected public keys. The main security-relevant conclusion is that some key generators are not using enough entropy.
Dr. Lenstra is a co-author of the paper (so it shouldn't be dismissed on the weakness of the reporting). The NY Times and Markoff should both be ashamed for publishing such a misleading article, particularly the title.
Re: Flaw found in online encryption method
#13interesting that they were able to identify that there was bug without being able to say what it was or how it happened.
Yeah, and I think they did not do a very good job explaining it in the paper. Perhaps they assume more familiarity than I have. But as far as I can tell, the result is that, of public keys collected "in the wild" show more duplication than should be expected, so the random number generation schemes used are not "random" enough. Is that it, or is there more to the story? (Edit) No, there's more. I don't quite understa…
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.
Re: Flaw found in online encryption method
#14As I posted to the other thread:
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.
Re: Flaw found in online encryption method
#15This is not about some new vulnerability. It is a survey of collected public keys. The main security-relevant conclusion is that some key generators are not using enough entropy. Dr. Lenstra is a co-author of the paper (so it shouldn't be dismissed on the weakness of the reporting). The NY Times and Markoff should both be ashamed for publishing such a misleading article, particularly the title.
This is not about some new vulnerability.
A more accurate statement is: the thesis that "when hundreds and thousands of RSA keys are generated, the entropy of each key (given the remaining keys) is still large" is shown (in this paper) to be empirically false because people in practice use weak pseudorandom generators.
This is important because when working with the security of RSA, we assume that N=pq for random looking primes p and q. In isolation this is true, but when there are tons of other keys out there, p and q no longer are random.
I also fail to understand why you mention Lenstra being a co-author of the paper.
Re: Flaw found in online encryption method
#16As I posted to the other thread: 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…
They didn't describe the technique, but the fact that the paper has the keyword "Euclidean algorithm" makes it pretty obvious--they just gathered a list of public keys, took the gcd of all the pairs, and whenever they found a gcd not equal to one, they'd cracked both keys out of that particular pair. See my earlier comment.
Re: Flaw found in online encryption method
#17This is not about some new vulnerability. It is a survey of collected public keys. The main security-relevant conclusion is that some key generators are not using enough entropy. Dr. Lenstra is a co-author of the paper (so it shouldn't be dismissed on the weakness of the reporting). The NY Times and Markoff should both be ashamed for publishing such a misleading article, particularly the title.
I really don't think it is about not using enough entropy. I think that someone took a shortcut and reused private keys without realizing that they were compromising their public keys by doing so.
Re: Flaw found in online encryption method
#18This seems similar to the length-extension property of Merkle Damgaard hashes like MD5 and SHA-2, in that it is something bad that happens in the real world with RSA that isn't a flaw in RSA per se, but is an attack that would ideally be foreclosed on by the algorithm.
In other words, all things being equal, you'd want to select the algorithm where the fewest number of implementation flaws could prove devastating in the future. The ability to conduct large-sample GCD collision surveys and the fact that common CSPRNGs mean that survey generates results is an argument against using RSA.
I don't see anything specific to SSL or X.509 here; this seems like an issue with every PKI. If you publish public keys to the whole world, people can survey them.
Re: Flaw found in online encryption method
#19This is not about some new vulnerability. It is a survey of collected public keys. The main security-relevant conclusion is that some key generators are not using enough entropy. Dr. Lenstra is a co-author of the paper (so it shouldn't be dismissed on the weakness of the reporting). The NY Times and Markoff should both be ashamed for publishing such a misleading article, particularly the title.
This is not about some new vulnerability. A more accurate statement is: the thesis that "when hundreds and thousands of RSA keys are generated, the entropy of each key (given the remaining keys) is still large" is shown (in this paper) to be empirically false because people in practice use weak pseudorandom generators. This is important because when working with the security of RSA, we assume that N=pq for random loo…
I take him to mean, "it is understandable that the NY Times would write up a story on RSA vulnerabilities when one of the authors is Arjen Lenstra, because Arjen Lenstra is a giant in the field".
I agree with you (and not the parent) about the importance of the study.
Re: Flaw found in online encryption method
#20As I posted to the other thread: 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…
They didn't describe the technique, but the fact that the paper has the keyword "Euclidean algorithm" makes it pretty obvious--they just gathered a list of public keys, took the gcd of all the pairs, and whenever they found a gcd not equal to one, they'd cracked both keys out of that particular pair. See my earlier comment.
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.