# More factored RSA keys, and assorted other considerations

Wednesday, 20 May, Year 7 d.Tr. | Author: Mircea Popescu

This is going to be a lengthy article that - like pretty much everything elsei on Trilema - deals with complex matter broadly unfamiliar to most certified experts in the respective fields, let alone the general public. To avoid personal injury, tread softly, mutter to yourself quietly and re-read insistently.

# Part One : The Conundrum

The verbiage on Phuctor's theory page reads in relevant part :

When Phuctor was originally released, back in October 2013, it was intended and consequently designed as a user-powered, one signature at a time sort of affair. This changed later on, when we decided to allocate actual computational resources to the task. At that time the approach changed in tandem, from "wait for users to post a key" to simply churning the entire keyserver set. This evolution leaves that verbiage in the lurch, or as Stan put it, "I still can't fathom why you threw that in there."

I obviously can fathom - after all, I'm the one that put it in. The admittedly parochial logic behind it was based on some presuppositions meanwhile invalidated : 1) that the set of tested keys will at all points be a minor fraction of the total visible keys ; 2) that the set of weak keys found will at all points be so tiny as to not raise significant problems with emailing the owners and 3) that we are acting in a world that is both larger than us and more important than us, a sleeping giant that we do not wish to upset.

Experience hence has shown the folly of all these presuppositions, as experience always does. Specifically :

As far as the first is concerned, there are strictly insurmountable problems with keeping information secret. "Information wants to be free" may not be sensu stricto correct, and may certainly be entirely nonsensical as used by the derps that came up with it. Nevertheless, there is something there : how would I keep anyone who feels like it from running the same very basic math on the same publicly accessible set of numbers ? Upon meditation, the "for all we know others unknown are at the current time in possession of the same information we have" problem can not actually be resolved through increasing the paranoia level with regards to server security from just under nine thousand to well over nine thousand. One doesn't need to root my computer in order to add two and two, he can do that on his own computer just as well.

This aside, how exactly is one going to implement the "we won't tell on your key" policy ? Do we show all keys as "passed" even if they aren't ? ♫But you don't want to lie, not to the young...♪ Yet if we don't, what is the difference between the key not being displayed and the key getting a big fat red warning ? Obviously, some naive observers might be fooled. Cui bono, fooling the naive observers ? The entire point of this entire exercise is to reduce the disadvantage of the naive, after all.

As far as the second is concerned, we went in with the expectation, and I quote,

Since there's about 4 million keys (a little under) in the bundle of publicly known keys that it is processing, if you're even vaguely mathematically literate and even marginally aware of what exactly theoretical RSA promises, you would on the strength of this introduction expect a key to be factored just a little before Elvis comes back as the Queen of England. So did we. So did everyone else.

There was absolutely no expectation any key will ever be factored through this mechanism. Ever. This is the truth.

As far as the third is concerned, well... let's give the mic over to Naggum for a moment :

The problem is that "exploitation" happens only to people stupider (and consequently less informed) than the "exploiter".

The root cause of this whole world problem is that some people are smarter than others. There are two basic solutions to this problem: Kill all the morons, or kill all the brains. If you look at how several political regimes have behaved throughout history, you might get the impression that they are precisely adopting one of those two options. (Social democracy is a little more advanced: Kill everything outside 2 sigma.) World history and evolution and nature in general keep telling us something we humans do not want to hear: Some people _have_ to die for the rest of us to live better. The only question that political systems can answer is _who_ gets to live or die. Those who do not realize this will not live well before they die young. Our current political systems have created a world where people are afraid that we are not "sustainable". Of course we are not. But instead of killing contemporary people, we are killing future people. It is definitely not sustainable to keep everybody alive forever. We will, eventually, resort to killing a lot of people, and I mean a _lot_, like probably half of the planet's population, because, like fruit flies in a laboratory jar that runs out of sugar, we will be too many before we get the point. And that is OK with me, I do not plan to hang around forever, and neither do I want children to make things worse. But in the end, nature exploited us, not vice versa, because people are generally stupid and ill-informed about the choices they make. (Which is probably what some people _really_ mean when they say people are not rational.)

The fact of the matter is that we're people well outside two sigmaii, which means both that "the world" is roughly the size of half a chickenshit in comparison, and already as hostile as it can ever get.

Seriously, I should care that "the Internet community" will get upset, for reasons ? Fuck "the Internet community", I wouldn't trade away a strand of chewed gum for the whole lot of it. Moreover, it's already upset. It'll never get more upset. The mere fact that we exist punctures its ever-paramount narrative, and that's really all it takes and all there is.

The "Internet community" of dullards, normies and business majors is fundamentally lazy, fundamentally stupid, and already penned and handled by the exact people who should be handling it. Not our problem, not our interest and not a valid point of consideration or concern or in other words - If you're not in the WoT, you are not a person.

So therefore, for the aforestated reasons and after very careful deliberationiii, the original policy is rescinded. We will be publishing broken keys freely, periodically, and without any attempt to insulate their owners or anyone else from the fallout. That's it.

# Part Two : The Broken Keys

We have thirteeniv fifteen keys so far.v Here they are :

