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

Wed May 11 18:19:48 UTC 2011

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 at cs.uwaterloo.ca> wrote:
>  [...]
> >>   * I'm hoping to write this up as a proposed spec soon, unless Ian or
> >> somebody wants to give it a shot.
> >
> > Please go ahead.
> 
> Here's a draft sketch that I've put into proposals/ideas in the the
> torspec repository.  Please let me know what I've gotten wrong, what
> is over/under-engineered, and so on.
> 
> Filename: xxx-ntor-handshake.txt
> Title: Improved circuit-creation key exchange
> Author:  Nick Mathewson
> Created: 11-May-2011
> Status: Draft
> 
> 
> This is an attempt to translate the proposed circuit handshake from
> "Anonymity and one-way authentication in key-exchange protocols" by
> Goldberg, Stebila, and Ustaoglu, into a Tor proposal format.
> 
> It assumes something like Robert Ransom's proposal draft is in place to
> provide an extended CREATE cell format that can indicate what type of
> handshake is in use.
> 
> Notation:
> 
>   Let a|b be the concatenation of a with b.
> 
>   Let H(x,t) be a tweakable hash function of output width H_LENGTH bytes.
> 
>   Let t_keyid, t_mac, t_key, and t_verify be a set of arbitrarily-chosen tweaks
>   for the hash function.
> 
>   Let EXP(a,b) be a^b in some appropriate group G where the appropriate DH
>   parameters hold.  Let's say elements of this group, when represented as
>   byte strings, are all G_LENGTH bytes long.  Let's say we are using a
>   generator g for this group.
> 
>   Let PROTOID be a string designating this variant of the protocol.
> 
>   Let KEYID be a collision-resistant (but not necessarily preimage-resistant)
>      hash function on members of G, of output length H_LENGTH bytes.
> 
> Instantiation:
> 
>   Let's call this PROTOID "ntor-curve25519-sha256-1"

Note that if the things you're hashing spill over a (56 mod 64) byte
boundary, you pay extra.  So it may behoove us to count bytes and see if
PROTOID couldn't be a little shorter.

>   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.

>   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.

> 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.

>     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, 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.

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.
> 
> 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