From: Adam Back <aba@dcs.ex.ac.uk>
Date: Tue, 22 Sep 1998 18:15:31 +0800
To: nobody@replay.com
Subject: Re: CHALLENGE response
In-Reply-To: <199809220601.IAA30078@replay.com>
Message-ID: <199809222241.XAA11854@server.eternity.org>
MIME-Version: 1.0
Content-Type: text/plain




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.