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 Example: my current GPG key.

Phuctor Example: my current GPG key.

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.

This entry was written by Stanislav , posted on Saturday October 19 2013 , filed under Cold Air, Computation, Cryptography, Distractions, Idea, NonLoper . Bookmark the permalink . Post a comment below or leave a trackback: Trackback URL.

26 Responses to “Phuctor: Fun with Public-key Cryptography.”

  • Roger says:

    It would be nice if the site told you what command to run to get the key in the needed format.

  • daniela says:

    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

  • daniela says:

    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=0×7B1B681C78F66053

    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

    • Stanislav says:

      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.

    • Stanislav says:

      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+jW926×4dEF+P2QfsbJfVxIat3DAtLKn+4+nfH
    xHBoby3ttUAyn+rrZsC7VpTJdOKQaDSyX0gCqDihmIGMQ6brchjZcqyhVlScOLmj
    Yn6WPU+MkhQ/ok3fBN5/wF82szX0AJdzE4biPlwiWNJvAY4OczNn34L7g/VdXfzG
    HYTkdKXJEvUJLL4JTY2GfssRszW/dlZiXMN8Nh2dYfDc28BPuRCtD18nD0Gf3dms
    tq0ng87zW1Z06tdkbLiJAsE7wK3hGg10vVnyYzVHYEul8VSWriExOd/XAv1WImyd
    =tz6R
    —–END PGP MESSAGE—–

  • Stanislav,

    I’ll try – this time from another machine. Here goes:

    -----BEGIN PGP MESSAGE-----
    Version: GnuPG v2.0.21 (MingW32)
    
    hQEMA4iazE/I7/8TAQf8D7mlHlAnzjy4zO6pJ1EEA2YeUM6yJndC3ArRMrfvqxJz
    kNh+8OrMZR1ZFlWKucKdVtmI6rr2vu/Gd80ZFibvPybOAZDzJQajObZ7xtJ/mxI6
    vWtnXYsYm4c4/fXNnZ7ooUfQdDqbJC76exG7xwWd85d+gE39SiIzqqA+QAqSkz1r
    cb+4pJFQ2jIgX+fXkT+MeJeN01NjhndptjNl8OiVlmMVH+Yd6H1u+9/u4MZqichx
    S69xNNSYknvXavLIQWad7S7uqTXC2+kYhOg3xr96KrO3Q/g4seuQJwdPGcsB7O00
    mdW4TzC98h0+rymHUpV/HtR5zhOf8iV0l1hdkV93Y9LpAeWOp7gM90zilhxO7sDT
    yZRQbRybu+enwK7UNEAh5CDDrUkFGuT2nDWec1bkh/K4bmQO+hBfeN/Gf+6tQPg1
    z7t8Yhj+4OQhD2FWxxfUSUTV1Jvg/xHHDkQMQNOIY0onrQ0557GH9zxJGUJQntCy
    1grNWv2uUOsezk8uLtrOwxoCMCvf3piMsmQTKjQDwrGSkhwgUOqhgBNgYD50LJQU
    icfYhf/SFl7Th/ZLsf/zHSM4PrmD+g5g1UycnRJcHGNURC5FCdwxTRQythoJJMm7
    Kf4lExJ2G6Tl5dPTNMbjgPT4pUQZRH+WPsO95ng7NxeevotcJQo/TKgQAcdnKHwm
    br2lXKIz3eM2vBdOc0WiEq066B+0blye92EyWUWMalO2fNPp0Qmxy+oC3mGb0gqO
    HGbGW+GUU55pJLsWbTUfEP6ceHlJhtt6zX/a9OpfBT+LeG1I8nKeJK+IR6K+lft3
    2+D/V6TMIZ+1ROwmpxDlAK6MeBe3UFlof7YaENF+XHin7vtlseg77sIXecCGC33r
    a1iaSpHkbdaorJZbE31LLykjx/N/1C1aUbQbncst1Dtqdr+dWlGfHTZn8krku7RC
    c1ntDK6rJHzvA2TxoCZHSDbbH8ajqMFhmzdA9dzPHu9oqdPlGqvA+rP9UqizKr1F
    0QebUmQ6Yb4j3qOKTUmKXxvAS1Kh32fIeDI90oCsvdhhnr71V0lgtEd7fzM+8+Rc
    7mkQaC9r8o7J9dqYmGj2D9VT/wfXdlem0795W+ncPoCehUyI94SWLrVKkSn/Vh5o
    zOKmDDyHiZIQAXwbtgpgT1ky7SFSkoIS6DFuxaoFQUNt8rc3MTKKNlIsou6GMMo5
    2TDTLkDpWj85bl+59gfKwzhBobXphY+xpWLs4DPoNIAtccODj4T3e3Jxjtdpv26G
    RgAr5BN9I8sNdHiOWDLKzVAcmt5iXyFRQu7a5gxhzfGAkKDhNHGkWybhHmFX0BpT
    fBWq4w/AB980Y1sCeMDld1MW5F1NHievlCOiwvRNb7W8PP08h90s1ckYJ/ITqw==
    =bFw9
    -----END PGP MESSAGE-----
    
  • Can’t I do anything right tonight? URL was indeed wrong. Sorry. Here goes. Should be exactly what you need….

    -----BEGIN PGP MESSAGE-----
    Version: GnuPG v2.0.21 (MingW32)
    
    hQEMA4iazE/I7/8TAQgAylWvRornf+osd+cg3pMHAUn9FfBdJUMcFNUxsVho4oNK
    Ybo0/ONimNho++FWKeKkBN40Aea6viyhk/us760oTK0Y8IVrKTaWfwHXVaXTxdE9
    HrdUIrKm+Zxg1wXGQ5ZFrv4xjZWxwpFw/8UkBNWkt90SUWx7y56xL9ZJoLEoDjjh
    fni/yt6VcTT6zkRW3z8tVlm+Sgoat18jEXODj+AS60/toUi9mroLRlV6be1h8guK
    m0fjpZ12re8ahqDgZqJmd5zxc33j7Sz18u+xnSGFUNNQwECyUgeKLzpZpxgkzHvU
    O+mQ8PoDM+h/RaNEQFHoPdij87LXb0yDM2cqpj+X+tLpAa4zA/Rt1bCvl2Mwwl7f
    nZo8QLGV3u20AWvWCnZ+g8PVXt/ashGZxNg7W6AjOjLWOqyrxb41idf+ibq6jNY8
    p2Qo4uR68eAay2zp8V/0/gECoRCxaxAf91Ac/ti7zoB7vExf/ZcXQPgUY8aah6zd
    xajExjU4KV5u/bkEuYoxpkysJGS/T55ny0w6jThsvIRfywjK6rPjUSC2vffLNVkR
    IKvxVPYh7zftjv3l64osHpXkRKVxYzzGPIoV5hqoJXIYQRn2eKMNnWF1BhHPhf4y
    13qNZH0MQmVGwAk6mzZBQj2CWxu1NUoKpt64Jq7i9tFoc1WbWAs2obvp93qOR39v
    vQrCDysDfRFLenW5h+O388CgNw5Nu2x0QGnxPn1B7LpEyIFN5QS4aSa982i5IxtE
    H08Vh/J6wFrt3HKwwq7TtWrMt350DuwTNrTnoBcUsnysUqDajHp7SY0rH8emJdBE
    V4GSvwub1mjaXNrJ87NNfIGI9Y8NJONnhKKVwDrGg7zyexqS/eZvDyLkL6hhiAK6
    maUh2HcN96z8gUBHGwOrG1JNzcnNUfQGZsYEHFY/84qBIfFRd8e0Ne+zHtY30139
    W8trwq+hFpNn7YcSShnBnz6SslK3XJ8SPrTnyRUR2fP00cxTmKAH1hFqcWBpeV2S
    SjRDEsF6Q4dS+SMoIuPGnXrAJkiNaTe7h9v/L7Zh9Vw9bAwE34Egs0/k2ESrGsPg
    RaWxtGV8h1f8v4kTj0nrnnbRXwQjBqDegk7k2Enc7Oe12spyIMyq2XN200DZJaFb
    NAFgMiuDsNTCZM/s/S/XCBfNLjLzsPxGZllTlucxZKMfUc9dK7TSCOuFxOabj+ew
    vUE4CHkcP5YFHeizVkXeS3Ia6NPxtWM2QsBptgGy/b8Gt76xt+1LxWCBpPBUYfp0
    u1smBEFmMlSbgbzCXmaAveBbZyDAGapWY+istYP64izmak8L030kuxC5JG5Alsxz
    mdZA+a4QHkPu
    =m0Ah
    -----END PGP MESSAGE-----
    
  • 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.

  • daniela says:

    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

    • Stanislav says:

      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

  • Sekenre says:

    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,

    • Stanislav says:

      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.

Leave a Reply

XHTML: You can use these tags: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong> <pre lang="" line="" escaped="" highlight="">