7 ms·

4096 RSA key in the strongset factored?

205 points by davout 11y ago

dragontamer 11y ago
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.
- arenaninja 11y ago
  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.
  - bostik 11y ago
    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.
  - dragontamer 11y ago
    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.
- lotsofmangos 11y ago
  The ongoing conversation is pretty fun too - http://log.bitcoin-assets.com/?date=17-05-2015#1134741 http://log.bitcoin-assets.com/?date=17-05-2015#1134741
davout 11y ago
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).
- belovedeagle 11y ago
  > 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.
hurin 11y ago
Can anyone confirm this is true?
- revelation 11y ago
  Well, it lists the key and says the first factor is 231. If you have a big enough calculator, this is trivial to verify.
  - asciilifeform 11y ago
    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.
- davout 11y ago
  You can confirm this independently with the key itself and the published prime.
  - hurin 11y ago
    I too can post a public key I have the private key for and a factor? Or intentionally create a weak key?
    - schoen 11y ago
      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.
      - cjbprime 11y ago
        It's: gpg --list-key --with-key-data <id>
      - 11y ago
jjoonathan 11y ago
> And the first factor - get a load of this - is 231. Which... yes, 231 = 3 * 77. The best part.
green7ea 11y ago
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.
- acqq 11y ago
  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.
  - ikeboy 11y ago
    https://eprint.iacr.org/2012/064.pdf https://eprint.iacr.org/2012/064.pdf https://factorable.net/weakkeys12.extended.pdf https://factorable.net/weakkeys12.extended.pdf
    - acqq 11y ago
      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.
      - ikeboy 11y ago
        http://shoestringfoundation.org/cgi-bin/blosxom.cgi/2004/07/01#non-pgp-key http://shoestringfoundation.org/cgi-bin/blosxom.cgi/2004/07/...
  - noondip 11y ago
    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
hhsnopek 11y ago
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?
- jjoonathan 11y ago
  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.
  - Adlai 11y ago
    From http://nosuchlabs.com/theory 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.
- schoen 11y ago
  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.
- ingenter 11y ago
  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.
cjbprime 11y ago
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 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.
- asciilifeform 11y ago
  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.
  - cjbprime 11y ago
    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.
tmbeihl 11y ago
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.
unfamiliar 11y ago
Is there any way to get GPG to print out the two factors when the key is generated? 231 is absurd.
- schoen 11y ago
  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.
  - userbinator 11y ago
    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-1min http://www.recordholders.org/en/list/memory.html#numbers-1mi...
    - schoen 11y ago
      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 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.
    - unfamiliar 11y ago
      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.
- userbinator 11y ago
  That doesn't protect against the possibility that one of the factors is itself composite.
strictfp 11y ago
This is not the first time low quality keys have been produced. I'm thinking of https://www.debian.org/security/2008/dsa-1571 https://www.debian.org/security/2008/dsa-1571. Seems like quality control is a bigger problem than we would like to admit.
gonzo41 11y ago
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.
- cnvogel 11y ago
  > like, hey lets meet up here at time x. in two days > that means nothing significant. It might still be significant in the far future that you have met a particular person on May, 19th 2015!
monochromatic 11y ago
> 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?
- ColinWright 11y ago
  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]: Also, shouldn't it only have 2 prime factors? It's possible that one of the "primes" it found was in fact composite, and it's that "prime" that has these factors. So you generate two large primes and multiply them together, not realising that one of your "primes" wasn't. [0] https://news.ycombinator.com/item?id=9561051 https://news.ycombinator.com/item?id=9561051
  - jugad 11y ago
    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.
- contravariant 11y ago
  Also, shouldn't it only have 2 prime factors?
  - detaro 11y ago
    Should. Obviously something went very wrong and the "primes" weren't properly checked to actually be primes.
    - 11y ago
asciilifeform 11y ago
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.
- noondip 11y ago
  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.
  - asciilifeform 11y ago
    Not known to me.
cmrx64 11y ago
This isnot really new work, see eg https://eprint.iacr.org/2012/064.pdf https://eprint.iacr.org/2012/064.pdf (and http://crypto.stanford.edu/~dabo/papers/RSA-survey.pdf http://crypto.stanford.edu/~dabo/papers/RSA-survey.pdf if you're interested in other RSA weaknesses)
userbinator 11y ago
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.
- jugad 11y ago
  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.
- nacs 11y ago
  > 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_against_plain_RSA https://en.wikipedia.org/wiki/RSA_(cryptosystem)#Attacks_aga...
rewqfdsa 11y ago
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.
- dang 11y ago
  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.
  - rewqfdsa 11y ago
    > 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.
  - schoen 11y ago
    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.
    - dang 11y ago
      I don't understand this well enough to know what an accurate title should say. Can you or anyone suggest one?
      - JoshTriplett 11y ago
        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.
ingenter 11y ago
Ahem. For the first key they mention, there are more factors there! 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\ 0450507289719327232580534861464796513972730400397
acqq 11y ago
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.
agwa 11y ago
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 <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
- schoen 11y ago
  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 rather than using it.
  - acqq 11y ago
    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.
