Re: Questions/Comments on ecash protocol

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

From: Ian Goldberg <iang@cory.EECS.Berkeley.EDU>
> I read these specs for a little while last night.  Here are some of my
> questions/comments.  To prevent this message from becoming huge, I won't
> quote much from the protocol document itself; the URL is above if you want it.
> I'll ignore the spelling/grammar; they can be fixed later.

I was also reading it, and I share some of Ian's questions, but for some
things I have a few different guesses.

> What is the function f, used in the payment_hdr to hash the payer_code
> and desc fields, as well as in WITHDRAW3 to calculate N = f(n) * r**h?
> There is reason to believe it is SHA, but I thought I saw some stuff in the
> client that indicated that the output of f is 132 _bytes_ long (but I'm
> not exceptionally sure of this, not having source and all).

One rather cryptic sentence, which Ian alludes to later, relates to
cancelling payments:  "The 'payer_hash' is the one-way image of a by
the payer generated random number...".  In the diagram it shows it as
f(payer_code), where payer_code is shown as "random code generated by
player".  (And, as Ian points out later, the document inconsistently
says that "the player generated random number" should be kept secret
while requiring that it be sent to the shop - at least, this is
inconsistent if it refers to payer_code.)  Assuming the use of the word
"a" is not a typo but refers to some number, this suggests that f() is
at least potentially a two-input function, some value a and a player
generated random number.

> Please clarify what parts of the payment_hdr are shipped around.  The document
> says that the shop checks if the descr_hash matches the description.
> Since the description is in the second part of the payment_hdr, does that
> mean that both parts are sent to the shop?  Noticing that the payer_code
> (which the payer is supposed to keep secret) is in the second part, this
> doesn't seem to be right.  Also, the document states that the payment hash
> is not sent from the payer to the shop or from the shop to the mint.  However,
> the payment hash is just the SHA of the first part of the payment_hdr,
> which _is_ sent around, so although the payment hash isn't transmitted
> per se, it can certainly be calculated.

It seems that the whole payment_hdr is sent to the shop, and only the
portion before the line is sent to the bank.  This is enough, as you say,
to calculate the payment hash, so the bank can decrypt the coins.  This
prevents the shop from changing any of the information in that first part
of the payment header before sending it to the bank.

My question in this part relates to coins made out to "@" which we have
been told can be deposited by anyone.  How does the bank know to which
account to deposit such a coin, given a deposit message?  The shop's ID
does not seem to be present in such a message, assuming that the
shop_accID field of the payment_hdr just has "@" in that case.  Is it the
userid field in the userhdr message which tells the bank this info?

BTW since apparently both deposit and payment messages are not encrypted,
coins made out to "@" are in danger of being stolen both while en route
from customer to shop and from shop to bank.  This is significant from
the point of view of payee anonymous systems, which will need to use such
coins.  More encryption will be necessary when such coins are passed
around.

> A (very slight) privacy concern: the payer's bank is sent in the clear,
> which gives a very small amount of information about the identity of the
> payer.  More on who knows what later.

Well, I would think identification of the payer's bank will be
necessary for any coin based system so you know where to cash in the
coins, so I don't think this is going to go away.  Of course as of now
everyone has the same bank so it is not an issue.

> Is it in fact the case that all coins on one payment use the same payment hash
> when encrypting their signatures (the field sig in onl_coin)?

The signatures are xor'd with the payment hash, but this is not the main
way they are encrypted - they are then encrypted with the bank's public
key.  The purpose of this xor is not so much to protect the coins as to
bind them unbreakably to the payment header.  Since the coins are always
sent around with that payment header I think they all do use the same
payment hash.

> If (M,e) is the mint's public modulus/exponent, and (N,h) is public mod/exp
> for a particular coin denomination, are the following statements true:
> 
> o If n is the coin number (in onl_coin, assumedly the same n as used in the
>   withdraw request), and hdr is the first part of the payment header,
>   then sig (in onl_coin) equals
> 
>      ([ SHA(hdr) XOR ((f(n)^(1/h)) mod N) ] ^ e) mod M

