Cell header changes / solving malleability

[Roger Dingledine]

On Fri, Aug 29, 2003 at 05:33:30PM -0400, Roger Dingledine wrote:
> On Thu, Aug 28, 2003 at 02:31:54AM -0400, Nick Mathewson wrote:
> > 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.

I was talking to Bram about a related problem, and he suggested something
that I think would help us a lot. If we make the hash cover all the
plaintext ever sent over the circuit to/from that node, we get the
following benefits:

a) We don't need to include randomness in each cell. In order to get
the hash in a cell right, the adversary needs to know all the plaintext
ever sent. As long as we send some randomness at first (either in the
begin cell, in a padding cell, etc), then he can't guess that and so he
can't ever construct correct hashes.

b) We shave a bit of time off our work, since we only initialize the
SHA1 once, and then do incremental hashing from there.

c) Previously, if the adversary could guess the payload of a cell
(including its randomness), then he could change the cell to whatever
he wanted and construct a valid hash -- and all future cells would
be unaffected. Now, he needs to correctly guess the payload of every
future cell too so he can munge the hash to agree with what the recipient
thinks it should be. If we're really paranoid we can send new randomness
periodically, eg in each sendme; but as my advisor used to say, "trust
the math".

The fun SHA1 attack where the bad guy can incrementally add to a hash
to get a new valid hash doesn't apply to us, because we never show any
hashes to anybody.

What do you think?
--Roger