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

81–90 of 114 posts

Re: 4096 RSA key in the strongset factored?

#81

Post by contravariant »

strags wrote: post #77
contravariant wrote: post #58

Earlier quoted context omitted.

Wouldn't RSA just fail if you used a non-prime factor? You shouldn't be able to decrypt any messages if you calculate the totient incorrectly, and for a public key pq, if either p or q isn't prime then (p-1)(q-1) won't be the totient.

I've always wondered about this. Wikipedia says ( http://en.wikipedia.org/wiki/RSA_(cryptosystem) ): "When m is not relatively prime to n, the argument just given is invalid. This is highly improbable (only a proportion of 1/p + 1/q − 1/(pq) numbers have this property), but even in this case the desired congruence is still true. Either m ≡ 0 (mod p) or m ≡ 0 (mod q), and these cases can be treated using the previous…

I think that's a different problem, although it is not entirely irrelevant since having a small prime factor like 3 implies that that the method will fail in at least 1/3 of the cases.

The other problem is that the value φ(n) will be wrong, even then there are some rare cases where the method might still work (see eximius comment about carmicheal numbers) but those are exceedingly rare.

Re: 4096 RSA key in the strongset factored?

#82

Post by diafygi »

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…

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/ba23ca66d2ca249e6f84

Here's the factored subkey: https://gist.github.com/anonymous/ba23ca66d2ca249e6f84#file-...

Here's the factored subkey's bad signature: 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?

#83

Post by garrettr_ »

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…

    This looks more like a fake sub key that someone tried to pollute the public key servers with
Does anybody know how that would be possible? I can't understand why a key server would accept a subkey unless it was correctly signed by the primary key. At the moment, all I can think is:

1. Misbehavior on the part of someone running a keyserver.

2. A bug in the keyserver software

    which isn't really an issue because PGP implementations will just ignore it
Has that always been the case? With all widely used PGP implementations?

I ask both of the questions because I can't understand why anybody would go to the trouble of doing this unless it supports some kind of attack (which may no longer be viable, but perhaps was at some time in the past).

Re: 4096 RSA key in the strongset factored?

#84

Post by asciilifeform »

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.

Re: 4096 RSA key in the strongset factored?

#85

Post by diafygi »

garrettr_ wrote: post #83
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…

This looks more like a fake sub key that someone tried to pollute the public key servers with Does anybody know how that would be possible? I can't understand why a key server would accept a subkey unless it was correctly signed by the primary key. At the moment, all I can think is: 1. Misbehavior on the part of someone running a keyserver. 2. A bug in the keyserver software which isn't really an issue because PGP im…

The SKS keyserver pool (which keys.gnupg.net alias's to) doesn't do any cryptographic verification, even verifying self-signatures, before upload. The software just checks to see if the format is valid.

It's up to the clients to do their own verification, which in this case GPG does perfectly (it doesn't import the invalid subkey since the self-signature is invalid).

Re: 4096 RSA key in the strongset factored?

#86

Post by davout »

diafygi wrote: post #85
garrettr_ wrote: post #83

Earlier quoted context omitted.

This looks more like a fake sub key that someone tried to pollute the public key servers with Does anybody know how that would be possible? I can't understand why a key server would accept a subkey unless it was correctly signed by the primary key. At the moment, all I can think is: 1. Misbehavior on the part of someone running a keyserver. 2. A bug in the keyserver software which isn't really an issue because PGP im…

The SKS keyserver pool (which keys.gnupg.net alias's to) doesn't do any cryptographic verification, even verifying self-signatures, before upload. The software just checks to see if the format is valid. It's up to the clients to do their own verification, which in this case GPG does perfectly (it doesn't import the invalid subkey since the self-signature is invalid).

If it's true it's a nice DoS vector

Re: 4096 RSA key in the strongset factored?

#87

Post by [deleted] »

davout wrote: post #86
diafygi wrote: post #85

Earlier quoted context omitted.

The SKS keyserver pool (which keys.gnupg.net alias's to) doesn't do any cryptographic verification, even verifying self-signatures, before upload. The software just checks to see if the format is valid. It's up to the clients to do their own verification, which in this case GPG does perfectly (it doesn't import the invalid subkey since the self-signature is invalid).

If it's true it's a nice DoS vector

[deleted]

Re: 4096 RSA key in the strongset factored?

#88

Post by agwa »

diafygi wrote: post #82
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…

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?

Re: 4096 RSA key in the strongset factored?

#89

Post by [deleted] »

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?

[deleted]

Re: 4096 RSA key in the strongset factored?

#90

Post by asciilifeform »

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?

Post reply on HN