[hashcash] Re: key management and signatures

  • From: Jonathan Morton <chromi@xxxxxxxxxxxxxxxxxxxxx>
  • To: hashcash@xxxxxxxxxxxxx
  • Date: Wed, 2 Jun 2004 12:33:08 +0100

The signature is done on the hashcash token, which makes it unique per
message without having to do PGP-style tricks with the message body.
It does mean the signature has to be in it's own header, but it's still
only valid if the hashcash is, and the key can still be selected and
distributed using the hashcash extension field.

The hashcash doesn't have to be full-strength to have a signature
attached to it - even 8 bits (a trivial amount) is probably enough. It
does need to be robustly unique to the message, so a good double-spend
database design is important.

Is this right (one direction only):

 X-Hashcash: 1:30:date:bob:token=nonce:...
(result: accepted, whitelist token nonce)

 X-Hashcash: 1:25:date:bob:...
 X-Token: sha1(sha1(stamp) . "nonce")
(result: accepted)

So how does Bob know to look up token "nonce" when he gets a message from
Alice? Is the token database keyed on "From:"?

Yes, that's broadly right. The "from" part might also be encoded into the extension field, so it's unambiguous, and also to help support mailing lists (see below).

I don't know much about cryptography, but I can think of several ways
of performing the signature that - theoretically at least - make key
generation and distribution simple and cheap. One such way is to
concatenate the base64 representation of the hashcash token's SHA-1
output with the key itself, and use the SHA-1 of that as the signature.

Why hash the secret after it's already been transmitted in the open? It'd be very simple to do this:

 X-Hashcash: 1:30:...
 X-Token: 20040630:nonce

What happens if a single message from Alice to Bob is posted on the Web, with full headers? This happens more often than you might think, particularly when mailing lists are involved. Now the spammers can web-scrape for X-Token headers which are valid for particular sender-recipient pairs, which means they can pretend to be that sender while spamming that recipient.

Plus, if hashcash is made to work with legacy mailing lists (by allowing tokens addressed to the list rather than directly to the recipient), this means that the list subscribers will *all* get a copy of the key the sender uses to post with. So now the spammer can post spam to the list as if he were a legitimate subscriber. Oops, what happened to limiting the key distribution?

This is far less likely to happen if the key is only sent once in the clear. In the case of the legacy mailing list, it would be better if it didn't get sent at all. That can be arranged by sending only "unsigned" hashcash to a recipient, until a mail from that recipient is received with hashcash attached. This means that at least two mails must be sent in each direction before the relationship is fully established:

A -> B: Hashcash(20) - no knowledge of B

B -> A: Hashcash(30) with Key(BA), Signed(BA)

A -> B: Hashcash(30) with Key(AB), Signed(AB), "I have your key"

B -> A: Hashcash(8), Signed(BA), "I have your key"

In the following example, L is a legacy mailing list:

A -> L: Hashcash(20) - no knowledge of L
L -> B: (same as above, looks like A -> L from hashcash' point of view)
- Now B knows A supports hashcash, but doesn't know anything about L except that it's an address at which B can receive mail.

B -> L: Hashcash(20) - no knowledge of L
L -> A: (same as above, looks like B -> L...)

Hashcash-aware listservs can fit into that paradigm by adding their own hashcash/signature to each post, marked as "from" the mailing-list posting address. The subscriber will then be able to build a full-duplex relationship with the listserv in the normal way, with the listserv stripping out the hashcash headers addressed to it before adding it's own and forwarding the mail.

Example with M as the aware list and C as a non-hashcash subscriber:

A -> M: Hashcash(20) - no knowledge of M
M -> B: Hashcash(20) from A, Hashcash(8) from M - no knowledge of B
M -> C: Hashcash(20) from A, Hashcash(8) from M - no knowledge of C

B -> M: Hashcash(30) with Key(BM), Signed(BM)
M -> A: Hashcash(30) with Key(MA), Signed(MA)
M -> C: Hashcash(8) - no knowledge of C

C -> M: (no hashcash)
M -> A: Hashcash(8), Signed(BM) - assumes A has received key unless timeout or nack
M -> B: Hashcash(30) with Key(MB), Signed(MB), "I have your key"

A -> M: Hashcash(30) with Key(AM), Signed(AM), "I have your key"
M -> B: Hashcash(8), Signed(MB), "I have your key"
M -> C: Hashcash(8)

B -> M: Hashcash(8), Signed(BM), "I have your key"
M -> A: Hashcash(8), Signed(MA), "I have your key"
M -> C: Hashcash(8)

In practice, the above scenario is for an existing listserv that has just transitioned to hashcash awareness. New subscribers to the list could set up a full-duplex relationship during the double-opt-in process.

You can see, however, that the listserv only ever generates one 30-bit stamp per hashcash-aware subscriber (unless, by severe misfortune, the key-bearing mail is dropped in transit - detection and handling of which is up to the listserv), with all other mails requiring only an 8-bit stamp which is nearly trivial to compute. Meanwhile, the listserv benefits from positive identification of posts from A and B, meaning that a spammer must impersonate C or subscribe themselves in order to spam the list.

from:     Jonathan "Chromatix" Morton
mail:     chromi@xxxxxxxxxxxxxxxxxxxxx
website:  http://www.chromatix.uklinux.net/
tagline:  The key to knowledge is not to rely on people to teach you it.

Other related posts: