[tor-dev] A concrete proposal for crypto (at least part of it)

[Watson Ladd]

Dear All,
Rather then get further sucked into a debate that is producing more
heat then light about Wegman-Carter, I've decided to make a concrete
proposal for how Tor can better protect its streams from manipulation.

Right now Tor encrypts the streams of data from a client to a OR with
AES-CTR and no integrity checks.
I propose the following: On establishment of a new connection between
a client and an OR (using either the Goldman et al paper or
ephermental DH) the client and the OR derive a single 16-byte K. The
client has an 8 byte counter which starts at 1, the client counter,
the OR an 8 byte counter which starts at 0, the OR counter. Each cell
from the client to the OR is protected by AES-GCM defined as in the
NIST standard, with a 4 byte string "TorC" being used to make our
counter 12 bytes. (If you read the standard you will see this is the
method for generating nonces recommended). The counter is incremented
by 2 each time a packet is sent. Under no circumstances can it go
backward. Under no circumstances does an OR or Client accept a packet
that reuses a nonce (nonces should be sent along if we make transport
unreliable). Under no circumstances are more then 2^64 packets sent.
Under no circumstances are packets longer then 2^32 bytes. Following
these rules an attacker who sends 2^64 forgery attempts has
probability 2^-36 of successfully forging one message. If we limit the
attacker to 2 billion forgery attempts (forgery must be online) then
the probability of forgery is 2^-68. I think we can live with that.
These numbers come from
http://cr.yp.to/antiforgery/securitywcs-20050227.pdf. Note that these
numbers assume AES is secure, and are theorems if AES is secure.

This proposal is independent from the establishment of streams. This
proposal eliminates issues relating to an intermediate node flipping
bits in an HTTP request, thereby tagging the traffic, amongst other
evil things manipulation can do. If we want more performance the
evaluation
of a polynomial over GF(2^128) can be replaced by GF(2^130-5), or AES
could be replaced by xsalsa20, and the nonce lengthened.
Sincerely,
Watson Ladd
---
"Those who would give up Essential Liberty to purchase a little
Temporary Safety deserve neither  Liberty nor Safety."
-- Benjamin Franklin