Implement HKDF from RFC5869

This is a customizable extract-and-expand HMAC-KDF for deriving keys.
It derives from RFC5869, which derives its rationale from Krawczyk,
H., "Cryptographic Extraction and Key Derivation: The HKDF Scheme",
Proceedings of CRYPTO 2010, 2010, <http://eprint.iacr.org/2010/264>.

I'm also renaming the existing KDF, now that Tor has two of them.

This is the key derivation scheme specified in ntor.

There are also unit tests.

4 files changed, 135 insertions, 15 deletions

diff --git a/src/common/crypto.c b/src/common/crypto.c
index 37d843396..2147738b4 100644
--- a/src/common/crypto.c
+++ b/src/common/crypto.c
@@ -2184,8 +2184,8 @@ crypto_dh_compute_secret(int severity, crypto_dh_t *dh,
     goto error;
   }
   secret_len = result;
-  if (crypto_expand_key_material(secret_tmp, secret_len,
-                                 secret_out, secret_bytes_out)<0)
+  if (crypto_expand_key_material_TAP((uint8_t*)secret_tmp, secret_len,
+                                     (uint8_t*)secret_out, secret_bytes_out)<0)
     goto error;
   secret_len = secret_bytes_out;
 
@@ -2211,15 +2211,18 @@ crypto_dh_compute_secret(int severity, crypto_dh_t *dh,
  * <b>key_out</b> by taking the first <b>key_out_len</b> bytes of
  *    H(K | [00]) | H(K | [01]) | ....
  *
+ * This is the key expansion algorithm used in the "TAP" circuit extension
+ * mechanism; it shouldn't be used for new protocols.
+ *
  * 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)
