Cell header changes / solving malleability

[Roger Dingledine]

On Thu, Aug 28, 2003 at 02:31:54AM -0400, Nick Mathewson wrote:
> Just to clarify: I don't think you say what exactly the SHA-1 hash is
> supposed to cover.  I assume that it covers all fields except ACI.  Is
> this right?

Good point. I think if we use integrity headers only for relay cells
(see below), then it should cover everything but the outer header.
That is, we can't predict the ACI, and the command already has to be
'relay' for us to realize we should check the integrity.

> Also, I assume that the purpose of the psuedorandomness is to prevent
> cell contents from being predictable, so that an attacker can't modify
> the contents and the checksum too.

Correct. The attacker must be able to guess some bits of the cell to be
able to remove them and add in his own bits. The hash requires him to
guess all the (covered) bits of the cell, so he can correct the hash when
he changes a bit. And because the hash covers the pseudorandomness, he
needs to be able to guess those bits in order to make the checksum match.

> In other words, SHA1 will significantly affect our processing demands.

Hm. I'd like to respond "no problem, we're going to be saturating our
links anyway, so what's a bit more cpu?"

But currently we're not able to reliably push more than about 3 megabits
through the moria onion routers. (Granted there are three of them on
the same machine, so we can probably handle closer to 8-10mbit. But still,
many of our planned nodes have 10mbit pipes

So I agree, we should seriously consider anything that will increase the
crypto load.

> But we may not need SHA1.  We only want a 4-byte digest, after all, and
> we don't care so much about simple collision-resistance as we do about
> preventing an attacker who knows A=E(H(msg|rand)) and B=E(msg|rand) and
> msg from modifying A and B such that A'=E(H(B')).
> 
> There may be cheap functions that meet this need.

This way lies madness. We should reduce the crypto load in our protocol,
not try to find hash functions that nobody else uses. 

But do feel free to poke around and see if you find any good-sounding
ones, so at least we'll know what we're missing.

> > We could instead back off on our threat model, and only concern ourselves
> > with evil nodes in the middle of the circuit, rather than evil ISPs who
> > own links. In that case non-relay nodes could skip the integrity header.
> 
> Or we could use an encryption mode other than Counter for our link
> connections.  Since cells are 256 bytes long, and 256 is an even
> multiple of our block size, we can probably use a mode where single-bit
> errors turn the rest of the connection's data to junk.

This is worth pursuing. Nick, can you do some research and let us know
what mode does what we want?

This would let us drop the integrity header from the non-relay cells. So
now only the endpoints of the circuit would need to do some more aes
(for prng) and a hash for each relay cell.

If we go this route, we may want a link-encrypt-cell abstraction, which
on the inside encrypts the cell back-to-front. This is so bit-flips in
the payload turn the header into gibberish (rather than having to wait
until the next cell to possibly notice).

And we should also note that we don't have any fixed plaintext to
use for detecting a trashed cell. Indeed, the outer header is now
only 3 bytes. This design choice basically requires us to switch from
"tolerate malformed cells and drop them" to "if we get a malformed cell,
freak out". There's a 1/25 chance that a random cell command will be
valid. Depending on how many circuits are currently present, the chance
of colliding with a known aci is quite low. What do we do if we receive
a cell for an unused aci -- close the entire connection to that OR? We'd
need to revamp our protocol to make sure never ever to send an extra
destroy cell, etc. Too brittle.

But let's back up a minute. Rather than worrying about detecting a
broken cell for sure right when the bitflip happens, is it ok to get ~95%
accuracy for each cell? After all, the chance that a repeated sequence of
trashed cells will all have valid cell commands is very low. So perhaps
we could leave the protocol the same, and simply add "if you get a cell
with an invalid cell command, close the connection." I'm ok with this.
It's not total security, but it seems far cleaner than a bunch more
crypto at each hop.

But on the third hand, remember that non-relay cells are really quite
rare. I think we're worrying about performance on something that is
far from the bottleneck. It may just be cleaner/easier to not add any
more crypto infrastructure, and just slap an integrity header on the
non-relay cells.

Hm.

> Assuming we want to use an integer number of bytes, two bytes is the
> optimal number if we have a number of streams in the range 2...257.

Good to know. (It agrees with my quick calculations I made while writing
the original mail.)

--Roger