Tor's integrity verification system?

Question

I am trying to understand the design of Tor(onion router). I am reading the original paper on the 2nd generation onion routing system. Where, under integrity checking on streams, they say, "When Alice negotiates a key with a new hop, they each initialize a SHA-1 digest with a derivative of that key. Then they each incrementally add to SHA-1 digest the contents of all relay cells they create, and include with each relay cell the first four bytes of the current digest. Each also keeps a SHA-1 digest of data received, to verify that the received hashes are correct."

How does this work?

What I think is happening: I believe, after initializing a new SHA-1 digest, all the contents of new relay cell are XORed with the digest to produce new "digest". And the first 4 bytes from this digest is put in the digest field of the relay cell and sent. Back at Bob(OR), a similar process is repeated and the first 4 bytes of the recently computed "digest" is compared with the one received.

I understand that this helps in preventing an insider attack at modifying the cell contents as the attacker must be able to deduce the current digest state. However, I don't understand the use of calculating SHA-1 of the cell contents at Bob's end and how it helps verify that the received hashes are correct.

Answer 1

No. What this means is that they concatenate all of this data and then SHA1-hash the concatenation. There's no xor-ing of digests or anything like that.

The reason it's described this way is because many hashing APIs allow you to specify the data in a streaming fashion: you can specify the first few bytes of the message to be hashed, then you can specify a few more bytes (which will effectively be appended to the previous parts), then some more, and so on; eventually you tell the API that you are done and please return the hash. You can think of the API as storing all of the data you passed to it, concatenating it, and hashing it all at the end. However, for better performance, the API doesn't actually need to store all of that data: because of the way that SHA1 works internally, it can hash the data on the fly and avoid the need to store so much. Anyway, the wording used to describe what is to be hashed is probably an artifact that mirrors the structure of the API for many SHA1 implementations.

This helps defend against man-in-the-middle attacks. If both endpoints have the same SHA1 hash, then they must be using exactly the same data. If a man-in-the-middle tries to modify any of this data while it is in transit, then the two endpoints will have different inputs to SHA1, so they will end up with different SHA1 digests. Depending upon how the rest of the protocol is constructed, that may provide an opportunity to detect the man-in-the-middle.