Re: New attack on mixminion (& fix)

[Roger Dingledine <arma@mit.edu>]

On Thu, Sep 05, 2002 at 04:16:21PM -0400, George Danezis wrote:
> > > If I understand your question properly, "no."  The payload encryption
> > > keys are based on the SK_i shared secrets, and those are chosen randomly
> > > each time.
> > I thought so. So since the adversary can never recognize that the new
> > payload is the same as the original one, then the attack as George
> > described it will not work.
> The attack takes place when you have a (Forward)(SURB)(message) series of 
> messages. The attacker tags the (SURB) part, but the message is always 
> rendered in clear (without the fix), because it has been decrypted by the 
> keys in the (Forward) block. If the payload is not dependant on the (SURB) 
> part then it will appear the same at the crossover points, if it is 
> resent, after the first message is tagged (and destroyed).

The payload *is* dependent on the (SURB) part, because it's encrypted
with the next secret in the SK_i sequence. So since a given SURB can
only be used once, then a resent payload will use a new SURB, and thus
be encrypted by a new secret. The cipherpayloads will be unlinkable.

Now, the spec currently says you deliver an 'encryption key' along with
your surb, so the person using the surb knows how to encrypt the payload
at the beginning so it won't look like plaintext at the crossover point.

The encryption key currently is 16 bytes of pseudo-random-number that's
generated after the hop secrets, based from a seed that the surb author
generates and stores in the 'tag' field of the innermost hop of the surb.

Would we get equivalent protection, based on the assumption that "if the
adversary sees the SURB then he can guess-and-check at the crossover
point to see if the payload-decrypted-with-that-key looks legible",
by simply having the encryption key be the hash of the surb? (I think
this is the gist of George's suggestion.) It would make it easier for
the sender.. but it seems the receiver would have to rebuild the entire
surb to uncover the last layer of encryption?

So all things being equal, I'm tempted to leave the
bundle-an-encryption-key-with-the-SURB approach, since we're going to need
to write software to process surbs anyway so it might as well do that too.

And given that we already have a mechanism to uniquely encrypt the
payload even at the crossover point.. do we need to encrypt it with a
hash of the encrypted second-header too?

Gosh. Crypto's hard. Let me know if that made no sense, and I'll try
again.
--Roger