From: Adam Back <aba@dcs.ex.ac.uk>
Date: Wed, 14 Oct 1998 20:32:33 +0800
To: tcmay@got.net
Subject: Re: ATTN: BlackNet, sog's keys 4 sale
In-Reply-To: <v03130307b249d4908a73@[209.66.100.146]>
Message-ID: <199810141153.MAA29777@server.eternity.org>
MIME-Version: 1.0
Content-Type: text/plain



Tim May comments on:
> At 6:41 PM -0700 10/13/98, Anonymous wrote:
> >Dear BlackNet,
> >
> >TOTO Enterprises, Bienfait, Saskatchewan hereby offers
> >for sale sog's key under the BlackNet anonymous
> >information market.
> >
> >Payments must be in anonymous ecash delivered to a
> >digital dead drop to be arranged later.
> >
> >Or alternatively, we are willing to take bids in
> >bottles of Scotch delivered to TOTO Key Escrow
> >Services, Box 281, Bienfait, Saskatchewan SOC OMO.

I looked up the key this message was encrypted to on one of the
keyservers by it's keyid -- 0x5A5AD16B.

Look at this:

Type Bits/KeyID    Date       User ID
pub   384/5A5AD16B 1994/02/11 *** KEY REVOKED ***
                              BlackNet<nowhere@cyberspace.nil>

A revoked key, and a rather small key size, this rings a bell, some of
you may recall that some time ago Paul Leyland factored that key.  In
fact I have the hex version of it on my own web pages somewhere as an
example to use with rsa-perl.

