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).<p>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.<p>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.<p>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.<p>I wrote a paper about my findings:
<a href="https://eprint.iacr.org/2015/262" rel="nofollow">https://eprint.iacr.org/2015/262</a>
Also some code:
<a href="https://github.com/hannob/pgpecosystem" rel="nofollow">https://github.com/hannob/pgpecosystem</a><p>And if you want to replicate the batch GCD attack Nadia Heninger has released source code for this:
<a href="https://factorable.net/resources.html" rel="nofollow">https://factorable.net/resources.html</a>
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.<p><pre><code> 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 <hpa@infradead.org>
gpg: key 0xBDA06085493BACE4: invalid subkey binding
gpg: key 0xBDA06085493BACE4: skipped subkey
gpg: key 0xBDA06085493BACE4: "H. Peter Anvin (hpa) <hpa@zytor.com>" not changed
gpg: Total number processed: 1
gpg: unchanged: 1</code></pre>
Author of 'phuctor' speaking. We <i>did not break RSA!</i> Please put that Luger down, unload it. You have things to live for!<p>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.
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: <a href="http://en.wikipedia.org/wiki/Hans_Peter_Anvin" rel="nofollow">http://en.wikipedia.org/wiki/Hans_Peter_Anvin</a><p>If it's true that the normal key generation process would reject creating a key with factors this small, this is especially concerning.<p>Edit: Fortunately it looks like this is garbage on the keyservers, rather than a real problem with hpa's key.
We think properly created RSA keys couldn't possibly have such tiny factors because they were created by sophisticated algorithms, presumably would be two <i>very</i> large primes, and yet... this happens.<p>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 <i>bloody obvious</i>. It's like an "is it plugged in?" sort of thing.<p>If I deliberately generated a public key that was divisible by 3, I wonder how long it would take for someone to notice...<p>I also entertain the (admittedly very slim) possibility that he did this deliberately to see what would happen.
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.
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.
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).<p>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).
This isnot really new work, see eg <a href="https://eprint.iacr.org/2012/064.pdf" rel="nofollow">https://eprint.iacr.org/2012/064.pdf</a> (and <a href="http://crypto.stanford.edu/~dabo/papers/RSA-survey.pdf" rel="nofollow">http://crypto.stanford.edu/~dabo/papers/RSA-survey.pdf</a> if you're interested in other RSA weaknesses)
This is not the first time low quality keys have been produced. I'm thinking of <a href="https://www.debian.org/security/2008/dsa-1571" rel="nofollow">https://www.debian.org/security/2008/dsa-1571</a>. Seems like quality control is a bigger problem than we would like to admit.
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.<p>like, hey lets meet up here at time x. in two days that means nothing significant.<p>but anyway, first step is getting an old mobile without data.
Can anyone who was involved in this please post the ASCII-armored key in question?<p>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.<p>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?<p>Why should we wait for somebody else to run a few obvious algorithms on our own keys?<p>Anybody knows what to use and has a good recipe?<p>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)<p>So even if you verify the persons identity correctly when you sign their key you can't tell if the key is garbage easily.<p>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 ;)
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:<p>>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.<p>Strikes me as disingenuous coming from this source.
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.
Aaaand we found another two. One of which belongs to a GNU dev with some public presence...<p>Still think it was 'cosmic rays' on SKS's machines? Do cosmic rays preferentially strike public keys belonging to major Open Source figures?