1. 51EAB526D87542022AA1BC85E99EF4B451221121vi [H. Peter Anvin <hpa-squee-infradead.org>; H. Peter Anvin (hpa) <hpa-squee-zytor.com>; H. Peter Anvin <h.peter.anvin-squee-intel.com>;], divisible by 231.
2. 1482E27395532CEC191ADD937765EA7193E6924Cvii [Tony Pelaez (HarryGuerilla) <tnyplz-squee-gmail.com>;], divisible by 21.
3. EF010E6F351E447C96C91AF1293987A8466F60E1viii, [Debarshi Ray <rishi.is-squee-lostca.se>; Debarshi Ray (GNU Developer) <rishi-squee-gnu.org>; Debarshi Ray (GMail Account) <debarshi.ray-squee-gmail.com>; Debarshi Ray (Red Hat Employee) <debarshir-squee-redhat.com>; Debarshi Ray (Fedora Packager) <rishi-squee-fedoraproject.org>; Debarshi Ray (GNOME Developer) <debarshir-squee-src.gnome.org>; Debarshi Ray (GNOME Foundation Member) <debarshir-squee-gnome.org>; Debarshi Ray (Freedesktop.org Developer) <debarshir-squee-freedesktop.org>; Debarshi Ray (Student at University of Helsinki) <debarshi.ray-squee-helsinki.fi>;], divisible by 9.
4. A50591247C8E37A64117B74F78AB527059E13694 and B01584E9F6CB9E76DEA61E2A73786CA0F4EACC4Fix [grenzenlosnaiv <grenzenlosnaiv-squee-live.de>;], divisible by 17742509903907 and 4294967297 respectively.x
5. 1F75CF2DD19ABC516D58454B0846265183C9F86F and 29A9D31313C5E0E8B73F8D155CF76C1F591D4EFFxi [Saeid <zarghani.s-squee-gmail.com>;], divisible by 73014444049 and 270582939711 respectively.
6. 89FAD5E452080D47B11508148CA2B56B92E193C9xii [Lou Anschuetz <lou-squee-ece.cmu.edu>;], divisible by 4294967297.
7. C1FEDFCEADA4849AFE940D192979698801093DA6 and 51D1FBC806EBF7EFA78D74092E271AF5D8322944xiii [Christopher Winterbottom <cqwberry-squee-gmail.com>;], divisible by 98784247831 and 30064771079 respectively.
8. F353FA51752FD981FE926C60E863669BEC4DA8F3 and F1573FEF30BE4BE50CD109AC3CAC41B5194C8916xiv [Li-Wen Kuo <li-wen-squee-gmx.de>;], divisible by 12884901891 and 21474836485 respectively.
9. F1D9FE5073EC39F3558905668C97B382AC1729F4xv [Tobias Michelis <michelis-squee-mi.uni-erlangen.de>;], divisible by 4294967297.
10. 1A5E4C59222FF18F2D5E2406E1548C609A6137AA and C8749C423CCE71A1230B138D2342919EC10A9C5Cxvi [Sebastian Heberer <pirat-squee-drpest.de>;], divisible by 4294967297 and 12884901891 respectively.

# Part Three : Discussion

First off, and to get this out of the way : Hanno Böck just got caught lying. Specifically :

Last year I started a project to analyze the data on the PGP key servers. And at some point I thought I had found a large number of vulnerable PGP keys – including the key in question here. In a rush I wrote a mail to all people affected. Only later I found out that something was not right and I wrote to all affected people again apologizing. Most of the keys I thought I had found were just faulty keys on the key servers.

He did no such thing. Had he done such a thing, or anything even remotely similar to it, he would know about all thisxvii. That he has absolutely no idea about any of it, yet finds it within himself to make all-knowing statements of a certain tendency is all the smoking gun anyone could ever need.xviii

I hold Paul Graham personally responsible for the fraudulent shenanigans dissected in On how the factored 4096 RSA keys story was handled, and what it means to you, and I expect an apology. Let me also underscore that I smushed the last too-big-for-his-britches schmuck that owed me an apology and failed to make good. Don't make me Karpeles you, Graham.

Second off, you will notice the heterogenity of these vulnerable keys. For instance : not all of them are "signed" by simply copying the signature block off a valid key, like it was the case with the first one found. Some are not signed at all - which notably means that yes gpg will import, and yes gpg will use. A few are actually validly self-signed. There goes that "cosmic ray" theory, as entertaining as it was.

Third off, what do you make of this :

Here's what Stan made of it :

 

#!/usr/bin/python

import pgpdump
import sys
import os
from shutil import copy

####################################################################

def get_rsa(pgpasc):
mods = []
exps = []
try:
packets = list(pgpdump.AsciiData(pgpasc).packets())
for p in packets:
if hasattr(p, 'modulus') and (p.modulus != None):
mods += [p.modulus]
if hasattr(p, 'exponent') and (p.exponent != None):
exps += [p.exponent]
except Exception, e:
print e
return [mods, exps]

## Litmus for Shitgnomancy
def litmus(path):
## Heuristic: at least one absurdly large exponent?
for e in exps:
if e > 65537:
return True
## Heuristic: at least one possibly-shitgnomiferous modulus?
for m in mods:
if (m & 0xFFFFFFFF) == ( (m >> 32) & 0xFFFFFFFF):
return True

####################################################################

indir = sys.argv[1]
outdir = sys.argv[2]
pgpfiles = [os.path.join(indir,fn) for fn in next(os.walk(indir))[2]]
keys = sorted(filter(lambda x: x.endswith('.gpg.asc'), pgpfiles))

## Test each key in indir and if heuristic positive, copy to outdir.
for k in keys:
if litmus(k):
print "Result: {0}".format(k)
copy(k, outdir)

 

To let him explain :

Dear MP,

It appears that we have... something. Heuristic worked as follows (see litmus.py) :

