4096 RSA key in the strongset factored?(trilema.com)
trilema.com
4096 RSA key in the strongset factored?
http://trilema.com/2015/full-disclosure-4096-rsa-key-in-the-strongset-factored/
26 comments
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-...
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-...
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/...
https://mvideos.stanford.edu/graduate#/SeminarDetail/Spring/...
What do you make of this? https://news.ycombinator.com/item?id=9575598
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 because PGP implementations will just ignore it.
gpg --verbose --keyserver hkp://hkps.pool.sks-keyservers.net --recv-key 0xbda06085493bace4
gpg: requesting key 0xBDA06085493BACE4 from hkp server hkps.pool.sks-keyservers.net
gpg: armor header: Version: SKS 1.1.5
gpg: armor header: Comment: Hostname: keyserver.witopia.net
gpg: pub 4096R/0xBDA06085493BACE4 2011-09-22 H. Peter Anvin <[email protected]>
gpg: key 0xBDA06085493BACE4: invalid subkey binding
gpg: key 0xBDA06085493BACE4: skipped subkey
gpg: key 0xBDA06085493BACE4: "H. Peter Anvin (hpa) <[email protected]>" not changed
gpg: Total number processed: 1
gpg: unchanged: 1I 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 rather than using it.
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 rather than using it.
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.
The users are the ones responsible for any key verification.
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-...
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-...
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.
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.
[deleted]
This looks more like a fake sub key that someone tried to pollute the public key servers with
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
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).
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).
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
fwiw this is currently being discussed on the sks mailing list, but the overwhelming opinon seems to be that the current behaviour should stay. https://lists.nongnu.org/archive/html/sks-devel/2015-05/msg0...
[deleted]
Author of 'phuctor' speaking. We did not break RSA! Please put that Luger down, unload it. You have things to live for!
We only found (at the time of this writing) two sets of two poor buggers each who happened to have generated RSA keys having a common factor.
We only found (at the time of this writing) two sets of two poor buggers each who happened to have generated RSA keys having a common factor.
Is the origin of the keys and why they're broken in this way known? Perhaps they were generated on embedded devices and their demise could be traced back to an early boot time entropy problem.
Not known to me.
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 problem with hpa's key.
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 problem with hpa's key.
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.
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.
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.
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 algorithms that we trust them blindly, and miss looking for the bloody obvious. It's like an "is it plugged in?" sort of thing.
If I deliberately generated a public key that was divisible by 3, I wonder how long it would take for someone to notice...
I also entertain the (admittedly very slim) possibility that he did this deliberately to see what would happen.
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 algorithms that we trust them blindly, and miss looking for the bloody obvious. It's like an "is it plugged in?" sort of thing.
If I deliberately generated a public key that was divisible by 3, I wonder how long it would take for someone to notice...
I also entertain the (admittedly very slim) possibility that he did this deliberately to see what would happen.
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.
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.
> If I deliberately generated a public key that was divisible by 3
This is already well known:
> When encrypting with low encryption exponents (e.g., e = 3) and small values of the m, (i.e., m < n1/e) the result of me is strictly less than the modulus n. In this case, ciphertexts can be easily decrypted by taking the eth root of the ciphertext over the integers.
https://en.wikipedia.org/wiki/RSA_(cryptosystem)#Attacks_aga...
This is already well known:
> When encrypting with low encryption exponents (e.g., e = 3) and small values of the m, (i.e., m < n1/e) the result of me is strictly less than the modulus n. In this case, ciphertexts can be easily decrypted by taking the eth root of the ciphertext over the integers.
https://en.wikipedia.org/wiki/RSA_(cryptosystem)#Attacks_aga...
From my understanding, this doesn't show that he can break RSA but rather that the key generator that generated the keys in the GPG strong suite were completely broken. The factors were 7 and 77 which is completly ridiculous, they should be in the range of 2^2048. This does mean further scrutiny on key generators is a must.
Exactly. The GPG that generated that keypair was obviously not doing what it was supposed to do.
It can be something on the level of the famous Debian patch fiasco.
The worrying thing is that nobody until now published such findings.
The second found p is 21(!?)
Edit: see the new post from agwa, if all the keys with bad properties came the same way it's much less worrying.
It can be something on the level of the famous Debian patch fiasco.
The worrying thing is that nobody until now published such findings.
The second found p is 21(!?)
Edit: see the new post from agwa, if all the keys with bad properties came the same way it's much less worrying.
Thanks.
The first paper mentions some 157 PGP keys and some "probably copy-paste errors." Maybe somebody can tell more about it, I wasn't able to evaluate the effects.
The second didn't analyze PGP keys, but otherwise was certainly impressive.
The first paper mentions some 157 PGP keys and some "probably copy-paste errors." Maybe somebody can tell more about it, I wasn't able to evaluate the effects.
The second didn't analyze PGP keys, but otherwise was certainly impressive.
A look at the PGP ecosystem through the key
server data
https://eprint.iacr.org/2015/262.pdf
https://eprint.iacr.org/2015/262.pdf
That one sounds optimistic:
"Based on my research it seems that over a very long time the use of PGP implementations with deeply awed random number generation functions was very rare."
"Based on my research it seems that over a very long time the use of PGP implementations with deeply awed random number generation functions was very rare."
The Phuctor operates by taking the greatest common divisor of the RSA modulus of a new PGP key with the product of other keys in its set. The factor that was found was 231. This is a result of bad prime generation, or a bad random number generator, not a advance in factoring technology.
Is there any way to get GPG to print out the two factors when the key is generated? 231 is absurd.
That doesn't protect against the possibility that one of the factors is itself composite.
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...
http://www.recordholders.org/en/list/memory.html#numbers-1mi...
In the era of 120fps 12MP smartphone cameras, capturing a 1000+ digit number on a screen doesn't seem so implausible, and "someone looking over your shoulder" shouldn't be taken so literally.
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.
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.
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?
RSA is not broken per se. (AFAIK) If you have a 4096-bit key, nobody is able to factor a 4096-number yet.
However, using a bad random prime generator might lead to birthday attack when someone is using the same prime as you. Having two keys that share a prime, it is possible to factor both.
Also, one of the "primes" used is 231, which is extremely stupid, its factors 3711, so there are two keys that are using the same non-prime number as one of "prime" factors for the key. And one of its factors is motherfucking second prime.
I suspect it's a backdoor or a blatant error in RSA key generator or prime checker.
However, using a bad random prime generator might lead to birthday attack when someone is using the same prime as you. Having two keys that share a prime, it is possible to factor both.
Also, one of the "primes" used is 231, which is extremely stupid, its factors 3711, so there are two keys that are using the same non-prime number as one of "prime" factors for the key. And one of its factors is motherfucking second prime.
I suspect it's a backdoor or a blatant error in RSA key generator or prime checker.
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 proof.".
I'm not sure I follow 100% - perhaps someone smarter can explain.
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 proof.".
I'm not sure I follow 100% - perhaps someone smarter can explain.
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.
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.
I suppose that would work, although with a factor of 3 more than 1/3 of all inputs are not relatively prime so in those cases it would fail anyway.
No, it seems to suggest that some version of the GPG software, under some conditions, erroneously generated a terribly weak key. It's a software (or even malware) issue rather than a mathematical issue.
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".
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".
Nah, it just found a weak key bug. A very embarrassing weak key bug, but not one that breaks RSA.
Disclaimer: I'm not a cryptographer, I have very possibly misread the article. Corrections welcome.
Disclaimer: I'm not a cryptographer, I have very possibly misread the article. Corrections welcome.
From http://nosuchlabs.com/theory
An RSA public key consists of a modulus n and an exponent e. Modulus n is a product of two large primes, p and q. If one knows p or q, one can derive the private key corresponding to the given public key.
A typical GPG public key contains one or more RSA moduli, depending on the number of sub-keys.
Under certain conditions, a public key modulus will share a common factor with an existing modulus belonging to someone else. This may happen if both keys were generated on a system with a thoroughly-broken entropy source, or if a particular GPG implementation has been back-doored.
An RSA public key consists of a modulus n and an exponent e. Modulus n is a product of two large primes, p and q. If one knows p or q, one can derive the private key corresponding to the given public key.
A typical GPG public key contains one or more RSA moduli, depending on the number of sub-keys.
Under certain conditions, a public key modulus will share a common factor with an existing modulus belonging to someone else. This may happen if both keys were generated on a system with a thoroughly-broken entropy source, or if a particular GPG implementation has been back-doored.
> And the first factor - get a load of this - is 231. Which... yes, 231 = 3 * 77.
The best part.
The best part.
oh, wait a second, it just factored a second one... (and no, it's not the one sharing a prime with the first factored one).
So summed up: 2 known keys factored so far, 2 more waiting to be identified among the running product (should apparently take a week to identify).
So summed up: 2 known keys factored so far, 2 more waiting to be identified among the running product (should apparently take a week to identify).
> 2 more waiting to be identified among the running product
I don't know anything about this factoring project; does this mean that keys are somehow "tested" in batches, and if the batch comes out "dirty" then you know you can easily factor something in that batch (for some value of "easy")?
EDIT: Ah, nevermind, just figured it out. For those coming after, there's a running product of all public moduli in the tested set; you can test one key against all of them simultaneously. When you find a GCD /= 1, you've found a factor, and you know the key you just tested has it, but there's an older key which has that factor too, and you don't know which one. Presumably you either go and test them one by one or store "snapshots" of the running product to test.
I don't know anything about this factoring project; does this mean that keys are somehow "tested" in batches, and if the batch comes out "dirty" then you know you can easily factor something in that batch (for some value of "easy")?
EDIT: Ah, nevermind, just figured it out. For those coming after, there's a running product of all public moduli in the tested set; you can test one key against all of them simultaneously. When you find a GCD /= 1, you've found a factor, and you know the key you just tested has it, but there's an older key which has that factor too, and you don't know which one. Presumably you either go and test them one by one or store "snapshots" of the running product to test.
This isnot really new work, see eg https://eprint.iacr.org/2012/064.pdf (and http://crypto.stanford.edu/~dabo/papers/RSA-survey.pdf if you're interested in other RSA weaknesses)
[deleted]
This is not the first time low quality keys have been produced. I'm thinking of https://www.debian.org/security/2008/dsa-1571. Seems like quality control is a bigger problem than we would like to admit.
> And the first factor - get a load of this - is 231. Which... yes, 231 = 3 * 77.
Why isn't the first factor just 3 then?
Why isn't the first factor just 3 then?
When you use factoring algorithms other than simple trial division - things like Pollard rho and its ilk - you are not guaranteed to get the smallest factor(s) first. Sometimes you get bigger factors, or combinations of factors, because those are what happen to pop out of the algebraic structure you're running over.
But any "primes" being used should have some serious factorisation algorithms run over them before being used, so this is really embarrassing.
EDIT
And to answer contravariant's question[0]:
[0] https://news.ycombinator.com/item?id=9561051
But any "primes" being used should have some serious factorisation algorithms run over them before being used, so this is really embarrassing.
EDIT
And to answer contravariant's question[0]:
Also, shouldn't it only
have 2 prime factors?
[0] https://news.ycombinator.com/item?id=9561051
Large pseudo prime generators usually check for divisibility by numbers upto a million or so, then follow it with Rabin-Miller or more sophisticated non-deterministic tests to verify primes.
These primes could not have been generated by any reputable prime generation algos that I can imagine.
These primes could not have been generated by any reputable prime generation algos that I can imagine.
They used the GCD (greatest common divisor) algo to find any common divisors between 2 large keys. 231 was such a number.
This signals to me that both the keys are corrupted/bad to have really small prime factors (3, 7 and 11).
I have taken courses on discrete math, cryptography and read a few prime generation algos. Its a standard first step to check numbers against primes upto a million or so (nowadays, a billion). No prime generation algo I can imagine generated these keys.
This signals to me that both the keys are corrupted/bad to have really small prime factors (3, 7 and 11).
I have taken courses on discrete math, cryptography and read a few prime generation algos. Its a standard first step to check numbers against primes upto a million or so (nowadays, a billion). No prime generation algo I can imagine generated these keys.
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.
Unless, by some incredible fluke, they managed to find a carmichael number.
RSA without CRT optimization of private operations will work regardless of how many factors modulus has, if key was generated correctly. With "correctly" meaning using correct value of phi(n), which is not (p-1)*(q-1) when either of p or q are composite (which in effect means that it will not work at all with essentially all interesting implementations).
IIRC PKCS#1 even supports more than two modulus factors in it's private key format (not that it is particularly useful for anything).
IIRC PKCS#1 even supports more than two modulus factors in it's private key format (not that it is particularly useful for anything).
[deleted]
In the army battle field tactical communication are handle by streaming ciphers on the radio. The idea is not to be impossible to breach. But strong enough that time is on your side, so that you can say "move those tanks over to feature 229", and that will be tactically perishable information.
on the internet, i would treat all information the same. if they can't break it today, they will wait until they have the math or the raw power to break what you have encrypted. so only talk about what doesn't matter if someone finds out about it.
like, hey lets meet up here at time x. in two days that means nothing significant.
but anyway, first step is getting an old mobile without data.
like, hey lets meet up here at time x. in two days that means nothing significant.
but anyway, first step is getting an old mobile without data.
> like, hey lets meet up here at time x. in two days
> that means nothing significant.
Can anyone who was involved in this please post the ASCII-armored key in question?
When I try to download any of the three stated fingerprints from keys.gnupg.net, I receive a key which is missing the vulnerable subkey (containing only the two non-vulnerable ones). That makes me worry that there may be an element of keyserver misbehavior in this story, though I don't understand the nature of the misbehavior.
Edit: agwa's post shows that my gpg is receiving the same thing from the keyservers that these folks had, but it's rejected it as invalid because it's missing a valid signature.
When I try to download any of the three stated fingerprints from keys.gnupg.net, I receive a key which is missing the vulnerable subkey (containing only the two non-vulnerable ones). That makes me worry that there may be an element of keyserver misbehavior in this story, though I don't understand the nature of the misbehavior.
Edit: agwa's post shows that my gpg is receiving the same thing from the keyservers that these folks had, but it's rejected it as invalid because it's missing a valid signature.
I guess the real question is why don't we, would-be "hackers" do our own tests of our own keys (and of our communication partners) at least for such obvious problems?
Why should we wait for somebody else to run a few obvious algorithms on our own keys?
Anybody knows what to use and has a good recipe?
The goal should be, don't trust the program which generated the keys, extract them and run the independent tests. I guess a lot of people would gladly use some time for that.
Why should we wait for somebody else to run a few obvious algorithms on our own keys?
Anybody knows what to use and has a good recipe?
The goal should be, don't trust the program which generated the keys, extract them and run the independent tests. I guess a lot of people would gladly use some time for that.
The issue with this is that gpg doesnt check these keys when you sign them (presumably because speed)
So even if you verify the persons identity correctly when you sign their key you can't tell if the key is garbage easily.
In fact i guess it doesn't matter much if the other person communicating with you is fooling you amd forwarding all the things he receives to the nsa/whay not regardless ;)
So even if you verify the persons identity correctly when you sign their key you can't tell if the key is garbage easily.
In fact i guess it doesn't matter much if the other person communicating with you is fooling you amd forwarding all the things he receives to the nsa/whay not regardless ;)
Ahem. For the first key they mention, there are more factors there!
The key is probably corrupted or generated improperly.
The key is probably corrupted or generated improperly.
In[2]:= k =
81702302396037694663397550711015464924940759880679873041484988446177\
6172171921668594148071323527016137506405823108520062504849249423700259\
4069053132814039014100827620971595602214630489243361923840267775021772\
6273104520032220014977312750288854523497313948088764458519260063105896\
2876114156934248895171959246969597637127280010272143593885240940877456\
2346621961304914007384387318325143353538246979304530784267221911051575\
6839282687004365570800854541114336776383656601174049938345659212966258\
5004880376777597714978023542434421914201119537685489173509942329090631\
6620146500331426421109143608494218561796112264508065622355348025160815\
9525991476849744470271874940233007048802875107373034946075277191548484\
7399385631524708487646079936572410398967582895983187640798072309362094\
7276541676286201059814590215482904158000967692144374256909343720156287\
9602749821990244128818939838635984666162324349353489741141768543542401\
0451956954083531228374002591372549525280610594684910812811287436481207\
0897631254242477930440433097372694687097106798722692728553899453853864\
6776550988064892974349821432957828887498719376843935338230526010842568\
8024147656806932474058888992099083804597481699305852902662863062054067\
183925164590726103552998367994727700722491707;
In[3]:= Mod[k, 231]
Out[3]= 0
In[4]:= PrimeQ[k/231]
Out[4]= False
In[5]:= k/231
Out[5]= 35368962076206794226579026281824876590883445835792152831811683\
3100336005269230159564566264642219487505414028494852173187231536471611\
9914542887035988231185720389968667087270823469537008330459707290159209\
9661353364980311702259746743425433025478148700135908263534397627385308\
7038512067581886118722465442406600419739236851636368083179044971965775\
2716260756113403162300436097137367240321798068505185846117222626502991\
7972189107914583118772974372664303512699903196388139036385254695090568\
3836616885229600336622387436373827893689140346804994669042932255386289\
6496240961102381095855593553741821858969074370611369916911524829154989\
2471064729866440194694575875270536897405648832413466395253223409210905\
4322444761638801525847830149818154360350822063888699559821489522975025\
6978765054779946444242883036619140901690111688730602659902275718330614\
7862718442748840688417371783090839236356998338668549503675212615484217\
9837233961886127308887977651083372888549578043554369993467884333890665\
1433796925381495343064039151702639555279085323422856589910272101255174\
8285128474697397430689599285636983964428089826285444521184129104123814\
2175622521276041907762975783068827748521127531377359006862728425481845\
0450507289719327232580534861464796513972730400397Update: some more factors for the key.
In[8]:= primes = Table[Prime[i], {i, 1, 10000000}];
In[9]:= r = k/231;
Select[primes, Mod[r, #] == 0 &]
Out[10]= {19, 7704959}
In[11]:= PrimeQ[k/231/19/7704959]
Out[11]= False
In[13]:= r/19/7704959
Out[13]= 2416008079731972085604323566968184938863361678449872200338542\
2782524728573078725530058065928860640441907473143687288939310762579324\
2201448845923773741805403670269789344162077509161854710812642480618084\
6418886532753250669796572553463393409872248215326471682480854051430439\
2318772751800215263874553179418646615820937142842296219000273581288825\
2789449984922109948745889094702540699357374091188011161049671668836093\
7278541145959209900694985382835863685677859045842263065588173367519102\
3000601703070615085046450531430050636608745665363730079826233868575064\
1515845148088351185382897973393486745557331417516226266671518736327371\
0952774886507742692568074519503781293211406810410464658659799378912020\
4022428232439503300191599103479511965185485160912786274522509295156878\
2006686251281732387799849219226976241206277650039929011945237627811183\
5293192238971567100891050322477609224503267676028587870533168970890197\
7752061262164585534348926085756033558766611288812716862195529175560192\
7171277951291635708971328803457524430235472568512308733137100548610807\
1730859408357205400252076841587686986935644804331821576562378722868016\
3691408455343059061584335066277570324891522017892861973483415607333423\
704276600438478560110515119729110048093857Did HPA publish this key anywhere? Tell anyone to use it?
Can anyone confirm this is true?
Yes:
817023023960376946633975507110154649249407598806798730414849884461776172171921668594148071323527016137506405823108520062504849249423700259406905313281403901410082762097159560221463048924336192384026777502177262731045200322200149773127502888545234973139480887644585192600631058962876114156934248895171959246969597637127280010272143593885240940877456234662196130491400738438731832514335353824697930453078426722191105157568392826870043655708008545411143367763836566011740499383456592129662585004880376777597714978023542434421914201119537685489173509942329090631662014650033142642110914360849421856179611226450806562235534802516081595259914768497444702718749402330070488028751073730349460752771915484847399385631524708487646079936572410398967582895983187640798072309362094727654167628620105981459021548290415800096769214437425690934372015628796027498219902441288189398386359846661623243493534897411417685435424010451956954083531228374002591372549525280610594684910812811287436481207089763125424247793044043309737269468709710679872269272855389945385386467765509880648929743498214329578288874987193768439353382305260108425688024147656806932474058888992099083804597481699305852902662863062054067183925164590726103552998367994727700722491707 `mod` 231
0Wait a minute, I get a different n value by downloading that key and running gpg --list-keys --with-key-data on it.
You have one ending in 131307671292149646652772992033083 and I have one ending in 726103552998367994727700722491707 that is not divisible by 231.
You have one ending in 131307671292149646652772992033083 and I have one ending in 726103552998367994727700722491707 that is not divisible by 231.
The key as seen by Phuctor had three sub-keys, one of which was an RSA key which turned out to be factorable.
Sorry, I was looking at the other one. But something is still very, very odd. (1) Two of the subkeys agree with one another for hundreds of digits and then disagree. (2) I did gpg --recv-key 51221121 and I got a key back from the keyserver with fingerprint 7EAA C969 3E7D 2205 46BE 576C BDA0 6085 493B ACE4 (only, no other keys) -- which doesn't match the key ID that it should, and is seemingly missing the vulnerable subkey entirely.
Can you post the ASCII-armored key that you have? I am getting a radically different key from the keyservers, and I wonder if there could be some kind of keyserver attack or misbehavior involved here too.
Well, it lists the key and says the first factor is 231. If you have a big enough calculator, this is trivial to verify.
Author of 'phuctor' speaking.
I can only confirm that we have a key, downloaded from an SKS dump, said key purporting to belong to one Mr. Anvin, containing one sub-key being an RSA public key which turned out to be factorable with trivial effort.
Anything else is mere conjecture.
I can only confirm that we have a key, downloaded from an SKS dump, said key purporting to belong to one Mr. Anvin, containing one sub-key being an RSA public key which turned out to be factorable with trivial effort.
Anything else is mere conjecture.
You can confirm this independently with the key itself and the published prime.
I too can post a public key I have the private key for and a factor? Or intentionally create a weak key?
Yes you can, we just need to find hpa's n value and see whether it is divisible by 231. If it is, the claim is correct.
I found the n value for my own PGP public key before and I can find hpa's too, I just have to remember the right arguments to gpg.
I found the n value for my own PGP public key before and I can find hpa's too, I just have to remember the right arguments to gpg.
you can trivially verify a key was broken if it was, duh, broken
This is kind of hilarious.
I think the article might be a bit dense for those who aren't aware of RSA's algorithm though.
I think the article might be a bit dense for those who aren't aware of RSA's algorithm though.
I agree. I've rolled OpenSSL certs for servers, but crypto isn't really a forte of mine. A generic rundown of implications would be nice.
In essence, RSA is a crypto-algorithm that relies on the fact that "Factorization" is a very very hard mathematical problem for standard computers to solve.
For example, what are the factors of 143?? Answer: 13 x 11. Factoring is hardest when the number is made up of two prime numbers. Public Key cryptography is basically a giant puzzle based on the difficulty of factoring numbers.
Now, instead of small numbers that we humans use, what is typically done is two 2000+ bit prime numbers are chosen and then the resulting 4000+ bit number is used as the "encryption puzzle".
This 4096 bit number happened to be 231, which is 3 x 77. Huzzzahh! I guess 231 is a 4096-bit number... but generally speaking, you'd hope that the number at the center of your "encryption puzzle" would be a bit... larger. So that it'd be harder to factor it.
For example, what are the factors of 143?? Answer: 13 x 11. Factoring is hardest when the number is made up of two prime numbers. Public Key cryptography is basically a giant puzzle based on the difficulty of factoring numbers.
Now, instead of small numbers that we humans use, what is typically done is two 2000+ bit prime numbers are chosen and then the resulting 4000+ bit number is used as the "encryption puzzle".
This 4096 bit number happened to be 231, which is 3 x 77. Huzzzahh! I guess 231 is a 4096-bit number... but generally speaking, you'd hope that the number at the center of your "encryption puzzle" would be a bit... larger. So that it'd be harder to factor it.
You know that in RSA the modulus n is effectively your public key, right? And that n = p * q, where p and q are essential parts of your private key?
So if you can factor n into the corresponding primes, you have just cracked the person's private key.
Implications? You can decrypt all RSA encrypted messages for that private key. You can IMPERSONATE the person whose private key you have cracked. (Signature = data encrypted with private key that can be verified with the public key.)
All encrypted messages sent to the compromised keys must be treated as leaked. All signatures made by the compromised keys are suspect.
It's as bad as it gets for the individuals in question.
So if you can factor n into the corresponding primes, you have just cracked the person's private key.
Implications? You can decrypt all RSA encrypted messages for that private key. You can IMPERSONATE the person whose private key you have cracked. (Signature = data encrypted with private key that can be verified with the public key.)
All encrypted messages sent to the compromised keys must be treated as leaked. All signatures made by the compromised keys are suspect.
It's as bad as it gets for the individuals in question.
The ongoing conversation is pretty fun too - http://log.bitcoin-assets.com/?date=17-05-2015#1134741
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 them time to update and so on is not practicable.
Strikes me as disingenuous coming from this source.
>Consequently, the originally intended, civilised process of emailing the victim, keeping things quiet for a while to give them time to update and so on is not practicable.
Strikes me as disingenuous coming from this source.
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?
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]
[deleted]
The forum you are referring to is 8chan (http://8ch.net/), yes? Are you sure you are not trolling?
[deleted]
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.
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.
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.
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?
The title should accurately represent the article, even if it turns out the article is wrong; anything else would be editorializing. So even if it turns out the factored subkeys are phony, this article doesn't say that, so neither should the title. The top two comments provide a useful correction.
So, the current title seems fine. If anything, the question mark is a bit of editorialism.
So, the current title seems fine. If anything, the question mark is a bit of editorialism.
The HN guidelines (and longstanding practice) are to prefer the article's title unless it is misleading or linkbait. A false title is misleading.
We sometimes add a question mark when a title is disputed but it isn't clear what a good (i.e. accurate and neutral) title would be. That's the best I've got until someone suggests an accurate and neutral title.
We sometimes add a question mark when a title is disputed but it isn't clear what a good (i.e. accurate and neutral) title would be. That's the best I've got until someone suggests an accurate and neutral title.
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.
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.
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/
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/
cramplet(1)
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?
Still think it was 'cosmic rays' on SKS's machines? Do cosmic rays preferentially strike public keys belonging to major Open Source figures?
> Still think it was 'cosmic rays' on SKS's machines?
Just FYI, this kind of stuff seems to have been done before, with vulnerable keys found:
https://eprint.iacr.org/2012/064.pdf (2012),
https://factorable.net/
(these two are mentioned and linked to from https://blog.hboeck.de/archives/872-About-the-supposed-facto...)
And (off-topic) if you are wondering why some of your recent comments are being downvoted so much, it's probably because of the tone (saying things such as "good job repeating my research" when work of the same kind with results of the same kind had been done before (see above.))
Still an interesting result and curious re. SKS servers (not) checking subkeys etc...
also https://news.ycombinator.com/item?id=9562170
Just FYI, this kind of stuff seems to have been done before, with vulnerable keys found:
https://eprint.iacr.org/2012/064.pdf (2012),
https://factorable.net/
(these two are mentioned and linked to from https://blog.hboeck.de/archives/872-About-the-supposed-facto...)
And (off-topic) if you are wondering why some of your recent comments are being downvoted so much, it's probably because of the tone (saying things such as "good job repeating my research" when work of the same kind with results of the same kind had been done before (see above.))
Still an interesting result and curious re. SKS servers (not) checking subkeys etc...
also https://news.ycombinator.com/item?id=9562170
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
[1]: https://news.ycombinator.com/item?id=9561407
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