From: hughes@ah.com (Eric Hughes)
Date: Tue, 8 Feb 94 00:06:46 PST
To: cypherpunks@toad.com
Subject: Magic Money coins
In-Reply-To: <199402080633.WAA27612@jobe.shell.portal.com>
Message-ID: <9402080759.AA00803@ah.com>
MIME-Version: 1.0
Content-Type: text/plain


>I was thinking over the attack I described on Magic Money and Chaum
>cash, and I now think it will not actually work, especially in the case
>of the Chaum cash.  

Well, with Chaum's signature pairs of the form <x,f(x)^(1/e)>, you'd
still have to calculate some inverse value of a one-way function.

On he other hand, Hal says that his attack against MM coins doesn't
work.  That's OK, as far as it goes.

The problem is really quite general.  Given a set of signatures on the
same modulus, how can one calculate signed values of a particular
sort?  In the proceeding, let { < a_i, a_i^(1/e) > } be the set of
signatures one has, e the public key, n = pq the modulus, S the set of
acceptable signed elements.

Note that the product of any two signatures, pairwise, yields another
valid signature.  A signature can be multiplied by itself as well.
These are valid as RSA signatures but possibly not as any special coin
format.  Note that the Chaum signature pair above prevents
multiplicative combinations entirely.

The problem is then "Can we find an element of S in the multiplicative
span of the { a_i } modulo n?"  (The multiplicative span is any
product of the a_i, possibly taken multiple times.)

Hal's attack was about the about problem, _but without the modulo n_.

There's a subtlety to remember here: factoring doesn't mean anything
in a field.  The RSA ring is almost-a-field; if you can find a
non-invertible element, you've factored the modulus.  Factoring only
make good sense in rings where lots of elements are _not_ invertible.

So Hal's factoring attack only considered direct multiplication,
forgetting that that modular equality was what was relevant.

The upshot is this.  Let s be in S.  What we are looking for is a
factorable (in integers) number of the form s+kn.  Now s can be any
element in S, and k any integer.  That's a wide range to choose from.

A.  First off, what is the size of the possible multiplicative span?
The short answer is "It's likely the whole thing".

Recall that in an RSA cryptofield (my term for a ring where it's
infeasible for an outsider to find a zero-divisor) the invertible
elements form a multiplicative group which comprise all the 'normal'
operations in the cryptofield.  Its structure is the product of two
groups, one of order p-1 and one of order q-1.  Now the number of
generators of the Z_p is \phi(p-1).  (That's the Euler \phi function.)
The average value of \phi(x) is x * (6 / \pi^2), i.e. on average 61%
of the numbers.  [N.B. This is for random x.  p and q can be picked to
change these values.]  

Eliding the rest of the calculation, we see that with a few
signatures, it's very likely that _every_ cryptofield number is in the
multiplicative span.

B.  The next question is "How tractable is finding particular
combinations?"  I don't know, but I wouldn't trust on the lack of an
efficient algorithm.

Remember, we can pick and set of numbers to get signed to span with,
any coin format to try to create [RANT: forge indicates intent] with
that span, and we're working in a modular cryptofield.  That's lots of
possibilities.

Here is one idea for such attack.  The numbers in S all have the same
upper bits.  Suppose one could calculate a number u which was 'close
to' 1 in a range containing S.  To be specific, suppose that

	P( | s - u*s | < sqrt(s) ) > .1

that is, multiplication by u likely doesn't move the value around by
more than the square root of s.  Then one can randomly pick coin
values, multiply by u, and likely get new coin values, since all the
upper bits are the same.

Are such u rare?  Maybe not.  Consider the number 3 and values near
n/2.  Observe that 

	3 * ((n-1)/2) = ((n-1)/2) - 1 (mod n)
	3 * ((n+1)/2) = ((n+1)/2) + 1 (mod n)

So for the numbers close to half the modulus, 3 is exactly such an
almost-identity.

But can we find one for our given range?  I think so.  Here's my first
guess at how to proceed.  And it really is a guess, even if it is
inspired by a Gauss sum.

Consider the following.  Take the range S and choose random { x_i } in
S with, say, some truncated Gaussian distribution in order to favor
number in the center.  Now calculate the term

	1     x_1   x_3         x_(2n-1)
	- * ( --- + --- + ... + -------- )
	n     x_2   x_4           x_2n

In other words, just calculate an average of a bunch of values that
move one element of S to some other element of S.  Such an element
*might* tend to preserve values of S near the center, maybe not.  It
may be that diddling the distribution helps.  It may be that a
different average works, say a geometric average (although taking
roots becomes an issue).  It may be that this technique works but
doesn't converge rapidly.  I don't know; I haven't tried it.

In any case, if it does work, there are lots of candidate u's that one
can sample.

It also appears that one might be able to directly calculate some of
these near-identities with continued fractions.

C. Recommendations

In any case, the issue of creating new signatures out of old is
sufficiently unsettled in my mind that I would avoid the issue
entirely.  

1.  Don't rely only on format of the signed number for validity.

2.  Do use a one-way function in the signature in order to prevent
multiplicative attacks.

3.  Use both techniques above.

Therefore I recommend the Magic Money signature format be changed.

Eric