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

91–100 of 114 posts

Re: 4096 RSA key in the strongset factored?

#91

Post by diafygi »

hannob wrote: post #70

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

The factored keypair in question is actually a subkey on HPA's public key. However, it appears that the self signature (which is a signature on the hash of the main public key and the subkey) does not match the hash_check. The issuer of this self signature has the same key_id as HPA's main key, which is why this subkey is listed under HPA's public key.

Here's a json breakdown of the invalid hash_check: https://gist.github.com/anonymous/ba23ca66d2ca249e6f84#file-...

EDIT: It's the EXACT SAME subkey self-signature packet as HPA's real subkey self-signature packet! Someone (by malice or mistake) manually added a subkey to HPA's public key and copied the signature from the other subkey directly onto the new subkey.

These are the same:

Bad subkey self-signature: https://gist.github.com/anonymous/ba23ca66d2ca249e6f84#file-...

Good subkey self-signature: https://gist.github.com/anonymous/ba23ca66d2ca249e6f84#file-...

Re: 4096 RSA key in the strongset factored?

#92

Post by diafygi »

agwa wrote: post #88
diafygi wrote: post #82

Earlier quoted context omitted.

Yes! It looks like someone inserted a broken subkey with an invalid signature into the keyserver. If your software didn't validate subkey signatures, you could very well think that a package was signed by HPA. Alternatively, it could be that someone was just fucking around and uploaded a subkey with invalid signature for the lolz. Here's a json export of the packets: https://gist.github.com/anonymous/ba23ca66d2ca249e…

That JSON export is cool - how did you generate it?

One of my side projects: https://github.com/diafygi/openpgp-python

Not fully functional yet, but was able to convert this public key to json. I manually removed the non-self signature packets for the gist.

Re: 4096 RSA key in the strongset factored?

#93

Post by zmanian »

hannob wrote: post #70

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

Here is Nadia H's lecture at Stanford from last week. Covers the GCD batch attack and her hypothesis about where the weak RSA keys are coming from.

https://mvideos.stanford.edu/graduate#/SeminarDetail/Spring/...

Re: 4096 RSA key in the strongset factored?

#94

Post by geofft »

hhsnopek wrote: post #11

I know of RSA, but could someone break down this article a bit? Does this mean RSA is now broken and we must find a new algorithm?

The article claims that a well-known person in Linux kernel etc. communities has a 4096-bit RSA private key with two "factors", one of which is 231 (which is itself not prime).

Standard RSA involves a private key which is the product of two prime numbers, and when we talk about "4096-bit RSA", we generally mean that the private key is the product of two 2048-bit numbers. Due to randomness, they might actually be 2047- or 2049-bit or something, but having one 8-bit prime and one 4088-bit prime -- let alone one 8-bit composite number -- is generally not what we mean by 4096-bit RSA, nor what software is intended to generate. It's well-known that the strength of an RSA key is restricted to the size of its smallest prime factor. (When I TA'd a crypto class a few years ago, I gave a homework assignment to break a "512-bit" RSA key that was intentionally generated as a 50-bit prime and a 462-bit prime: the entire class was able to factor it without even thinking about hardware beyond their personal laptops.)

So the mystery is not so much how it was factored, but how the key was generated that way in the first place, and whether this was even an intentional part of this person's PGP key. Other comments here imply that this particular subkey isn't even usable, so the answer to the second part seems like "not really".

Re: 4096 RSA key in the strongset factored?

#96

Post by [deleted] »

asciilifeform wrote: post #90
throwaway2391 wrote: post #80

I was extremely surprised to see the source of this at the top of HN, as I am familiar with this web site and its operator from an an extremely toxic online forum, which I won't mention or elaborate on. I am careful not to share negative remarks, but I will firmly state that I believe that this: >Consequently, the originally intended, civilised process of emailing the victim, keeping things quiet for a while to give…

You are just the man to expose the sham, perhaps? Where did we cheat? Who and why placed the key on SKS? Or is Mircea's pact with Satan spiffy enough to enable him to alter the laws of arithmetic?

[deleted]

Re: 4096 RSA key in the strongset factored?

#97

Post by cjbprime »

asciilifeform wrote: post #84
cjbprime wrote: post #16

For people who don't know hpa, the owner of the factored key: he's a core Linux kernel maintainer and has been the kernel.org sysadmin in the past: http://en.wikipedia.org/wiki/Hans_Peter_Anvin If it's true that the normal key generation process would reject creating a key with factors this small, this is especially concerning. Edit: Fortunately it looks like this is garbage on the keyservers, rather than a real prob…

I, for one, would still like to learn who and why placed the garbage on the SKS servers. (And no, I cannot prove to the satisfaction of everyone that I had not somehow done it myself. Though if anyone can picture what such proof would look like, I'd be happy to try.) And why Mr. Anvin's key was chosen, rather than another.

I don't find that especially interesting.

If the design of the keyservers is such that they'll accept untrusted info and will relay it expecting clients to verify it, we shouldn't be surprised when we find bogus data on the keyservers.

We should be surprised if the clients do something other than reject the bogus data, but so far we're seeing them do the right thing.

Re: 4096 RSA key in the strongset factored?

#98

Post by throwaway2391 »

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.

In time for him to edit, I sent asciilifeform (the author of 'phuctor') mail on how I thought he could improve his comments here, just some suggestions to clean up the language so it's more civil for HN, rather than ad-hominem, antagonistic, etc. (As you can see below, I suggested only three deletions, and highlighted seven paragraphs as being very positive.)

He published it on his blog called it "hate mail" and named it tard.png (for retard).

My brief suggestions to him -http://www.loper-os.org/pub/tard.png

His publication of it - http://www.loper-os.org/

Re: 4096 RSA key in the strongset factored?

#99

Post by diafygi »

asciilifeform wrote: post #95

Aaaand we found another two. One of which belongs to a GNU dev with some public presence... Still think it was 'cosmic rays' on SKS's machines? Do cosmic rays preferentially strike public keys belonging to major Open Source figures?

Can you please disclose the key ids? Are they the same instances of inserting subkey under someone's public key with an invalid self-signature[1]? If so, it seems that this attack is exploiting the fact that the sks-keyserver pool doesn't verify self-signatures and some non-gpg client might not verify self-signatures either (dunno which one, though).

[1]: https://news.ycombinator.com/item?id=9561407

Re: 4096 RSA key in the strongset factored?

#100

Post by jugad »

userbinator wrote: post #37

We think properly created RSA keys couldn't possibly have such tiny factors because they were created by sophisticated algorithms, presumably would be two very large primes, and yet... this happens. Dumb-and-stupid trial division by the first 1000 or so primes wouldn't take much time and could've easily caught this. I see this as a nice precautionary tale that we may sometimes think too highly of sophisticated algori…

I have seen the source code for some large prime generation algos... and they all have a test / verify stage which checks for divisibility by primes upto about a million (or billion), and the prime is then tested against the Miller-Rabin test.

My first reaction after reading this article was that, either they are using a bad version of a self authored prime generation algo, or keys are corrupted.

The guys who wrote the large prime generating algos are very well aware of your concerns (and share them too). I think you should not be too hasty in doubting these 'sophisticated algorithms'. One should probably verify that such issues exist in the prime generating algo, before we start calling one of our best mathematicians/programmers as incompetent.

Post reply on HN