Document CREATE_FAST better in the code. Move our key expansion algorithm into a separate function in crypto.c

svn:r5530

6 files changed, 104 insertions, 47 deletions

diff --git a/src/common/crypto.c b/src/common/crypto.c
index 8299173e71..9374103014 100644
--- a/src/common/crypto.c
+++ b/src/common/crypto.c
@@ -1487,11 +1487,9 @@ crypto_dh_compute_secret(crypto_dh_env_t *dh,
                          const char *pubkey, size_t pubkey_len,
                          char *secret_out, size_t secret_bytes_out)
 {
-  char hash[DIGEST_LEN];
   char *secret_tmp = NULL;
   BIGNUM *pubkey_bn = NULL;
   size_t secret_len=0;
-  unsigned int i;
   int result=0;
   tor_assert(dh);
   tor_assert(secret_bytes_out/DIGEST_LEN <= 255);
@@ -1503,7 +1501,7 @@ crypto_dh_compute_secret(crypto_dh_env_t *dh,
     warn(LD_CRYPTO,"Rejected invalid g^x");
     goto error;
   }
-  secret_tmp = tor_malloc(crypto_dh_get_bytes(dh)+1);
+  secret_tmp = tor_malloc(crypto_dh_get_bytes(dh));
   result = DH_compute_key((unsigned char*)secret_tmp, pubkey_bn, dh->dh);
   if (result < 0) {
     warn(LD_CRYPTO,"DH_compute_key() failed.");
@@ -1517,12 +1515,9 @@ crypto_dh_compute_secret(crypto_dh_env_t *dh,
    *   bytes long.
    * What are the security implications here?
    */
-  for (i = 0; i < secret_bytes_out; i += DIGEST_LEN) {
-    secret_tmp[secret_len] = (unsigned char) i/DIGEST_LEN;
-    if (crypto_digest(hash, secret_tmp, secret_len+1))
-      goto error;
-    memcpy(secret_out+i, hash, MIN(DIGEST_LEN, secret_bytes_out-i));
-  }
+  if (crypto_expand_key_material(secret_tmp, secret_len,
+                                 secret_out, secret_bytes_out)<0)
+    goto error;
   secret_len = secret_bytes_out;
 
   goto done;
@@ -1539,6 +1534,44 @@ crypto_dh_compute_secret(crypto_dh_env_t *dh,
     return secret_len;
 }
 
+/** Given <b>key_in_len</b> bytes of negotiated randomness in <b>key_in</b>
+ * ("K"), expand it into <b>key_out_len</b> bytes of negotiated key material in
+ * <b>key_out</b> by taking the first key_out_len bytes of
+ *    H(K | [00]) | H(K | [01]) | ....
+ *
+ * Return 0 on success, -1 on failure.
+ */
+int
+crypto_expand_key_material(const char *key_in, size_t key_in_len,
+                           char *key_out, size_t key_out_len)
+{
+  int i;
+  char *cp, *tmp = tor_malloc(key_in_len+1);
+  char digest[DIGEST_LEN];
+
+  /* If we try to get more than this amount of key data, we'll repeat blocks.*/
+  tor_assert(key_out_len <= DIGEST_LEN*256);
+
+  memcpy(tmp, key_in, key_in_len);
+  for (cp = key_out, i=0; key_out_len; ++i, cp += DIGEST_LEN) {
+    tmp[key_in_len] = i;
+    if (crypto_digest(digest, tmp, key_in_len+1))
+      goto err;
+    memcpy(cp, digest, MIN(DIGEST_LEN, key_out_len));
+    if (key_out_len < DIGEST_LEN)
+      break;
+    key_out_len -= DIGEST_LEN;
+  }
+  memset(tmp, 0, key_in_len+1);
+  tor_free(tmp);
+  return 0;
+
+ err:
+  memset(tmp, 0, key_in_len+1);
+  tor_free(tmp);
+  return -1;
+}
+
 /** Free a DH key exchange object.
  */
 void
diff --git a/src/common/crypto.h b/src/common/crypto.h
index 9ac368f5e9..4c91462878 100644
--- a/src/common/crypto.h
+++ b/src/common/crypto.h
@@ -141,6 +141,8 @@ int crypto_dh_compute_secret(crypto_dh_env_t *dh,
                              const char *pubkey, size_t pubkey_len,
                              char *secret_out, size_t secret_out_len);
 void crypto_dh_free(crypto_dh_env_t *dh);
+int crypto_expand_key_material(const char *key_in, size_t in_len,
+                               char *key_out, size_t key_out_len);
 
 /* random numbers */
 int crypto_seed_rng(void);
diff --git a/src/or/circuitbuild.c b/src/or/circuitbuild.c
index c63c99d184..1755596de1 100644
--- a/src/or/circuitbuild.c
+++ b/src/or/circuitbuild.c
@@ -553,8 +553,9 @@ circuit_send_next_onion_skin(circuit_t *circ)
         return -1;
       }
     } else {
-      /* We are not an OR, and we're building the first hop of a circuit to
-       * a new OR: we can be speedy. */
+      /* We are not an OR, and we're building the first hop of a circuit to a
+       * new OR: we can be speedy and use CREATE_FAST to save an RSA operation
+       * and a DH operation. */
       cell_type = CELL_CREATE_FAST;
       memset(payload, 0, sizeof(payload));
       crypto_rand(circ->cpath->fast_handshake_state,
@@ -769,9 +770,10 @@ circuit_init_cpath_crypto(crypt_path_t *cpath, char *key_data, int reverse)
   return 0;
 }
 
-/** A created or extended cell came back to us on the circuit,
- * and it included <b>reply</b> (the second DH key, plus KH).
- * DOCDOC reply_type.
+/** A created or extended cell came back to us on the circuit, and it included
+ * <b>reply</b> as its body.  (If <b>reply_type</b> is CELL_CREATED, the body
+ * contains (the second DH key, plus KH).  If <b>reply_type</b> is
+ * CELL_CREATED_FAST, the body contains a secret y and a hash H(x|y).)
  *
  * Calculate the appropriate keys and digests, make sure KH is
  * correct, and initialize this hop of the cpath.
diff --git a/src/or/command.c b/src/or/command.c
index 73c3137cbb..3aca6756fd 100644
--- a/src/or/command.c
+++ b/src/or/command.c
@@ -211,6 +211,8 @@ command_process_create_cell(cell_t *cell, connection_t *conn)
     }
     debug(LD_OR,"success: handed off onionskin.");
   } else {
+    /* This is a CREATE_FAST cell; we can handle it immediately without using
+     * a CPU worker.*/
     char keys[CPATH_KEY_MATERIAL_LEN];
     char reply[DIGEST_LEN*2];
     tor_assert(cell->command == CELL_CREATE_FAST);
diff --git a/src/or/onion.c b/src/or/onion.c
index cb65b93598..dc13592a71 100644
--- a/src/or/onion.c
+++ b/src/or/onion.c
@@ -344,68 +344,81 @@ onion_skin_client_handshake(crypto_dh_env_t *handshake_state,
   return 0;
 }
 
-/** DOCDOC */
+/** Implement the server side of the CREATE_FAST abbreviated handshake.  The
+ * client has provided DIGEST_LEN key bytes in <b>key_in</b> ("x").  We
+ * generate a reply of DIGEST_LEN*2 bytes in <b>key_out/b>, consisting of a
+ * new random "y", followed by H(x|y) to check for correctness.  We set
+ * <b>key_out_len</b> bytes of key material in <b>key_out</b>.
+ * Return 0 on success, <0 on failure.
+ **/
 int
 fast_server_handshake(const char *key_in, /* DIGEST_LEN bytes */
                       char *handshake_reply_out, /* DIGEST_LEN*2 bytes */
                       char *key_out,
                       size_t key_out_len)
 {
-  char tmp[DIGEST_LEN+DIGEST_LEN+1];
-  char digest[DIGEST_LEN];
-  int i;
+  char tmp[DIGEST_LEN+DIGEST_LEN];
+  char *out;
+  size_t out_len;
 
   if (crypto_rand(handshake_reply_out, DIGEST_LEN)<0)
     return -1;
 
   memcpy(tmp, key_in, DIGEST_LEN);
   memcpy(tmp+DIGEST_LEN, handshake_reply_out, DIGEST_LEN);
-  tmp[DIGEST_LEN+DIGEST_LEN] = 0;
-  crypto_digest(handshake_reply_out+DIGEST_LEN, tmp, sizeof(tmp));
-
-  for (i = 0; i*DIGEST_LEN < (int)key_out_len; ++i) {
-    size_t len;
-    tmp[DIGEST_LEN+DIGEST_LEN] = i+1;
-    crypto_digest(digest, tmp, sizeof(tmp));
-    len = key_out_len - i*DIGEST_LEN;
-    if (len > DIGEST_LEN) len = DIGEST_LEN;
-    memcpy(key_out+i*DIGEST_LEN, digest, len);
+  out_len = key_out_len+DIGEST_LEN;
+  out = tor_malloc(out_len);
+  if (crypto_expand_key_material(tmp, sizeof(tmp), out, out_len)) {
+    tor_free(out);
+    return -1;
   }
-
+  memcpy(handshake_reply_out+DIGEST_LEN, out, DIGEST_LEN);
+  memcpy(key_out, out+DIGEST_LEN, key_out_len);
+  memset(tmp, 0, sizeof(tmp));
+  memset(out, 0, out_len);
+  tor_free(out);
   return 0;
 }
 
-/** DOCDOC */
+/** Implement the second half of the client side of the CREATE_FAST handshake.
+ * We sent the server <b>handshake_state</b> ("x") already, and the server
+ * told us <b>handshake_reply_out</b> (y|H(x|y)).  Make sure that the hash is
+ * correct, and generate key material in <b>key_out</b>.  Return 0 on success,
+ * true on failure.
+ *
+ * NOTE: The "CREATE_FAST" handshake path is distinguishable from regular
+ * "onionskin" handshakes, and is not secure if an adversary can see or modify
+ * the messages.  Therefore, it should only be used by clients, and only as
+ * the first hop of a circuit (since the first hop is already authenticated
+ * and protected by TLS).
+ */
 int
 fast_client_handshake(const char *handshake_state, /* DIGEST_LEN bytes */
                       const char *handshake_reply_out, /* DIGEST_LEN*2 bytes */
                       char *key_out,
                       size_t key_out_len)
 {
-  char tmp[DIGEST_LEN+DIGEST_LEN+1];
-  char digest[DIGEST_LEN];
-  int i;
+  char tmp[DIGEST_LEN+DIGEST_LEN];
+  char *out;
+  size_t out_len;
 
   memcpy(tmp, handshake_state, DIGEST_LEN);
   memcpy(tmp+DIGEST_LEN, handshake_reply_out, DIGEST_LEN);
-  tmp[DIGEST_LEN+DIGEST_LEN] = 0;
-  crypto_digest(digest, tmp, sizeof(tmp));
-
-  if (memcmp(digest, handshake_reply_out+DIGEST_LEN, DIGEST_LEN)) {
+  out_len = key_out_len+DIGEST_LEN;
+  out = tor_malloc(out_len);
+  if (crypto_expand_key_material(tmp, sizeof(tmp), out, out_len)) {
+    tor_free(out);
+    return -1;
+  }
+  if (memcmp(out, handshake_reply_out+DIGEST_LEN, DIGEST_LEN)) {
     /* H(K) does *not* match. Something fishy. */
     warn(LD_PROTOCOL,"Digest DOES NOT MATCH on fast handshake. Bug or attack.");
     return -1;
   }
-
-  for (i = 0; i*DIGEST_LEN < (int)key_out_len; ++i) {
-    size_t len;
-    tmp[DIGEST_LEN+DIGEST_LEN] = i+1;
-    crypto_digest(digest, tmp, sizeof(tmp));
-    len = key_out_len - i*DIGEST_LEN;
-    if (len > DIGEST_LEN) len = DIGEST_LEN;
-    memcpy(key_out+i*DIGEST_LEN, digest, len);
-  }
-
+  memcpy(key_out, out+DIGEST_LEN, key_out_len);
+  memset(tmp, 0, sizeof(tmp));
+  memset(out, 0, out_len);
+  tor_free(out);
   return 0;
 }
 
diff --git a/src/or/or.h b/src/or/or.h
index bd00f1a575..b3a78f74dc 100644
--- a/src/or/or.h
+++ b/src/or/or.h
@@ -924,6 +924,11 @@ typedef struct crypt_path_t {
   /** Current state of Diffie-Hellman key negotiation with the OR at this
    * step. */
   crypto_dh_env_t *dh_handshake_state;
+  /** Current state of 'fast' (non-PK) key negotiation with the OR at this
+   * step. Used to save CPU when TLS is already providing all the
+   * authentication, secrecy, and integrity we need, and we're already
+   * distinguishable from an OR.
+   */
   char fast_handshake_state[DIGEST_LEN];
   /** Negotiated key material shared with the OR at this step. */
   char handshake_digest[DIGEST_LEN];/* KH in tor-spec.txt */