Re: some related work on tagging attacks

[Bodo Moeller <moeller@cdc.informatik.tu-darmstadt.de>]

Thanks for your comments on my paper.

> 1 - In section 2, near the end of paragraph one you describe the problem
> that the final receipient knows the route length of the message by finding
> out how much padding is present. This can be avoided, as we do in
> mixminion, by adding the padding at the end of a fixed length header. This
> wastes some space, and makes the maximum route length smaller, but has the
> advantage of keeping the route length secret for everyone but the original
> sender.

I describe how the route length can be kept secret, but apparently
that paragraph is not clear enough.  *After* the colon, I describe the
problem, and *before* the colon, I have described my solution --

     Also it may be desireable to define a maximum length for the
     actual message payload, i.e. the part of the plaintext as
     recovered by the final mix that can be chosen by the sender: as a
     message proceeds through the mix chain, more and more of the data
     will be pseudo-random gibberish; the length of the useful part of
     the final plaintext reveals that chains leaving less than this
     amount cannot have been used.

It seems I should present these ideas in a more natural order ...


> 2 - Markus Jakobson has done some similar work about hybrid mixes. His
> page is http://www.rsasecurity.com/rsalabs/staff/bios/mjakobsson/ and the
> paper I am thinking of is
> 
> M. Jakobsson, A. Juels, "An Optimally Robust Hybrid Mix
>                              Network", PODC '01 (ps,pdf) 
> http://www.rsasecurity.com/rsalabs/staff/bios/mjakobsson/hybridmix/hybridmix.pdf
> 
> He has done a lot about proving things about mixes so you might be 
> interested to have a look.

I've seen that paper, and maybe I should also have cited it, but just
to point out that it assumes a quite different model of operation.
The following is an important difference:

     We assume the existence of a bulletin board. This is a publicly
     shared piece of memory to which all players have read access and
     appendive, sequential write access with authentication.2 We
     assume further that all writes to the bulletin board proceed in
     synchronous time steps.

     2 A bulletin board may be simulated or replaced by an
       authenticated broadcast channel or Byzantine agreement protocol
       [23]. In an asynchronous network, the latter is only robust
       against an adversary actively corrupting fewer than one-third
       of the servers, and alters the security of our mix construction
       accordingly.

     [hybridmix.pdf, p. 4]

I'm thinking of Mixmaster-style systems where participants may not
even use the same list of available mixes and all systems work more or
less independently of each oher.  In Markus Jakobsson and Air Juels's
model, you can obtain better security properties (robustness), but
only because you have much stronger assumptions.  There aren't really
that many similarities between these papers, at least not if you look
at them in the context of earlier works such as Chaum's original paper
and the Mixmaster protocol description.


> 3 - It is worth thinking how to do reply blocks. ... ?

I guess so, but this will lead to a more complicated construction,
presumably with more complicated (weaker) security properties.


-- 
Bodo Möller <moeller@cdc.informatik.tu-darmstadt.de>
PGP http://www.informatik.tu-darmstadt.de/TI/Mitarbeiter/moeller/0x36d2c658.html
* TU Darmstadt, Theoretische Informatik, Alexanderstr. 10, D-64283 Darmstadt
* Tel. +49-6151-16-6628, Fax +49-6151-16-6036