1. Flag RSA keys with outlandishly large exponents. This yielded up many things but no clear pattern thus far. We table it for later.
2. Flag RSA keys which appear to have the repeating 32-bit word pattern seen in the earlier curios. This ended up hitting pay dirt.

litmus_mod_only contains the keys themselves. lusers.txt contains the parsed-out emails claimed in the keys. Start by reading these.

Yours,
-S

Would you like to see the paydirt ? Sure. Here you go :

1. Ludwig Hügelschäfer <ludwig-squee-hammernoch.net>
2. Ludwig Hügelschäfer <mlisten-squee-hammernoch.net>
3. Ludwig Hügelschäfer <enigmail-mod-squee-hammernoch.net>
4. Ludwig Hügelschäfer <ludwig.huegelschaefer-squee-gmx.de>
5. grenzenlosnaiv <grenzenlosnaiv-squee-live.de>
6. Saeid <zarghani.s-squee-gmail.com>
7. Lou Anschuetz <lou-squee-ece.cmu.edu>
8. Christopher Winterbottom <cqwberry-squee-gmail.com>
9. Li-Wen Kuo <li-wen-squee-gmx.de>
10. Tobias Michelis <michelis-squee-mi.uni-erlangen.de>
11. Sebastian Heberer <pirat-squee-drpest.de>
12. Kosta <kosta-squee-embros.org>
13. Christoph Giesel <mail-squee-cgiesel.de>
14. Christoph Giesel <chris-squee-cgiesel.de>
15. Christoph Giesel <christoph-squee-cgiesel.de>
16. Raymond Häb <ray-squee-haeb.eu>
17. Raymond Häb <ray.haeb-squee-gmx.de>
18. Raymond Häb <raymond.haeb-squee-rwth-aachen.de>
19. Kristof Koerner <buero-squee-kristofkoerner.de>
21. Kristof Koerner <unterricht-squee-kristofkoerner.de>
22. Daniel Düngel <pirat-squee-duengel.com>
23. PGP Global Directory Verification Key
24. Philippe Baeriswyl <philippe.baeriswyl-squee-liip.ch>
25. Charly Avital(RSA4096) <shavital-squee-mac.com>
26. Charly Avital (RSA-AES256) <shavital-squee-netbox.com>
27. Matthias <kaizoku-squee-schmidt-system.de>
28. Ismael de Moura Costa (email pessoal) <ismaelcosta-squee-unb.br>
29. Tim Fiedler <tfcoding-squee-gmail.com>
30. Marcus Benjamin <markymac99-squee-mac.com>
31. Stefan Thöne <stefan-squee-frontflip.de>
32. Thomas Scholz <ts-squee-elktc.org>
33. Thomas Scholz <dings-squee-bums.li>
34. Thomas Scholz <tscholz-squee-gmx.de>
35. Thomas Scholz <tststs-squee-gugux.de>
36. Thomas Scholz <thomas.scholz-squee-ploenk.net>
37. Thomas Scholz <tscholz-squee-rz.uni-mannheim.de>
38. Thomas Scholz <tscholz-squee-rumms.uni-mannheim.de>
39. Thomas Scholz <thomas.scholz-squee-ca.uni-mannheim.de>
40. Thomas Scholz <tscholz-squee-wendy.rz.uni-mannheim.de>
41. Thomas Scholz RUM-CA <tscholz-squee-rz.uni-mannheim.de>
42. Thomas Scholz <tscholz-squee-einstein.rz.uni-mannheim.de>
43. Thomas Scholz <thomas.scholz-squee-mail.ca.uni-mannheim.de>
44. Thomas Scholz <thomas.scholz-squee-einstein.rz.uni-mannheim.de>
45. Thomas Scholz INTERN <tscholz-squee-mailtux.ca.uni-mannheim.de>
46. Thomas Scholz <thomas.scholz-squee-crypto.nc1UW1aoi420d85w1SoS.de>
47. http://www.crypto.nc1UW1aoi420d85w1SoS.de (official homepage)
48. Shumitsu Muryokoin <shumitsu-squee-muryokoin.org>
49. Martin M. Stoppler <martin-squee-stoppler.de>
51. Felix Arndt <kontakt-squee-felixarndt.de>
52. Dominik Rapp <dominikrapp-squee-zoho.com>
53. Henry Hertz Hobbit <hhhobbit-squee-gmail.com>
54. Henry Hertz Hobbit <hhhobbit-squee-hotmail.com>
55. Henry Hertz Hobbit <hhhobbit-squee-securemecca.net>
56. Henry Hertz Hobbit <henryhertzhobbit-squee-yahoo.com>
57. Michael Starck <michael.starck-squee-piratenpartei-hessen.de>
58. Robert Manigk <p1ng0ut-squee-arcor.de>
59. Shingondo <shingondo-squee-shingondo.org>
60. Ben Donnachie <benjamin-d-squee-ntlworld.com>
61. Ben Donnachie <benjamin_d-squee-ntlworld.com>
62. Ben Donnachie <bd348-squee-student.open.ac.uk>
63. Benjamin Donnachie <benjamin-squee-py-soft.co.uk>
64. Ben Donnachie <benjamin-squee-pythagoras.no-ip.org>
65. Ben Donnachie <benjamin.donnachie-squee-ntlworld.com>
66. Benjamin Donnachie <benjamin.donnachie-squee-ntlworld.com>
67. Matthias Klein <mco500-squee-arcor.de>
68. Matthias Klein <matthias.klein-squee-web.de>
69. Matthias Klein <matthias.klein-squee-live.de>
70. Matthias Klein <web-junkie-squee-t-online.de>
71. Matthias Klein <privat-squee-matthias-klein.eu>
72. Matthias Klein <kontakt-squee-matthias-klein.eu>
74. Matthias Klein <matthias-squee-piratenpartei-gelsenkirchen.de>
75. Thomas Weitzel <tweitzel-squee-synformation.com>
76. Tim Fiedler <tfcoding-squee-gmail.com>
77. Christopher Hart <hartct-squee-gmail.com>
78. Jeremy Low <jeremylow-squee-gmail.com>
79. Axel Rau (Computing -squee- Chaos Claudius) <Axel.Rau-squee-Chaos1.DE>
80. Carl Christoph Leimbrock <christoph.leimbrock-squee-gmx.de>
81. matkoya-squee-gmail.com <matkoya-squee-gmail.com>
82. Jürgen Neuwirth <juergen.neuwirth-squee-piratenpartei-bayern.de>
83. Charly Avital (Test2) <shavital-squee-mac.com>
84. Vincent Thenhart <email_vincent-squee-web.de>
85. Vincent Thenhart <vincent.thenhart-squee-piraten-rlp.de>
86. Charly Avital <shavital-squee-mac.com>
87. Charly Avital (GnuPG) <shavital-squee-mac.com>
88. Charly Avital <shavital-squee-netvision.net.il>
90. Christian Vögl <voegl.m-squee-t-online.de>
91. Robert L. Vaessen (MobileMe key generated with gpg) <rvaessen-squee-me.com>
92. Robert J. Hansen
93. Robert J. Hansen <rjh-squee-sixdemonbag.org>
94. Karsten Krüger (Privater Key von Karsten Krüger) <kk-squee-kkrueger.de>
95. Martin Weinelt <mweinelt-squee-gmail.com>
96. Martin Weinelt <martin-squee-linuxlounge.net>
98. Martin Weinelt (BP DART-Racing WS2010/11) <martin.weinelt-squee-dart-racing.de>
99. debian.sur5r.net Archive Automatic Signing Key (sur5r) <debian-squee-sur5r.net>
100. Leonardo Zillo Monte Xillo <leonardo-squee-zillo.it>
101. Piraten | Martin Letzel <piratenpartei-squee-letzel.org>
102. Stefan Körner <stefan-squee-skworld.de>
103. Apple Product Security <product-security-squee-apple.com>
104. Torsten Ennenbach <torsten.ennenbach-squee-set-sign.de>
105. Paul Karrer <p.karrer-squee-arrowecs.at>
106. Konstantin Pisarenko <kpisarenko-squee-gmail.com>
107. Andreas Heimann <Andreas.Heimann-squee-piratenpartei-hessen.de>
108. Henry Irish <henryirish-squee-me.com>
109. Lukas D. Jacobs <ich-squee-lukasjacobs.de>
110. Lukas D. Jacobs <pirat-squee-lukasjacobs.de>
111. Lukas David Jacobs <ich-squee-lukasjacobs.de>
112. Lukas David Jacobs <pirat-squee-lukasjacobs.de>
113. Kristian Biss (Mfr Voll Name) <Kristian.Biss-squee-piraten-mfr.de>
114. Trotzik (Bei Zeus die Dicken schon wieder) <trotzik-squee-piraten-mfr.de>
115. Stephen Domorod III (Stephen at Domorod dot Org) <stephen-squee-domorod.org>
116. Matthias Pannek <matthias-squee-pannek.de>
117. Jeffrey Rolland <jrolland-squee-softhome.net>
118. Christian Busch <chris-squee-debilux.org>
119. Christian Busch (Jabber) <chris-squee-im.debilux.org>
120. Charly Avital (1.0.7) <shavital-squee-mac.com>
121. Charly Avital (1.0.7) <shavital-squee-netbox.com>
122. Charly Avital (1.0.7) <shavital-squee-netvision.net.il>
123. Larry B. Macy, Ph.D. <macy-squee-upenn.edu>
124. ms-squee-shingondo.org <ms-squee-shingondo.org>
125. Andrew Orr <andrew-squee-andreworr.ca>
126. Jochen Schäfer <js.josch-squee-gmx.de>
127. Jochen Schäfer <jochen-squee-joschs-robotics.de>
128. Jochen Schäfer <jochen.schaefer-squee-joschs-robotics.de>
129. Luciano Buszmicz (Never forget: 2 + 2 = 5 for extremely large values of 2.) <lbuszmicz-squee-zimbra.itx.net>
130. Herbert Saurugg <herbert.saurugg-squee-bmlv.gv.at>
131. Herbert Saurugg (aufgrund der Umstellung auf BMLVS - 2009) <herbert.saurugg-squee-bmlvs.gv.at>
132. Karsten Krüger (für die vertraulichen Dinge des Lebens) <kk-squee-kkrueger.de>
133. Marco Hien <marco.hien-squee-math.uni-augsburg.de>
135. PGP Corporation Update Signing Key
136. PGP Corporation Update Signing Key <update-key-squee-pgp.com>
137. Sven Arnold <psykoman-squee-system-failures.org>
139. Kai Schmalenbach <davekay.de-squee-gmail.com>
140. Kai Schmalenbach <schmalenbach-squee-metaq.de>
141. Kai Schmalenbach <kaischmalenbach-squee-metaq.de>
142. Thomas Hofmann <toho89-squee-gmail.com>
143. Andreas Heimann <andi-heimann-squee-gmx.de>
144. Matthias_Schmidt <ms-squee-schmidt-system.de>
145. Paul Okkerse (Hoofd ICT) <paulokkerse-squee-huighaverlag.nl>
146. Simon Lange <pirat.simon-squee-me.com>
148. Carl Christoph Leimbrock <christoph.leimbrock-squee-gmx.de>
149. Carsten Lenz <carsten.lenz-squee-piraten-ulm.de>
151. Stephan Urbach <stephan.urbach-squee-german-bash.org>
152. Herr Urbach <stephan.urbach-squee-piratenpartei-hessen.de>
153. Tim Fiedler <tifi-squee-goapple.de>
154. Raphael Randschau <nicolai86-squee-me.com>
155. Raphael Nicolai Fabian Randschau (Uni Kiel) <rra-squee-informatik.uni-kiel.de>
156. Marcus Benjamin <markymac99-squee-mac.com>
157. Marcus Benjamin <markymac-squee-charter.net>
158. Christoph Giesel <christoph.giesel-squee-piraten-lsa.de>
159. Heiko <pirat-barnim-squee-piratenbrandenburg.de>
161. Shell Arkell <shell-squee-zenrio.net>
162. Ralf Oltmanns <ralf-squee-it-roxx.de>
163. Ralf Oltmanns <ralf-squee-oltmanns.name>
164. Ralf Oltmanns <osm-squee-abo.ist-total.net>
165. Ralf Oltmanns (Piratenpartei Deutschland Landesverband Bayern) <pirat-squee-oltmanns.name>

