Attack on Magic Money and Chaum cash

[Hal <hfinney@shell.portal.com>]

I think there may be a security weakness in Magic Money coins, and in
Chaum's "online" cash system from the Chaum/Fiat/Naor paper.

Magic Money coins are numbers of a particular form, RSA-signed by the
bank.  They look like Y^(1/e) where Y is the number and e is the
bank's public exponent corresponding to the particular denomination of
the coin.

The structure of Y is a 0, a 1, a string of bytes of 0xff, then
a defined 18-byte string of bytes, then 16 random bytes.  This Y is
generated by the user, and is then blinded by multiplying by some
random r^e, and sent to the bank.  The bank RSA-signs Y*r^e to get
r*Y^(1/e), and the user divides by r to get Y^(1/e).  This is the
coin.

The coin is checked by raising it to the power e, to get Y, then
checking to see if it is of the proper form.  Actually, the Magic
Money code only checks the 18-byte special string (just above the 16
random bytes) to make sure it matches the exact byte sequence that is
always supposed to be there.  In addition the bank checks the 16
random bytes against a list of spent coins to make sure this coin
hasn't been spent before.

The other relevant point is that the bank has to sign everything you
give to it (with payment) - it can't check the bit pattern for
legality, since what it is signing is blinded.  So you can really get
the bank to sign anything.

Yesterday I opined that this would be safe, but now I don't think so.
The danger I would see is an attacker who gets the bank to sign 2, 3,
5, 7, 11, 13, 17, 19, ....  The bank won't know it is signing these
special numbers because they are blinded.  If someone gets a lot of low
primes signed he may be able to forge money, especially with the
incomplete checks in the Magic Money program.

The idea would be for him to try to factor a legal Y using just the
primes he has.  If he can find a factorization using only small primes
of a number which holds the magic 18-byte sequence in the right place,
he can multiply together the signed forms of the primes to produce a
signed version of that number.  This would be a successfully forged coin.

So, the question is whether it would be feasible to collect enough
signed small primes to be able to generate more valid coins than you
have primes.  (It costs you a coin each time you get the bank to sign
something, so for this to be a money-making venture you want to get
more out of it than you put into it!)  I think there are a reasonable
fraction of numbers factorable by only small primes.  Since there are
2^128 possible money values (based on the 16 random bytes) there
should be quite a lot which are factorable by only small primes.

Magic Money could help by checking the high bytes as well as the magic
18; it would be take more time to factor 1024 bit numbers than 272 bit
ones ((18+16)*8), and there would be fewer that are factorable by
small primes.  But the problem would still exist.  The attacker can run
a fast sieve to identify numbers which are factorable in his set.

The same attack would apply to Chaum's online cash.  His cash is of the
form, (x,f(x)^(1/e)), where f() is a one-way function like MD5.  To forge
this you would again get signed forms of the small primes, then keep
picking random x's, until you got a f(x) which could be factored by your
set.  Presto, you can create a fake coin.

I don't know how this attack can be prevented.

Hal