From: nobody@shell.portal.com
Date: Mon, 7 Feb 94 01:16:12 PST
To: cypherpunks@toad.com
Subject: Magic Money attack feasible?
Message-ID: <199402070913.BAA09983@jobe.shell.portal.com>
MIME-Version: 1.0
Content-Type: text/plain


-----BEGIN PGP SIGNED MESSAGE-----

I've done some experiments with this factor-multiplication problem. I think
the solution is to check the whole coin rather than just the ASN string, 
and possibly to make sure the coin has no small factors. Doing a slowtest() 
on a 1024-bit number takes slightly under a minute on a fast PC, so that is 
too slow. But the sieve is fast, and if you #define BIGSIEVE, it catches all 
factors below 8192.

I tried making some coins and trial-dividing them by the small primes in 
the primetable[] (up to 8191). There were a few factors being found, mostly
8-bit ones, but the remaining coin, when all the factors were divided out, 
wasn't much smaller. I think finding coins with all small factors will be 
pretty intractible.

The paper refers to Chaum's digicash, using x and f(x). If f(x) were only
16 bytes, and not padded, this attack would be a serious problem. But the
padding (01 and then repeat FF until the last 34 bytes) makes the attack
much harder and probably impractical. The PKCS-format signature was, after
all, designed to break up the multiplicativity of RSA. What exactly does
the ASN string (those magic 18 bytes) do, other than pad out the MPI? Does
it have some special mathematical properties?

Personally, I think the padding gets rid of the problem. A 1024-bit number,
padded with FF's to make it as big as possible, is very likely to have two
or more fairly large factors (more than 16 bits or so). Since you would 
have to get two or more signatures to forge one, you lose money instead 
of gaining it. You are unlikely to find two coins which have the same large 
factors, so you can't re-use signed primes - the whole key to this attack.

It is possible to move everything up, and leave the last 16 bits open. Then 
you could sieve the coin, and add 2 until you found one which had no 
factors below 8192, making the attack even harder. I don't think this is 
necessary, but I hope someone will work out the math. And if it turns out 
to be necessary, it is at least possible to make all the coins prime, 
making this attack completely impossible.

For now, I will modify the code to check the whole number, and to make sure
that the coin is as long as the modulus it's signed with. If the other
change is necessary, let me know. I'm not going to post any more code to
csn.org until someone (1) checks the existing (sent today) code on a big-
endian machine, and (2) figures out if this attack is a problem. It should 
be mathematically possible to find the probability that a number of size m 
is composed only of primes smaller than size n, but I don't know how to do 
it. Does anyone?

                                                  Pr0duct Cypher


-----BEGIN PGP SIGNATURE-----
Version: 2.3a

iQCVAgUBLVXwJsGoFIWXVYodAQEZ4gP/QOGoZgRcR1CJkaWErSesMCzsEAu1fCVB
OAhLGXI8hIErDuMy9f395agFxjPK3EgSWF6nnoze+BbfZDF0nTAgbgdEroHPy3k7
Pp/FV0jES3BqPFOX/0JCWHx8LRm4n2tMqUgLsX0125xywU9tk097DJTPxrAh9Xbs
zrEVlsJuGRs=
=akie
-----END PGP SIGNATURE-----