(fwd) Re: CHALLENGE? Toto/signature attack w. unpublished public key

[Adam Back <aba@dcs.ex.ac.uk>]

[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.