stateless reply blocks

[Roger Dingledine <arma@mit.edu>]

We've got a standard security/crypto problem to tackle here (wow, it's
been a while :) I'm sure this problem is already solved many different
ways, so somebody who's still familiar with security should jump in and
correct me. (David?)

We'd like to let users create reply blocks and receive anonymous mail in
such a way that they don't have to remember much. When the last mix in
the path delivers the mail via smtp, it includes a header "X-Tag:" with
some encrypted stuff from which the receiver can reconstruct the secrets
used in the reply block.

Option one: the user memorizes a good password. He generates a random 128
bit seed for each reply block, so
TAG = E(sha1(password)[0:16], (nHops | seed | padding))

So TAG is 32 bytes of material (probably more to ascii-armor it since
it's in a header). It all looks random. When a reply message comes in,
he uses his password to decrypt the TAG, learn number of hops and seed,
and from there he uses PRNG(seed, 16*nHops) to generate the required
secrets (16 bytes of secret per hop) for decrypting the message.

But this option requires that the user remember a good password, and
anybody overhearing the message as it gets delivered (such as the exit
node) can attempt a dictionary attack to recover the secrets and read
the message. On the plus side, in some sense it really is stateless,
because the receiver doesn't have any keys on his machine.

Option two: the user generates a 128 bit random key, and stores it
on his machine. He can encrypt it with Hash(password) if he likes.
Now TAG = E(key, (nHops | seed | padding))

Again TAG is 32 bytes of random-looking material, which the user can
easily decrypt when it arrives to learn the seed, and regenerate the
secrets he used to build the reply block. Now he's not vulnerable to a
dictionary attack from a passive adversary (in order to even start the
dictionary attack they need to recover the encrypted key from his hard
drive). But now he's got something potentially incriminating on his
machine. But then, he's got the Mixminion reply handling software anyway.


What do you guys think? I've avoided any public key solutions here,
because the receiver is effectively sharing a key with himself, so the
added space of storing a 1024 bit TAG, and the added computation of a
public key op, is not necessary.

--Roger