- diafygi 11y ago
  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 https://gist.github.com/anonymous/ba23ca66d2ca249e6f84 Here's the factored subkey: https://gist.github.com/anonymous/ba23ca66d2ca249e6f84#file-hpa-pub-json-L466 https://gist.github.com/anonymous/ba23ca66d2ca249e6f84#file-... Here's the factored subkey's bad signature: https://gist.github.com/anonymous/ba23ca66d2ca249e6f84#file-hpa-pub-json-L484 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-hpa-pub-json-L498 https://gist.github.com/anonymous/ba23ca66d2ca249e6f84#file-... Good subkey self-signature: https://gist.github.com/anonymous/ba23ca66d2ca249e6f84#file-hpa-pub-json-L566 https://gist.github.com/anonymous/ba23ca66d2ca249e6f84#file-...
schoen 11y ago
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.
tedunangst 11y ago
Did HPA publish this key anywhere? Tell anyone to use it?
hannob 11y ago
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 https://eprint.iacr.org/2015/262 Also some code: https://github.com/hannob/pgpecosystem 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 https://factorable.net/resources.html
- asciilifeform 11y ago
  It remains to be seen whether 'These keys don't really do any harm.' And good job repeating my research without any acknowledgment. Does your sponsor know about Phuctor? What if he were to read this thread?
- zmanian 11y ago
  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/2015/EE/380/9469 https://mvideos.stanford.edu/graduate#/SeminarDetail/Spring/...
- diafygi 11y ago
  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-hpa-pub-json-L490 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-hpa-pub-json-L498 https://gist.github.com/anonymous/ba23ca66d2ca249e6f84#file-... Good subkey self-signature: https://gist.github.com/anonymous/ba23ca66d2ca249e6f84#file-hpa-pub-json-L566 https://gist.github.com/anonymous/ba23ca66d2ca249e6f84#file-...
deleted 11y ago
[deleted]
zobzu 11y ago
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 ;)
throwaway2391 11y ago
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.
- asciilifeform 11y ago
  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 11y ago
    [deleted]
  - deleted 11y ago
    [deleted]
- cramplet 11y ago
  The forum you are referring to is 8chan (http://8ch.net/ http://8ch.net/), yes? Are you sure you are not trolling?
  - deleted 11y ago
    [deleted]
asciilifeform 11y ago
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?
- diafygi 11y ago
  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 https://news.ycombinator.com/item?id=9561407
- wfn 11y ago
  > 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 https://eprint.iacr.org/2012/064.pdf (2012), https://factorable.net/ https://factorable.net/ (these two are mentioned and linked to from https://blog.hboeck.de/archives/872-About-the-supposed-factoring-of-a-4096-bit-RSA-key.html 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 https://news.ycombinator.com/item?id=9562170

205 points by davout 11y ago

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.

arenaninja 11y ago
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.
- bostik 11y ago
  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.
- dragontamer 11y ago
  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.
lotsofmangos 11y ago
The ongoing conversation is pretty fun too - http://log.bitcoin-assets.com/?date=17-05-2015#1134741 http://log.bitcoin-assets.com/?date=17-05-2015#1134741

davout 11y ago

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).

belovedeagle 11y ago
> 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.

hurin 11y ago

Can anyone confirm this is true?

revelation 11y ago
Well, it lists the key and says the first factor is 231. If you have a big enough calculator, this is trivial to verify.
- asciilifeform 11y ago
  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.
davout 11y ago
You can confirm this independently with the key itself and the published prime.
- hurin 11y ago
  I too can post a public key I have the private key for and a factor? Or intentionally create a weak key?
  - schoen 11y ago
    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.
    - cjbprime 11y ago
      It's: gpg --list-key --with-key-data <id>
    - 11y ago

jjoonathan 11y ago

> And the first factor - get a load of this - is 231. Which... yes, 231 = 3 * 77. The best part.

green7ea 11y ago

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.

acqq 11y ago
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.
- ikeboy 11y ago
  https://eprint.iacr.org/2012/064.pdf https://eprint.iacr.org/2012/064.pdf https://factorable.net/weakkeys12.extended.pdf https://factorable.net/weakkeys12.extended.pdf
  - acqq 11y ago
    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.
    - ikeboy 11y ago
      http://shoestringfoundation.org/cgi-bin/blosxom.cgi/2004/07/01#non-pgp-key http://shoestringfoundation.org/cgi-bin/blosxom.cgi/2004/07/...
- noondip 11y ago
  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

hhsnopek 11y ago

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?

jjoonathan 11y ago
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.
- Adlai 11y ago
  From http://nosuchlabs.com/theory 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.
schoen 11y ago
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.
ingenter 11y ago
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.

cjbprime 11y ago

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 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.

asciilifeform 11y ago
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.
- cjbprime 11y ago
  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.

tmbeihl 11y ago

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.

unfamiliar 11y ago

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

schoen 11y ago
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.
- userbinator 11y ago
  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-1min http://www.recordholders.org/en/list/memory.html#numbers-1mi...
  - schoen 11y ago
    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 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.
  - unfamiliar 11y ago
    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.
