commit f8c392b65751908ecb7be7f10d41aa3bf0fbe86c Author: Nick Mathewson <nickm@torproject.org> Date: Tue Nov 27 15:39:54 2012 -0500 Turn xxx-ntor-handshake into a real proposal --- proposals/216-ntor-handshake.txt | 151 ++++++++++++++++++++++++++++++++ proposals/ideas/xxx-ntor-handshake.txt | 151 -------------------------------- 2 files changed, 151 insertions(+), 151 deletions(-) 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 + diff --git a/proposals/ideas/xxx-ntor-handshake.txt b/proposals/ideas/xxx-ntor-handshake.txt deleted file mode 100644 index 081d6af..0000000 --- a/proposals/ideas/xxx-ntor-handshake.txt +++ /dev/null @@ -1,151 +0,0 @@ -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 -