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