userbinator 11y ago
That doesn't protect against the possibility that one of the factors is itself composite.

strictfp 11y ago

This is not the first time low quality keys have been produced. I'm thinking of https://www.debian.org/security/2008/dsa-1571 https://www.debian.org/security/2008/dsa-1571. Seems like quality control is a bigger problem than we would like to admit.

gonzo41 11y ago

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.

cnvogel 11y ago
> like, hey lets meet up here at time x. in two days > that means nothing significant. It might still be significant in the far future that you have met a particular person on May, 19th 2015!

monochromatic 11y ago

> 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?

ColinWright 11y ago
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]: Also, shouldn't it only have 2 prime factors? It's possible that one of the "primes" it found was in fact composite, and it's that "prime" that has these factors. So you generate two large primes and multiply them together, not realising that one of your "primes" wasn't. [0] https://news.ycombinator.com/item?id=9561051 https://news.ycombinator.com/item?id=9561051
- jugad 11y ago
  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.
contravariant 11y ago
Also, shouldn't it only have 2 prime factors?
- detaro 11y ago
  Should. Obviously something went very wrong and the "primes" weren't properly checked to actually be primes.
  - 11y ago

asciilifeform 11y ago

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.

noondip 11y ago
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.
- asciilifeform 11y ago
  Not known to me.

cmrx64 11y ago

This isnot really new work, see eg https://eprint.iacr.org/2012/064.pdf https://eprint.iacr.org/2012/064.pdf (and http://crypto.stanford.edu/~dabo/papers/RSA-survey.pdf http://crypto.stanford.edu/~dabo/papers/RSA-survey.pdf if you're interested in other RSA weaknesses)

userbinator 11y ago

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.

jugad 11y ago
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.
nacs 11y ago
> 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_against_plain_RSA https://en.wikipedia.org/wiki/RSA_(cryptosystem)#Attacks_aga...

rewqfdsa 11y ago

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.

dang 11y ago
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.
- rewqfdsa 11y ago
  > 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.
- schoen 11y ago
  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.
  - dang 11y ago
    I don't understand this well enough to know what an accurate title should say. Can you or anyone suggest one?
    - JoshTriplett 11y ago
      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.

ingenter 11y ago

Ahem. For the first key they mention, there are more factors there! 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\ 0450507289719327232580534861464796513972730400397

acqq 11y ago

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.

agwa 11y ago

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

schoen 11y ago
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 rather than using it.
- acqq 11y ago
  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.
diafygi 11y ago
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 https://gist.github.com/anonymous/ba23ca66d2ca249e6f84 Here's the factored subkey: https://gist.github.com/anonymous/ba23ca66d2ca249e6f84#file-hpa-pub-json-L466 https://gist.github.com/anonymous/ba23ca66d2ca249e6f84#file-... Here's the factored subkey's bad signature: https://gist.github.com/anonymous/ba23ca66d2ca249e6f84#file-hpa-pub-json-L484 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-hpa-pub-json-L498 https://gist.github.com/anonymous/ba23ca66d2ca249e6f84#file-... Good subkey self-signature: https://gist.github.com/anonymous/ba23ca66d2ca249e6f84#file-hpa-pub-json-L566 https://gist.github.com/anonymous/ba23ca66d2ca249e6f84#file-...

schoen 11y ago

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.

tedunangst 11y ago

Did HPA publish this key anywhere? Tell anyone to use it?

hannob 11y ago

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 https://eprint.iacr.org/2015/262 Also some code: https://github.com/hannob/pgpecosystem 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 https://factorable.net/resources.html

asciilifeform 11y ago
It remains to be seen whether 'These keys don't really do any harm.' And good job repeating my research without any acknowledgment. Does your sponsor know about Phuctor? What if he were to read this thread?
zmanian 11y ago
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/2015/EE/380/9469 https://mvideos.stanford.edu/graduate#/SeminarDetail/Spring/...
diafygi 11y ago
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-hpa-pub-json-L490 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-hpa-pub-json-L498 https://gist.github.com/anonymous/ba23ca66d2ca249e6f84#file-... Good subkey self-signature: https://gist.github.com/anonymous/ba23ca66d2ca249e6f84#file-hpa-pub-json-L566 https://gist.github.com/anonymous/ba23ca66d2ca249e6f84#file-...

deleted 11y ago

[deleted]

zobzu 11y ago

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 ;)

throwaway2391 11y ago

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.

asciilifeform 11y ago
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 11y ago
  [deleted]
- deleted 11y ago
  [deleted]
cramplet 11y ago
The forum you are referring to is 8chan (http://8ch.net/ http://8ch.net/), yes? Are you sure you are not trolling?
- deleted 11y ago
  [deleted]

asciilifeform 11y ago

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?

diafygi 11y ago
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 https://news.ycombinator.com/item?id=9561407
wfn 11y ago
> 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 https://eprint.iacr.org/2012/064.pdf (2012), https://factorable.net/ https://factorable.net/ (these two are mentioned and linked to from https://blog.hboeck.de/archives/872-About-the-supposed-factoring-of-a-4096-bit-RSA-key.html 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 https://news.ycombinator.com/item?id=9562170