Phuctor: Fun with Public-key Cryptography.
All of my readers are invited to test the security of their GPG public keys using a new and very simple online tool: "Phuctor" (part of a long-term collaborative project with Mircea Popescu.)
Phuctor is based on cutting-edge Ancient Greek technology.
Engine now re-written, using GMP. Roughly 100-fold speed boost! The service is now essentially "real-time."
Edit: Feel free to post bug reports as comments under this post. But keep in mind that reports without an accompanying pubkey (the one which triggered said bug) aren't particularly helpful.
It would be nice if the site told you what command to run to get the key in the needed format.
Dear Roger,
Use the same format your public key is in when you give it to people. That is, "ASCII armored." See the manual.
Yours,
-Stanislav
Did something change in the required format?
I sent my key a couple of days ago, was just tested - OK, for now - and I tried to submit other ones but it tells me
Error: Was that really a GPG public key? Try again.
Thank you a lot
Dear Daniela,
Please post the key here. (It's a public key, after all.)
Also make sure it is in a standard "ASCII-armored" form, with no extra line breaks or garbage mixed in. If a stock GPG client won't swallow it, neither will Phuctor.
Yours,
-Stanislav
http://sprunge.us/KVhF won't work
Dear J,
This one appears to have non-UTF-8 junk in the username field. Genuine bug! Thank you.
Yours,
-Stanislav
Sorry for taking so long to respond, forgot to look back.
non-UTF8? I'm 90% certain that there isn't, but feel free to prove me wrong.
Dear Stanislav,
first of all let me take the opportunity and thank you for the website which I have been reading for a long while.
With regards to the GPG supercollider, I have tried a number of submissions, also including some random people found on pgp.mit.edu and they all went through (occasionally I got the "does not contain RSA modules", fair enough).
But this one keeps giving me the error. I wonder if Roger has the same problem? Maybe it is not the format he has wrong. Maybe we have a conceptual error, I for one am ignorant in criptography and trying to learn a little bit. I apologize if it is very stupid question.... i think not asking and remaining ignorant would be stupider.
I paste the key below, it has been double checked at http://pgp.mit.edu:11371/pks/lookup?op=get&search=0x7B1B681C78F66053
mQGiBD+NgCARBAC2U5mDH6d9X3hnF4GuWDIJin2ANSAwP+fICLdOjBuLQWW3riBHUzCIi3aP
F909jx5sxtEMknwAaJ1V//F+l/r5KknsSKcFkxaWkmnIF7AVv1UnDUFCshSC7Swzdgkk0IIY
aVic0qFpRRzF0fyYejcKZQscf+MEyLhx07YaavZeJwCg4TZFkhco3E5qV9rTSs6AThblJc0E
AKEMjYmGEVFWCDiGsnv+7QB6io8tcBAEi0RQgcEk/YJTiX5ZYEDj5mlIAd+pUJofYVbbbaar
3qHz0pp7KuiVrmgDhoJcul1aAFYaYvw5nhJ5lEFwdjv49FkgRw48yKaZ1w41safskbrz69SY
sO+7mR/MtsOckticGUFVc76+Fz5yA/9lvse9eila+VCC+YkCzYeTXPB7ZuDdfsohOWTEI8nT
Iv8MZsf3WRYEGCfC8HOOQZLEYEJd7OFFuFLNL0hlD/BQNOx/392gKFgzYRxLpm9OqE/8qzN5
1N605z2+OxQqt4qnat9N2VnwobzQH6Zyq3F5jJFWYrmiPRlRbqJo5crHMLQhSmVhbi1NaWNo
ZWwgUG91csOpIDxqbUBwb3VyZS5jb20+iFsEExECABsFAj+NgCAGCwkIBwMCAxUCAwMWAgEC
HgECF4AACgkQextoHHj2YFNwqgCg0C/B+uA+dZ4glon1GlZ6Fv0zh8wAoNU1zjlX0AgxsHwm
5NvArpcwCYLquQENBD+NgCEQBADEPkLsNSqaVcXfHN5msRR/wOeENXnq7Wx8ui1UOsHJMiE9
Qwx5uu8C83BnfP6ArfTZ0E4a/8XZOG60XcCU6pfkIU8FXbVtKWVsPTIW8T9MZAZFKwhvqKMZ
UowYszFW2qB0cYPLyq7bMRdEBkIuo9pdnCakykMhossvQc1fgTcR5wADBwQAgqKfLkQ3Fcvr
2kZZcHJP/dvDbcGd37Z19KtSQyIpYQzxXtLUhH7ljkoyzkRxUuHR8X21Ezk5GASG46Ks+NfK
qxawEs5Db8qeb1aYoOP6/ABxo0ZGZSTYd11cAvYmkpuNpViWDbhnBryejIrPzVgfiJGANZWJ
M0PiTHitFm3g/B+IRgQYEQIABgUCP42AIQAKCRB7G2gcePZgUz2EAKCPLusKlTNViUHyK9W5
Dq4l0cWDkACfUAPpeUR3WZZCME0pS+Rs7v6Uc0g=
=XrEg
Dear daniela,
Looks like this key is an ElGamal key. The vulnerability in question does not apply to these (although other, more interesting ones, which will be added to the widget eventually, do.)
The routine that checks for keys having no RSA moduli should have picked this fact up, rather than spewing a generic "this key is garbage". I'll check on it.
Yours,
-Stanislav
Hi Stanislav. Have you considered contacting one of the MIT keyservers and requesting a dump? If you can prove it is for research purposes and you are not a spammer then I imagine they will assist you. It would certainly give you a large sample size to assess.
Dear Mike the goat,
Public keys being, well, public - we'll get them one way or another. Various people are helpfully working on making it happen.
Yours,
-Stanislav
I know they are public but out of courtesy to the site owners who may not want the whole world grabbing dumps see below... I may have a source for the entire MIT dump too if you give me some time.
-----BEGIN PGP MESSAGE-----
Version: GoatPGP
hQEMA4iazE/I7/8TAQf/VdvmqZTnPBp5DS2RSTmykB1CFZtIncmB6SBeI+/Xmiz7
KyUYsDrNN1nMBtebAkuBDIfp3NU6xLl8q64YBkpsY3QsTWxoLSSl51Z+VL31iYSd
nMXmuMCLasS6y1KuLBPh0dhNojYJvdAWwV09+pQ8PSZBfKL6aw4T5TVTiPvrkrma
KgwKUkvI5RlvPhfKI2Ts3f4ss9N+Kz7Mab2WHEnwC9d73lXSQgVpzOPDS9RjHwC7
yjjN+7i/tlSqkNnqtS7yt0hFC7+4g8JXJ6lQd3P/ok5dVYYqXmO5ZLwjnhR1EWt3
MGQowu6gx5K/NcwlF75nvV1XcqcozsvG9BigZBq+JdKvAQ0sfPpXAXJ62305jfXv
SRm8z6kaYFRDuv0kiP901OuB3fBIjUeseAR62DihssYtpaoLd0PDQq0Ot9EHz2os
fCzEj/gNsLr2R+7PQWrOoZmmw/NFheRGH9MJNAiQKS7bYB+lFGEyn2sGyCnEaoRp
J+pHvM19YSxW0jbG0wnngsC9HJDklxro0oL8QYSH1WHO03PTIsn+9qCctu7hp34n
GHVPAg05XIxhcgaL6wXElw==
=7Jda
-----END PGP MESSAGE-----
Oops, hit encrypt prematurely before adding another dump location that has 4+GB of keys.
-----BEGIN PGP MESSAGE-----
Version: GoatPGP
hQEMA4iazE/I7/8TAQf8CDhUy2c2woQcBQ560eyrqWmtKfIGA6p98e3JebgHUkhH
f0oRiebvLwErEDI+wZZPg/SKRKTAcEbWaZMCpVsLaqzXoRX0IxsXGmW5SjbbyopW
eUJEwsAT+CYD/kNKCPyPOcMGMl2d1GPiaVNArL5BSXvZbDUjG+WETlv0mqwEGfmo
DhCtWqNXk2W6tzrk7dqClSIU4d+jW926x4dEF+P2QfsbJfVxIat3DAtLKn+4+nfH
xHBoby3ttUAyn+rrZsC7VpTJdOKQaDSyX0gCqDihmIGMQ6brchjZcqyhVlScOLmj
Yn6WPU+MkhQ/ok3fBN5/wF82szX0AJdzE4biPlwiWNJvAY4OczNn34L7g/VdXfzG
HYTkdKXJEvUJLL4JTY2GfssRszW/dlZiXMN8Nh2dYfDc28BPuRCtD18nD0Gf3dms
tq0ng87zW1Z06tdkbLiJAsE7wK3hGg10vVnyYzVHYEul8VSWriExOd/XAv1WImyd
=tz6R
-----END PGP MESSAGE-----
Dear Mike the goat,
Please check the first link. All I get is a few kb of checksum.
Yours,
-Stanislav
And this message appears to be corrupt...
Stanislav,
I'll try - this time from another machine. Here goes:
Getting a 404 on this one.
Can't I do anything right tonight? URL was indeed wrong. Sorry. Here goes. Should be exactly what you need....
This one works. Thanks!
No problems. My apologies for spamming your blog with crap. Feel free to remove those old posts! I would have sent it in the clear but didn't want to step on anyone's toes nor aggravate the key server ops into restricting access or putting a .htpasswd on the area.
I am severely jet lagged and have moved well past the tired stage and into the strangely stimulated zone where your concentration is shot and a decent sleep appears to be out of the question. Let me know how your project goes!
Hey Stanislav. I mentioned your phuctor project on my blog the other day, even managed to troll a response out of Mr. Popescu :-).
A few quick questions. I realize some of this may be commercial in confidence so feel free to neglect to respond to anything which might be an issue or respond privately (my key is on the link above).
I hope you managed to get that keydump. How are you planning on importing this information? Just a script that pumps it into your software one by one until the job is done. I suggest that once you have imported that dump you keep your site updated. You can do this in one of two ways the first is to run your own SKS type key server and let it use the "gossip" protocol to keep it up to date but this is a lot of hassle for no real payoff. The second way is much easier.
Depending on what keyserver software the URL I gave you is running the behavior may be different but I will outline what should work. The SKS software dumps keys into an archive at a rate of 15000 per archive. The complete dump you downloaded was up to sequence number 0228. The individual dump archives begins to get uploaded on at 1000 UTC every Sunday. The individual dump files are finished by 1200. The 4+GB tarball of everything is ready at 1500Z (times rounded to be conservative). My suggestion is once you have put the big tarball into your collection you run a script from cron at any time after 1200Z on Sunday to do your import routine.
You are currently up to sequence 0228. Unless the way the software operates has changed since I last played with it you will need to refetch this archive and any other files with a sequence number greater than that. Your script needs only simple logic. Keep the current sequence in a file. If there exists seq+1 then download both seq and seq+1, then increment your counter on successful processing. You need to process the last one as it will be filled up to 15000 before making a new file, so it won't be the same as last week's file of the same number. If seq doesn't exist or seq has jumped more than seq+1 then error out (keydumps should never go backwards nor should there be more than a file added in a week, typically only a few keys change every week). You will want to keep track of the keyID's to avoid reprocessing keys you already looked at the week before.
My knowledge is somewhat dated with regards to keydumps but it used to be that new data was always appended to the end, that is to say that the older files that are already at 15000 are never retrospectively modified. This makes sense but if the behavior has changed since I last played about five years back you will probably want to use rsync to avoid moving files that haven't changed and keep track of keyids so you don't waste processing time on rechecking keys that are already in your database. The site I gave you has anonymous rsync available.
The format of the keydump chunk files are sks-dump-SSSS.pgp.bz2 and are in the same directory as the big dump. SSSS is the four digit sequence number. Where number is less than four digits it is zero padded so we are at 0228 right now. 0228 will continue to grow until it hits 0228 and then 0229 will be generated.
Hope this info helps. I did a research project a while back with PGP keys, determining likely fraud (or lost keys) by tracking people with numerous keys signed by differing parties but with the same name and email address. Using the sequence files is nicer on the keyserver than pulling down a massive tarball every week.
So now for the questions!
1. It would seem very useful (for research purposes) to keep a log of weak keys and the modulo shared. I realize there are privacy implications linked to them and you likely don't want to leave it lying around on a web server where a 0day might result in the weak key list being leaked. Nonetheless it is great research and you may actually be able to sell the data (for a nominal fee) to a IT sec research group if they want to do an analysis. Perhaps you can generate a keypair and keep it offline somewhere and then have your processing script for phuctor when it encounters a weak key to log the keyIDs and data then encrypt it to the well secured key and add it to your weak key log.
2. How long is it taking phuctor to process the average (1024R) key, rip it apart, determine the modulo and query the database to determine if others share the keys.
3. You mention that if bad keys are found the user is notified and the key is deleted. Does this mean that both (or more) parties are notified and all keys removed?
Very interested in what you guys are doing,
Mike.
Dear Stanislav,
perhaps you can update us on this blog when the 4GB tarball has been fed and digested by the algorythm?
I also would like to ask why you do not ask the machine (processor, OS) where the keys were generated.
Best regards
Daniela
Dear daniela,
The donated keys will be fed in piecemeal, at least until we get a hardware upgrade. At present I've been rather busy with other matters.
The interface is strictly minimal, asking only for a key, to make automated submission easier. Besides, the expectation is that most of the keys one submits belong to other people.
Yours,
-Stanislav
Have you considered collecting the public keys used by CryptoLocker?
They may be generated on a cloud based VM with no good source of entropy,
Dear Sekenre,
Right now we have a plentiful supply of keys to throw in the hopper, but a not-so-plentiful one of CPU cycles. This will change.
Yours,
-Stanislav
Perhaps you could do this in a distributed manner. If the key checking becomes a commercial venture (where people submit keys to be checked for a small fee) you could even pay people fractions of satoshis per key processed. No doubt people have PCs sitting around with idle cycles that could be used for this process. Obviously you would need a way to synchronize the list of products between machines but this shouldn't be too much of a headache - well it will grow quickly I suppose.
I may have access to something a bit more suitable to your project, 1.5 petaflops. I know that some students at our local university used to do weather modelling on it and it was made available essentially for free. I might be able to inquire about pricing - as far as I know it is practically idle and is only occasionally used for education.
I'm getting the same error as Daniela, (Error: Was that really a GPG public key? Try again.), not sure why. The public key I'm pasting is this one http://pgp.mit.edu/pks/lookup?op=get&search=0xCE5BEE6C81FCA4D4
[...] processed more than 6500 public keys and found 60 with one or more duplicate moduli. The Phuctor, as announced on Stanislav "asciilifeform" Datskovskiy's blog Loper OS utilizes Euclid's [...]
[...] claim was based on use of a service the Loper-OS and Mircea Popescu operate called Phunctor, which they describe as an “RSA [...]
[...] claim was based on use of a service the Loper-OS and Mircea Popescu operate called Phunctor, which they describe as an “RSA [...]
[...] 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 [...]