link padding document

[Andrei Serjantov]

Rachel,

Others: Sorry for yet another long email, a lot of this is not relevant to
OR. The document got updated with references to related work which we
should examine.

>    In the course of my work at Harvard this summer and while reading
> the discussion here, it has also occurred to me that a rigorous
> analysis/taxonomy of traffic padding methods would be useful.

Indeed. I am currently in the process of doing this. You have seen the
first part of the document for OR (or real-time mix networks). Also
thinking about padding for mixmaster (mixminion), but I was not planning
to put out a document for general reading. Maybe I should?

> Though, I'd personally like it to be more general in focus....
>
> Some things I've been thinking about (that aren't currently in
> Andrei's document)
>
> - end to end link padding (when is it necessary/possible)

Errr... I take it you mean end to end -- we have so far been using "link"
to mean COR to COR (I think!)

> - other reasons that full link padding is impractical (DoS)

I am not sure I know what you mean -- If you are doing full link padding
and you've still got too much traffic, just break connections in a
draconian fashion when your buffers start overflowing! That's what we came
up with Mat and thought it was ok!

> - an analysis of traffic shaping as it's been described (what
> does it buy you, how do you need to set up the intervals so
> that you don't leak too much information)

Do elaborate, sounds interesting.

> - If padding changes are there any covert channels/tagging attacks
> that can be used to communicate information between corrupt nodes?

My 2 cents: Well, you know that real-time mixes (they are not mixes,
remember?) can bridge honest nodes anyway as they all get to see the real
traffic volumes? i.e. if a connection goes through A,B and C , A and C are
compromised and B is honest, you can corellate the number of cells at A
and C and thus do traffic confirmation....

> - I've been thinking about what you can get with nodes that have
> a constant number of neighbors which are fully padded links.
> You ought to gain an exponential level of uncertainty with
> each step in the path and if the path is sufficiently long your
> level of security should be similar to full link padding...I'm told
> George has been thinking about similar things (hi george, are you
> here?)

George is not around on this list but I have added my (slightly old)
thoughts on this subject to the document.

http://www.cl.cam.ac.uk/~aas23/or.txt

> - it might be a good idea to make the list of things we need to protect
> against with link padding more concrete (basically
> anything a passive adversary can do) however, there
> are schemes which will hide the amount of bandwidth on each link but
> not much else and this might be useful in certain circumstances
> (high efficiency requirements, or if you use some other mechanism
> to acheive desirable properties)

> - how is the link padding situation different in a cascade situation
> like WebMixes?

Again, I have added some thoughts on cascades to my document. It would be
interesting to see what the various systems do, I have a list of the
relevant ones and added it as well.

> Anyway, I realize this is a lot of questions and such, but I've been
> thinking about the answers and I think they would be good
> things to talk about in a document such as the one Andrei mentioned.

I need a little more time (a small number of days) to think and write the
rest of the document and afterwards I plan to open it up for additions by
anyone who cares to! Although I have never worked in this way, and this is
probably not the way to do it, I am willing to try once!

I would ask not to redistribute it, beyond Paul, Roger, Mat, Rachel and
Bruce (who else is on the list?).

> I intend to flesh out each of these points as I get time, though
> other people are welcome to do that first.

Ok.

Thanks,

A.

------------------
Andrei Serjantov
Queens' College
Cambridge CB3 9ET
http://www.cl.cam.ac.uk/~aas23/