Are you on this list ? We probably have your private key.xix

And the best part ? I'm not even sure this was actually what the shitgnomes were trying to cover up. Stay tuned, the saga of Phuctor continues.

PS. I am really looking forward to more "oh, we did this last year and forgot to mention it to anyone" + "oh nothing really happened, it's just how the Internet works" + assorted nonsense. Go for it boys, the comedy goldmines await your labour!

———
1. I am aware most articles are written in a manner that makes them superficially appear approachable, easy and fun. This is absolutely never the case. I would know, because I write them. They are fun to write, yes, but they're not supposed to be fun to read. []
2. I don't mean him, or me, I mean us. This is what the entire point of the Republic is : a place for the only people who matter, that "just so happen" to be the people everyone's trying to murder. []
3. I seriously lost two nights' sleep over this, which is rare with me. []
4. Fuck me it found two more while I was doing the write-up. []
5. So far in this context means that Phuctor has processed 159`336 keys. []
6. Numeric value : 8170230239603769466339755071101546492494075988067987304148498844617761721719
21668594148071323527016137506405823108520062504849249423700259406905313281403901410082762
09715956022146304892433619238402677750217726273104520032220014977312750288854523497313948
08876445851926006310589628761141569342488951719592469695976371272800102721435938852409408
77456234662196130491400738438731832514335353824697930453078426722191105157568392826870043
65570800854541114336776383656601174049938345659212966258500488037677759771497802354243442
19142011195376854891735099423290906316620146500331426421109143608494218561796112264508065
62235534802516081595259914768497444702718749402330070488028751073730349460752771915484847
39938563152470848764607993657241039896758289598318764079807230936209472765416762862010598
14590215482904158000967692144374256909343720156287960274982199024412881893983863598466616
23243493534897411417685435424010451956954083531228374002591372549525280610594684910812811
28743648120708976312542424779304404330973726946870971067987226927285538994538538646776550
98806489297434982143295782888749871937684393533823052601084256880241476568069324740588889
92099083804597481699305852902662863062054067183925164590726103552998367994727700722491707. []
7. Numeric value : 3031874832053583743418292416372595502099634576341315290167303447940896540435
52345310511975303590935244481948247376401432307103818091777320274166257340264331696427788
43820440287608502427017776857269490773429050263926830246409710132226138115684031880138324
99315445911152479447953897832028961727910760577857345909513420880711566183055344315448208
15189782112077811874252865235796365042902051353241295725761213063753498336305286779774625
74313488820577959634372076837817948119361159907327939505395820850075258926732304880546382
18121459625570075016156281579252730109288078262517095342621532804321605585499878821551725
4263519. []
8. Numeric value : 8197390857930122495849886562470137189068756241045853345396708829779573185913
78792339415324255980163059743127714787086007659129438357469037360629245249705616603601365
63597964146991710522851815219493862072638245521162544016209541093774656536696344417650823
49152687118176002646235036007018218530990808110784085609984103493668490069882331296050726
59148709662519992770928241586882303261927623688308807480924828026178227826500232989258797
61721238970587973321189711176439396770655963604567146740276786029404138338726088474566611
34442803025681035341370085255365136140771869414017143486972849683925905356740246160827637
44494544558022802316339056649025168309463869160798052335969727740908414036010857683088184
61710283106767985721173378055475097926017173809924807346856948601492783226587906746941939
36060958883108067041074467521324201140558209298564151341183396803584754058788057295587730
56569821737406806683979766620026684983212939057835493907061843702537913655031320296990391
00326043248192047531754247006078437079036897801687200801156127058901013497147676702383977
92795134394789315147677565147168277841479001338032176084161559558010542509101918915636532
15342770779317932920084062741642010198566264962129579715127047847615770686855802050721189. []
9. Numeric values : 25526728199009057709398989586453690214904358229000555691738418155709599299
18160940994757774003022518929810044066740604565527975700160861486821065474174387293826935
59662145362339218055437009235577983172238607640347230823715572532055273632167902408545124
80788484485298963611047591040747211019092370621057704528363385920290537397040177458849430
94689834455986241625199628124838834820988620591040907862034577387030435001900586859440322
09067799996713635313458853612476941709302609689124628629849821403812266273651103048895862
07282737805245223854336961443695677803916743852838594109393768608251819065306021206057809
048295897

and

254471910020622974741613878533246957366345522968779071910619797751416162710425629338257850
156214306739276378255808049277464512466694513005396516900934317779045890004040559857294380
564181148461993661282908043780818992490345911046618480065856408662978878438851761341763509
237996998282198949871374657292359910532065350788049403374666549631113167000243930234183333
495764615993982749946613023097306372588785602877941865079249724490743458909135780965633992
284013600110504114134841012605185623803267848957450921144290192844350798393278473476083455
86307186831172171955343555350038959105541680962601456297155387993164183508343. []

10. Noting that 17742509903907 / 4294967297 = 4131 and the German meaning of the "grenzenlosnaiv" string, it is very likely this key exists as a training exercise for parties unknown. []
11. Numeric values : 16672257823521270371961164662125862296899812729169425291114489871863688113
67122963460006314830485743876540906881863271070920033024495963439286236322049961116516443
71368137287076681934969061181392776722975670973820744407487192112162201006712752084027830
44034022429423104279321017051078834408051586643315905452258822023212127325203856713926663
36628944779423111210830696700670806871753004469452802841901468552421016817404854350172137
16808018858975821015063666477169095086019680246350759221785200965931506062120690355105370
53261504301271697889391638721378329772344005716520375774724704751488265269774432055008867
229275469

and

63111812154962004116209412772135771764335180129874077503652320692902196823033111148598717
65660824814553154059429259638225867434239907928572987056097422649628064116861025113336284
55324434899298910704343021088751740670011136739823871025094632000111152696756229356518569
85187113817556050366609536875064937003150568571348567021875134271124971561538241658995689
60541365507282340768521118761247054438227698903952331114489434247743079966115954652649104
49172801887558399253096341610653488516924974363644661037775426721231658928989538345259343
6521547118378104303751147008586189340679520589366968743556304798004917247994251759. []

12. Numeric value : 117964043832425833134470740787358129784114456283752419342645582340953251431
48578558765309942999937387197801832249564462305216914764571810573887167594523290210967914
04116232100723166335618288851166923558093098286166267626628137674357217659637821178898284
73574169534012900636497385641932036608042904849263950188214230868921729578982513164932063
73809247325314970758076327923827247266864977692292330458186586541299744720414305573769450
51960323853627318325435606119355148304793407058340361907456768359973063438329538608005419
79618873721400795779080118813418706279180898215088255657615452323556652196146569473073868
54500851. []
13. Numeric values : 816708949049219316249137802707618040343445921615851995965391153505370824748
56664360460028004264449500871945629879290055404982628899216470128821039450960200583146680
25193170055583650261114433119755132491163921835276644123947260793576455390847834402514136
90337842919220026145606082508720088848598890301024115420804330103101427495459629407524084
86164663244022832839322787188693133760127271244278458996880240344473319141667934707790399
15724197918559633990059898867246909255081870669889825013484935133477808178535453323831842
85888596659532771788536275859666005400618251605639212775146326729520107278181394188352770
60404561906849840662206517465417579892599666355580498678265912741060282856126300266216736
41760609255985078714350143523275328759106456435018048097111064392220193473863109522647664
00746068888801637864717488325978701759621275112467360486617384536192578376764502915946183
03602045560932690965022239335637306389766704319639368279979122869714354659291820581287126
29017111447125931436198691729468886449421187304915037860804958873741941797115941531488261
41847991713726697025209185534864453107762256723146159022094394936231658019824935209907447
83682223742678848641605960916724945878393963569854451657597952828119471381594684211724764
9

and

30272436267370592935927683546275707596211768532578881152780386765089694968550014063197482
15344516176829167088048662433234621728486012336115797902534715097670596535588558118650239
40977746729669103033881025402172779766776404798270810069039821750829724934647537688187789
93321199200096396072303398683098042295937640783041329776470795092494232974452414868377494
27825027048634761257953599619572197410684747518265364985855562443343643637469776953626136
25258874763944618960610543058180905005340472180568558970964928040941234025709598582731597
08019121330896859060262587884427398800064088529634352117284565739258028711652930425763310
77755759669985137518098341461822232302796298950420639638764800291091063277609164433477144
12544002395970052464660259148611244676047879611421598195059898939161463733632925981205958
85465749574547687699075418613291138873247935061700600347838057013869166402764069292615374
55452250857429515497694863647517049263964583701591007894970220027677592993225342421978606
75045354932732689347255982379373625929001010227113820535039621871455162006022369107811987
01951664649941425468152833958581674008838786108111225907798874331557671311370668193417952
5009854277225103956061247800498802170252261111710555365880816565908566722983. []

14. Numeric values : 753231629734215095039311089646892853049081111032594923534482075739340266016
37856106751590154109358122728299712877052359482752462718740410337240588794321640142886550
83192423855568971677554301066731077513887982302526063007236613929745116067701523720058572
14389485783779647945312609390161093580811684684584176647736984258266730468745091231754131
48099900755304035582423436579058899950099238885085313418018438204661263296296360474488787
38521515663164432530506106986859103914132106418684515388843478387728183646911706555351959
06786355765882921864371694828638557543033284743572814292905853325384709890970441667372716
74898538521340513314748139188394298509067702297008631280871057113465745527818280556700158
98911867086343407362250584987574302248869107884810137359450826907280557890154398399182738
48414718226279276387749234122917487389606300709396077642992077195767444792730429592490507
75546729645078453563924998520884889112806996957379967728950970273926556751627876760711550
93951090640975808386604339388913045163078767335243053093864294911420910293699644772373021
19384077404629003519498936612630436228246571542992429033779830886921470891657566897297174
39305268085608161462770405711678050850558118662086210821247936654551597592806936359715168
1

and

65487389511097733523236551751948689607113248033298155484592472649627499169754702830189306
78657959370411670127073765502590061403333134124670776696990859471566989028610685353285009
11768678463614980094397492969316919268591710548465447455912048134236636858328385523978539
82644737917185370141846097472351962344267367164868242481388096236682753269414251051781765
77734834670332129839123263208668758028131671106139259946666183987551551308637440124384152
46073372167852444090374019093851181379333581474552729347021592666657810596563662560031169
77528444577348253993493248224572200189177833746239774046680672718868759550140707501008300
24701680838000748740220676484084364567218076578592133282849704429532204901392504168237650
60192612050400221008468212877403067238901306171444073779045299634744268048468177893966795
63124845569385276771589340294675431851543329006006237877269091491322114750102770420863824
20482572759627769565482018341248517157271233360867910286810334497049696741286179961722002
94848196451674665075230305125121320600350879318603047022659522723314077309342833773551202
20983530858434615625640442110354506401645560214301516012804040715184632521017733619272320
7126620137630199683458747749046869956250863673881944589932269914259206065385. []

15. Numeric value : 231036427461512813069782326469186742089206935382435884936326148373384936826
66618943828237707563563567191567768366287903851601276211660367075075558865360113399385553
26951298108747653706534259540439453383358205261358698396079714708891213475450942875181771
45065395282461022992054746039501967530610007348868024842672720695787835890412423405234084
89170547705084141480319545890060547864005718054327987768744667746409439647775858117289845
09762175906646388935569017267676917725214022951441318524453690097898220489452803365591384
61099779853243934970555470915573327297353910909059920488223388569170550698730292327738710
63937409. []
16. Numeric values : 222567807409507066819438199932606490824445396425529801468396492110367893
48111334813117913823222317749618626749516383215681163136110921477559313855276110774512129
21848202120790522045879897158791414388648392398613547596701894675516410215291943521699501
31876073234459906134472020552940692750890496620923040039616946450968406945043735527443740
33506505249622606928703088789450194922083461855048828400362408415058546054733143383156891
60640437522941861135600731717621660753862817281974831931680844013848452531041455855467138
54757101807552572291061512264192357868900098951176075281231602495066972399560156435790481
50192704621

and

25286784648294624481570535343637010718406459809243706575076548873485492686168555635562538
32810101202314404468498636254537974504634961804346873044291454191913610075499996591439556
24777770266168822439384588269333992453322600595230299600692066168101529002979316947217505
73804691916791907761678804392601995848707582969637308818339820753913619751024047553325552
94761379192874548094957794359119691525967129358370831291927000284693689250111471367088150
36079226146034065545213426189899633491105175774573868161830680296889413143854464294540776
58454923247735276780281924575559176175868196226600684019529354735523015770359339135. []

17. Not to mention he wouldn't feel the need to use eight heaps of vague in the shape of "at some point" "large number" "something was not right" "most of the keys" bla bla in a four line paragraph.

Seriously bitch, you did shit at some point last year ? What did you do, other than father a large number of Angelina Jolie's children, until you discovered that something was not right with most of her tits ?

Dumbass. []

18. Also, the claim that "keyservers will just accept any random data" is rank nonsense. If they did, I could just store fifty terrabytes worth of broken keys on their drives. But we'll leave this discussion for when the #b-a keyserver actually comes online. []
19. You will notice that most but not all the names in the first list are also in the second list. Of the ones that are on both lists, some have a surviving key (so far). Others, like for instance Sebastian Heberer, do not.

Of the names that are only on the first list, all seem to be sharing the "divisible by very low factors" and "fake key with pasted over signature block" characteristics of the original HPA key.

It would appear then that there are at least two different classes of diddled keys visible in the public keyset. (Three if you count obvious exercises like EF010E6F351E447C96C91AF1293987A8466F60E1 separately). []

Category: Breaking News

18 Responses

1. 1
grenzenlosnaive
Thursday, 21 May 2015

> grenzenlosnaiv

:D

2. 2
grenzenlosnaive
Thursday, 21 May 2015

Even if the 'obscure German mail client' thing was bullshit, it strikes how well represented Germany is in the list of lusers.

3. 3
Mircea Popescu
Thursday, 21 May 2015

This it does.

Care to share the story of the Grepunzel key ?

4. Out of curiosity, did you obtain complete factorizations of any of the RSA moduli above?
Computing \phi(n), and thus the secret exponent d is unfeasible without knowing the complete factorization of n and even in the case of an ill formed (e.g. random large number) n significantly large factors are most likely to be in.
In case you got complete factorizations, did you check whether the self-signature on the pubkey packet was correctly reproducible with your private key? Otherwise, this may just be the result of a corruption of key material (not good on the functional standpoint, but not a broken keypair).

5. 5
Mircea Popescu
Friday, 22 May 2015

The assumption that "large factors are likely to be in a random large n" is incorrect. The probabilty is computable and not very high. The rest of your questions are actually covered in the source material - reading which is both a required by your declared curiosity and unavoidable from a comprehension standpoint. There really is nothing one can do to understand something other than read.

6. 6
lobbes
Friday, 22 May 2015

Thank you for spelling this shit out for me. I know enough to know I understand roughly none of it, but also know enough to know that I should put in the time to educate myself.

The problem is usually having no way of knowing what source material is a) relevant and b) valid

7. 7
Mircea Popescu
Friday, 22 May 2015

So it is. The meagre counterpart to that problem being that as one attempts to educate himself, the differences between relevant and irrelevant, valid and invalid become more and more apparent, and readily observable. So it's not all midnight black.

8. Concerning the b-smoothness of large n: can you provide a quantitative estimate of the largest factors as a function of the size of n instead of "not very high"?

Having read the source material again, I could not find any evidence of validation of the correct retrieval of the secret keys.
The only claim explicitly made is that some of them are divisible by a known factor, but nothing is said on the primality of the remaining cofactor.
If the remaining cofactor is not prime, n has not been factored, and thus the secret exponent cannot be computed.

For instance, take the modulus of:
EF010E6F351E447C96C91AF1293987A8466F60E1 Debarshi Ray
In the provided material you note that it's divisible by nine, but the result of the division is not prime.
In particular, the cofactor is divisible by 110923,199974947 (obtained via a run of Pollard's p-1) and the
remaining cofactor from these divisions is still not prime (Miller-Rabin primality test, which yields
no false positives for compositeness).
Similarly, the modulus of Peter Anvin's key is also divisible by 19 and 7704959, in addition to 3, 7 and 11 as
you pointed out, and the cofactor is still composite in this case too.
Thus, given the provided material, there is no evidence in the provided material that you know the complete
factorization of the modulus of the key.

I would regard as non deniable evidence something as text file signed by the private key corresponding to one of the keypairs
claimed to be broken containing, e.g., this post.

9. Alex,

Take a look at precisely how this class of mutilated keys (which include your example) was created. Specifically,

1) 64-bit window over the legit modulus is taken, where upper 32 are set to equal the lower. Then move 64 upwards, repeat.

2) The public exponent is changed to 281479271743489.

I have not yet taken the time to work out the number-theoretic implications of (1). However, my current conjecture is that it has essentially the same effect as choosing an entirely random integer for the modulus.

As for (2), the enemy (it is abundantly clear that we are looking at the work of human hands) may very well be relying on possession of known signatures to make use of (2).

In short, we do not yet know for how many of the samples the private key may be obtained with reasonable effort, publicly-known methods, and while lacking any samples of material signed with these keys.

Plenty of work to be done here!

10. 10
Mircea Popescu
Friday, 22 May 2015

@Alex It is difficult to estimate how much you know about the topic on the basis of what you've said so far, but perhaps https://primes.utm.edu/howmany.html might be interesting ?

In particular, the cofactor is divisible by 110923,199974947

The full factorization of the found keys was deliberately left as an exercise to the reader, for now. See here.

What you would regard or wouldn't regard as whatever is a matter about as interesting as what any other "Alex" thinks about the weather and the Queen of England. Ye ken ?

11. 11
Obama's Red Stapler
Friday, 22 May 2015

> Miller-Rabin primality test, which yields
> no false positives for compositeness

This is incorrect. The original Miller algorithm was deterministic, but it relied on an unproven assertion about the zeros of a certain L-function. The Rabin upgrade removed that problem and also made it probabilistic, which means that both the quality of your RNG and the count of runs are important in estimating the likeliness of corectness of your result. This becomes especially relevant with large numbers, as Apocalyptic correctly points out here.

12. 12
Mircea Popescu
Friday, 22 May 2015

What he literally says is that M-R yields no false composites, which IS correct : if you get a factor of n, you've most definitely got a factor of n (also trivial to check).

Meanwhile he is apparently turning around and using that as if it meant that M-R yielding no factor means n is prime, which indeed is incorrect.

13. 13
Peru Ana
Friday, 22 May 2015

Not my field, but I have been trying to follow the discussions. I read the tree Trilema articles on the topic and most of the #bitcoin-assets discussions. There is one thing I don't understand: if the large number N is the product of two primes, p and q, and someone obtains two other numbers, p' and q' which while prime or not nevertheless multiply to the same N, are not they now able to do anything the owner (who has p and q) can do, whatever that may be?

Example:
.p = 7 and q = 12, mistakenly believed by owner to be prime. So N = 84.
.Phuctor finds that 84 is divisible by 3.
.p'=28 and q' = 3 can now be constructed, so that N' = N = 84.
Why does it matter whether p' is a prime or is not a prime? Apparently somehow RSA worked with q not being prime, so why wouldn't it work with p' not being prime?

Thanks!

14. 14
Mircea Popescu
Friday, 22 April 2016

If N is the product of two prime numbers, there exist no other numbers that multiplied yield the same N.

15. CTRL-Fing phuctor stats pages for my name is the only news I need "on the inside".

Hope everybody is happy with the MPExplosion! Fireworks are the best, forget the rest, I'm a pyromaniac under test//////////

1. [...] discussed prior (principally having to do with how the part of the world made up by you sucks irredeemably, by the way) Phuctor now very conveniently links broken keys straight off its stats page. Let's [...]

2. [...] of course, is not without its own pitfalls. [↩]Such as perhaps an overflow of some kind, as the most obvious, banal example. [↩] [...]

3. [...] might remember Hanno Böck getting caught lying back in 2015 : Hanno Böck just got caught lying. Specifically : Last year I started a project to [...]

»
If this is your first comment, it will wait to be approved. This usually takes a few hours. Subsequent comments are not delayed.