| Cryptome DVDs. Donate $25 for two DVDs of the Cryptome collection of 47,000 files from June 1996 to January 2009 (~6.9 GB). Click Paypal or mail check/MO made out to John Young, 251 West 89th Street, New York, NY 10024. The collection includes all files of cryptome.org, cryptome.info, jya.com, cartome.org, eyeball-series.org and iraq-kill-maim.org, and 23,100 (updated) pages of counter-intelligence dossiers declassified by the US Army Information and Security Command, dating from 1945 to 1985.The DVDs will be sent anywhere worldwide without extra cost.

23 September 1998

See related keys: http://jya.com/anon-keys.htm, http://jya.com/totos-keys.htm

    Date: Sat, 19 Sep 1998 11:52:47 +0100
    From: Adam Back <aba@dcs.ex.ac.uk>
    To: cypherpunks@cyberpass.net
    Subject: CHALLENGE? Toto/signature attack w. unpublished public key

    This post discusses the possibility of generating a RSA public key n,
    and e given a signature s on a message m creating using an unknown
    (unpublished) n and e.  A message and signature whose validity has
    some bearing on a current IRS investigation is given as a target for
    an attack if such an attack is feasible.

    Toto published one signed message [1] but not a public key for the
    signature.  It seems to me that there should be other public keys
    which one could generate which could have signed the same message.

    I would like comments on the feasibility of the signature attack
    proposed below, and suggestions for more efficient methods.

    (For those not following the Toto saga, he was the author of a series
    of anti-government rants and future fiction stories on cypherpunks.
    The posting of [1] to the list seems to have been deemed a handy
    excuse for the IRS to arrange Carl Johnson's incarceration See:
    http://jya.com/cejfiles.htm.  They claim that the presence of a public
    key on Carl Johnson's hard disk proves that he authored the post in
    question [1].)

    What we have is:

    Unknowns: e, n, d
    Knowns: m, s

    Where m = padding || md5( message )

    A signature is computed as:

    	s = m ^ d mod n

    and verified by checking that:

    	s ^ e mod n = m

    ( where RSA says: n = p.q, d.e = 1 mod (p-1).(q-1) )

    We are trying to find an n and an e which satisfy s ^ e mod n = m,
    with the additional constraints that log2( n ) = 1024 and n > s
    (because we have the signature s, and it is 1024 bits in length).

    For bonus points it would be nice for n mod 2^64 = 0xCE56A4072541C535,
    which is the key-id in the signature.  (I say bonus points because the
    key-id in the signature is not authenticated, or included in the
    message digest, so could have been for example edited after the
    signature was made, or filled with random numbers for whatever
    reason).

    Tinkering with PGP I can extract the values for the knowns:

    s =   0x08F4D5CBC10063725B206F787EB7370BBD0C5B4854CE79A9007D1801AEAEE6E6
    	D2C68D7EDF877FECE1FA539D08BEC54BD152BA05113951E8A84CDECAD2CB8E7A
    	C28BE916570BA7BB9C00C64DF57113C4AE81613BD351541523CD3A028FBF220E
    	F7469BD4175302DCB5B6E886974877F28A2D301433AFFFE26081008BFF687B37

    m =   0x0001FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF
    	FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF
    	FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF003020
    	300C06082A864886F70D0205050004105A82A30F832DC6839C20DD6DB2EF783B

    (the 00 01 FF .. FF 00 are the PKCS#7 required padding, then the
    3020300c06082a864886f70d020505000410 is the ASN padding indicating
    various PKCS #7 cruft, and 5A82A30F832DC6839C20DD6DB2EF783B is the
    digest of the message (which includes some of the info in the
    signature block: timestamp, signature type, etc))

    So next we would like to solve:

    	s ^ e mod n = m

    or in other words find e, k and n st:

    	s ^ e - m = k * n

    I have been trying to factor f3 = s ^ e - m for e = 3, and can get
    factors:

    f = 2 2 5 11 17 26496937

    and

    251048771208077840279253039518619486761149393656018551881762776705901\
    323868599665917317036581098944533770815064901485649759588104677561495\
    719846643046535204246014520276297740544890135011586884286882393788265\

    716989378535974685125268132766806309723740928058713253950594405611241\
    121342427851929130344133177905256374336176401503386547907484013668011\
    870701681839150463738400849274433891413410494500220449307074230633487\
    686485522732190007426023068542565670710414256907678005650439818373128\
    045462081252984434043133357326332595300178784873354995536385391488171\
    082297914170316457453668703759313538562865586078736676571820284813613\
    435988240345557012477625002576044754861439307189875911957770722297269\
    127365840009630893296289725097984631185778357339553526670628683341222\
    179800672224971064029655723085468566526546006022122686584662976524189\
    679277675211381453870834486124773894995875790430641434242560016378644\
    4039359130261

    (I call the f resulting from choosing e = 3, f3, other e values can be
    denoted f5, f7, etc).

    It seems to me that if we can get get a factor out (or construct a
    composite from factors) which is greater than s, and is 1024 bits
    long, then this "key" could have signed the message in question.

    If the number has 2 or more factors, which we know because we
    constructed it by multiplying them, then we could even "sign" another
    message with this key, by generating a d based on the p, q (and
    possibly other multiples) and have both messages appear to be signed
    by the same key.

    If we can get some larger factors, we stand a chance because we have
    the flexibility of being able to adjust a potentional n's size by
    multiplying by combinations of factors found so far 5 11 17 26496937.
    This means we can adjust n's size by adding bits by multiplying by
    combinations as follows

    combination		bits added

    5			2 - 3
    11			3 - 4
    17			4
    5 11			5 - 6
    5 17			6 - 7
    11 17			7 - 8
    26496937		24 - 25

    So the challenge is to find other factors of:

    f =	251048771208077840279253039518619486761149393656018551881762776705901\
    	323868599665917317036581098944533770815064901485649759588104677561495\
    	719846643046535204246014520276297740544890135011586884286882393788265\
    	716989378535974685125268132766806309723740928058713253950594405611241\
    	121342427851929130344133177905256374336176401503386547907484013668011\
    	870701681839150463738400849274433891413410494500220449307074230633487\
    	686485522732190007426023068542565670710414256907678005650439818373128\
    	045462081252984434043133357326332595300178784873354995536385391488171\
    	082297914170316457453668703759313538562865586078736676571820284813613\
    	435988240345557012477625002576044754861439307189875911957770722297269\
    	127365840009630893296289725097984631185778357339553526670628683341222\
    	179800672224971064029655723085468566526546006022122686584662976524189\
    	679277675211381453870834486124773894995875790430641434242560016378644\
    	4039359130261

    One could also try other values for e, although they result in larger
    f.

    What is the best factoring code available to have a go at factoring
    the above?  (I have been usign the demo pollard-rho factoring code
    which comes with ssh-1.2.26 in the gmp-2.0.2-ssh-2/demos directory).
    Anyone interested to give this a go, who has say got a few (hundred?)
    workstations already setup for another factoring challenge which they
    could divert to attack the above f3 (or f5, f7, etc).

    Course, if Toto is still at large, and Carl Johnson is not the only
    one with the key (and some messages on cypherpunks recently lend
    credence to this), he might trash this challenge by posting another
    signed message, or weaken it's value by posting a public key which
    proved could be shown to have been derived by this method.
    (Interestingly, I think merely posting a public key claiming to be the
    `real key' which we couldn't factor nor show to be a factor of f
    wouldn't prove that that key was any more legitimate than a key
    generated by a success on this challenge, all it would tend to show
    would be that the person who posted it had more compute power
    available than us!)

    Adam

    [1]
    -----BEGIN PGP SIGNED MESSAGE-----

    "Contrary to one famous philosopher,
    you're saying the medium is not the
    message," Judge Thomas Nelson said,
    alluding to the media theorist Marshall
    McLuhan.

    http://www.nytimes.com/library/cyber/week/120997encrypt-bernstein.html

      Bullshit!
      The bits and bytes of email encryption are a clear message
    that I wish to exercise my right to speak freely, without those
    who wish to do me harm invading my privacy.
      The death of strong encryption on the InterNet will be the
    global death of free speech on the InterNet. Accordingly, I
    feel it is necessary to make a stand and declare that I stand
    ready and willing to fight to the death against anyone who
    takes it upon themselves to try to imprison me behind an
    ElectroMagnetic Curtain.

      This includes the Ninth Distric Court judges, if they come to
    the conclusion that the government that they represent needs to
    electronically imprison their citizens 'for their own safety.'

    The problem: Criminals with a simple
    encryption program can scramble their data
    beyond even the government's ability to read it.

    http://www.zdnet.com/zdnn/content/zdnn/1208/261695.html

      Fuck the lame LEA pricks who whine about not being able to
    stop someone bringing in a planeload of drugs without being
    able to invade the privacy of every person on the face of
    the earth.
      Am I supposed to believe that I have knowledge of when and
    where major drug shipments are taking place, simply by virtue
    of hanging out as a musician, yet the LEA's are incapable of
    finding out the same information by being competent in their
    profession? Barf City...
    [I will shortly provide information for any LEA which wishes
      to prosecute me for my coming 'physical' death threat, on
      how to hunt me down like the filthy dog that I am.]

    "Why are you saying that the fact that [encryption]
    is functional takes it out of the First Amendment
    context?" Myron Bright, one of the judges, asked
    the Justice Department attorney, who was still in
    mid-sentence. He answered that the regulations
    were not aimed at suppressing speech, but only at
    the physical capacity of encryption to thwart
    government intelligence gathering.

      The Spanish language has the same "physical capacity." So
    does (:>), (;[), and {;-|). Likewise, BTW, FWIW, FYI, and
    my own personal favorite, YMMV (You Make Me Vomit? --or--
    Your Mileage May Vary?). <-- Ambidextrous encryption.
      An-cay e-way pect-exay ig-pay atin-lay usts-bay of

    ildren-chay?
      Whispering also has the "physical capacity" to "thwart
    government intelligence gathering."

      When does the bullshit stop? When do we stop making the
    use of the Spanish language over the InterNet illegal?
    When do we stop making whispering, pig-latin, anagrams
    and acronyms illegal?
      When do we stop saying that our government is such a
    piece of crap that it is a danger to let its citizens
    communicate freely, in private, and share their private
    thoughts with one another?

    At one point Fletcher called the government's case
    "puzzling."

    http://www.news.com/News/Item/0,4,17114,00.html

      Only because her mom taught her that it was unladylike to
    say "Bullshit!"

    In arguments Monday, a Justice Department
    lawyer, Scott McIntosh, said the government's
    intent was to preserve the ability of intelligence
    agencies to eavesdrop on foreign governments
    and citizens.

    http://www.nytimes.com/library/cyber/week/120997encrypt-bernstein.html

      Let's see if I have this right...
      The U.S. government needs to destroy the right to free speech
    and right to privacy of its own citizens in order to infringe
    upon the human rights of the governments and citizens of other
    countries? Countries which already have strong encryption?
    Countries like Red China, which is currently engaged in
    encryption research with an American company who got permission
    to export much more diverse encryption material (after making
    a huge campaign donation to the Whitehouse) than Professor
    Bernstein will ever likely share with others?
      Apologies to Judge Fletcher, but that's not "puzzling." That's
    the same-old-same-old Bullshit!

    OFFICIAL 'PHYSICAL' DEATH THREAT!!!
      The pen is mightier than the sword. Thus, I prefer to wage my
    'war to the death' against those who would stomp on my basic
    human rights *"in the interests of National Security"* with my
    electronic pen, on the InterNet, using encryption when I have
    reason to fear persecution by Facist, Nazi motherfuckers.
    [* ~~ TruthMonger Vernacular Translation ~~ "so that the
    government can maintain its authority over the citizens
    by use of force and violation of human rights, rather than
    going to all of the trouble of acting in a manner that will
    garner the citizens' respect."]

      I will continue to express my thoughts through the words
    I send electronically over the InterNet, both publically
    and privately. I will fight to the bandwidth death against
    anyone who wants to deny me my right to express my opinions
    and access the opinions of those who also wish to express
    their own opinions and share their true thoughts with their
    fellow humans.
      If the ElectronicMagnetic Curtain slams down around me,
    then I will have no choice but to continue my current fight
    in MeatSpace.
      And I am not alone...

      I will share the same 'DEATH THREAT!!!' with Judges Fletcher,
    Nelson and Bright that I have shared with the President and
    a host of Congressional and Senatorial representatives:
      "You can fuck some of the people all of the time, and all of
    the people some of the time, but you are going to end up in a
    body bag or a pine box before you manage to fuck all of the
    people all of the time."

      Am *I* going to whack you out? Maybe...
      I would prefer just dumping some tea in Boston Harbor, if that
    will get my message across in MeatSpace, but if it won't, then
    I guess I will have to take stronger action.
      There are undoubtedly a plethora of LEA's ready and willing to
    prosecute and imprison me for agreeing with Patrick Henry, who
    said, "Give me liberty, or give me death." The irony, of course,
    is that I do not pose a great danger to anyone but myself as
    long as I continue to have my human rights and my liberty
    unthreatened.

      The chances of me actually getting off of my fat butt and
    going out into the real world to whack out the enemies of
    freedom are probably pretty small (unless I run out of
    cigarettes and beer, and wouldn't have to make an extra
    trip).
      I fully understand that this does not lessen the potential
    of any LEA who gets a wild hair up their butt to throw a
    mountain of taxpayer resources into prosecuting me and
    imprisoning me for their own professional/political gain.
      However, if you are performing actions so outrageously against
    basic human rights and freedoms as to get me off of my lazy ass,
    then I am the least of your problems, because there undoubtedly
    are millions of people more functional than myself (who get out
    of the house and go further than the liquor store) who are less
    willing than myself to put up with increasingly heavy chains
    placed around their hands and feet 'in the interests of national
    security.'

      Feel free to have the Federales break down my door and
    imprison me for pointing out the obvious. After all, I fit
    the profile of a domestic terrorist--I quote the Constitution
    and the Bill of Rights, and I speak out against increasingly
    big government.
      But remember...it's the quiet ones you've got to watch...
    If you force everyone to 'be quiet', then you've got a world
    of trouble on your hands.

    Sincerly,
    John Gilmore <gnu@toad.com>
    ~~~~~~~~~~~~~~~~~~~~~~~~~~~
    p.s.
    NOTICE TO LEA AGENTS IN NEED OF A CAREER BOOST!
      Yes, I'm just a troublemaking asshole, trying to get John
    <spit> Gilmore <fart> in trouble.
      However, if you want to go to the trouble of tracking me
    down, I will give you some hints, since it seems likely that
    anyone who has trouble finding a ton of cocaine at an
    airport might not be competent in CyberSpace, either.
      You might want to check with the Webmasters at the sites
    quoted above to see who has accessed their web sites this
    morning. The anonymous remailer I will be using is an open
    secret to CypherPunks around the world as a really bad
    attempt at disguising my true MeatSpace identity. This alone
    ought to be enough for some aggressive young LEA and/or
    federal prosecutor to earn themself some brownie-points,
    since I am a sorry enough son-of-a-bitch that they would not
    have much trouble convicting me in front of a jury of 'their'
    peers, assuming that they can make certain that I am not
    tried by a jury of my own peers.

    Bonus Points:
      I can also be tied into Jim Bell's Worldwide Conspiracy to
    assassinate government authorities, through my implementation
    of an Assassination Bot.

    (I am willing to 'rat out' Jim for two bottles of Scotch. If
    he is willing to rat _me_ out for less, then I guess it's
    just my hard luck, eh? <--that's another hint!)

    p.p.s.
      You can also charge me with use of 'conventional' encryption
    in the commission of a crime.
      Must be your lucky fucking day, eh?

    -----BEGIN PGP SIGNATURE-----
    Version: 2.6.2

    iQCVAwUBNI24Hs5WpAclQcU1AQFaggP8CPTVy8EAY3JbIG94frc3C70MW0hUznmp
    fRgBrq7m5tLGjX7fh3/s4fpTnQi+xUvRUroFETlR6KhM3srSy456wovpFlcLp7uc
    xk31cRPEroFhO9NRVBUjzToCj78iDvdGm9QXUwLctbbohpdId/KKLTAUM6//4mCB
    i/9oezfegWc=
    =4/6E
    -----END PGP SIGNATURE-----

    Date: Sat, 19 Sep 1998 19:28:09 +0200
    From: Anonymous <nobody@replay.com>
    To: cypherpunks@cyberpass.net

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

    September 19, 1998, U.S. Medical Center for Federal
    Prisoners, Springfield, Missouri, not a Magic Circle.

    -----BEGIN PGP SIGNATURE-----
    Version: 2.6.2

    iQCVAwUBNgPkchp0s99tXiQlAQEoHQP+IX2GivNiJpIB3ryiu+bte0+YyJRTZDWB
    bbF/qRIGrOOVKpNxuu+riAz0oUxHW3xuooPmIVcR8O0tfXljrxyAvK4qdtPFWyr9
    +PaE5clU7XdRqxiKGfao569W1vRPJW5vlmUm+/BHmRF1ADG/HqTy/EbivKEvZGcw
    UmrV65r+9ho=
    =wa8X
    -----END PGP SIGNATURE-----

    Date: Sat, 19 Sep 1998 19:46:43 +0100
    From: Adam Back <aba@dcs.ex.ac.uk>
    To: cypherpunks@cyberpass.net
    Cc: jya@pipeline.com
    Subject: TruthMonger key's password!

    Anonymous writes on cpunks (blank subject field from nobody@replay.com
    earlier today).

    > -----BEGIN PGP SIGNED MESSAGE-----
    >
    > September 19, 1998, U.S. Medical Center for Federal

    > Prisoners, Springfield, Missouri, not a Magic Circle.
    >
    > -----BEGIN PGP SIGNATURE-----
    > Version: 2.6.2
    >
    > iQCVAwUBNgPkchp0s99tXiQlAQEoHQP+IX2GivNiJpIB3ryiu+bte0+YyJRTZDWB
    > bbF/qRIGrOOVKpNxuu+riAz0oUxHW3xuooPmIVcR8O0tfXljrxyAvK4qdtPFWyr9
    > +PaE5clU7XdRqxiKGfao569W1vRPJW5vlmUm+/BHmRF1ADG/HqTy/EbivKEvZGcw
    > UmrV65r+9ho=
    > =wa8X
    > -----END PGP SIGNATURE-----

    That one I can verify the signature of (unlike the 0x2541C535 key-id
    signed post which I proposed we try a signature attack on because of
    lack of public key), because I have on my keyring the secret key since
    adding the secret key to my key ring from this post which was made to
    cypherpunks [1] with headers below (look in the archives, or copied
    below):

    : From: nobody@REPLAY.COM (Anonymous)
    : To: cypherpunks@toad.com
    : Date: Tue, 23 Sep 1997 01:58:52 +0200 (MET DST)
    : Subject: Persistent Persona

    The key in that message was:

    Type Bits/KeyID    Date       User ID
    sec  1024/6D5E2425 2041/12/07 TruthMonger

    -----BEGIN PGP SECRET KEY BLOCK-----
    Version: 2.6.3i

    lQHgA4dN5oIAAAEEAM/3b3wHc1iQEmtk9NQhmrHmZmlCdZH4T3kf2APlwA/NRsfU
    pAa++0pBdgMMOr9QBMWNWuRuZriEUE/jH9cdMkgBeOrvsviFSe2wN074LrCZSugO
    6KabPwokodYl8+R8xY5NC1pZUD4sYf49L6xOwpjiXukrRKqwABp0s99tXiQlAAUR
    ARwSOk76t7D7A/0n7XVeJ5qLKatxrzKZ1+U9PLhEeeQkknETkj9aFmRNrj/I4n/Y
    TgxKh74zK1/kM4y6bunTNU6+pBDPrvYJgqoq4kMlS3jXNdGBFn0Tw0j2klSZpXzA
    Tb593tKD66dztQXiYbYYhydQixUp22NwjruiIfwjFdtU7tOhKfLgZ+dGJQIAH40N
    9Gpt3oSQ+ua6I1mOEYzWXdH8HdaNQKxGVRYVH71Wi2TpDLuZbbYq6RB9LDQ0VJO0
    6DumKr1OSG32zda+kwIAvjPYd8xEOyCo2NJfL2ZUBh9/GC9nb9UTxdwFP7AFx0F7
    DTA+prGb672ly3NAa7/gje2W4isd3NN+T6T13WHmcAH+MnnMDMclF/hNKrhR39aB
    1ZvVEBh8yz8xWCm5BQOqp55KyJGgDY0kAcwqejE0PHV8dMG6TVteVvOu7D7GDFcB
    4KXvtAtUcnV0aE1vbmdlcg==
    =HBLx
    -----END PGP SECRET KEY BLOCK-----

    which means that anyone can create such signatures.

    That PGP correctly copes with signatures made by keys it has only a
    private key for (and no public key) is something of a surprise -- PGP
    must be smart enough to use the private key if the public key isn't
    around on the keyring.  (The public key is a subset of private key).

    Erk! just tried to create a signed file with that private key, and I
    didn't notice before when I commented on the posting of this key that
    key has a passphrase!  It wouldn't be one of those John Young
    forwarded to the list from an anonymous source would it....

    Holy smoke!  Now we are getting somewhere, the person who remailed
    those passphrases to John Young knew that keys passphrase, and yet the
    key was posted back in Sep 97!

    John Young writes on cpunks:
    > This allegedly is forwarded from CJ, though from an unknown source
    > so think twice:
    >
    >       "Passwords:  sog, sog709, sog709cejCJP,sog709cjpCEJ, D'Shauneaux,
    >       D'shauneaux, and others..."

    The passphrase was sog709.  Try it and see.  Check in the archives for
    yourself for that message, (subject 'Persistent Persona') and become
    paranoid!

    What is going on here?  Is Toto still at large, drunk behind the
    keyboard?  Is Toto not one person?  Or have the IRS extracted Carl
    Johnson's passphrases from him and got busy playing mind-games with
    us?

    Adam

    [1]
    ======================================================================
    Date: Tue, 23 Sep 1997 01:58:52 +0200 (MET DST)
    Subject: Persistent Persona
    To: cypherpunks@toad.com
    From: nobody@REPLAY.COM (Anonymous)

    -----BEGIN PGP MESSAGE-----
    Version: 2.6.2

    lQHgA4dN5oIAAAEEAM/3b3wHc1iQEmtk9NQhmrHmZmlCdZH4T3kf2APlwA/NRsfU
    pAa++0pBdgMMOr9QBMWNWuRuZriEUE/jH9cdMkgBeOrvsviFSe2wN074LrCZSugO
    6KabPwokodYl8+R8xY5NC1pZUD4sYf49L6xOwpjiXukrRKqwABp0s99tXiQlAAUR
    ARwSOk76t7D7A/0n7XVeJ5qLKatxrzKZ1+U9PLhEeeQkknETkj9aFmRNrj/I4n/Y
    TgxKh74zK1/kM4y6bunTNU6+pBDPrvYJgqoq4kMlS3jXNdGBFn0Tw0j2klSZpXzA
    Tb593tKD66dztQXiYbYYhydQixUp22NwjruiIfwjFdtU7tOhKfLgZ+dGJQIAH40N
    9Gpt3oSQ+ua6I1mOEYzWXdH8HdaNQKxGVRYVH71Wi2TpDLuZbbYq6RB9LDQ0VJO0
    6DumKr1OSG32zda+kwIAvjPYd8xEOyCo2NJfL2ZUBh9/GC9nb9UTxdwFP7AFx0F7
    DTA+prGb672ly3NAa7/gje2W4isd3NN+T6T13WHmcAH+MnnMDMclF/hNKrhR39aB
    1ZvVEBh8yz8xWCm5BQOqp55KyJGgDY0kAcwqejE0PHV8dMG6TVteVvOu7D7GDFcB
    4KXvtAtUcnV0aE1vbmdlcg==
    =HBLx
    -----END PGP MESSAGE-----

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

    mQENAzOCm1EAAAEIANB5WCFbEjUhNaZ2cEWuh9xcP48QBixzJpxPqGc0Sogj9W1L
    ezM5GDF0tZp5ksNbWf5+ErNxXo0yOM7LjDl+sRrEmcbuTkjqPJxG/q4JZ7Al3/FF
    h1SFGWpQNz9BPewgHS8/Lp9Ywl+ELeau+FPrr/xmktYifBBaaPUTS5oNMhn4Ih0r
    yez6WFn6lRYz+FLsXchjkg+I22tC1aD6iKv/BxCM//GzJ8UNkE7Vx94jZxJ/0vqE
    3msqN1coj99okoggWzR5xe/wcLjUjXBw4Z208zhKNEC1AemkJV5HSbztfOgpZOqX
    4dwsSDREfFcerM3gusIv3Gz+oU5WPTNSVeg5/HkABRG0GVRydXRoTW9uZ2VyIDx0
    bUBkZXYubnVsbD6JARUDBRAzgptRPTNSVeg5/HkBAXUeB/4y3/VlUzua8TVbAiTW
    KPXvqTq28XHrhNrTiDWXX7KaFmRyZC20OLbRNtJH1XJUeZv7yhxXkIO2jW6e1i95
    MWcx0JAheNjdqKAdNFUVaqs6R2+ySAU7PtfbfVx/RUxsTW8jLfppI7ajTf3E9z3u
    nO6NpN/z74DO659tiwfNjT8YoRH3EEomSKNZ3yIGhbyTHv+FOrJs8sQ3jhqmFb37
    nr0er1+BWi9Sr2LS7aK+iCK/ZKhUqaofkoo6S/M6nTWKU7RiDhvK0wm40Lassb83
    z3NjwN2NNZDwCPYM3d12LjxWA70qljx/qsSRptvkDmnLKXnEUvTsnf9dErhpYLtg
    yGBFiQCVAwUQM4LW/7BfjJBm+4xlAQEbJAP/RsKZ/khOS+4nD7JfPnKMKMVjDOif
    x0enjzf7kW//GnMsi70yaYi6QeoT0YUYVNQ+wWwGUPgAejs2PLk1VIbn4GIvRU+1
    Uj6xTTfHkIibUtvz7LtC/JmNafWSETDnJOlqszgzTnE0duDwZ83ISWdzHkhEXnfC
    BxcPay75u1zC6FQ=
    =j6da
    -----END PGP PUBLIC KEY BLOCK-----

    Date: Sat, 19 Sep 1998 22:07:54 +0100
    From: Adam Back <aba@dcs.ex.ac.uk>
    To: cypherpunks@cyberpass.net
    Subject: Toto knows how to make a 0xdeadbeef attack?

    As a result of my trawl through my cypherpunks archive last week
    looking for publically posted private keys by Toto et al, I grepped
    out a selection of encrypted messages sent to the list.  I thought I'd
    have a go at decrypting these with the selection of passphrases John

    Young posted earlier today, in case any were encrypted with the
    publically posted keys, or with a conventional encryption key.

    I came across this post [1] posted in 5 Sep 97 which contains this
    encrypted message, and "challenge" to decrypt it.

    Now if you try to decrypt it, it says you need key 0xE6A9C799, the
    public key for which is on the key servers.  However keyids are
    actually stored as 64 bits, internally to PGP messages, but only the
    least significant 32 bits are displayed by PGP normally.  I use
    pgpacket to look at things and it gives you all 64 bits, the message
    has keyid:

    	0xAA33463CE6A9C799

    however the key I got off the keyserver [2] has keyid:

    	0xAA33063CE6A9C799

    which differs by 0x400000000000 or one bit.  That would require
    knowing how to create a 0xdeadbeef key or at least use software to do
    this, if it is available.

    Unless the bit flip is part of the "challenge".  Who knows.

    Toto did allude to hacking skills, though largely claimed ignorance.
    I wonder if this was feigned, or if there are other Totos who are
    doing the key hacks etc.  eg this challenge out of bureau42.ml.org
    remailer.

    Toto is a one man computer crypto forensics persons full-employment
    insurance! -- the amount of stuff posted to the list with various
    passwords, keys, etc.  The IRS guys must be either hiring some one who
    knows crypto, or are going to be seriously confused at this point.
    Then there's the use of S-Tools, they must be going boggle eyed
    guessing passphrases for S-Tools for all the images ever posted
    anonymously, or pseudonymously to the list.  One wonders almost if
    this was his aim.

    Any hints Toto(s)?  Firstly I haven't got the private key(s) for
    0xAA33[0|4]63CE6A9C799, and secondly, what's the deal with the bit
    flips/0xdeadbeef attacks?

    My september forward secret key is below [3].  It is authenticated by
    my high security key, and 12 days time or so, the private key gets
    wiped.

    Adam

    [1]
    ======================================================================
    Date: Fri, 5 Sep 1997 17:31:53 GMT
    From: bureau42 Anonymous Remailer <remailer@bureau42.ml.org>
    Comments: This message did not originate from the Sender address above.
            It was remailed automatically by anonymizing remailer software.
            Please report problems or inappropriate use to the
            remailer administrator at <remailer-admin@bureau42.ml.org>.
    Subject: EFF $10,000,0000 Challenge
    To: cypherpunks@toad.com
    Sender: owner-cypherpunks@Algebra.COM
    Precedence: bulk
    X-Mailing-List: cypherpunks@algebra.com
    X-List-Admin: ichudov@algebra.com
    X-Loop: cypherpunks@algebra.com

    The Electronic Forgery Foundation is proud to announce a major
    breakthrough in encryption technology -- Forged Encryption.

    We are offering a prize of $10,000,000.00 for anyone who can
    correctly decipher the following Forged Encryption message.

    -----BEGIN PGP MESSAGE-----
    Version: PGP for Personal Privacy 5.0
    MessageID: od2CIT3fELE7K6bkIkKGJBj0MPUJ2TT8

    hQCMA6ozRjzmqceZAQQAh02x0Dxer5vzZiSJ+v7bnMZQdgp425z5OH0NF/f/mXXc
    vInw+UsuTXqWNEV5rEQKYjU3qHoe6suCz5f9hEEnOIBacsD28pYU4ahkGOCTuTY6
    N3xKrtDRqLPInB8PY7Kfd56jjQsVVRKmJBwXqHbPax4YyUB6ZbKKvSPiuUsAAQSl
    BAH3CFNKcmYjf+VtpjAVOpDNM/PMm1e6m33rZ01Sq6pXC0TTabCf7hkWscet0PCL
    VX0l1Zw5IKaFqo+pZ3EICRMF6HQrc30G7L9TFeKr//3YsO3/bC4VBgNQHA0qf2nD
    ldxAsTGPlRthBTxrzE0LjeOKi/pQOLXQMPQUwEIaL9rncjFgniplFoL6Nj0guJvW
    VvS+gxth8hpeWss7WlFFioV0vShsS/lahA+eg/9nVy8ken8pr4m484w2vwoiSdce
    CarVigVaRh6tCgh0jub7CHuDFg==
    =Q9+G
    -----END PGP MESSAGE-----

    The EFF doesn't have a copy of the correct answer locked away in
    a secret underground cave in Tibet, for verification, because
    the above Forged Encryption message is just a bunch of crap we
    typed in pretty much at random.

    Does the government want to keep your private key in escrow? Give
    them a copy of your EFF private key.
    Hell, give them _two_ copies, in case one is corrupted.{;>) Smile
    when you give them to the government agent. Ask him how his day
    has been. Offer him some coffe, and ask about his family. Tell
    him you will send him a Christmas card with another copy of your
    EFF private key, just in case the government misplaces the copies
    you gave them.
    Put your hand over your heart, salute the flag, and sing "God Bless
    America" as the government agent leaves. Then fart.

    Use the EFF Forged Encryption sofware regularly, to send messages
    with Subject:'s like "The Plot Against the PREZ," "Confirmation of
    the date of our armed assault," "The Nuke has arrived."
    Keep a copy of your EFF Forged Encryption secret key in a directory
    named "Off the Pigs."
    Most importantly, never reveal in your private email to others that
    you are a deaf, dumb and blind quadraplegic who has been homebound
    since birth. That way, the outrageous claims that government agents
    make against you in their secret deposition for a warrant to kick
    in your door and terrorize you will look all the more foolish during
    your trial.

    We at the Electronic Forgery Foundation realize that some of you wise
    guys are thinking that, for $10 million, it is well worth your while
    to write a program that will decipher the above message into something
    meaningful. Well, knock yourself out, dudes, but if you think that
    known forgers couldn't possibly be lying about the $10 million, then
    go directly to http://www.clueserver/fucking_idiot, do not pass GO
    and do not collect $200.

    ---------------------------------------------------------------------
      This message is copyrighted under the auspices of the Electronic
      Forgery Foundation. Any misquoting, misrepresentation, or other
      abuse of this message would be greatly appreciated. Hell, you can
      tell people you wrote it, if you want to. We don't really care.
    ---------------------------------------------------------------------

    [2] (long)keyid 0xAA33063CE6A9C799 (Toto <toto@sk.sympatico.ca>)
    -----BEGIN PGP PUBLIC KEY BLOCK-----
    Version: 5.0
    Comment: PGP Key Server 0.9.3-db2test

    mQCNAzMs140AAAEEAL1CAoB5pd97hIOoT6L0v05Ov8nw0unf0db6NXZ91EJAyq9p
    DoPGJl7Z6m5McIsNI2DrCEEt7KYdt0ZIGcqqK2gmCePYI0oQOFj+jznI3jKXg1k2

    R+ngk+cUn21EfrNXFGPk1Tuc1/3Qib6cX6BZRJvvz1FNYNt/zqozBjzmqceZAAUR
    tBtUb3RvIDx0b3RvQHNrLnN5bXBhdGljby5jYT6JAJUDBRAzgrFaG9qyus40wB0B
    AeagA/47sR2GW3y/e3z63ZHqvZwsrNZabNtVsLU6QoEfomfOc0ViI+RY3w5dAjQI
    62zCSj/DXaLEwYGNbqVcwjlos5STdoxFqRHpHf6hLCZSNjUaIqY19n0U0qTs6Hw4
    WuRURrbMLJYVEgiZpRynmMPnwQ+1USQ1MV6MevboXeJ08lHoDYkAlQIFEDM9HqMi
    iRpDQSB+5QEBHJYD/0/VRUy8EAZdjjzx/82+zUJmen9rRI3EQtd+kzInP9V13ZG5
    qFFihznQJukXX9A53g9l4RbZo1P+yHF+bdD3OnEbPIWDL/+0Rd3DZp53N1Pigw6A
    MGoyvNzYt83zNaoXlxYksBIirBusiSbJlHotQLGYTv1aaBGVAYAd8zDALdYtiQA/
    AwUQM4KBc4I3FG4quJ9UEQLr0QCdFQDsbIKVKU6f5olwRSACnq/YtJoAnig/jD9Q
    c8CVTPsw++ok1kWZeqXViQCVAwUQM4J+6pfboLn8NWjNAQGTigQAnrFZ8OiAguWq
    i1LsClKo0t9y+Ly98EPnpBt2FgQN9/Z8PSZjPqEn9AJk7Z5TBhGJNXBmkULiuNA9
    zvGTsRM0S7Oi6/WFUcL9rio6gMsxTnDythGaFa5YDQXgXtFxqcjsojGhe922KFnV
    i4xxatO9vm9Zo3JaNAK8zvg2rIrd7VSJAJUDBRAzgn8PsF+MkGb7jGUBAYbmBACV
    tqTdmo9Zu/e9hpEL1FQXnp1qzKilzchxf+9/mBmbCy6O/QKVkdUTptkYMVyUHh0q
    1KJV4caZIx3vQyeRsK7Fe5vex38LzN9lcP99lOE9Y8nns1bwaiUONe1McWEtkEkG
    SMi3FaIxRCb4f5ENjRV8EzydQbHD5+Pyp0+gw9LuXIkBFQMFEDOC1g34yQH5HnUh
    EwEBoHAH/RDpelRJCSEtRC7upHwGbfuZL3RhlgXomiOL5plSn2i2El7hm1k1UKcG
    UHvcz1ni2deWRK/qLle9xN8wXIjZMATWJLfeSoSpZoq8yFKdN+r2fkpwyN4h6hmb
    SI0DBm73eiO7cIRgxszpQDnI5uhTp083JUX/dtFlBMtr/XsIBfg6PN6pYYIAZ1cn
    pqkKHHFpdJe3+/AIHzw53nJUKm8EX+Bui1EOfljB63U6oP+Q1F3Wo0C1PaN/9Hbo
    3IkVSLC1i3JUQwjh0moFuB+ZeLUFTxBwp+F2Y1AcvQT6JJW529WPTXOvfT2/+wU7
    uVaynaHMum8snzPWMr5v0dQbq+6+OPU=
    =leOK
    -----END PGP PUBLIC KEY BLOCK-----

    [3]

    Type Bits/KeyID    Date       User ID
    pub  2048/86B519BD 1998/09/10 Adam Back <aba@dcs.ex.ac.uk> (FS key, Sep 98)

    -----BEGIN PGP PUBLIC KEY BLOCK-----
    Version: 2.6.3i

    mQENAzX3ILwAAAEIAL368F4iaAlWFsXFUXdgSttJaHpjcLXmqZP93FlhQRyhSco6
    6wyTWEa0UQ25ynf/r/sh4Z7/xjD+HSUUCnpLDJnN9143JUO1UbDIGTq3vC+uKJjr
    1OnZQMI0SOrpdUUvbz9zyC2Zsj+CACGbX+sFpecT/XxMpSeEbfoNoy5+AWjB7eIa
    27qloHFGRZrDfFvewaSybck21PGVEwkTrpBQ4Yf1RGDod+Xe079jq79uZNNDgnTN
    UaFXFS0BmH0nJmjWE5/QkNsgy0aPuFcR65TKn54Fj7e82g1ScEYlwS3iRBuebpAU
    pH81flyI4qr9dvBatcpQXut+PxXT+mQxbIa1Gb0ABRO0LUFkYW0gQmFjayA8YWJh
    QGRjcy5leC5hYy51az4gKEZTIGtleSwgU2VwIDk4KYkBFQMFEDX3IQ0+e8qoKLJF
    UQEBhH4H/3u1USAlPwbGPMfMwZwBU4uCm6EPf03LKgtGa/elSn8nvrSbRrvLVdnQ
    aQWJBQpLegUkDlrd0LG9guGdaEJxJ3pZteeaDuC9WeHJWBuUbiyrNooTk7QGeVM1
    9yTAW9zaHW/NpXSYL45XfHYuYrKiX50gAY+CSc3rE4Ei++R0gTAwRnS9JkKqsdzP
    CJThyy+ppteG5d7aw8L26AQQGUvcZKR3wTvGpGAfU6bZo1gmvnloSYelbxvUfkq2
    ybHBZWXj7iBRPwTT6przBVp3DaCm8/gOzUBxvJZkoDsbf/iVBX/Qf8sVGq/86ksB
    /JmE7cAVNveJ+a9wx4kTNVmjP7Aciao=
    =vpQX
    -----END PGP PUBLIC KEY BLOCK-----

    Date: Sat, 19 Sep 1998 23:28:19 +0100
    From: Adam Back <aba@dcs.ex.ac.uk>
    To: cypherpunks@cyberpass.net
    Subject: Re: CHALLENGE? Toto/signature attack w. unpublished public key

    Anonymous writes:

    > > So next we would like to solve:
    > >
    > >         s ^ e mod n = m
    > >
    > > or in other words find e, k and n st:
    > >

    > >         s ^ e - m = k * n
    >
    > In addition it has to be that n is the right length based on the "s"
    > padding.  This limits it to an 8 bit range, in this case 1024-1031
    > bits.

    The constraint I gave was that log(n) = 1024.  Bear in mind that the
    msbyte of s = 0x08, so we know that n > s, and I think we know that n
    < 2^1024 also based on the s padding from the signature. So based on
    this n would be in the range 1020 - 1024 bits, right?

    > If you make n be a product of a bunch of small primes, so that you
    > can make signatures with it, then a third party can detect this and
    > know it is bogus.

    He has to factor your n to determine that it is bogus though?  This
    would imply that he had more compute than you do.  (Not unreasonable
    threat model mind).

    > Also, this approach won't match the keyid of the original signature.

    Agree.  Weak counterpoint is that the keyid is not authenticated,
    though if IRS have a key, they know it's keyid, and if that keyid is
    the one posted (unauthenticated inside the armor 0xCE56A4072541C535),
    this tips the probability of authorship towards the key they have.

    This though is perhaps not incontroverible proof, if one posits that
    Toto or unknown others were trying to create a complicated mess for
    people to confuse themselves analysing.

    Evidence suggests that this was/is the case: there are other messages,
    for example one with a signature with what is perhaps a 0xdeadbeef
    attack against a key on the keyservers, with the same 32 bit keyid,
    but a 64 bit key id differing by 1 bit.  Another key which almost but
    not quite makes sense to PGP (a few bits twiddled).  Plus lots of
    still undecrypted encrypted messages posted to the list, plus possibly
    stegoed images posted (one image was posted together with a password
    which was also publically posted together with instructions for
    recovering using S-TOOLS4.ZIP (a stego package for windows), and lots
    of other anonymously and pseudonymously posted images.)

    (One of the encrypted keys which passphrases were forwarded to the
    list for just today had been posted to the list over a year ago --
    Carl Johnson couldn't have posted the passphrase because he is
    incarcerated).

    > Another approach is to generate an n such that the discrete logarithm
    > is solvable mod n.  Then you can solve for e in s^e = m mod n, with
    > the base of the discrete log being s.  Doing this you can match the
    > keyid and size of n without too much difficulty.

    Yes!  Excellent.  This construct (discrete logs over composite modulus
    to allow the same operation) is used by the identity based crypto
    people.  The trap door is not that good, because 512 bit discrete logs
    are as you suggest rather expensive to compute.

    > Unfortunately e will not be small; it will be about the same size as n.
    > There are one or two keys on the public keyring which have large e's,
    > apparently generated by hacked versions of pgp.  Some people feel
    > safer with random e than a small e.  So this could perhaps be accepted.

    It's not a hacked version of PGP, I've generated such keys myself
    also: it is just a lesser documented feature of pgp2.x, (pgp -kg 1024
    768) would give you a 1024 bit n and a 768 bit e).

    > (OTOH given two keys that both sign the same message, one with a small
    > e and one with a large one, it is obvious that the first is the legit
    > one and the second is the cloned one.)

    Not so obvious with the other key tinkering which has been going on
    here.  It seems likely that Toto et al were purposefully trying to sow
    confusion, and seem to delight in leaving little clues to people
    trying to understand it looks like this strategy has been operational
    for over a year now (some of the encrypted messages which passphrases
    were forwarded to the list for just today had been posted to the list
    over a year ago -- Carl Johnson couldn't have posted the passphrase
    because he is incarcerated).

    > Unfortunately with a 1024 bit RSA modulus it is not going to be
    > feasible to solve 512 bit discrete logs using a reasonable amount
    > of effort.  However by using more factors in the RSA modulus it should
    > become practical.  The number of factors needed will depend on how much
    > resources you have to work on the discrete log.

    Resources available: one low end pentium based linux PC? :-) Just that
    the attack is clearly feasible is interesting though a demonstration
    would be perhaps more convincing to less technically aware IRS people.
    The biggest resource overhead is implementing that lot though, unless
    there exist packages or libraries which already do most of it for you.

    > Once you have your n and e you can sign other messages with the key.
    > The n looks OK from outside because the fact that it has more than two
    > factors is not detectable, as long as its factors are not too small.
    > Actually there may be a way of distinguishing n's with two factors from
    > n's with more, check into this.
    >
    > Also check into whether n's of this form can be factored via a p-1
    > factoring attack.  It may be that making the discrete log easy also makes
    > the modulus factorable.

    I think the answer to that is yes.

    In connection with previous discussions of implementing forward
    secrecy using identity based crypto (search archives for cypherpunks /
    coderpunks /cryptography for posts with

    Subject: non-interactive forward secrecy / identity based crypto

    ) another Anonymous describes some of the identity based crypto papers
    on this topic, which suggests another method of being able to compute
    discrete logs mod composite n.

    : Maurer describes an alternative set of parameters as well.  Rather than
    : choosing small primes for the discrete logs, larger primes with a
    : special form are used which make the problem easy.  This is based on the
    : Pohlig-Hellman discrete log algorithm, which applies when p-1 has all small
    : factors.  The problem is that there also exists a p-1 factoring algorithm
    : which works when p-1 has all small factors.  However the former algorithm
    : costs the square root of the size of the factors, while the later takes
    : work proportional to the size of the factors themselves.  This gives a
    : window where the discrete log can be done but the factoring will fail.

    :
    : For this embodiment, Maurer suggests a modulus which is the product of
    : two primes, each 100 digits (333 bits) in length.  This will produce
    : a 666 bit modulus.  Have each of the primes be such that (p-1)/2 is a
    : product of several 13-15 digit (43-50 bit) primes.

    So it could be done, I think, and in such a way that you have lower
    cpu overhead than the attacker trying to prove one key more likely
    than the other.

    Adam

    Date: Sat, 19 Sep 1998 22:39:19 +0100
    From: Adam Back <aba@dcs.ex.ac.uk>
    To: cypherpunks@cyberpass.net
    Subject: (fwd) Re: CHALLENGE? Toto/signature attack w. unpublished public key

    [I thought I posted the post Anonymous is replying to to cypherpunks &
    cryptography.  He however seems to have followed up to coderpunks.]

    Here [1] is a suggestion from Anonymous which sounds technically good,

    an improvement over my approach to finding additional keys capable of
    signing the message, it shows that quite plausibly one could generate
    another key which could have signed the message in question.

    Hope Carl Johnson can get a technical expert with enough smarts to
    understand the below, and express this if it is necessary.

    Adam

    [1] Forwarded message from coderpunks:
    ======================================================================
    Date: Sat, 19 Sep 1998 21:48:07 +0200
    From: Anonymous <nobody@replay.com>
    Comments: This message did not originate from the Sender address above.
    	It was remailed automatically by anonymizing remailer software.
    	Please report problems or inappropriate use to the
    	remailer administrator at <abuse@replay.com>.
    Subject: Re: CHALLENGE? Toto/signature attack w. unpublished public key
    To: coderpunks@toad.com
    Sender: owner-coderpunks@toad.com
    Precedence: bulk

    A very interesting problem...

    Adam Back writes:

    > This post discusses the possibility of generating a RSA public key n,
    > and e given a signature s on a message m creating using an unknown
    > (unpublished) n and e.  A message and signature whose validity has
    > some bearing on a current IRS investigation is given as a target for
    > an attack if such an attack is feasible.
    > [...]
    > So next we would like to solve:
    >
    >         s ^ e mod n = m
    >
    > or in other words find e, k and n st:
    >
    >         s ^ e - m = k * n

    In addition it has to be that n is the right length based on the "s"
    padding.  This limits it to an 8 bit range, in this case 1024-1031 bits.

    There are two approaches here.  First, the one you are doing: try
    different e values and factor s^e - m until you find one which looks
    like it could be a plausible k * n.  The problem is that n is supposed
    to be the product of two large primes, and if it is, you won't be able
    to factor it.  So you might be able to create a public key which looks
    reasonable, but you can't create a private key which does, one which is
    a multiple of two large primes.  If you make n be a product of a bunch
    of small primes, so that you can make signatures with it, then a third
    party can detect this and know it is bogus.

    Also, this approach won't match the keyid of the original signature.

    Another approach is to generate an n such that the discrete logarithm
    is solvable mod n.  Then you can solve for e in s^e = m mod n, with
    the base of the discrete log being s.  Doing this you can match the
    keyid and size of n without too much difficulty.

    Unfortunately e will not be small; it will be about the same size as n.
    There are one or two keys on the public keyring which have large e's,
    apparently generated by hacked versions of pgp.  Some people feel
    safer with random e than a small e.  So this could perhaps be accepted.
    (OTOH given two keys that both sign the same message, one with a small
    e and one with a large one, it is obvious that the first is the legit
    one and the second is the cloned one.)

    If you know the factorization of the size of the exponentiation group mod
    n, and all the factors are small enough, you can solve the discrete log
    problem mod n.  You solve the discrete log separately for each factor
    and then combine the results.  With an RSA modulus, the group order is
    LCM(p-1,q-1), or equivalently (p-1)(q-1)/GCD(p-1,q-1).  If you were able
    to solve discrete logs mod p-1 and q-1 then you could solve discrete
    logs mod n.

    Unfortunately with a 1024 bit RSA modulus it is not going to be
    feasible to solve 512 bit discrete logs using a reasonable amount
    of effort.  However by using more factors in the RSA modulus it should
    become practical.  The number of factors needed will depend on how much
    resources you have to work on the discrete log.

    Once you have your n and e you can sign other messages with the key.
    The n looks OK from outside because the fact that it has more than two
    factors is not detectable, as long as its factors are not too small.
    Actually there may be a way of distinguishing n's with two factors from
    n's with more, check into this.

    Also check into whether n's of this form can be factored via a p-1
    factoring attack.  It may be that making the discrete log easy also makes
    the modulus factorable.

    Date: Sun, 20 Sep 1998 07:02:05 +0200
    From: Anonymous <nobody@replay.com>
    Subject: Re: CHALLENGE? Toto/signature attack w. unpublished public key
    To: cypherpunks@cyberpass.net

    > > In addition it has to be that n is the right length based on the "s"
    > > padding.  This limits it to an 8 bit range, in this case 1024-1031
    > > bits.
    >
    > The constraint I gave was that log(n) = 1024.  Bear in mind that the
    > msbyte of s = 0x08, so we know that n > s, and I think we know that n
    > < 2^1024 also based on the s padding from the signature. So based on
    > this n would be in the range 1020 - 1024 bits, right?

    Actually there is somewhat more flexibility than this.  You made up the
    padding, it didn't come from the file, did it?  You could add perhaps 1
    more byte of FF without stretching credibility too extremely.  Then n
    could be 1020 - 1032 bits.  It's too bad that s started out so small
    (assuming the "true" n was 1024 bits).

    > > If you make n be a product of a bunch of small primes, so that you
    > > can make signatures with it, then a third party can detect this and
    > > know it is bogus.
    >
    > He has to factor your n to determine that it is bogus though?  This
    > would imply that he had more compute than you do.  (Not unreasonable
    > threat model mind).

    But didn't YOU have to factor n also?  That's what you showed, originally,
    a large s^e which you factored down to get some small factors and a big
    one.  If you manage to get a prime factorization you can combine factors
    to get your n.  But it won't be any harder for him to factor than it was
    for you.

    > Resources available: one low end pentium based linux PC? :-) Just that
    > the attack is clearly feasible is interesting though a demonstration
    > would be perhaps more convincing to less technically aware IRS people.
    > The biggest resource overhead is implementing that lot though, unless
    > there exist packages or libraries which already do most of it for you.

    The discrete log algorithm is similar to quadratic sieve and other modern
    factoring algorithms.  You do multiple factorizations of other numbers
    and combine them to generate the desired relationships.  The difference
    is that the factor base is not just the primes, it uses special numbers.

    There was a break a few years ago of the discrete log modulus being
    used by Sun's RPC.  This was something like 200-300 bits.  Maybe that
    discrete log code could be obtained from the authors.

    Date: Sun, 20 Sep 1998 09:36:42 +0100
    From: Adam Back <aba@dcs.ex.ac.uk>
    To: cypherpunks@cyberpass.net
    Subject: Re: CHALLENGE? Toto/signature attack w. unpublished public key

    Anonymous writes:
    > > > In addition it has to be that n is the right length based on the "s"
    > > > padding.  This limits it to an 8 bit range, in this case 1024-1031

    > > > bits.
    > >
    > > The constraint I gave was that log(n) = 1024.  Bear in mind that the
    > > msbyte of s = 0x08, so we know that n > s, and I think we know that n
    > > < 2^1024 also based on the s padding from the signature. So based on
    > > this n would be in the range 1020 - 1024 bits, right?
    >
    > Actually there is somewhat more flexibility than this.  You made up the
    > padding, it didn't come from the file, did it?

    I used PGP to make an m to match a 1024 bit n which I presumed from a
    1024 bit s; s is from the signature packet from the signed post in
    question.  I made the assumption that for a 1024 bit s, the padded
    message digest m would be of size 1024 bit also, with it's leading 00
    01 FF ... FF etc.

    > You could add perhaps 1 more byte of FF without stretching
    > credibility too extremely.  Then n could be 1020 - 1032 bits.  It's
    > too bad that s started out so small (assuming the "true" n was 1024
    > bits).

    I see what you are saying: that if n had been even 1032 bits, it would
    still be possible (though relatively unlikely) to result in a s <
    1024, which would mean that the m I presumed could have had been a
    byte longer.  I think your assumption that PGP would not encode the
    leading 0 byte (in the s) is correct, from past PGP code tinkering.
    In fact I guess that actually this statement generalises and (with an
    even smaller probability) the n could have been 1040 bits, and the s
    just happened to come out < 1024 bits, and so on.

    I'll see if I can induce this effect by generating a 1025 bit key, and
    seeing if any of the signatures come out at 1024 bits:

    n =	0x0181291263B847EBEBFDC65E9128DDE9015522B461618F43CDBBF3D707507BA9
    	  A71B002F4F852EEC1465710B1641C8816D3E0851C41C2A11E89062E424116A69
    	  6E0FB179C7439C6C2F88A214E8D9877658A82982783FA5597262D6CD648111EB
    	  A3AB12FC9EB71FB90222624D188E31A3B3333020740860E5F11250D10E2E61F77D
    e =	0x11
    s =	0x5AA544A471AA79074796D0C85BE01DF44BBED7F14C1189D2D114F8A4E9D4D20E
    	  1E67ED9CFA8E20F4D9B84B9C82918F5721D984C7D3A2E2561D399982DFD38873
    	  3665745849F83EA14A2D2D586CCB253515E63CF81E2C3927D991E25FAE673DEC
    	  E18DB2F6014850CE97F2910393166577F120C4A9512B122F47E05FB117702D6B

    So yes, n = 1025 bits, and this particular s is 1023 bits, and this
    one is 1025 bits:

    s' =	0x012B4B5218E1173DCEF5525C3E9E72BA962371372DA9E9D8D1B469A3BD1060E1
    	  5F0ABA0E0BD9B497944FA9AE039F7F006591470857E0CB4FCB460485307A4366
    	  54105112BD2E548B6BA9E6B950BC37D39A51ADC169B34935D052DFEEEA9A9FFC
    	  BEA4D85BF22D87D66BCB3530EE5316F22A4A4BC4FAB33E592B019E87DE1EAB7336

    (most of them work out to be < 1025 bits).

    > > > If you make n be a product of a bunch of small primes, so that you
    > > > can make signatures with it, then a third party can detect this and
    > > > know it is bogus.
    > >
    > > He has to factor your n to determine that it is bogus though?  This
    > > would imply that he had more compute than you do.  (Not unreasonable
    > > threat model mind).
    >
    > But didn't YOU have to factor n also?  That's what you showed, originally,

    > a large s^e which you factored down to get some small factors and a big
    > one.  If you manage to get a prime factorization you can combine factors
    > to get your n.  But it won't be any harder for him to factor than it was
    > for you.

    Yes, you are right.

    Presented with two public keys (n,e), and (n',e') and a signature s,
    that even if the attacker manages to factor n but not n' the attacker
    can't prove that there isn't another public key (n'',e'') which is the
    real key which signed the message.  Ie the reason the attacker is
    unable to factor (n',e') may be either because it is a multiple of two
    512 bit primes, or because it is a mutliple of primes of special form
    I quoted a post describing in the other post, and he doesn't have
    enough compute to recover it.  With the quoted algorithm from Maurer,
    the attacker needs more compute to show that the key has a special
    form than you do to create the key.

    Adam

    Date: Mon, 21 Sep 1998 13:17:29 +0200
    From: Anonymous <nobody@replay.com>
    To: cypherpunks@einstein.ssz.com

    ...

          some of the internal key-IDs have been modified. however, both
          versions should have been posted in various 'true' messages. No
          information if some of the false messages were ever encrypted
          with the key twiddles in hidden 32 bits, but probably not.

    ...

    Date: Tue, 22 Sep 1998 03:08:09 +0200
    From: Anonymous <nobody@replay.com>
    Subject: Re: CHALLENGE? Toto/signature attack w. unpublished public key
    To: cypherpunks@cyberpass.net

    This value is wrong: it has 3 bytes of 0's inserted and is therefore
    missing the last three bytes of the signature.

    s =   0x08F4D5CBC10063725B206F787EB7370BBD0C5B4854CE79A9007D1801AEAEE6E6
            D2C68D7EDF877FECE1FA539D08BEC54BD152BA05113951E8A84CDECAD2CB8E7A
            C28BE916570BA7BB9C00C64DF57113C4AE81613BD351541523CD3A028FBF220E
            F7469BD4175302DCB5B6E886974877F28A2D301433AFFFE26081008BFF687B37

    Here is the correct value, from the signed message.

    08F4D5CBC10063725B206F787EB7370BBD0C5B4854CE79A97D1801AEAEE6E6D2
    C68D7EDF877FECE1FA539D08BEC54BD152BA05113951E8A84CDECAD2CB8E7AC2
    8BE916570BA7BB9CC64DF57113C4AE81613BD351541523CD3A028FBF220EF746
    9BD4175302DCB5B6E886974877F28A2D301433AFFFE260818BFF687B37DE8167

    Date: Tue, 22 Sep 1998 19:57:09 +0100
    From: Adam Back <aba@dcs.ex.ac.uk>
    To: cypherpunks@cyberpass.net
    Cc: shoulson@cs.columbia.edu
    Subject: pgpacket bug (Re: CHALLENGE? Toto/signature attack w. unpublished public key)

    Anonymous writes:
    > This value is wrong: it has 3 bytes of 0's inserted and is therefore
    > missing the last three bytes of the signature.
    >
    > s =   0x08F4D5CBC10063725B206F787EB7370BBD0C5B4854CE79A9007D1801AEAEE6E6
    >         D2C68D7EDF877FECE1FA539D08BEC54BD152BA05113951E8A84CDECAD2CB8E7A
    >         C28BE916570BA7BB9C00C64DF57113C4AE81613BD351541523CD3A028FBF220E
    >         F7469BD4175302DCB5B6E886974877F28A2D301433AFFFE26081008BFF687B37
    >
    >
    > Here is the correct value, from the signed message.
    >
    > 08F4D5CBC10063725B206F787EB7370BBD0C5B4854CE79A97D1801AEAEE6E6D2
    > C68D7EDF877FECE1FA539D08BEC54BD152BA05113951E8A84CDECAD2CB8E7AC2
    > 8BE916570BA7BB9CC64DF57113C4AE81613BD351541523CD3A028FBF220EF746
    > 9BD4175302DCB5B6E886974877F28A2D301433AFFFE260818BFF687B37DE8167

    Hmm!  That explains this output of pgpacket which I had already
    forwarded to Mark Shoulson as a bug in pgpacket:

    % pgpacket < totopost.asc
    ---------------------------
    Packet Type:    Secret-Key Encrypted Packet (signature)
    Length: 149
    Version:        3
    Adding 5 bytes of header to digest
    Signature of canonical text document
    Signature Created:      9 Dec 1997  21:29:02
    Signing Key ID: 0xCE56A4072541C535
    Public Key Algorithm:   1 (RSA)
    Message Digest Algorithm:       1 (MD5)
    Check bytes:    0x5A82
    128 bytes of data (1)
    Data:   08F4D5CBC10063725B206F787EB7370BBD0C5B4854CE79A9007D1801AEAEE6E6D2C68D7E
    DF877FECE1FA539D08BEC54BD152BA05113951E8A84CDECAD2CB8E7AC28BE916570BA7BB9C00C64D
    F57113C4AE81613BD351541523CD3A028FBF220EF7469BD4175302DCB5B6E886974877F28A2D3014
    33AFFFE26081008BFF687B37

    ---------------------------
    Packet Type:    UNKNOWN PACKET!! (36)
    Length: 129
    (No handler known.  Skipping 1 bytes)
    Data:   0x67

    I couldn't figure out what the spurious packet was about, you just
    solved that one... pgpacket is inserting spurious 00s in the message.
    (I've Cc'ed Mark Shoulson).

    Adam

    Date: Tue, 22 Sep 1998 08:01:07 +0200
    From: Anonymous <nobody@replay.com>
    Subject: CHALLENGE response
    To: cypherpunks@cyberpass.net

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

    mQEMAzJEMpEAAAED/0jftmc14q6/r/pGe61N+QymMfQlUdrMNWSl9n9wnst1BGft
    /GztVfzwS5QDPc2vAvCJjeYFBj60BbJpILMC6rGH7pnc/GFcQjQDUJzHfGHASkDl

    2jvDbzG8f7I5oM6NAC5thtjmMoe9FasHMW+lQ3B3IFNSFgIULM5WpAclQcU1A/0S
    K/k9FEU/SX93bC3SqTwwdaW9bvksN6Tqs8YSmVcRCoCAQQrTB9i0I+1y86gA9DnC
    UR0EuvalZ54+g/+4G0TOqLVoeSXYhyktqwrIFmwDyK3RPEU6OkwxzlBALNvEKzKB
    SsdTm7J6O+jg56yEI3YyyBJM6N+zKvmm7DGB8I2+IbQKVG90bywgdG9vP4kAlQMF
    EDYHKcPOVqQHJUHFNQEB7RID/0H14HGr6lB8bqWCxoZfoZ97oHFEURrYVxOGb5MP
    ZOOEKCk5d/Q/9d0D0imSZRrV6EQRsiuhA9d0LQy0DuLQC3/NguKFK0Z3fY9gT8/q
    xV9JJmmoYTjSEDke0RfexfvNDuOa9aISVxndwYGkkYlUcsZBmOeo1OKPdhWCLbnI
    CsB7
    =cutG
    -----END PGP PUBLIC KEY BLOCK-----

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

    Interested readers may want to verify that the key above does give a
    valid signature when applied to the message below.

    (It will be necessary to remove any existing key with keyid 0x2541C535
    before this key can be added to the keyring.)

    -----BEGIN PGP SIGNATURE-----
    Version: 2.6.2

    iQCVAwUBNgcq+c5WpAclQcU1AQHnZQP+NrThyaPmy8BDw21geFB3B1s59QJJ4Ycs
    i1yqu9p6NZfb6qD2pF8AnOSOUMA3KCs98fKMJU9S9TN9eTk5DRbIvXHHSdhMRhuw
    qDlmcpy4HggT9yHK0vjOTm6UUR/xkvt0WCheAQEe9ZeshFyPa5BAJ7Sqy2dcI1Xv
    X3DzB5pn2yk=
    =SmV7
    -----END PGP SIGNATURE-----

    [Snip PGP signed message given above.]

    Date: Tue, 22 Sep 1998 23:41:21 +0100
    From: Adam Back <aba@dcs.ex.ac.uk>
    To: nobody@replay.com
    CC: cypherpunks@cyberpass.net
    Subject: Re: CHALLENGE response

    Kudos anonymous!

    What form are your primes (did you use Maurers idea to increase the
    relative hardness of factoring compared to discrete log, or did you
    just use more smaller primes?)  How many primes have you used, and how
    many CPU hours did it take to calculate the discrete log to discover e?

    Also is the code for finding discrete logs given the prime
    factorisation of the modulus available?

    Obvious counter-measures to this attack on a persistent anonymous
    identity are to post more than one signature, or to sign the public
    key (as would happen with a self signed PGP public key).

    I am left wondering if there are implications of this demonstration
    for other protocols (*) involving RSA signatures, where one signed
    message is observed before the key is obtained.

    - For example, the general case of receiving a message signed by
    someone, not having the public key, and looking up the public key on a
    key server by keyid (as pgp5.x, and some pgp2.x mail interfaces
    automate).  With an anonymous individual (and with many peoples keys
    where they have poor connection in the web of trust) all you are
    aiming to do is to send a message to the author of a given message.
    With this attack an attacker who could intercept the key server
    lookup, and return an alternate public key with associated
    certificates which would match the signature.
    Are there other protocols where this attack would have implications?

    Adam

    (* Toto's impromptu 'protocol' was publishing one signature only, and
    then having his machine seized containing the public (and private?)
    keys which arguably created the signature).  The result of the
    identity attack is that Toto's (currently unwanted) proof of
    authorship has been called into question.

    Date: Wed, 23 Sep 1998 03:00:57 +0200
    From: Anonymous <nobody@replay.com>
    Subject: Re: CHALLENGE response
    To: cypherpunks@cyberpass.net

    > What form are your primes (did you use Maurers idea to increase the
    > relative hardness of factoring compared to discrete log, or did you
    > just use more smaller primes?)  How many primes have you used, and how

    > many CPU hours did it take to calculate the discrete log to discover e?

    N is the product of two primes, but each p-1 has about 16 small prime factors
    (about 25-35 bits) to allow calculating the discrete log efficiently.  With
    this choice of primes it took about three hours to run the discrete log.

    > Also is the code for finding discrete logs given the prime
    > factorisation of the modulus available?

    Here you go.  This uses cryptolib by Jack Lacy of AT&T (not to be
    confused with cryptlib by Peter Gutmann), available from

    ftp://ftp.funet.fi/pub/crypt/cryptography/libs/cryptolib_1.1.tar.gz

    /* Calculate discrete log using various algorithms */
    /* Algorithms based on Handbook of Applied Cryptography by Menezes et al */

    #include "libcrypt.h"

    /* Modular multiplication - m1*m2 mod n */
    static void
    bigMultiplyN (BigInt m1, BigInt m2, BigInt n, BigInt result)
    {
        BigInt tmp = bigInit(0);
        bigMultiply (m1, m2, tmp);
        bigMod (tmp, n, result);
        freeBignum (tmp);
    }

    /* Modular addition, m1+m2 mod n */
    static void
    bigAddN (BigInt m1, BigInt m2, BigInt n, BigInt result)
    {
        bigAdd (m1, m2, result);
        if (bigCompare (result, n) >= 0)
            bigSubtract (result, n, result);
    }

    /* Iterate the pollard rho.  Modify x, a, b with next values */
    static void
    prhoiter (BigInt base, BigInt val, BigInt mod, BigInt order,
        BigInt *x, BigInt *a, BigInt *b)
    {
        int xgroup;

        /* First decide what group x is in */
        /* This is a cheat to be fast */
        xgroup = ((unsigned)(*x)->num[0]+1) % 3;

        switch (xgroup) {
        case 0:
            bigMultiplyN (*x, val, mod, *x);
            bigAddN (*b, one, order, *b);
            break;
        case 1:
            bigMultiplyN (*x, *x, mod, *x);
            bigAddN (*a, *a, order, *a);
            bigAddN (*b, *b, order, *b);
            break;
        case 2:
            bigMultiplyN (*x, base, mod, *x);
            bigAddN (*a, one, order, *a);
            break;
        }
    }

    /* Pollard rho algorithm for discrete log */

    BigInt
    pollardrho (BigInt base, BigInt val, BigInt mod, BigInt order)
    {
        BigInt
            x = bigInit(1),
            a = bigInit(0),
            b = bigInit(0),
            x2 = bigInit(1),
            a2 = bigInit(0),
            b2 = bigInit(0);
        int cnt = 0;

        for ( ; ; ) {
            prhoiter (base, val, mod, order, &x, &a, &b);
            prhoiter (base, val, mod, order, &x2, &a2, &b2);
            prhoiter (base, val, mod, order, &x2, &a2, &b2);
            if (bigCompare (x, x2) == 0)
                break;
            if (++cnt % 1000 == 0) {
                printf ("%d\r", cnt);
                fflush (stdout);
            }
        }
        if (cnt >= 1000)
            printf ("\n");

        if (bigCompare (b, b2) < 0)
            bigAdd (order, b, b);
        bigSubtract (b, b2, b);
        if (bigCompare (a2, a) < 0)
            bigAdd (order, a2, a2);
        bigSubtract (a2, a, a);

        if (bigCompare (b, zero) == 0) {
            printf ("Pollard rho failed\n");
            exit (1);

        }
        getInverse (b, order, b2);
        bigMultiplyN (a, b2, order, a);
        return a;
    }

    /*
    * Do the CRT with multiple congruences.  congs are the values that the
    * answer should be congruent to, mods are the moduli for each congruence.
    * n tells how many in each array.
    */
    static BigInt
    crtmult (BigInt congs[], BigInt mods[], int n)
    {
        int i;
        BigInt prod = bigInit(0);
        BigInt prod1 = bigInit(0);
        BigInt sum = bigInit(0);
        BigInt quot = bigInit(0);
        BigInt rem = bigInit(0);
        BigInt dum = bigInit(0);
        BigInt inv = bigInit(0);
        BigInt term = bigInit(0);

        /* Compute product of moduli */
        bigCopy (one, prod);
        for (i=0; i<n; ++i) {
            bigMultiply (prod, mods[i], prod1);
            bigCopy (prod1, prod);
        }

        for (i=0; i<n; ++i) {
            bigDivide (prod, mods[i], quot, dum);
            bigDivide (quot, mods[i], dum, rem);
            getInverse (rem, mods[i], inv);
            bigMultiplyN (congs[i], quot, prod, term);
            bigMultiplyN (term, inv, prod, term);
            bigAddN (term, sum, prod, sum);
        }

        return sum;
    }

    /* Pohlig-Hellman discrete log algorithm for composites */
    /* Return the exponent such that base^exponent == val modulo mod. */
    /* Group order is product of factors[], of which there are n */
    /* Assume each factor is to the first power */

    BigInt
    phlog (BigInt base, BigInt val, BigInt mod, BigInt factors[], int n)
    {
        BigInt
            prod = bigInit(0),
            prod1 = bigInit(0),
            exp = bigInit(0),
            dum = bigInit(0),
            b = bigInit(0),
            v = bigInit(0);
        BigInt *dlogs;
        BigInt dl;
        int i;

        dlogs = (BigInt *) malloc (n * sizeof (BigInt));

        /* Compute product of factors to get group order */
        bigCopy (one, prod);
        for (i=0; i<n; ++i) {
            bigMultiply (prod, factors[i], prod1);
            bigCopy (prod1, prod);
        }

        /* Sanity check */
        bigPow (base, prod, mod, b);
        if (bigCompare (b, one) != 0) {
            printf ("Inconsistency in group order on b\n");
            fBigPrint (b, stdout);
        }
        bigPow (val, prod, mod, v);
        if (bigCompare (v, one) != 0) {
            printf ("Inconsistency in group order on v\n");
            fBigPrint (v, stdout);
        }

        for (i=0; i<n; ++i) {
            bigDivide (prod, factors[i], exp, dum);
            bigPow (base, exp, mod, b);
            bigPow (val, exp, mod, v);

            printf ("Trying dlog with factor: "); fBigPrint (factors[i], stdout);
            printf ("b: "); fBigPrint (b, stdout);
            printf ("v: "); fBigPrint (v, stdout);

            /* Special case for 2, pollardrho doesn't work too well on it */
            if (bigCompare (factors[i], two) == 0) {
                if (bigCompare (b, v) == 0) {
                    dlogs[i] = bigInit(1);
                } else if (bigCompare (v, one) == 0) {
                    dlogs[i] = bigInit(0);
                } else {
                    printf ("Inconsistent b, v for factor == 2\n");
                    exit (1);
                }
            } else {
                /* Now find log of v mod b, has group order factors[i] */
                dlogs[i] = pollardrho (b, v, mod, factors[i]);
            }

            printf ("dl: "); fBigPrint (dlogs[i], stdout);
            bigPow (b, dlogs[i], mod, b);
            if (bigCompare (b, v) != 0) {
                printf ("Error in discrete log calc!\n");
                exit (1);
            }
        }

        /* Combine results with CRT */
        dl = crtmult (dlogs, factors, n);

        return dl;
    }