I was wondering about this too.  There is a reblocking problem in
trying to concatentate "pure RSA" operations.  In particular M must be
at least as big as N.  This is not necessarily a problem, but it is a
slightly unusual constraint on key creation.  However I agree overall
that this formula is a reasonable reading of the doc.

> o A deposit (which contains a userID in the userhdr, a payment_hdr in
>   the dep record, and a pair (n,sig) for each coin) is accepted by the bank iff
> 
>      ([ SHA(payment_hdr) XOR ((sig^(1/e)) mod M) ] ^ h) mod N = f(n)
> 
>   _and_ either payment_hdr.shop_accID corresponds to userID,
> 	  or   a payer_code is supplied such that
> 		 payment_hdr.payer_hash = f(payer_code).

There also needs to be some clause for the "@" payee.  In that case I
think the payment is accepted if the signature checks, with credit to the
userID account.

That business about cancelling via payer_code I agree is not very
sensible.  It doesn't seem necessary - the coin can just be re-spent,
made out to someone else.

> Where is the facility for tracing double spenders?  Perhaps it's just
> part of the "incomplete" part of the document, but I can't even see
> where it would fit in to what we've got; neither the withdrawal nor the
> payment messages seem to encode _any_ information about the payer in
> the coins, and the bank cannot seem to know who withdrew the coin that
> ended up being spent twice (due to the blinding).

There is no such thing!  This is one of the most common misconceptions.
This version of ecash does not trace double spenders.  It prevents double
spending by checking each coin to make sure it has not already been
spent.  Tracing of double spending is only necessary in offline systems
where coins are not checked right away, but that is not present here.

> Is there a way to change the public key associated with an account?
> Is it just a meeter of sending another OPENACC1 message?

My guess is there would need to be some manual intervention to do this.

> Exactly what kind of anonymity/privacy/security does ecash offer?
> Let's examine who knows what.
> [...]
> If Eve or Mitch can determine either r (the blinding factor) used in
> the withdrawal, or the payer_code, used in the payment, they can steal the
> money.  This has ramifications to Doug's "agnostic" banks; more security
> has to be added to the present ecash system if unblinded withdrawals are
> allowed.  This also brings up the "Netscape" question: how are these numbers
> generated?  Does it have to do with that 25 character string you enter
> at the beginning?  I've noticed a bit in the program that seeds a RNG with
> (time(0) ^ ((getpid()<<16)|getuid())).  I think publication of _at least_
> the code pertaining to blinding factor and payer_code generation is
> _absolutely vital_.

Well, as I said, I think this payer_code business is pretty questionable.
I'm sure the next version of the doc will clear that up a great deal.  As
far as determining r, that is not possible from the protocol messages.
Chaum has proven that it is absolutely indeterminate.  So I don't
understand what you mean about "more security has to be added to the
present ecash system if unblinded withdrawals are allowed."  Do you just
mean that the coin messages should not be sent in the clear in that case?
I observed that coin withdrawal messages can be sent in the clear in some
postings I made last year - the use of r effectively encrypts them.  But
of course that can't be done with unblinded messages.

There have been claims that the long string you type in at startup time
deterministically seeds the RNG, so that if you lose your wallet but you
tell DigiCash this string (via some secure channel, presumably) they can
reconstruct the coins you should have.  Presumably they could figure out
what the r values were when you withdrew all your coins, reconstruct the
coin numbers, and see which ones haven't been spent.  This is both good
and bad, in that it provides a well understood amount of entropy (rather
than relying on whatever it can scrounge up), but of course is vulnerable
to lazy typing.  Also, you have to write down the string, and if someone
found this they could perhaps get your coins.

> I think I'll stop here; comments from anyone, and especially answers to my
> questions from DigiCash people, are welcome.  I'm sorry if it's not as
> complete as you (or I) would like; I'm quite tired, as my building had
> two fire alarms in a row at 3am this morning...
> 
>    - Ian "Well, it's a start..."

Very good comments.  I'm sure the next version will be much better if
they are careful to clear up the kinds of issues you have raised.

Hal