Link padding and the intersection attack

[Roger Dingledine]

[Posting to list with Carl's permission]

On Thu, Aug 08, 2002 at 05:57:45PM -0400, Carleton Bosley wrote:
> ok, I haven't responded yet because I'm at work, but I'll look at this
> later. My question for now: What exactly is link padding?
> 
> Google brings up some interesting links below, but I haven't quite found a
> definition yet. Sending lots of fake messages, basically, which are then
> dropped and do not generate more fake response messages? That seems likely
> insecure, but if you're just checking the two links, may be better.
> 
> So, what are the fake messages, where are they sent (uniformly at random
> to routers?), and what is the n^2 -- the number of times such a (single?)
> fake message is sent?
> 
> Carl
> 
> http://www.eskimo.com/~weidai/freedom-attacks.txt
> http://www.wired.com/news/politics/0,1283,43355,00.html

Padding comes in a variety of forms.

In onion routing, cells are 128 bytes (8 bytes for header, 120 for
payload). The fundamental idea behind padding is to send a cell where
the adversary can't tell if the payload contains data or just junk.

1) With \emph{link padding}, you might send cells at fixed rates between
two routers or between a user and a router. If the link is encrypted,
the two participants can distinguish data from padding, but an observer
cannot. When a cell is scheduled to be sent, the sender uses a data cell
if available, else a padding cell. (You don't actually need the rate to
be fixed -- you just need each cell to plausibly be data or padding.)

Of course, it's more complex than that, e.g. because an adversary watching
part of the system might know that no data cells entered a router
during a given time, so the cells it's sending out are less likely to
be data cells.

1b) So link padding could be just between Alice and the first router,
or it might be only between routers, or both. In my recent mails I've
been focusing on link padding between Alice and the first router.

2) \emph{Long-range padding}, aka \emph{end-to-end padding}, is where some
routers cannot determine whether a given data cell actually contains
data. For instance, maybe it looks like a data cell at one node in
the path, but a later node can distinguish it as a padding cell after
decryption (and know to drop it). End-to-end padding is often done by
Alice all the way through to the last router in her path, so the routers
in between can't tell when she's sending actual data.

Hope this helps to clarify. Ask more questions. And check out the
archives, particularly the July ones, at http://archives.seul.org/or/dev/
for lots more discussion of link and long-range padding.

--Roger