--- begin forwarded text
Date: 21 Nov 1999 22:20:08 -0000
To: [EMAIL PROTECTED]
From: lcs Mixmaster Remailer <[EMAIL PROTECTED]>
Subject: Marked cash in Lucre
Sender: [EMAIL PROTECTED]
Earlier this year there was discussion of David Wagner's blinding as a way
of creating electronic cash that would not be covered by existing patents.
See the archives at
http://privacy.nb.ca/cryptography/archives/coderpunks/new/1999-03/
for the threads "Anonymous cash via blinded authentication" and
"Getting around Chaum's patent". David Wagner's original posting is
at http://www.deja.com/getdoc.xp?AN=145097228.
This algorithm has been implemented by Ben Laurie in his Lucre package,
info at http://anoncvs.aldigital.co.uk/lucre/. There have been rumors
that Lucre might serve as the foundation for an actual field trial of
electronic cash.
The idea is that the bank "signs" a number by raising it to a secret
exponent k, modulo a strong prime p. The bank can then recognize a
signed pair y, y^k by raising the first one to the k power. The y values
have some internal redundancy, like the right half is the hash of the
left half.
To blind, David Wagner suggested the bank also publish a generator g
and a value g^k, similar to what is done in Diffie Hellman exchanges.
The client then chooses a random blinding factor r and calculates
y * g^r, which he sends to the bank. The bank raises this to the k
power (a power unknown to the client), producing y^k * g^rk. The
client is able to calculate g^rk by taking the published g^k value to
the r power. (g^k)^r = g^kr = g^rk. He can therefore divide this out
and be left with y^k, a properly "signed" value.
This is what is implemented in Lucre.
However, there is a flaw. During the discussion earlier this year, it
was pointed out that Chaum had proposed a similar algorithm for another
purpose, blind undeniable signatures. Instead of blinding by multiplying
by g^r, he blinded by raising to a random power. Unblinding was then
done by raising to the inverse power. This worked OK for Chaum, but
in the Coderpunks discussion it was pointed out that it would allow
the bank to "mark" the cash. It could misbehave during the transaction
and raise the blinded y value to a power k' instead of k. This cannot
be detected by the client since there is no public key to verify the
"signature" against (which is why these are not technically signatures).
Then when the coin is deposited after unblinding, the bank can recognize
that it was the same coin which was marked with the special k' power.
It was suggested at the time that David Wagner's blinding was immune to
this marking attack. However recently it has been learned that this
is not true; the bank can mark cash using Wagner blinding as well.
The current Lucre implementation would be vulnerable.
During withdrawal, the user submits y * g^r. The bank, to mark the cash,
raises it to the k' power rather than the k power. The creates
y^k' * g^rk'. The user unsuspectingly unblinds by calculating g^kr and
dividing it, leaving y^k' * g^(r(k'-k)). This is what is later submitted
to the bank, along with y.
The bank, at this point, knows y, k, k', g, and the product above. It
does not know r. It can calculate y^k' and divide to get g^(r(k'-k)).
It can raise to the inverse power of (k'-k) to get g^r. Now it can
multiply by y to get y * g^r.
This is the same value which was submitted to be signed in the first
place. By keeping a record of the values which were signed using the
special k' exponent, the bank can look back and see which one this one
is, thereby linking the deposit to the withdrawal, which is exactly what
blinding is supposed to prevent.
Hence the current Lucre implementation cannot be viewed as safe.
It appears that there is a simple fix, but other people should look at it
to be sure. The flaw in the existing implementation was not discovered
for months, presumably because no one looked closely at it. The fix
is simple but it would add confidence for more people to study it.
The proposed fix is to combine the two forms of blinding, Wagner's
and Chaum's. Choose two random blinding factors, r and s, and blind
by calculating y^s * g^r. This is sent to the bank which returns (if
it is not cheating) y^sk * g^rk. As in Wagner's blinding, the user can
calculating g^rk and divide out, to leave y^sk. As in Chaum's blinding,
the user can then raise to the 1/s power to leave y^k. Hence the blinding
is easily removed.
If the bank cheats by raising to the k' power, the user gets
y^sk' * g^rk'. He divides by g^rk to get y^sk' * g^((k'-k)r). He then
raises to the 1/s power to get y^k' * g^((k'-k)r/s). This is what he
gives to the bank at deposit time, along with y.
The bank can calculate and divide off y^k', and raise to the inverse
(k'-k) power as before, leaving g^(r/s). However at this point it appears
to be stopped. There seems to be no way to correlate this value to the
y^s * g^r that it saw at blinding time. If it could guess s, it could
compute g^r by exponentiating, and y^s likewise, and find y^s * g^r,
but there is no way it can guess s.
By having two blinding factors rather than one, there is one additional
degree of freedom and it appears that the bank cannot recognize
marked cash. It can of course realize that the deposited cash is not
properly signed, but it has no way to distinguish marked cash from simple
counterfeits, which would not be a very effective way of marking.
--- end forwarded text
-----------------
Robert A. Hettinga <mailto: [EMAIL PROTECTED]>
The Internet Bearer Underwriting Corporation <http://www.ibuc.com/>
44 Farquhar Street, Boston, MA 02131 USA
"... however it may deserve respect for its usefulness and antiquity,
[predicting the end of the world] has not been found agreeable to
experience." -- Edward Gibbon, 'Decline and Fall of the Roman Empire'
