Re: Request for comments: tor protocol overhaul

[Paul Syverson <syverson@itd.nrl.navy.mil>]

First a quibble:

> Sixth, we get forward anonymity: the keys at each hop are ephemeral,
> so an adversary who owns a node in the path can't record the stream,
> then arrive at each successive hop and demand the stream's decryption.

The description of forward anonymity is a bit mangled.  Even with
ephemeral DH keys, you can go to each hop and demand decryption if the
circuit is still active. And even without them, i.e. the current
technique, you cannot do this if the circuit is not active and the
"onion keys" have been deleted.  The advantage of ephemeral keys is in
the following: In our current setting, keeping the entire stream of a
connection (including setup) and then later breaking the long-term
decryption key for that OR will allow you to first get the onion key
and then read the whole stream (iterate as needed to get the whole
path and ultimate outside endpoint 'n plaintext).
With ephemeral DH keys, the ephemeral (onion) key is never sent. So,
saving the stream against later breaking of the longterm key won't
help you; it won't get you the ephemeral key. I assume everybody knows
this, but it seemed garbled to me here.

Something a bit more serious:

> 
> If a stream ID is accidentally matched even once in a circuit, the whole
> circuit is screwed. But 64 bits of stream ID to prevent accidental
> matching is plenty. Consider 8 hops to a path and 7 exit connections
> per hop. That's 64 possible patterns that might accidentally match at
> each cell. We're still looking at 58 bits of security -- so we expect
> the first collision to occur after around 2^66 bytes of data.

When discussing it with Roger and Nick, I noted that when we were
having religious wars about such inband signalling in the design of the
first second generation onion routing ;>), we came up with an encoding
scheme that made it impossible to have collisions.

I looked through the mail archives on onion-router.net and could find
reference to this, but not how we did it (you can look yourselves if
you like, but I think I checked thoroughly). It may be in some other
archive not on the web site, but I couldn't find it. I think the
scheme involved the OP checking to see if any data encryption produced
a control message and if so playing some game shifting the bytes around
so that one never got an appropriate length string of zeros in true
data.  

I think we could do something even simpler however, the OP simply
check for collisions as it produces encrypted layers for relay data
cells. If it runs into one, it can just give the relevant node a
dummy/drop command for that cell and re-encrypt the application data
with the next part of the key streams (and iterate the check). That
should also mean there is never a possibility of collision. I don't
know if the overhead on the OP of even this small check on every layer
of every cell is worth the tradeoff of making collision impossible
absent other changes. (And I was on the inband signaling side of the
war, so that would be OK with me.)  But, if it meant we could reduce
the stream ID to say four bytes because now there can never be a
collision, then it might be worth it. Without collision, how long
would the stream ID need to be? My guess is four would be
adequate. How bad is the overhead on the OP from this?  My guess is
not too much. And hey, that frees up four bytes to solve our other
problems that we're not talking about yet.

aloha,
Paul