Date: Mon, 26 Jun 1995 13:46:27 +0100 From: Paul LeylandWe announce the first known hostile attack on a PGP public key.
In 1993, Tim May created BlackNet as a proof-of-concept implementation of an information trading business with cryptographically protected anonymity of the traders. He created a 1024-bit key, and invited potential traders to encrypt their sales pitch and a public key for a reply with the BlackNet key, posting the result in one or more Usenet newsgroups. BlackNet would then reply in the same manner. The original proposal went only to a few people and May acknowledged his authorship shortly afterwards, when his pedagogical point had been made. It was soon posted to the Cypherpunks list, and from there to Usenet. Six months afterwards in February 1994, a 384-bit key was created in the BlackNet name, and the BlackNet message was spammed to hundreds of newsgroups by the new key owner, L. Detweiler.
At least one message was posted encrypted in the 384-bit key. The encryptor, either by design or by unwitting use of PGP's encrypttoself option, also encrypted the message to his own key, exposing his identity to anyone who cared to look him up on the key servers and use finger.
Factoring 384-bit integers is not too difficult these days. We wanted to see whether it could be done surreptitiously. Jim Gillogly picked the 384-bit BlackNet key as a suitable target, partly because of its apparent interest and partly because he had saved a copy of the reply. Paul Leyland took the key to pieces. The public exponent was found to be 17 and the public modulus:
To factor this 116-digit integer, we used the same technology as the RSA-129 project which completed last year. That computation was so large that it was necessary for it to be done in a blaze of publicity in order to attract enough resources. Ours, we estimated, would take about 400 mips-years, less than a tenth of the earlier one. Arjen Lenstra and Paul Leyland have been factoring integers for years, Lenstra with a MasPar at Bellcore and Leyland with a dozen or so workstations at Oxford University. Alec Muffett has been contributing to factorizations for almost a year, using forty or so machines outside working hours at Sun Microsystems UK. Jim Gillogly threw a couple of machines into the pot, for a total peak power of around 1300 mips, plus the MasPar. The computation began on March 21st on the workstations and continued until June 23rd. Lenstra slipped in three weeks runtime on the MasPar between other factorizations; he also performed the matrix elimination and emailed the factors (PGP-encrypted) to Leyland. About 50% of the computation was done by the MasPar.
The factors, as can easily be checked, are: 5339087830436043471661182603767776462059952694953696338283 and 5981374163444491764200506406323036446616491946408786956289
Over in Oxford, a doctored PGP was created. It could generate only one secret key, that from two primes hard-coded into it. The key was generated and tested on the following message:
> -----BEGIN PGP MESSAGE----- > Version: 2.6 > > hDwDqeLyyFpa0WsBAYCumTBz0ZUBL7wC8pMXS4mBS0m3Cf6PrPer+2A0EQXJZM46 > OvPnqNWz5QK3Lwyg9DeEqAPF5jH/anmgXQEE3RNhybQUcqnOSVGMO2f5hjltI73L > 8CRXhFzMCgjdCwTRf0Oq61j4RAptUviqhDq/r7J2FpY7GwpL5DxuJ+YrWNep69LK > Q/CkKxtwvv2f0taly4HCLCcqw59GQ5m++WnOwDQWKG7yUaXJuUG/mJdr/o+ia3y+ > QKyqOesHdSjWoXDpK7F2Cvxf2KpV3+vzbv+TriRyDV+zR/8womdJl6YAAAKtmWO2 > fy0sp/cqr/1ZGQKmfZWz5L0bh1e/sJXJq9PjvPc05ePxZ35XEoRTCqxbq2GPynkH > YSynfXZY//814TKmdQxPBvkc8Nbi0rc/GYyoAmItDui4mQISYskGkmLieoWDDlpP > E9tZlb/7Xa22QS53Or6DwU/y226WXQvrWq5OJ+8OhQyEnLWsEdfgFoe1l9aeweX5 > 0ao5lcp098Q4JFfQWoaU9D7kmKvg+AVT44Pv16/nPvihAoC2O14xg7t1U8032ybs > 4FLpvxyqoF7+oDV/QNw4Evk1ZnxE5+PH2sOf1qCJdljVSd3wGSfUQaDPRx5RH0XC > SAgYMsIRaytpdoq521tHUZt2BIg7Ii89TfUBrnkenBFAqdZAf+JR1PSB4yaV3YtG > PCS4lNQkmWx+ItjP0zsHVcAR0TiBcpV0gMY+tx0h40CTkDi2vHiVyswSJr4halsW > SIixrdi6B0i3f7v7xlOpFI2khza1c/dH8nrF1uPLECeAZ8TQq53ZlyN472KYuTVZ > 8y5NqyXd672dYEtzsOlUa9YwFKKyGisyDhZmE5wSOg2Pjopvl0WkuZSR/kdxrX/N > hFdfXRy1Kgkr+vz9abumhcWS5lYCCfVLk/CIgRqHO09nlEJCTb1T/U788Gptr3/d > 3dj8C/LECdY7fIdkmTgYhXmfv7fQxLWln29Yux0cEpRq2ud8rjYVSuEaTUO9dF4n > 9oFRsPdbb0TOxaMVFm2hnELzeKAk/poInfEZkN2ZnusxJ4aM1HkBRva+CAMhQHdT > XMisoNawWEDPwiwu91owIrBevPJNvX155jUTwKNj0UPBwS6TfS5gXl9g+LoBnMWQ > nbMMMYVXbJVsAeVOlzTSBftpbglx1k7ocDaAJTZ3OCjf0FcKJsa+4Hybc713611c > WSHV5esfY9k/yw== > =nLfz > -----END PGP MESSAGE-----A successful decryption resulted in:
> Although I realize blacknet was a hoax of some sort, I'm curious as > to the reasons behind it and I would like to know the motives of the > person who did it, malicious to make fun of cypher punks or simply > poking fun at cyberspace in general. > I'm interested in forming a similar net, not for the buying and > selling of information, but for the fun of doing it, who knows what might > come about in a network somewhat limited and away from the internet, but > based on pgp without people flaming, and without the netloons like > dwetler and sternlight, (I have my doubts about dwetler's actual motives > in spamming the mailers) > SO, hopefully they key I encrypt it to is the actual one, and if not > hopefully whoever is intercepting this is as interested in creating > what I am, why else be eaves dropping?? > Looking forward to hearing from whoever out there, and > I hope you're competent enough with unix to extract my pgp key > from my .plan > > > -- > Finger firstname.lastname@example.org for PGP public key 2.6ui > GJ/GP -d+ H+ g? au0 a- w+++ v+(?)(*) C++++ U++1/2 N++++ M-- -po+ Y+++ > - t++ 5-- j++ R b+++ D+ B--- e+(*) u** h* r+++ y? > > >The next step was to create a revocation certificate and send that off to the PGP key servers. After all, the key has undoubtedly been compromised.
The moral of this story is that 384-bit keys can be broken by a small team of people working in secret and with modest resources. Lest anyone object that a MasPar is not a modest resource, we'd re-iterate that it did only 50% of the work; that we took only three months and that we used only 50 or so quite ordinary workstations. We believe that we could have used at least twice as many machines for at least twice as long without anyone noticing. The currently minimum recommended key size, 512 bits, is safe from the likes of us for the time being, but we should be able to break them within five years or so. Organizations with more than "modest resources" can almost certainly break 512-bit keys in secret right now.
Alec Muffett email@example.com
Paul Leyland firstname.lastname@example.org
Arjen Lenstra email@example.com
Jim Gillogly firstname.lastname@example.org
and, of course, BlackNet (email@example.com) 8-)
P.S. The 384-bit BlackNet secret key is:
> -----BEGIN PGP MESSAGE----- > Version: 2.6.2i > > lQDAAy/ty1QAAAEBgM98haqmu+pqkoqkr95iMmBTNgb+iL54kUJCoBSOrT0Rqsmz > KHcVaQ+p4vLIWlrRawAFEQABfAw0gFVVGhzZF63Nc8HJin4jAy2WgIOsvST5ne1Y > CbfyDIZ6siTHUAos8wMBQZ6Q8QDA2b6tiYqrGu6E1+F0DGPSk9MGif5/LKFrAMDz > 8HXIK1zrEFEDq9/5dUXO2rk1tH+mkAEAv0EE9e5EJn+quL3/YvAg6bKOlM7HgVKq > JEDDtCBCbGFja05ldDxub3doZXJlQGN5YmVyc3BhY2UubmlsPg== > =/BEI > -----END PGP MESSAGE-----
[Made with Macintosh] [Built with BBEdit]
Michael Sattler <firstname.lastname@example.org>