long-range dummies

[Matej Pfajfar <badbytes@freehaven.net>]

Here's a suggestion as to how we can introduce long-range dummies -
Paul, I think you've already figured out a good way to do this so jump
in any time!

(1)
Introduce a new field to the cell - say "padding mask", or PMASK, 16
bits long (say).
Introduce a new field to the onion - say HOP_PMASK, also 16 bits.

The idea is for a node to forward all DATA/CREATE cells unless
the PMASK field matches the HOP_PMASK field (meaning "this is a dummy, 
shoot it").

The onion proxy can now randomly insert dummy DATA/CREATE cells into
the cell stream. It can control the range of the dummies by setting
the PMASK field to the appropriate value.

This effectively hides the true volume of the traffic from all (but
last) nodes in a circuit. As to what amount of padding is required to
prevent volume signature attacks (if it can prevent them at all)- no idea yet.

Alternatively - hashes could be used to achieve the same purpose (as
Roger suggested) but this doesn't cope well with (2) below.

(2)
A good thing to have would be for the nodes to be able to add dummy
cells themselves.

Adding dummies in the "backward" direction is easy enough - each node
can introduce dummy cells into the stream and set the PMASK to their
HOP_PMASK value. The onion proxy can kill the dummies on sight because
it knows all the HOP_PMASK values. This also means that the PMASK
header field should not be encrypted (apart from link-encryption on
long-standing inter-router connections). 

Now for the forward direction. There are two possibilities (as I see
them). The first are fixed-range dummies, whereby each node can add
dummy cells but they all have the same range.
A way to do this is to introduce another field to the onion, say
NEW_PMASK, which tells each node how to tag dummy cells. Clearly the
NEW_PMASK must correspond to the HOP_PMASK value of some subsequent
node, which will then be able to recognize the dummies and kill them.

I am not sure how to do variable range dummies - we could tell each
node what the HOP_PMASK values of subsequent nodes are so it can
choose a range for its dummies. This is obviously crap because a node
can then easily recognize dummies targeted at any of those nodes.
The only way I can think of (and this is too messy I think) is to give
each node two HOP_PMASK values. One for dummies generated by the onion
proxy and one for those generated by intermediate nodes in the
circuit. We can then give each node a list of all subsequent
HOP_PMASK2 values and it can choose from that list when generating dummies.
But then if node n-1 generates a dummy for node n+1, node n will be able 
to recognize it. I guess that leaves us with K+1 HOP_PMASK values (for a 
circuit of length K) - now nodes can't recognize eachother's dummies.
We could use the Key Seed Material to generate the HOP_PMASK values.?

Anyway this is clearly not a solution but perhaps an idea as to how
things could be done. By all means rip it apart.
Back to Roger's code ...

Matej
-- 
Matej Pfajfar

GPG Public Keys @ http://matejpfajfar.co.uk/keys