Re: [tor-dev] New paper by Goldberg, Stebila, and Ostaoglu with proposed circuit handshake

[Watson Ladd <watsonbladd@xxxxxxxxx>]

On Wed, May 11, 2011 at 1:19 PM, Ian Goldberg <iang@xxxxxxxxxxxxxxx> wrote:
> On Wed, May 11, 2011 at 01:33:17PM -0400, Nick Mathewson wrote:
>> On Fri, May 6, 2011 at 11:12 AM, Ian Goldberg <iang@xxxxxxxxxxxxxxx> wrote:
>> Â[...]
>> [...]
>
>> Â Set H(x,t) == HMAC_SHA256 with message x and key t. So H_LENGTH == 32.
>>  Set t_mac  == PROTOID | ":mac"
>> Â Â Â t_key1 Â== PROTOID | ":key1"
>> Â Â Â t_key2 Â== PROTOID | ":verify"
>> Â Set EXP(a,b) == curve25519(a,b), and g == 9 .
>
> Careful! ÂThe arguments to curve25519 are (output, exponent, base).
> (Note the order; that confused me when we were coding up Sphinx.)
> Presumably you meant for EXP(a,b) to mean a^b, though.
>
> Note that 9 does not have prime order in curve25519; it has order 8
> times a prime. ÂBut if the client always ensures private keys are 0 mod
> 8 (as djb requires; see below), this problem is mostly elided.

