Turn xxx-ntor-handshake into a real proposal

1 files changed, 151 insertions, 0 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
+