From f8c392b65751908ecb7be7f10d41aa3bf0fbe86c Mon Sep 17 00:00:00 2001 From: Nick Mathewson Date: Tue, 27 Nov 2012 15:39:54 -0500 Subject: Turn xxx-ntor-handshake into a real proposal --- proposals/216-ntor-handshake.txt | 151 +++++++++++++++++++++++++++++++++++++++ 1 file changed, 151 insertions(+) create mode 100644 proposals/216-ntor-handshake.txt (limited to 'proposals/216-ntor-handshake.txt') diff --git a/proposals/216-ntor-handshake.txt b/proposals/216-ntor-handshake.txt new file mode 100644 index 0000000..081d6af --- /dev/null +++ b/proposals/216-ntor-handshake.txt @@ -0,0 +1,151 @@ +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_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 a,A=KEYGEN() yield a new private-public keypair in G, where a is the + secret key and A = EXP(g,a). If additional checks are needed to insure + a valid keypair, they should be performed. + + 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" (We might want to make + this shorter if it turns out to save us a block of hashing somewhere.) + + Set H(x,t) == HMAC_SHA256 with message x and key t. So H_LENGTH == 32. + Set t_mac == PROTOID | ":mac" + t_key == PROTOID | ":key" + t_verify == PROTOID | ":verify" + + Set EXP(a,b) == curve25519(.,b,a), and g == 9 . Let KEYGEN() do the + appropriate manipulations when generating the secret key (clearing the + low bits, twiddling the high bits). + + 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.) + +Protocol: + + Take a router with identity key digest ID. + + As setup, the router generates a secret key b, and a public onion key + B with b, B = KEYGEN(). The router publishes B in its server descriptor. + + To send a create cell, the client generates a keypair x,X = KEYGEN(), and + sends a CREATE cell with contents: + + NODEID: ID -- H_LENGTH bytes + KEYID: KEYID(B) -- H_LENGTH bytes + CLIENT_PK: X -- G_LENGTH bytes + PARAMSLEN: -- 2 bytes + PARMS: -- PARAMSLEN byets + + (The "PARAMS" component is used to encode any additional authenticated + information that's needed for establishing the right kind of circuit. + XXXXX nickm added it; we need to ask if it's safe!!!!) + + The server generates a keypair of y,Y = KEYGEN(), and computes + + secret_input = EXP(X,y) | EXP(X,b) | ID | B | X | Y | PARAMSLEN | PARAMS + | PROTOID + KEY_SEED = H(secret_input, t_key) + verify = H(secret_input, t_verify) + auth_input = verify | ID | B | Y | X | PARAMSLEN | PARAMS | 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 is in G^* [see below], and computes + + secret_input = EXP(Y,x) | EXP(B,x) | ID | B | X | Y | PARAMSLEN | PARAMS + | PROTOID + KEY_SEED = H(secret_input, t_key) + verify = H(secret_input, t_verify) + auth_input = verify | ID | B | Y | X | PARAMLENS | PARAMS | PROTOID + | "Server" + + The client verifies that AUTH == H(auth_input, t_mac). + + [NOTE: It may be adequate to check that EXP(Y,x) is not the point at + infinity. See tor-dev thread.] + + 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]) | SHA(K0 | [02]) | ... + + where K0==g^xy, and K is divvied up into Df, Db, Kf, and Kb portions. + + Instead, let's have it be + + K = K_0 | K_1 | K_2 | K_3 | ... + + Where K_0 = H(m_expand | INT8(i) , KEY_SEED ) + and K_(i+1) = H(K_i | m_expand | INT8(i) , KEY_SEED ) + and m_expend is an arbitrarily chosen value, + and INT8(i) is a octet with the value "i". + + Ian says this is due to a construction from Krawczyk at + http://eprint.iacr.org/2010/264 . + +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 + -- cgit v1.2.3-54-g00ecf