CHALLENGE? Toto/signature attack w. unpublished public key

[Adam Back]

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