Re: New attack on mixminion (& fix)

[Nick Mathewson <nickm@alum.mit.edu>]

[Summary: I don't think George's original attack works quite as well as
it was originally described, but the weakness it uses can still be
exploited.  Thus, I am in favor of his proposed change to the crossover
step.] 

On Fri, 2002-09-06 at 01:08, Roger Dingledine wrote:
> 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.

Let's see.  When I send a *FORWARD* message through [N_1 N_2] [N_3 N_4]
with crossover after N_2, then the cipher payload is:
	E(SK_1, E(SK_2, E(SK_3, E(SK_4, P))))
  where P is the plaintext, and E(x,y) is LIONESS_ENC(SHA1(x|'...'), y)

The crossover node can only see E(SK_3, E(SK_4, P)), which will be
different on a subsequent try (since SK_3 and SK_4 will be different),
so we win.

With a *REPLY* message, however, I send as a payload:
        E(SK_1, E(SK_2, E(X)))
         Where X = E(SURB_SK, P)
   where SURB_SK is a secret key that came with the SURB.

 [The sender eventually gets D(SK_4, D(SK_3, X))].

The crossover point sees only E(SURB_SK, P). If the sender never tries
to re-use a SURB, then the crossover point will never see the same
payload twice.

>                                          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.

Here's the problem: the SURB is "reusable" so long as the message never
reaches any nodes in the second hop.  George's attack would work
reliably against any sender that accidentally used the same SURB twice
for the same payload... or which could be tricked into using the same
SURB twice for the same payload.

Here's worse exploit of the same weakness: Alice wants to talk to some
Bob she doesn't know.  Marvin (the attacker) tricks Alice into using one
of Marvin's SURBs instead.  Marvin tags H2 as it leaves Alice.  At the
crossover point, H2 will be junk... but Marvin doesn't need H2 to read
the payload [E(SURB_SK, P)], since Marvin generated SURB_SK in the first
place!

I believe George was right when he said:
>>>>>>It is trivial to fix the above by making sure that the payload comes out
>>>>>>as junk if the second header is touched. We just use the hash of the 
>>>>>>second header to transform the payload using an All or nothing transform 
>>>>>>(like BEAR).

I put a pair of proposed changes in the spec to try to do this.  While
formerly the crossover step did:
	H2 = SPRP_DEC(SHA1(P), "Hide Header", H2)
I changed it to do:
	P = SPRP_DEC(SHA1(H2), "Hide Payload", P)
	H2 = SPRP_DEC(SHA1(P), "Hide Header", H2)

George, could you please check my changes to see whether they were what
you had in mind?  (Specifically, I'm unsure of the ordering.  Does it
mattter?)

Yours,
-- 
Nick