Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Flaw found in online encryption method

nytimes.com

Post reply on HN
Print view View original

31–37 of 37 posts

Re: Flaw found in online encryption method

#31

Post by patio11 »

btilly wrote: post #27
tptacek wrote: post #24

Earlier quoted context omitted.

No, the owners of the vulnerable keys are by all appearances unrelated.

Huh, I did my back of the envelope wrong when I first decided that wasn't plausible. Here is a better back of the envelope. Suppose that we're using a random number generator that has 4 billion possible internal states. (We're using a C integer under the hood.) Suppose that we're having it generate random 256 bit integers, which we then test for primality. The probability of these integers being prime is about 1/log(…

This would be an interesting time to work at Google, because one assumes that an interested researcher there could get his hands on a Very Big Pile of Keys fairly quickly, and this seems to be made for map/reduce.

Re: Flaw found in online encryption method

#32

Post by feralchimp »

tyw wrote: post #21

Would it be valuable to set up a service that could check your public keys against a database of others checking for common factors? Or just better to fix the entropy problems and assume the problem doesn't exist anymore?

I think the original article alludes to this but doesn't say it explicitly:

If they built such a service to let people test their own public keys, the service would actually provide a much bigger service to attackers than it would to users.

Public keys are public, right? There are huge LDAP databases out there just brimming with certificates (i.e. signed public keys) just waiting to be harvested. And most of the people whose certificates are in these databases would not be paying attention to this news, but an attacker certainly would.

You probably see where this is going.

Re: Flaw found in online encryption method

#33

Post by lambda »

spot wrote: post #2

interesting that they were able to identify that there was bug without being able to say what it was or how it happened.

Well, that's the thing. They don't know who generated these keys or how. They don't know what the bug is; all they can see is the end result, not how it happened, without talking to the people who generated the keys and investigating the algorithms used, the entropy sources used, and trying to recreate the state of the system at the time the keys were generated.

But without knowing the bug, there is still the enormous vulnerability; pretty much anyone else could do what they have done, crack these keys, and MITM any of the sites that use them.

So, they could have kept quiet, tried to track down who had generated the keys, try to track down how they had generated the keys, and see if there is a problem. But the longer they do that, the more people they'll have to contact, the more likely it is that word will leak out, and the more likely it is that someone nefarious could use this information to their advantage.

By making a big announcement about it, they let everyone know now. Everyone knows to start looking at these keys. They will likely notify any CAs that they can identify of the bad keys that they have found so that they can be revoked (though they have mentioned that finding contact information has sometimes been difficult). Yes, it means that we don't really know how this happened; but it does mean that a lot more people will probably start auditing their entropy sources and pseudo-random number generators to make sure they are working properly.

Re: Flaw found in online encryption method

#34

Post by lambda »

robrenaud wrote: post #22
jalapeno_dude wrote: post #13

Earlier quoted context omitted.

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)…

Is it possible/likely that many of these bad pairs are from this debian/openssl bug? http://taint.org/2008/05/13/153959a.html

They explicitly excluded the Debian/OpenSSL blacklisted keys from their sample before checking for shared factors.

Re: Flaw found in online encryption method

#35

Post by viraptor »

Amateur question, but is it possible that the weak numbers are ones that pass some primality test which can give false-positives? Like Miller–Rabin I believe is only a probabilistic test - if it was run with not enough iterations, there would be some specific numbers which need more than N iterations (where N is an arbitrary threshold in some software). Would those number be in the "weak" subset found in the paper?

Re: Flaw found in online encryption method

#36

Post by currere »

feralchimp wrote: post #32
tyw wrote: post #21

Would it be valuable to set up a service that could check your public keys against a database of others checking for common factors? Or just better to fix the entropy problems and assume the problem doesn't exist anymore?

I think the original article alludes to this but doesn't say it explicitly: If they built such a service to let people test their own public keys, the service would actually provide a much bigger service to attackers than it would to users. Public keys are public, right? There are huge LDAP databases out there just brimming with certificates (i.e. signed public keys) just waiting to be harvested. And most of the peop…

Couldn't the service allow you to check your private keys, rather than check a public key, without transmitting the actual key.

You know (pub,priv). They know either (pub,priv) or (pub).

Essentially, make use of your unique (probably!) ability to sign something with your private key.

There's the issue of traffic analysis which needs to be solved - they have to reveal to you whether the key is compromised, and there's only two possible answers, so they have to be careful not to reveal it to in the traffic metadata.

Re: Flaw found in online encryption method

#37

Post by currere »

currere wrote: post #36
feralchimp wrote: post #32

Earlier quoted context omitted.

I think the original article alludes to this but doesn't say it explicitly: If they built such a service to let people test their own public keys, the service would actually provide a much bigger service to attackers than it would to users. Public keys are public, right? There are huge LDAP databases out there just brimming with certificates (i.e. signed public keys) just waiting to be harvested. And most of the peop…

Couldn't the service allow you to check your private keys, rather than check a public key, without transmitting the actual key. You know (pub,priv). They know either (pub,priv) or (pub). Essentially, make use of your unique (probably!) ability to sign something with your private key. There's the issue of traffic analysis which needs to be solved - they have to reveal to you whether the key is compromised, and there's…

Better yet, they can just publish something encrypted with every compromised public key. Only people with the corresponding private keys can ascertain if they're compromised.
Post reply on HN