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

4096 RSA key in the strongset factored?

trilema.com

Post reply on HN
Print view View original

61–70 of 114 posts

Re: 4096 RSA key in the strongset factored?

#61

Post by rewqfdsa »

dang wrote: post #57
rewqfdsa wrote: post #41

You shouldn't be surprised to see blatant lies from Mircea Popescu, who also claims that he's a billionare, that English literature literally does not exist, that bitcoin literally makes states and laws obsolete, and that nuclear weapons are ineffective.

Let's stay on topic, please. Is this title misleading or linkbait? If so, we should change it as the HN guidelines ask. Would "Two pairs of RSA keys having a common factor found" do? Suggestions for an accurate, neutral title are always welcome. Edit: We've detached this subthread as off-topic.

> Would "Two pairs of RSA keys having a common factor found" do?

Yes, that works. There's potentially a serious RSA keygen issue here, but nobody's broken RSA itself, and the headline does a very poor job of communicating this fact.

Re: 4096 RSA key in the strongset factored?

#62

Post by userbinator »

schoen wrote: post #48
unfamiliar wrote: post #21

Is there any way to get GPG to print out the two factors when the key is generated? 231 is absurd.

It might not be a good idea for other reasons to have them on your screen, where other locally-installed software could view them, they would be (more strongly) broadcast in the RF spectrum, someone might see them over your shoulder, etc.

Valid points about other software, but I don't think 1000+-digit random-looking numbers would be easily memorised by someone looking over your shoulder casually.

http://www.recordholders.org/en/list/memory.html#numbers-1mi...

Re: 4096 RSA key in the strongset factored?

#63

Post by acqq »

schoen wrote: post #59
agwa wrote: post #54

When I try to import HPA's key from the public key servers, I get an "invalid subkey binding" error and the weak sub key isn't imported. That error means that the sub key isn't properly signed by HPA's master key, so there is no cryptographic proof that this weak sub key actually belongs to HPA. This looks more like a fake sub key that someone tried to pollute the public key servers with, which isn't really an issue…

I think you may have solved the mystery, including my confusion about why I couldn't get the vulnerable subkey from the keyservers. My gpg was silently discarding the vulnerable subkey because it doesn't have a proper signature. If this is the explanation, then this is either an attack by a random person or an attack or flaw in a keyserver, but an attack that's unlikely to work because users will discard the bad key…

The keyservers aren't secure anyway. The are more like a big public walls on which everybody can write any number.

The users are the ones responsible for any key verification.

Re: 4096 RSA key in the strongset factored?

#64

Post by schoen »

dang wrote: post #57
rewqfdsa wrote: post #41

You shouldn't be surprised to see blatant lies from Mircea Popescu, who also claims that he's a billionare, that English literature literally does not exist, that bitcoin literally makes states and laws obsolete, and that nuclear weapons are ineffective.

Let's stay on topic, please. Is this title misleading or linkbait? If so, we should change it as the HN guidelines ask. Would "Two pairs of RSA keys having a common factor found" do? Suggestions for an accurate, neutral title are always welcome. Edit: We've detached this subthread as off-topic.

It is actually a pure factorization of two separate keys. But subsequent evidence in this conversation (from agwa above) makes me think that they aren't valid keys that are actively being used by the people in question, but rather spurious additional data being returned by keyservers for some reason, that probably wouldn't be accepted as valid by gpg.

Re: 4096 RSA key in the strongset factored?

#65

Post by contravariant »

detaro wrote: post #52
contravariant wrote: post #46

Earlier quoted context omitted.

Also, shouldn't it only have 2 prime factors?

Should . Obviously something went very wrong and the "primes" weren't properly checked to actually be primes.

Well, obviously something went wrong. But the way I understand it RSA shouldn't work at all if you used a composite factor, decrypting a message will just give a wrong result.

Unless, by some incredible fluke, they managed to find a carmichael number.

Re: 4096 RSA key in the strongset factored?