More technically we have H=the curve25519 group, which is Z/pZxZ/8Z.
Since private keys are 0 mod 8 they always annihilate the Z/8Z part.
So the curve25519 group is in fact one that is cyclic with prime order
when we generate private keys the right way. The problem is completely
elided
>
>> Â Set KEYID(B) == B. Â(We don't need to use a hash function here, since our
>> Â Â Âkeys are already very short. ÂIt is trivially collision-resistant, since
>> Â Â ÂKEYID(A)====KEYID(B) iff A==B.)
>
> Is "====" intentional?
>
>> Protocol:
>>
>> Â Take a router with identity key digest ID.
>>
>> Â As setup, the router generates a secret key b, and a public onion key
>
> All "generates a secret key" operations should follow djb's
> recommendation, of course (fiddle with the 2 high bits, and clear the
> low 3 bits).
>
>> Â B = EXP(g,b). ÂThe router publishes B in its server descriptor.
>>
>> Â To send a create cell, the client generates a keypair of x, X=EXP(g,y) and
>
> X=EXP(g,x) presumably?
>
>> Â sends a CREATE cell with contents:
>>
>> Â Â NODEID: Â Â ID Â Â Â Â Â Â -- H_LENGTH bytes
>> Â Â KEYID: Â Â ÂKEYID(B) Â Â Â -- H_LENGTH bytes
>> Â Â CLIENT_PK: ÂX Â Â Â Â Â Â Â-- G_LENGTH bytes
>>
>> Â The server checks X,
>
> What is "checks X" here? ÂSince the server doesn't really care whether
> or not the crypto is good, this check can probably be elided.
In the GSO paper it is required that X be a non identity element. This
is nontrivial given the curve25519 wire format,  but is either
squaring four times or checking that EXP(X,y) is not zero. when we
calculate it.
>
>> generates a keypair of y, Y=EXP(g,y) and computes
>>
>> Â Â secret_input = EXP(X,y) | EXP(X,b) | ID | B | X | Y | PROTOID
>> Â Â KEY_SEED = H(secret_input, t_key)
>> Â Â verify = H(secret_input, t_verify)
>
> Depending on the lengths involved, the above may be doing some
> unnecessary work.
Counting time! EXP(X,y), EXP(X,b), B, X and Y are all 32 bytes, so we
have 160 bytes there. The nearest boundary above is 184, but PROTOID
is 23 bytes and ID is 32 bytes (H_LENG), so we have a total of 215
bytes, wasting 33 bytes in the hash (This is assuming I interpreted 56
(mod 64) correctly). We could take a page out of DJB's book and make
ID simply B to fix this.
>
>> Â Â auth_input = verify | ID | B | Y | X | PROTOID | "Server"
>>
>> Â The server sends a CREATED cell containing:
>>
>> Â Â SERVER_PK: ÂY Â Â Â Â Â Â Â Â Â Â -- G_LENGTH bytes
>> Â Â AUTH: Â Â Â H(auth_input, t_mac) Â-- H_LENGTH byets
>>
>> Â The client then checks Y, and computes
Here we want to count the bytes in the inner and outer hashes. The
outer hash hashes 64 bytes: nothing we can do about that. But the
inner one hashes the key length plus the message length, which here is
189 bytes, 5 bytes over
a nice block boundary.
>
> Here, the check is more important. ÂIdeally, one would check that Y \in
> G^* (which should have prime order, but doesn't here). ÂBut in
> curve25519, I think you can get away with something a bit cheaper. ÂIf Y
> isn't in G at all, but is on the twist curve, the AUTH verification
> below is certain to fail, so that's OK. ÂIf it's in G, but has low order
> (i.e. order dividing 8), then EXP(Y,x) will end up being the point at
> infinity, which would be bad. Â(Indeed, it would be pretty much the same
> problem that Tor had lo those many years ago.) So I think it's probably
> OK to check that EXP(Y,x), which you're computing anyway, is not the
> point at infinity. ÂI don't remember offhand how curve25519 represents
> that point; it may be as simple as all-0s, but you should check.
Checking EXP(Y,x) is non zero is correct, according to my reading of
the Curve25519 paper and the GSO paper. Again, curve25519 takes place
on a group that has structure Z/pZxZ/8Z, and valid private keys
annihilate the Z/8Z component.

>
> Berkant and Doug, opinions on this?
>
>> Â Â secret_input = EXP(Y,x) | EXP(B,x) | ID | B | X | Y | PROTOID
>> Â Â KEY_SEED = H(secret_input, t_key1)
>
> Above, you used t_key, not t_key1, to create the KEY_SEED.
>
>> Â Â verify = H(secret_input, t_verify)
>> Â Â auth_input = verify | ID | B | Y | X | PROTOID | "Server"
>>
>> Â Â The client verifies that AUTH == H(auth_input, t_mac).
>>
>> Â Both parties now have a shared value for KEY_SEED. ÂThey expand this into
>> Â the keys needed for the Tor relay protocol.
Here the counting is the same, as the same things are being HMACed.
>>
>> Key expansion:
>>
>> Â Currently, the key expansion formula used by Tor here is
>>
>> Â Â Â ÂK = SHA(K0 | [00]) | SHA(K0 | [01]) | SHH(K0 | [02]) | ...
>
> SHH => SHA
>
>> Â Â Â Âwhere K0==g^xy, and K is divvied up into Df, Db, Kf, and Kb portions.
>>
>> Â Instead, let's have it be
>>
>> Â Â Â ÂK = H(KEY_SEED, t_expand1) | H(KEY_SEED, t_expand2) | ...
>>
>> Â where t_expand1..N are tweaks for the hash.
>
> Krawczyk has a paper on how to do this crypto-correctly:
>
> http://eprint.iacr.org/2010/264
>
> See section 8 for an explanation of why the above is not ideal. ÂNote
> that our "KEY_SEED" is approximately his "PRK", not his "SKM", as it's
> already been hashed. ÂSo if t_expand = PROTOID | ":expand", what's he's
> suggesting is
>
> K = K_1 | K_2 | ...
> where
> K_1 = H(t_expand | 0, KEY_SEED)
> K_(i+1) = H(K_i | t_expand | i, KEY_SEED)
>
> Note that KEY_SEED is used as the HMAC *key*, not the *message*.
>
>> Performance notes:
>>
>> Â In Tor's current circuit creation handshake, the client does:
>> Â Â ÂOne RSA public-key encryption
>> Â Â ÂA full DH handshake in Z_p
>> Â Â ÂA short AES encryption
>> Â Â ÂFive SHA1s for key expansion
>> Â And the server does:
>> Â Â ÂOne RSA private-key decryption
>> Â Â ÂA full DH handshake in Z_p
>> Â Â ÂA short AES decryption
>> Â Â ÂFive SHA1s for key expansion
>>
>> Â While in the revised handshake, the client does:
>> Â Â ÂA full DH handshake
>> Â Â ÂA public-half of a DH handshake
>> Â Â Â3 H operations for the handshake
>> Â Â Â3 H operations for the key expansion
>> Â and the server does:
>> Â Â ÂA full DH handshake
>> Â Â ÂA private-half of a DH handshake
>> Â Â Â3 H operations for the handshake
>> Â Â Â3 H operations for the key expansion
>
> Note that each H operation is 2 underlying hashes.
>
> Â - Ian
> _______________________________________________
> tor-dev mailing list
> tor-dev@xxxxxxxxxxxxxxxxxxxx
> https://lists.torproject.org/cgi-bin/mailman/listinfo/tor-dev
>
The GSO paper uses HMAC for only some of the operations that we are
doing them on and use hash functions of double the length of the HMAC.
Is this an important detail or an unimportant one?

Sincerely,
Watson Ladd
_______________________________________________
tor-dev mailing list
tor-dev@xxxxxxxxxxxxxxxxxxxx
https://lists.torproject.org/cgi-bin/mailman/listinfo/tor-dev