4096 RSA key in the strongset factored?(trilema.com) |
4096 RSA key in the strongset factored?(trilema.com) |
Still think it was 'cosmic rays' on SKS's machines? Do cosmic rays preferentially strike public keys belonging to major Open Source figures?
Just FYI, this kind of stuff seems to have been done before, with vulnerable keys found:
https://eprint.iacr.org/2012/064.pdf (2012),
(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...
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
Here's a json breakdown of the invalid hash_check: https://gist.github.com/anonymous/ba23ca66d2ca249e6f84#file-...
EDIT: It's the EXACT SAME subkey self-signature packet as HPA's real subkey self-signature packet! Someone (by malice or mistake) manually added a subkey to HPA's public key and copied the signature from the other subkey directly onto the new subkey.
These are the same:
Bad subkey self-signature: https://gist.github.com/anonymous/ba23ca66d2ca249e6f84#file-...
Good subkey self-signature: https://gist.github.com/anonymous/ba23ca66d2ca249e6f84#file-...
https://mvideos.stanford.edu/graduate#/SeminarDetail/Spring/...
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: 1We 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.
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.
And why Mr. Anvin's key was chosen, rather than another.
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.
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.
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.
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...
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.
http://www.recordholders.org/en/list/memory.html#numbers-1mi...
The best part.
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).
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.
Why isn't the first factor just 3 then?
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?
These primes could not have been generated by any reputable prime generation algos that I can imagine.
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.
like, hey lets meet up here at time x. in two days that means nothing significant.
but anyway, first step is getting an old mobile without data.
> like, hey lets meet up here at time x. in two days
> that means nothing significant.
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.
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.
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 ;)
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 817023023960376946633975507110154649249407598806798730414849884461776172171921668594148071323527016137506405823108520062504849249423700259406905313281403901410082762097159560221463048924336192384026777502177262731045200322200149773127502888545234973139480887644585192600631058962876114156934248895171959246969597637127280010272143593885240940877456234662196130491400738438731832514335353824697930453078426722191105157568392826870043655708008545411143367763836566011740499383456592129662585004880376777597714978023542434421914201119537685489173509942329090631662014650033142642110914360849421856179611226450806562235534802516081595259914768497444702718749402330070488028751073730349460752771915484847399385631524708487646079936572410398967582895983187640798072309362094727654167628620105981459021548290415800096769214437425690934372015628796027498219902441288189398386359846661623243493534897411417685435424010451956954083531228374002591372549525280610594684910812811287436481207089763125424247793044043309737269468709710679872269272855389945385386467765509880648929743498214329578288874987193768439353382305260108425688024147656806932474058888992099083804597481699305852902662863062054067183925164590726103552998367994727700722491707 `mod` 231
0You have one ending in 131307671292149646652772992033083 and I have one ending in 726103552998367994727700722491707 that is not divisible by 231.
I can only confirm that we have a key, downloaded from an SKS dump, said key purporting to belong to one Mr. Anvin, containing one sub-key being an RSA public key which turned out to be factorable with trivial effort.
Anything else is mere conjecture.
I think the article might be a bit dense for those who aren't aware of RSA's algorithm though.
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.
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.
>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.
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?
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.
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.
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.
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/
If this is the explanation, then this is either an attack by a random person or an attack or flaw in a keyserver, but an attack that's unlikely to work because users will discard the bad key rather than using it.
The users are the ones responsible for any key verification.
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-...
This looks more like a fake sub key that someone tried to pollute the public key servers with
1. Misbehavior on the part of someone running a keyserver.
2. A bug in the keyserver software
which isn't really an issue because PGP implementations will just ignore it
I ask both of the questions because I can't understand why anybody would go to the trouble of doing this unless it supports some kind of attack (which may no longer be viable, but perhaps was at some time in the past).
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).
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.
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".
Disclaimer: I'm not a cryptographer, I have very possibly misread the article. Corrections welcome.
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.
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"Based on my research it seems that over a very long time the use of PGP implementations with deeply awed random number generation functions was very rare."
We also know from Nadia Heninger and Hovav Shacham's research that you can reconstruct private keys relatively efficiently if you have some missing bits.
https://eprint.iacr.org/2008/510.pdf
But I think you're right that human memory isn't a very significant threat to RSA private parameters. Realistically, cameras would be the threat, not a human being glancing it them.
Not fully functional yet, but was able to convert this public key to json. I manually removed the non-self signature packets for the gist.
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.
Unless, by some incredible fluke, they managed to find a carmichael number.
IIRC PKCS#1 even supports more than two modulus factors in it's private key format (not that it is particularly useful for anything).
So, the current title seems fine. If anything, the question mark is a bit of editorialism.
We sometimes add a question mark when a title is disputed but it isn't clear what a good (i.e. accurate and neutral) title would be. That's the best I've got until someone suggests an accurate and neutral title.
Wikipedia says ( http://en.wikipedia.org/wiki/RSA_(cryptosystem) ): "When m is not relatively prime to n, the argument just given is invalid. This is highly improbable (only a proportion of 1/p + 1/q − 1/(pq) numbers have this property), but even in this case the desired congruence is still true. Either m ≡ 0 (mod p) or m ≡ 0 (mod q), and these cases can be treated using the previous proof.".
I'm not sure I follow 100% - perhaps someone smarter can explain.
The other problem is that the value φ(n) will be wrong, even then there are some rare cases where the method might still work (see eximius comment about carmicheal numbers) but those are exceedingly rare.