4096 RSA key in the strongset factored?

http://trilema.com/2015/full-disclosure-4096-rsa-key-in-the-strongset-factored/

by davout • 11 years ago

205 103 11 years ago

trilema.com

dragontamer2• 11 years 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• 11 years 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• 11 years 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.

dragontamer2• 11 years 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• 11 years ago

The ongoing conversation is pretty fun too - http://log.bitcoin-assets.com/?date=17-05-2015#1134741

davout4• 11 years 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• 11 years 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.

hurin2• 11 years ago

Can anyone confirm this is true?

revelation• 11 years 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.

asciilifeform8• 11 years 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.

davout4• 11 years ago

You can confirm this independently with the key itself and the published prime.

hurin2• 11 years ago

I too can post a public key I have the private key for and a factor? Or intentionally create a weak key?

ycitm• 11 years ago

Yes:

    817023023960376946633975507110154649249407598806798730414849884461776172171921668594148071323527016137506405823108520062504849249423700259406905313281403901410082762097159560221463048924336192384026777502177262731045200322200149773127502888545234973139480887644585192600631058962876114156934248895171959246969597637127280010272143593885240940877456234662196130491400738438731832514335353824697930453078426722191105157568392826870043655708008545411143367763836566011740499383456592129662585004880376777597714978023542434421914201119537685489173509942329090631662014650033142642110914360849421856179611226450806562235534802516081595259914768497444702718749402330070488028751073730349460752771915484847399385631524708487646079936572410398967582895983187640798072309362094727654167628620105981459021548290415800096769214437425690934372015628796027498219902441288189398386359846661623243493534897411417685435424010451956954083531228374002591372549525280610594684910812811287436481207089763125424247793044043309737269468709710679872269272855389945385386467765509880648929743498214329578288874987193768439353382305260108425688024147656806932474058888992099083804597481699305852902662863062054067183925164590726103552998367994727700722491707 `mod` 231
    0

schoen10• 11 years ago

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

jjoonathan2• 11 years ago

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

The best part.

green7ea• 11 years 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.

acqq5• 11 years 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.

ikeboy2• 11 years ago

https://eprint.iacr.org/2012/064.pdf

https://factorable.net/weakkeys12.extended.pdf

noondip2• 11 years ago

A look at the PGP ecosystem through the key server data

https://eprint.iacr.org/2015/262.pdf

hhsnopek• 11 years 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?

jjoonathan2• 11 years 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• 11 years ago

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.

schoen10• 11 years 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.

ingenter3• 11 years 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.

contravariant5• 11 years ago

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.

geofft• 11 years ago

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

cjbprime3• 11 years 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

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.

asciilifeform8• 11 years 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.

cjbprime3• 11 years 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• 11 years 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.

unfamiliar2• 11 years ago

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

schoen10• 11 years 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.

userbinator3• 11 years 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-1mi...

userbinator3• 11 years ago

That doesn't protect against the possibility that one of the factors is itself composite.

strictfp• 11 years 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. Seems like quality control is a bigger problem than we would like to admit.

gonzo41• 11 years 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.

cnvogel2• 11 years 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• 11 years 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• 11 years 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

jugad3• 11 years 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.

contravariant5• 11 years ago

Also, shouldn't it only have 2 prime factors?

detaro• 11 years ago

Should. Obviously something went very wrong and the "primes" weren't properly checked to actually be primes.

jugad3• 11 years ago

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.

asciilifeform8• 11 years 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.

noondip2• 11 years 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.

asciilifeform8• 11 years ago

Not known to me.

cmrx64• 11 years ago

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)

userbinator3• 11 years 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.

jugad3• 11 years 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• 11 years 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_aga...

rewqfdsa2• 11 years 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.

dang3• 11 years 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.

rewqfdsa2• 11 years 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.

schoen10• 11 years 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.

asciilifeform8• 11 years ago

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.

throwaway23912• 11 years ago

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/

ingenter3• 11 years 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

ingenter3• 11 years ago

Update: 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\
    704276600438478560110515119729110048093857

acqq5• 11 years 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.

agwa2• 11 years 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

schoen10• 11 years 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.

acqq5• 11 years 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.

diafygi5• 11 years 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

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

agwa2• 11 years ago

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

garrettr_• 11 years ago

    This looks more like a fake sub key that someone tried to pollute the public key servers with

Does anybody know how that would be possible? I can't understand why a key server would accept a subkey unless it was correctly signed by the primary key. At the moment, all I can think is:

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

2. A bug in the keyserver software

    which isn't really an issue because PGP implementations will just ignore it

Has that always been the case? With all widely used PGP implementations?

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

diafygi5• 11 years ago

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

schoen10• 11 years 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• 11 years ago

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

hannob• 11 years 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 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

diafygi5• 11 years 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-...

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

zmanian• 11 years 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/...

undata• 11 years ago

What do you make of this? https://news.ycombinator.com/item?id=9575598

zobzu• 11 years 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 ;)

throwaway23912• 11 years 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.

asciilifeform8• 11 years 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?

cramplet• 11 years ago

The forum you are referring to is 8chan (http://8ch.net/), yes? Are you sure you are not trolling?

asciilifeform8• 11 years 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?

diafygi5• 11 years 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

wfn• 11 years 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 (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

4096 RSA key in the strongset factored?

Related Stories