WRONG: Attack on Magic Money and Chaum cash

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.  Specifically, it will take as much work to forge
cash as to factor the modulus.

My idea was to collect signed forms of small primes, then try to find a
"smooth" number of the proper form, one which can be factored over this
set of primes.  By multiplying together the proper primes, one could
generate a signed number which would look like cash.

What I was remembering as I was driving tonight is that this is very
similar to a family of algorithms for factoring large numbers.  The one
I know best is the continued fraction algorithm, but I think the number
field sieve uses broadly similar principles.  In the cfrac algorithm,
the goal is to find two squares which are equal mod n.  This lets you
factor n immediatly by taking its gcd with the sum or difference of the
two numbers.

This is done by taking a bunch of squares and trying to factor them
over a set of small primes.  If you generate enough factorizations,
approximately as many as there are primes, you can multiply selected
ones together and generate two equal squares.

The point is, finding as many smooth numbers as there are small primes
will let you factor n.  But that is the same criterion I had to meet in
my proposed attack in order to make a profit.  So it seems that in
general my attack will not work; it will be as hard as factoring the
modulus.

There may still be a problem with Magic Money because its cash values
leave the low order 128 bits free, but I'm not so sure about it.  I was
wrong, I think, to suggest that a simple sieve could quickly identify
smooth numbers.  Although a sieve will easily tell you that a number
has _no_ factors less than some cutoff, it will not easily tell you
that a number has _only_ factors in that range.  It may be that the
only way to identify smooth numbers is by trial division, which would
be the same situation as for Chaum cash.

So, unless there is in fact some trick that can be used to quickly find
smooth numbers given that the low order 128 bits are free, I don't
think there is any need to worry about my attack on Magic Money.  And
it looks like Chaum's online cash is completely invulnerable to this
approach.

Sorry to have raised a red flag unnecessarily.

Hal

>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

In thinking about my own averaging technique for finding
near-identities, I realize it needs some modification.

Remember the example that 3 was a near-identity near n/2.  Well so is
5, and 7, and -3, -5, -7, etc.  Even though 3 (or -1) seems to be the
best of the near-inverses, any one whose action is sufficiently
bounded will do.

The new observation is that the candidates for near-inverses will be
clustered and not distributed flatly over the ring.  There will also
be more than one cluster.  So you've got two choices.  First make a
histogram of the candidate choices and only average by clusters.
Secondly, one might also be able to transpose the clusters onto each
other and average them all.  The inverse image of this transposition
may also yield more near-inverses.

I think that averaging can be made to work, but it's not obvious to me
exactly what the technique will be.

Eric