#67

Post by asciilifeform »

dang wrote: post #57
rewqfdsa wrote: post #41

You shouldn't be surprised to see blatant lies from Mircea Popescu, who also claims that he's a billionare, that English literature literally does not exist, that bitcoin literally makes states and laws obsolete, and that nuclear weapons are ineffective.

Let's stay on topic, please. Is this title misleading or linkbait? If so, we should change it as the HN guidelines ask. Would "Two pairs of RSA keys having a common factor found" do? Suggestions for an accurate, neutral title are always welcome. Edit: We've detached this subthread as off-topic.

Incidentally, anyone who suspects that I, Mircea, or Hitler fabricated these keys in order to troll the planet, is free to contact anyone who runs an SKS mirror and ask to examine their copies.

I do not know where the key came from, and especially whether it originates from the person who it claims to belong to (other people have found persuasive evidence that this is not the case) but I did find them 'in the wild.' Doubters are encouraged to check for themselves.

Re: 4096 RSA key in the strongset factored?

#68

Post by schoen »

userbinator wrote: post #62
schoen wrote: post #48

Earlier quoted context omitted.

It might not be a good idea for other reasons to have them on your screen, where other locally-installed software could view them, they would be (more strongly) broadcast in the RF spectrum, someone might see them over your shoulder, etc.

Valid points about other software, but I don't think 1000+-digit random-looking numbers would be easily memorised by someone looking over your shoulder casually. http://www.recordholders.org/en/list/memory.html#numbers-1mi...

If you had a 2048-bit public key modulus, each factor (only one factor is sufficient to reconstruct the private key) is only about 308 decimal digits, or 256 hex digits. :-)

We also know from Nadia Heninger and Hovav Shacham's research that you can reconstruct private keys relatively efficiently if you have some missing bits.

https://eprint.iacr.org/2008/510.pdf

But I think you're right that human memory isn't a very significant threat to RSA private parameters. Realistically, cameras would be the threat, not a human being glancing it them.

Re: 4096 RSA key in the strongset factored?

#69

Post by dang »

schoen wrote: post #64
dang wrote: post #57

Earlier quoted context omitted.

Let's stay on topic, please. Is this title misleading or linkbait? If so, we should change it as the HN guidelines ask. Would "Two pairs of RSA keys having a common factor found" do? Suggestions for an accurate, neutral title are always welcome. Edit: We've detached this subthread as off-topic.

It is actually a pure factorization of two separate keys. But subsequent evidence in this conversation (from agwa above) makes me think that they aren't valid keys that are actively being used by the people in question, but rather spurious additional data being returned by keyservers for some reason, that probably wouldn't be accepted as valid by gpg.

I don't understand this well enough to know what an accurate title should say. Can you or anyone suggest one?

Re: 4096 RSA key in the strongset factored?

#70

Post by hannob »

I'm almost certain this news is wrong. I know that because I made the same mistake a while ago. Luckily for me I didn't publish it, but I already had written mails to a number of people (including hpa) warning them of a compromised key (which was a false alarm).

Here's what's going on: There are a number of keys on the keyservers that are faulty copies of real keys - they share most of the values, but have some errors. I don't exactly know why that is happening, but I assume it's because of network transmission errors or server crashes during transmissions.

These keys don't really do any harm. GPG will refuse to import them because of the faulty self-signature. So nobody will ever encrypt with those keys.

A Batch GCD attack on the PGP keyserver set has already been done a while ago by Lenstra and again by me recently. If you replicate this you'll find two old broken keys with unknown origin. These seem to be the only vulnerable ones, but they're expired. You'll find one key which looks like a test by someone and a large number of those broken keys with small factors.

I wrote a paper about my findings: https://eprint.iacr.org/2015/262 Also some code: https://github.com/hannob/pgpecosystem

And if you want to replicate the batch GCD attack Nadia Heninger has released source code for this: https://factorable.net/resources.html

Post reply on HN