Re: [ANN] M.0.0.3rc2: Reply block issue

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

On Tue, 2003-02-18 at 14:03, George Danezis wrote:
> Dear Nick and All,
> 
> This has popped up in the past, but at the time it was a theoretical issue 
> while now we have an actual implementation. 
> 
> Executive summary: I believe, and I need other's opinions on this, that it
> is important that a user specified tag should be attached to each SURB,
> and revealed when a reply is decoded.
> 
> Long version: Think of the following scenario: I (George) sends two 
> anonymous messages to Nick and Roger, pretending to be Grace and Glory 
> respectively. Both messages contain some reply blocks so that Nick and 
> Roger can reply to me. 
> 
> Roger and Nick are good friends and believe that Grace and Glory are 
> actually the same woman (well man in this case). In order to test this 
> Nick gives his reply block to Roger, who using it writes an email to 
> Glory. I receive the email, as Glory, and I reply as if nothing wrong had 
> happened. Therefore their hypothesis that Grace is indeed Glory is 
> confirmed. 

Good attack!

>The solution to this problem is to 'bound' SURBS to particular pseudonyms 
> (in a very loose sense). Therefore in the TAG field of the SURB I include 
> 'To: Glory' and 'To: Grace' respectively. When I receive the email from 
> Roger, writing to Glory, the decoded messages is clearly addressed 'To: 
> Grace' and this cannot be modified by the network. Therefore I know that I 
> should reply saying 'I am sorry Roger you must be mistaken. I am not 
> Glory, but Grace'.

This solution has the disadvantage that any attacker who sees the TAG
field (e.g., an attacker who controls the exit node) can tell which
pseudonyms we're using.

Here's another solution that fits with the current protocol, and does
not reveal that information.  We use bound SURBs as in your description,
but instead of modifying the TAG field as you suggest, we generate SURBS
as usual, but instead of using a single long-term secret SEC, we use a
different long-term secret for each psuedonymous identity.

In other words, when we generate a "Glory" SURB, we choose a random S as
our tag and generate keys from H(S|SEC_GLORY|"Generate").  When we
generate a "Grace" SURB, we choose a random S and generate keys from
H(S|SEC_GRACE|"Generate")

Later, when we receive a message, we check whether we can decrypt the
message with H(TAG|SEC_GLORY|"Generate") or
H(TAG|SEC_GRACE|"Generate").  Whichever one works, tells us which
pseudonym we used.

This approach has the advantage that an attacker who sees the "Tag"
(a.k.a. Decoding Handle) field on an outgoing message has no way of
telling which pseudonym we're using. 

What do you think?

-- 
Nick Mathewson <nickm@alum.mit.edu>