Random chaff [was: more work for Grobbages]

[Brian Mearns]

On Wed, Sep 23, 2009 at 3:38 AM, Nick Mathewson <nickm at torproject.org> wrote:
> On Fri, Sep 18, 2009 at 10:19:17PM -0400, Ted Smith wrote:
>> On Fri, 2009-09-18 at 04:25 -0400, grarpamp wrote:
>> > Nodes usually have a max bandwitch set.
>> > Nodes often comsume less than this.
>> > All node to node traffic is encrypted.
>> > Perhaps implement a random stream generator
>> > that only runs when it or its chosen path has
>> > free bandwidth, tags its traffic as chaff, pipes
>> > it through some number of nodes, or if it has
>> > idle neighbors, and ultimtely sink it somewhere.
>> > It would be even harder to follow an actual client
>> > dl/ul stream if things were maybe udp with the stream reassembly
>> > info inside each onion wrapped cell. Or something
>> > like that. No doubt this is old ideas.
>>
>> Indeed it is, and it's my understanding that this doesn't really work.
>> More astute minds than I can explain in full, but you can render this
>> sort of safeguard useless quite easily.
>
> The issue with padding isn't that it doesn't work at all, but that it
> doesn't work well enough to do any good.  Last I checked, the state of
> the art in low-volume padding could slow down correlation attacks by
> 10-50%, depending on how you're counting.
>
> This sounds good until you think about how fast correlation attacks
> actually are.  If a correlating attacker (one watching both ends of
> the communication) needs only a second of traffic to link sender and
> receiver, then forcing him to collect an extra half-second of traffic
> doesn't actually help the user very much, assuming that the user
> intends to use Tor for more than a second and a half.
>
> What would need to change for padding to become useful? If it turns
> out that correlation attacks are far more difficult than the research
> community thinks, or if somebody comes up with a padding approach that
> actually delays correlation enough[**], I think we should come back
> to the question.
>
> [*] You can do high-cost methods that defeat correlation[***] pretty
>    easily: constant-rate traffic is one of them.  There's a FAQ
>    entry about why constant-rate traffic probably won't work in
>    the wild:
>      http://wiki.noreply.org/noreply/TheOnionRouter/TorFAQ#YouShouldPad
>
> [**] What's "enough"?  I'd say "the lifetime of a circuit," but I
>      might be wrong.
>
> [***] But you'd still need to worry about active attacks in this case.
>
>
> peace,
> --
> Nick
>

So, if I understand this correctly, a correlation attack works (on a
very basic level) by noticing that Alice sent a message to Bob (a
known Tor node) at time X, and Dave (another known Tor node) sent a
message to Wally (a web server) at time X+e, where e is about how long
we would expect it to take for the onion to be routed. Is that more or
less the idea?

It seems like determining e (time to route the packet) with any degree
of precision would be pretty difficult, so is this really a big
problem? (or is that still being debated?) On the other hand, if an
attacker could monitor a good number of nodes, wouldn't it be fairly
easy to determine each three-node circuit segment (like Alice, to Bob,
to Charlie) and trace the whole thing end-to-end? It seems like this
could be defeated with a more intelligent type of "chaff", where the
receiving relay generates N random dummy onions (with an appreciable
circuit length) for each onion it receives, and then sends all N+1
into the network in a random order.

Then again, I may have completely missed the boat on this whole
correlation attack thing.

-Brian

-- 
Feel free to contact me using PGP Encryption:
Key Id: 0x3AA70848
Available from: http://keys.gnupg.net