We need to split streamid into recognized and streamid

[Roger Dingledine]

I broke the insert-dummies-if-conflict design, but I have a bandaid for
it, but at this point I don't think we should apply the bandaid. Here's
why.

a) The special cases in the protocol are turning into a mess. It will
be hard to argue correctness, much less security.
b) Special cases that are rare but can happen sometimes are really hard
to test and debug. They will similarly be hard to maintain.
c) I've spent the past several days trying to make this work and still
haven't gotten it right.

I think the real fix is to make it sufficiently unlikely that a cell will
be incorrectly recognized. Then if we like we can check for conflicts
(easy to do) and close the circuit if we find one.

With n bits of recognized and 3 hops to each circuit (meaning
2 opportunities per relay cell to conflict -- the nearest hop in the
circuit can't conflict because it never looks at the encrypted incoming
relay cell), we're looking at 250*2**n bytes of _outgoing_ material for
each expected conflict. For n=2, that's 16 megabytes. For n=4, that's 1TB.

We can sneak out a few more bytes by looking more closely at
suspected-recognized cells, and deciding they're not actually recognized
if the relay_command is invalid, or the claimed cell length is more than
RELAY_PAYLOAD_SIZE. This raises it to 3.3 petabytes per expected conflict.

[Alternate design: keep 2 bytes of recognized, and if recognized=0, check
integrity: if integrity matches, count it as recognized, else pass it
on. What security problems are we introducing by making integrity serve
two duties?]

Below are some details of the problem with the insert-dummies-if-conflict
design.

On Wed, Dec 17, 2003 at 02:59:55AM -0500, Roger Dingledine wrote:
>  assuming the "send a dummy
> instead if the encryption happens to make recognized='00' prematurely"
> idea (also not implemented yet) works.

Imagine the following scenario.

Alice -> 1 -> 2
Alice has a circuit open through 1 to 2, and wants to deliver a relay
cell to 2.

For simplicity, imagine all stream ciphers are currently at counter 1000.

Normally, she would set the 'recognized' field to 0, crypt it to 2,
crypt it to 1, then deliver it. So afterwards all four counters in the
system (2 at Alice, 1 at 1, 1 at 2) will be at 1509. (Payload sizes are
509 currently.)

But let's imagine she crypts it to 2, and the resulting 'recognized'
field is also 0. Then she crypts it to 1, and sends it to 1, but when
1 decrypts it he recognizes it and doesn't pass it to 2.

So to not screw things up, our current plan is that Alice will insert
a dummy relay cell into the circuit, destined for 1, and thus we avoid
'losing' the relay cell destined for 2. Specifically, when Alice realizes
there is a relay conflict, she rewinds her counter for 2 back to 1000
(she hasn't sent anything yet, after all), sends the dummy relay cell
instead, and then repeats trying to send the original relay cell.

But the problem here is that the dummy relay cell to 1 doesn't change
2's counter. So when we try again to address the relay cell to 2 we're
going to have the same problem.

Ok, so we'll address the dummy relay cell to 2, to make sure to advance
its counter. But that's exactly the problem -- we can't address relay
cells to 2 based on 2's current counter state.

And we can't address relay cells to a hop later than 2 in the circuit
(which would seem to solve the problem), because 2 is the end of the
circuit.

A bandaid is to have a special-case where if you're the end of the
circuit and you get a relay cell with recognized=257, then you also
treat it as recognized. (I had originally said recognized=1, but after
playing with it I realized that when they both have a 0 byte they're much
more likely to collide.) I partly implemented this (including rechecking
all the hops when crypting with recognized=257, since it might crypt to
recognized=0 at an intermediate hop which would screw up the ciphers --
and it's turtles all the way down, deciding what to do when the padding
cell conflicts). But in any case, it still seems to not work, and barring
breakthrough solutions at this point I'm not really inclined to keep
messing with it.

--Roger