[Cryptography] traffic analysis

[Jerry Leichter]

On Jan 27, 2015, at 5:08 AM, grarpamp <grarpamp at gmail.com> wrote:
> With the abundance of even just passive adversaries
> these days, the importance of cover traffic, fill, flooding,
> chaff, however you call it can't be overstated as a
> necessity if you wish to hide the endponts ot actual
> traffic without playing too much that risky odds game.
> 
> It amazes me that, while there are some papers
> about it, no one appears to have actually produced
> software for users to download, install and run, for a
> working network based on it.
The problem is that every network out there is built on the basis of statistical assumptions about demand:  Not everyone will want to send stuff at the same time, and even peak demand is well below theoretical peak demand.  To go to the extreme, sure, Google Fiber offers 1Gb/second - but how many customers running all out will overload any possible backbone behind the single link from the house to the concentrator?

If everyone starts sending constant cover traffic, links will be quickly overloaded all over the place.  At which point the providers will start charging per bit (which is what caps really amount to - they're just quantized units of per bit traffic) and have a real case for doing so - and nobody will be happy.

There's room to do much better.  For one thing, you don't need to saturate your link with cover traffic - you need to send enough cover traffic so that a listener can't tell the difference between cover and real traffic.  If your cover traffic rate equals your average rate over some period of time, you're not adding more traffic - you're simply replacing some of your cover messages with real messages.  But ... what happens when you have a peak demand way above your average?  As Stealthmonger has commented concerning anonymity, if you want security against traffic analysis, you have to accept delays:  Set your cover traffic rate somewhat higher than your average rate, and you'll *eventually* catch up with peaks (though as with any queueing system, the delays can grow without bound - requiring unbounded memory *somewhere*).

Different network designs can also help.  If you own the link and both of its ends, it costs you exactly the same to send continuous random bits as to leave the line idle.  Any encrypted traffic (assuming an encryptor whose output is indistinguishable from random noise() is then safe from observation.  The Hot Line between the US and Moscow was, I believe, designed to work this way.  How this extends to a packet-switched network, especially one where you can't trust the switches, is unclear.

I'm not aware of any open research on these kinds of questions - though it may well be out there.  What's the optimum cover traffic rate under various assumptions about the real traffic rate and distribution?  When is it safe to use the traffic other users present as cover for your own?  Clearly if there's only one other user sending traffic, you can't use him for cover as *he* can tell which of the packets are yours.  But is there a way to mix traffic from multiple users in a way that requires large numbers of them to conspire to reveal anything?  The mixmaster stuff looks at this specifically from the point of view of a store-and-forward node - is there some suitable useful analogue on a single link?  Can we somehow get the same guarantees without storage inside the network?

Just as researchers, for many years, ignored denial of service attacks on the theory that "We can't do much about them, but who would bother to make such attacks anyway?", most modern work ignores traffic analysis as "impractical".  Well ... we had to change our attitudes about DoS, and we're now going to have to change our attitudes toward traffic analysis.

                                                        -- Jerry