Tor : Computing Digest for Relay-Cells

[Roger Dingledine]

[Cc'ing to or-dev, since this info might be useful for other people as
well. Stefan is implementing a Tor client in Java. -RD]

On Mon, May 10, 2004 at 06:54:06PM +0200, Stefan wrote:
> ok, i don't understand what data you use for computing the digest.
> 
> i will make a example :
> 
> i connect to the first router and send a create cell. then i get a created 
> cell. now i want to send a relay begin cell. how do i compute the digest. do 
> i have to use the create, created and the new relay cell with a digest of 
> zero? do i have to use the unencrypted or the encrypted cell?

You send a create cell to node#1, and he replies with a created cell.
When the created cell comes back, you can derive key material K from
H(g^xy | 00) | H(g^xy | 01) | ...
The server sends the first 20 bytes of K in the created cell, to prove
that he established the same session key you hoped he did (that is, to
prove that he knows the private key of node#1). So you should verify
those to make sure everything is ok.

 From the spec:
   The first 20 bytes of K form KH, bytes 21-40 form the forward digest
   Df, 41-60 form the backward digest Db, 61-76 form Kf, and 77-92
   form Kb.

   KH is used in the handshake response to demonstrate knowledge of the
   computed shared key. Df is used to seed the integrity-checking hash
   for the stream of data going from the OP to the OR, and Db seeds the
   integrity-checking hash for the data stream from the OR to the OP. Kf
   is used to encrypt the stream of data going from the OP to the OR, and
   Kb is used to encrypt the stream of data going from the OR to the OP.

So now you want to send an 'extend' cell to node#1, to ask it to send a
create cell to node#2. So you build an 'extend' cell:

main header: circid is the one chosen for node#1. command is 'relay'.

relay header: relay command 'extend', recognized 0, streamid 0, digest
0 (for now), length 2+4+42+12+128.

relay payload: the addr:port of node#2 (in network order, not host order),
and the onionskin (the same format you used for the create cell, before).

Now that you've built the extend cell, you can calculate the right value
for digest: It will be the first 4 bytes of the sha-1 of: Df (the one
derived from node#1's session key, that is) (20 bytes) concatenated with
the relay header+payload of the cell (509 bytes).

Once the digest is set, then you want to encrypt the cell to node#1:
encrypt all 509 bytes (relay header+payload) with the Kf derived from
node#1's session key.

Then send it down the wire. (TLS will add another layer of encryption
to it, and then peel it off again on the other side.)

A while later, if you're lucky, a relay cell will return. You will know
this because the cell->command will be 'relay'. The remaining 509 bytes
will be encrypted at this point. But you know which circuit it came from
(cell->circ_id tells you), so you can decrypt it: Use Kb to decrypt the
509 bytes of payload.

At this point, "recognized" should be 0. If it's not, something has gone
wrong. If it is, then you should check the digest to be sure. (Recognized
is only 2 bytes, so it's useful to improve performance, but not to detect
tampering.) Set the digest field to 0, and compute the first 4 bytes
of the sha1 of: Db from node#1 (20 bytes) concatenated with the relay
header+payload of the new cell (509 bytes). If that matches the cell's
digest (before you zeroed it, of course), then we're in business. Now
confirm that the relay command is 'extended'.

Now you should compute KH, Df, Db, Kf, Kb from the payload of this
extended cell. These are the keys derived from the session key with
node#2.

Now say you want to send a relay begin cell, to exit from node#2. So you
build a cell, with the command 'relay' and the circ_id appropriate for
the circuit to node#1. The relay header is like before, but with a relay
command 'begin', and a random stream_id that you generated to signify
this new stream you're beginning. The payload (from tor-spec) is
  ADDRESS | ':' | PORT | [00]
and the length is strlen(relay payload)+1. Now you set the digest
appropriately (first 4 bytes of sha1 of Df-for-node#2 plus this relay
header+payload). Now you encrypt it with Kf-for-node#2, and then a second
time with Kf-for-node#1. You send it down the wire toward node#1.

Node#1 will try to decrypt it, find that recognized is not zero, and
send it to node#2, which will recognize it. A while later you should get
a relay cell back. Decrypt with Kb-for-node#1, see if you recognize it,
repeat for later nodes in the circuit until it's recognized or there are
no more nodes in the circuit. Then check the digest (Db for the node that
recognized it, plus relay header+payloads of all cells that have come from
that node so far (decrypted and with their digests set to 0, that is)).

I hope your SSL has some sort of SHA1_Update()-style interface that lets
you just hand it more bytes. That way it can keep the previously seen
cells in internal state and you don't need to worry about remembering
them.

> sorry for this stupid question, but when i connect to a or and i've created a 
> connection and i'm sending a relay begin cell i only get a destroy cell. 

Sounds like you're getting closer! :)

Let me know if the above works, or where it breaks.

> Stefan

Thanks,
--Roger