+crypto_expand_key_material_TAP(const uint8_t *key_in, size_t key_in_len,
+                               uint8_t *key_out, size_t key_out_len)
 {
   int i;
-  char *cp, *tmp = tor_malloc(key_in_len+1);
-  char digest[DIGEST_LEN];
+  uint8_t *cp, *tmp = tor_malloc(key_in_len+1);
+  uint8_t 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);
@@ -2228,7 +2231,7 @@ crypto_expand_key_material(const char *key_in, size_t key_in_len,
   for (cp = key_out, i=0; cp < key_out+key_out_len;
        ++i, cp += DIGEST_LEN) {
     tmp[key_in_len] = i;
-    if (crypto_digest(digest, tmp, key_in_len+1))
+    if (crypto_digest((char*)digest, (const char *)tmp, key_in_len+1))
       goto err;
     memcpy(cp, digest, MIN(DIGEST_LEN, key_out_len-(cp-key_out)));
   }
@@ -2244,6 +2247,65 @@ crypto_expand_key_material(const char *key_in, size_t key_in_len,
   return -1;
 }
 
+/** Expand some secret key material according to RFC5869, using SHA256 as the
+ * underlying hash.  The <b>key_in_len</b> bytes at <b>key_in</b> are the
+ * secret key material; the <b>salt_in_len</b> bytes at <b>salt_in</b> and the
+ * <b>info_in_len</b> bytes in <b>info_in_len</b> are the algorithm's "salt"
+ * and "info" parameters respectively.  On success, write <b>key_out_len</b>
+ * bytes to <b>key_out</b> and return 0.  On failure, return -1.
+ */
+int
+crypto_expand_key_material_rfc5869_sha256(
+                                    const uint8_t *key_in, size_t key_in_len,
+                                    const uint8_t *salt_in, size_t salt_in_len,
+                                    const uint8_t *info_in, size_t info_in_len,
+                                    uint8_t *key_out, size_t key_out_len)
+{
+  uint8_t prk[DIGEST256_LEN];
+  uint8_t tmp[DIGEST256_LEN + 128 + 1];
+  uint8_t mac[DIGEST256_LEN];
+  int i;
+  uint8_t *outp;
+  size_t tmp_len;
+
+  crypto_hmac_sha256((char*)prk,
+                     (const char*)salt_in, salt_in_len,
+                     (const char*)key_in, key_in_len);
+
+  /* If we try to get more than this amount of key data, we'll repeat blocks.*/
+  tor_assert(key_out_len <= DIGEST256_LEN * 256);
+  tor_assert(info_in_len <= 128);
+  memset(tmp, 0, sizeof(tmp));
+  outp = key_out;
+  i = 1;
+
+  while (key_out_len) {
+    size_t n;
+    if (i > 1) {
+      memcpy(tmp, mac, DIGEST256_LEN);
+      memcpy(tmp+DIGEST256_LEN, info_in, info_in_len);
+      tmp[DIGEST256_LEN+info_in_len] = i;
+      tmp_len = DIGEST256_LEN + info_in_len + 1;
+    } else {
+      memcpy(tmp, info_in, info_in_len);
+      tmp[info_in_len] = i;
+      tmp_len = info_in_len + 1;
+    }
+    crypto_hmac_sha256((char*)mac,
+                       (const char*)prk, DIGEST256_LEN,
+                       (const char*)tmp, tmp_len);
+    n = key_out_len < DIGEST256_LEN ? key_out_len : DIGEST256_LEN;
+    memcpy(outp, mac, n);
+    key_out_len -= n;
+    outp += n;
+    ++i;
+  }
+
+  memwipe(tmp, 0, sizeof(tmp));
+  memwipe(mac, 0, sizeof(mac));
+  return 0;
+}
+
 /** Free a DH key exchange object.
  */
 void
diff --git a/src/common/crypto.h b/src/common/crypto.h
index eb8b1de16..2d31e8d8b 100644
--- a/src/common/crypto.h
+++ b/src/common/crypto.h
@@ -239,8 +239,15 @@ ssize_t crypto_dh_compute_secret(int severity, crypto_dh_t *dh,
                              const char *pubkey, size_t pubkey_len,
                              char *secret_out, size_t secret_out_len);
 void crypto_dh_free(crypto_dh_t *dh);
-int crypto_expand_key_material(const char *key_in, size_t in_len,
-                               char *key_out, size_t key_out_len);
+
+int crypto_expand_key_material_TAP(const uint8_t *key_in,
+                                   size_t key_in_len,
+                                   uint8_t *key_out, size_t key_out_len);
+int crypto_expand_key_material_rfc5869_sha256(
+                                    const uint8_t *key_in, size_t key_in_len,
+                                    const uint8_t *salt_in, size_t salt_in_len,
+                                    const uint8_t *info_in, size_t info_in_len,
+                                    uint8_t *key_out, size_t key_out_len);
 
 /* random numbers */
 int crypto_seed_rng(int startup);
diff --git a/src/or/onion.c b/src/or/onion.c
index cce4bdf73..472051585 100644
--- a/src/or/onion.c
+++ b/src/or/onion.c
@@ -362,8 +362,8 @@ fast_server_handshake(const uint8_t *key_in, /* DIGEST_LEN bytes */
                       uint8_t *key_out,
                       size_t key_out_len)
 {
-  char tmp[DIGEST_LEN+DIGEST_LEN];
-  char *out = NULL;
+  uint8_t tmp[DIGEST_LEN+DIGEST_LEN];
+  uint8_t *out = NULL;
   size_t out_len;
   int r = -1;
 
@@ -374,7 +374,7 @@ fast_server_handshake(const uint8_t *key_in, /* DIGEST_LEN bytes */
   memcpy(tmp+DIGEST_LEN, handshake_reply_out, 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)) {
+  if (crypto_expand_key_material_TAP(tmp, sizeof(tmp), out, out_len)) {
     goto done;
   }
   memcpy(handshake_reply_out+DIGEST_LEN, out, DIGEST_LEN);
@@ -405,8 +405,8 @@ fast_client_handshake(const uint8_t *handshake_state,/*DIGEST_LEN bytes*/
                       uint8_t *key_out,
                       size_t key_out_len)
 {
-  char tmp[DIGEST_LEN+DIGEST_LEN];
-  char *out;
+  uint8_t tmp[DIGEST_LEN+DIGEST_LEN];
+  uint8_t *out;
   size_t out_len;
   int r = -1;
 
@@ -414,7 +414,7 @@ fast_client_handshake(const uint8_t *handshake_state,/*DIGEST_LEN bytes*/
   memcpy(tmp+DIGEST_LEN, handshake_reply_out, 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)) {
+  if (crypto_expand_key_material_TAP(tmp, sizeof(tmp), out, out_len)) {
     goto done;
   }
   if (tor_memneq(out, handshake_reply_out+DIGEST_LEN, DIGEST_LEN)) {
diff --git a/src/test/test_crypto.c b/src/test/test_crypto.c
index fd983de00..6c731386d 100644
--- a/src/test/test_crypto.c
+++ b/src/test/test_crypto.c
@@ -832,6 +832,56 @@ test_crypto_base32_decode(void)
   ;
 }
 
+static void
+test_crypto_hkdf_sha256(void *arg)
+{
+  uint8_t key_material[100];
+  const uint8_t salt[] = "ntor-curve25519-sha256-1:key_extract";
+  const size_t salt_len = strlen((char*)salt);
+  const uint8_t m_expand[] = "ntor-curve25519-sha256-1:key_expand";
+  const size_t m_expand_len = strlen((char*)m_expand);
+  int r;
+  char *mem_op_hex_tmp = NULL;
+
+  (void)arg;
+
+#define EXPAND(s) \
+  r = crypto_expand_key_material_rfc5869_sha256( \
+    (const uint8_t*)(s), strlen(s),              \
+    salt, salt_len,                              \
+    m_expand, m_expand_len,                      \
+    key_material, 100)
+
+  /* Test vectors generated with ntor_ref.py */
+  memset(key_material, 0, sizeof(key_material));
+  EXPAND("");
+  tt_int_op(r, ==, 0);
+  test_memeq_hex(key_material,
+                 "d3490ed48b12a48f9547861583573fe3f19aafe3f81dc7fc75"
+                 "eeed96d741b3290f941576c1f9f0b2d463d1ec7ab2c6bf71cd"
+                 "d7f826c6298c00dbfe6711635d7005f0269493edf6046cc7e7"
+                 "dcf6abe0d20c77cf363e8ffe358927817a3d3e73712cee28d8");
+
+  EXPAND("Tor");
+  tt_int_op(r, ==, 0);
+  test_memeq_hex(key_material,
+                 "5521492a85139a8d9107a2d5c0d9c91610d0f95989975ebee6"
+                 "c02a4f8d622a6cfdf9b7c7edd3832e2760ded1eac309b76f8d"
+                 "66c4a3c4d6225429b3a016e3c3d45911152fc87bc2de9630c3"
+                 "961be9fdb9f93197ea8e5977180801926d3321fa21513e59ac");
+
+  EXPAND("AN ALARMING ITEM TO FIND ON YOUR CREDIT-RATING STATEMENT");
+  tt_int_op(r, ==, 0);
+  test_memeq_hex(key_material,
+                 "a2aa9b50da7e481d30463adb8f233ff06e9571a0ca6ab6df0f"
+                 "b206fa34e5bc78d063fc291501beec53b36e5a0e434561200c"
+                 "5f8bd13e0f88b3459600b4dc21d69363e2895321c06184879d"
+                 "94b18f078411be70b767c7fc40679a9440a0c95ea83a23efbf");
+
+ done:
+  tor_free(mem_op_hex_tmp);
+}
+
 static void *
 pass_data_setup_fn(const struct testcase_t *testcase)
 {
@@ -863,6 +913,7 @@ struct testcase_t crypto_tests[] = {
   { "aes_iv_AES", test_crypto_aes_iv, TT_FORK, &pass_data, (void*)"aes" },
   { "aes_iv_EVP", test_crypto_aes_iv, TT_FORK, &pass_data, (void*)"evp" },
   CRYPTO_LEGACY(base32_decode),
+  { "hkdf_sha256", test_crypto_hkdf_sha256, 0, NULL, NULL },
   END_OF_TESTCASES
 };