A quick altavista on "Leyland BlackNet" turns up the goods [1] below.
(http://www.irdg.com/mep/nni/384broke.txt)

> Hey, I could tell you all that BlackNet was used a while back to
> distribute some of the keys used by The Performance Artist Sometimes
> Known as Toto.

Well this message does indeed seem to contain a key for:

Type Bits/KeyID    Date       User ID
sec  1024/2541C535 1997/11/07 son of gomez <InfoWar@dev.null>

and some claimed passwords for a "carljohn" sympatico account.

Curiouser and curiouser.  Intentional or not?  Intentional I think
from the contents, [2].

Adam


[1]
======================================================================
------- Forwarded Message

From: pcl@sable.ox.ac.uk (Paul Leyland)
Newsgroups: alt.security.pgp,sci.crypt,alt.privacy
Subject: The BlackNet 384-bit PGP key has been BROKEN
Date: 26 Jun 1995 10:09:15 GMT
Organization: Oxford University, England
Lines: 165
Message-ID: <PCL.95Jun26110915@sable.ox.ac.uk>
NNTP-Posting-Host: sable.ox.ac.uk
Xref: mozo.cc.purdue.edu alt.security.pgp:21006 sci.crypt:40008 alt.privacy:225
76

- -----BEGIN PGP SIGNED MESSAGE-----


We 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:

3193508200533105601431099148202479609827976414818808019973596061739243\
9454375249389462927646908605384634672078311787

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 yusuf921@raven.csrv.uidaho.edu 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    alec.muffett@uk.sun.com
Paul Leyland    pcl@oucs.ox.ac.uk
Arjen Lenstra   lenstra@bellcore.com
Jim Gillogly    jim@acm.org

and, of course, BlackNet<nowhere@cyberspace.nil>     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-----


- -----BEGIN PGP SIGNATURE-----
Version: 2.6

iQCVAwUBL+6HEzt/x7zOdmsfAQGRpQP9FZluArrT5+zsG/R6y/MF7O3d7ArEkVe2
rUQgP7W2NxudAFHTNaL9mqLBDVNW/3PqWIhvHMtrSgG+ZAFBH5bP03tizfOFr+SL
eO1JQgYFey7Wh5J/YCuE0VTlYMZ7bhnoiGIvTYZgxIzVWAYyGmlWKRDjfKz/Pks8
qavbPg6qbPo=
=s12J
- -----END PGP SIGNATURE-----
- --
Paul Leyland <pcl@sable.ox.ac.uk>        | Hanging on in quiet desperation is
Oxford University Computing Services     |     the English way.
13 Banbury Road, Oxford, OX2 6NN, UK     | The time is gone, the song is over.
Tel: +44-1865-273200  Fax: 273275        | Thought I'd something more to say.
Finger pcl@sable.ox.ac.uk for PGP key    |

------- End of forwarded message -------

[2]
======================================================================
ATTN: Jeff Gordon

As a bonus PRIZE for people figuring this out, here's
Toto's sympatico username and password:

username: carljohn
password: 574kxy
SMTP: smtp.sk.sympatico.ca
POP3: mailhost.sk.sympatico.ca
POP3 username: carljohn

  I sent much of my outgoing mail through CJ's system
because he had so many hackers and system intruders
that he was a one-man 'Crowds' unit.

Toto

-----BEGIN PGP PUBLIC KEY BLOCK-----
Version: 2.6.2

mQCNAzRiaHcAAAEEAPdnnUJRJoktl6tMtRcrV330FvNPok4FvTMOT82V0lIRA7ZQ
jiAcv4Egm8nx6M6dc75eWIIPo4gZOWf5xjZzN8XjD2ytwMNqQnis0RMN9OI8ysk2
I7frJO0FNLikupHf+tUMhDc52qQbOcsVC53GZ8FdwY1zzaX7Dc5WpAclQcU1AAUR
tB9zb24gb2YgZ29tZXogPEluZm9XYXJAZGV2Lm51bGw+iQCVAwUQNGJph85WpAcl
QcU1AQFXPQQA8adaDwM3DnttrJPTjUd9I/fQ6q73Zvp6oLPP3MSon4uEbIVJryPB
wZYfcjXb6Co84XFpaL8shtgP0cHYRZDfQraCwsaJWOm1Lh+ZhZyqHh2oF4QrpOhm
A5YzxYI7SX3GIu/X1XO5vcb+BnJqbl2+RUaHnGqcwwrwxjSc1stGwJ4=
=Yx4A
-----END PGP PUBLIC KEY BLOCK-----

-----BEGIN PGP SECRET KEY BLOCK-----
Version: 2.6.2

lQHgAzRiaHcAAAEEAPdnnUJRJoktl6tMtRcrV330FvNPok4FvTMOT82V0lIRA7ZQ
jiAcv4Egm8nx6M6dc75eWIIPo4gZOWf5xjZzN8XjD2ytwMNqQnis0RMN9OI8ysk2
I7frJO0FNLikupHf+tUMhDc52qQbOcsVC53GZ8FdwY1zzaX7Dc5WpAclQcU1AAUR
AUzSerlWWdq7A/+EGrDs3oHlVDzmPEouO2m1gWLN6erKPgd5tiB7eWECJoiRC9AU
Va2LJLxltmNKIq9znAMeeCpI3nirprYgHMvyASVPrXIo4WXB0NGSyTXSGFbmbfBA
ZhIzgLYfSV7KC9e340B4wqQv/hSGyc9p7/umXgdccspoXM4fIwddYNt0+QIA+XS0
WUPNqr4lyW47GVAhFIuoYsTLi+ZTRRQbS2LAyV2dhGSFVo1Q1HrB/S58dQFTaN85
lRytpZKX2dc+9VC3JgIATZegUu3m2FmRMf7kr0IsRV94q0lxQm4egMPdru6CQGZl
G7K9uGX/d/Rbtd0iP7aZ1iNDpgSakmNl5o3aYupCdQIAir0t68n1g91DzWwOMJKF
7E9fmQ21a7a2rDGk+5SV9nw3PxGwx/64CPHriDQz/ItYLPZKpHVLysuFGavYUFX/
26JZtB9zb24gb2YgZ29tZXogPEluZm9XYXJAZGV2Lm51bGw+
=yYBi
-----END PGP SECRET KEY BLOCK-----