prop224: Service address creation/validation

This also adds unit test and a small python script generating a deterministic
test vector that a unit test tries to match.

Signed-off-by: David Goulet <dgoulet@torproject.org>

4 files changed, 327 insertions, 0 deletions

diff --git a/src/or/hs_common.c b/src/or/hs_common.c
index b524296159..00befabbc2 100644
--- a/src/or/hs_common.c
+++ b/src/or/hs_common.c
@@ -346,6 +346,184 @@ rend_data_get_pk_digest(const rend_data_t *rend_data, size_t *len_out)
   }
 }
 
+/* Using an ed25519 public key and version to build the checksum of an
+ * address. Put in checksum_out. Format is:
+ *    SHA3-256(".onion checksum" || PUBKEY || VERSION)
+ *
+ * checksum_out must be large enough to receive 32 bytes (DIGEST256_LEN). */
+static void
+build_hs_checksum(const ed25519_public_key_t *key, uint8_t version,
+                  char *checksum_out)
+{
+  size_t offset = 0;
+  char data[HS_SERVICE_ADDR_CHECKSUM_INPUT_LEN];
+
+  /* Build checksum data. */
+  memcpy(data, HS_SERVICE_ADDR_CHECKSUM_PREFIX,
+         HS_SERVICE_ADDR_CHECKSUM_PREFIX_LEN);
+  offset += HS_SERVICE_ADDR_CHECKSUM_PREFIX_LEN;
+  memcpy(data + offset, key->pubkey, ED25519_PUBKEY_LEN);
+  offset += ED25519_PUBKEY_LEN;
+  set_uint8(data + offset, version);
+  offset += sizeof(version);
+  tor_assert(offset == HS_SERVICE_ADDR_CHECKSUM_INPUT_LEN);
+
+  /* Hash the data payload to create the checksum. */
+  crypto_digest256(checksum_out, data, sizeof(data), DIGEST_SHA3_256);
+}
+
+/* Using an ed25519 public key, checksum and version to build the binary
+ * representation of a service address. Put in addr_out. Format is:
+ *    addr_out = PUBKEY || CHECKSUM || VERSION
+ *
+ * addr_out must be large enough to receive HS_SERVICE_ADDR_LEN bytes. */
+static void
+build_hs_address(const ed25519_public_key_t *key, const char *checksum,
+                 uint8_t version, char *addr_out)
+{
+  size_t offset = 0;
+
+  tor_assert(key);
+  tor_assert(checksum);
+
+  memcpy(addr_out, key->pubkey, ED25519_PUBKEY_LEN);
+  offset += ED25519_PUBKEY_LEN;
+  memcpy(addr_out + offset, checksum, HS_SERVICE_ADDR_CHECKSUM_LEN_USED);
+  offset += HS_SERVICE_ADDR_CHECKSUM_LEN_USED;
+  set_uint8(addr_out + offset, version);
+  offset += sizeof(uint8_t);
+  tor_assert(offset == HS_SERVICE_ADDR_LEN);
+}
+
+/* Helper for hs_parse_address(): Using a binary representation of a service
+ * address, parse its content into the key_out, checksum_out and version_out.
+ * Any out variable can be NULL in case the caller would want only one field.
+ * checksum_out MUST at least be 2 bytes long. address must be at least
+ * HS_SERVICE_ADDR_LEN bytes but doesn't need to be NUL terminated. */
+static void
+hs_parse_address_impl(const char *address, ed25519_public_key_t *key_out,
+                      char *checksum_out, uint8_t *version_out)
+{
+  size_t offset = 0;
+
+  tor_assert(address);
+
+  if (key_out) {
+    /* First is the key. */
+    memcpy(key_out->pubkey, address, ED25519_PUBKEY_LEN);
+  }
+  offset += ED25519_PUBKEY_LEN;
+  if (checksum_out) {
+    /* Followed by a 2 bytes checksum. */
+    memcpy(checksum_out, address + offset, HS_SERVICE_ADDR_CHECKSUM_LEN_USED);
+  }
+  offset += HS_SERVICE_ADDR_CHECKSUM_LEN_USED;
+  if (version_out) {
+    /* Finally, version value is 1 byte. */
+    *version_out = get_uint8(address + offset);
+  }
+  offset += sizeof(uint8_t);
+  /* Extra safety. */
+  tor_assert(offset == HS_SERVICE_ADDR_LEN);
+}
+
+/* Using a base32 representation of a service address, parse its content into
+ * the key_out, checksum_out and version_out. Any out variable can be NULL in
+ * case the caller would want only one field. checksum_out MUST at least be 2
+ * bytes long.
+ *
+ * Return 0 if parsing went well; return -1 in case of error. */
+int
+hs_parse_address(const char *address, ed25519_public_key_t *key_out,
+                 char *checksum_out, uint8_t *version_out)
+{
+  char decoded[HS_SERVICE_ADDR_LEN];
+
+  tor_assert(address);
+
+  /* Obvious length check. */
+  if (strlen(address) != HS_SERVICE_ADDR_LEN_BASE32) {
+    log_warn(LD_REND, "Service address %s has an invalid length. "
+                      "Expected %ld but got %lu.",
+             escaped_safe_str(address), HS_SERVICE_ADDR_LEN_BASE32,
+             strlen(address));
+    goto invalid;
+  }
+
+  /* Decode address so we can extract needed fields. */
+  if (base32_decode(decoded, sizeof(decoded), address, strlen(address)) < 0) {
+    log_warn(LD_REND, "Service address %s can't be decoded.",
+             escaped_safe_str(address));
+    goto invalid;
+  }
+
+  /* Parse the decoded address into the fields we need. */
+  hs_parse_address_impl(decoded, key_out, checksum_out, version_out);
+
+  return 0;
+ invalid:
+  return -1;
+}
+
+/* Validate a given onion address. The length, the base32 decoding and
+ * checksum are validated. Return 1 if valid else 0. */
+int
+hs_address_is_valid(const char *address)
+{
+  uint8_t version;
+  char checksum[HS_SERVICE_ADDR_CHECKSUM_LEN_USED];
+  char target_checksum[DIGEST256_LEN];
+  ed25519_public_key_t key;
+
+  /* Parse the decoded address into the fields we need. */
+  if (hs_parse_address(address, &key, checksum, &version) < 0) {
+    goto invalid;
+  }
+
+  /* Get the checksum it's suppose to be and compare it with what we have
+   * encoded in the address. */
+  build_hs_checksum(&key, version, target_checksum);
+  if (tor_memcmp(checksum, target_checksum, sizeof(checksum))) {
+    log_warn(LD_REND, "Service address %s invalid checksum.",
+             escaped_safe_str(address));
+    goto invalid;
+  }
+
+  /* Valid address. */
+  return 1;
+ invalid:
+  return 0;
+}
+
+/* Build a service address using an ed25519 public key and a given version.
+ * The returned address is base32 encoded and put in addr_out. The caller MUST
+ * make sure the addr_out is at least HS_SERVICE_ADDR_LEN_BASE32 + 1 long.
+ *
+ * Format is as follow:
+ *     base32(PUBKEY || CHECKSUM || VERSION)
+ *     CHECKSUM = H(".onion checksum" || PUBKEY || VERSION)
+ * */
+void
+hs_build_address(const ed25519_public_key_t *key, uint8_t version,
+                 char *addr_out)
+{
+  char checksum[DIGEST256_LEN], address[HS_SERVICE_ADDR_LEN];
+
+  tor_assert(key);
+  tor_assert(addr_out);
+
+  /* Get the checksum of the address. */
+  build_hs_checksum(key, version, checksum);
+  /* Get the binary address representation. */
+  build_hs_address(key, checksum, version, address);
+
+  /* Encode the address. addr_out will be NUL terminated after this. */
+  base32_encode(addr_out, HS_SERVICE_ADDR_LEN_BASE32 + 1, address,
+                sizeof(address));
+  /* Validate what we just built. */
+  tor_assert(hs_address_is_valid(addr_out));
+}
+
 /* Initialize the entire HS subsytem. This is called in tor_init() before any
  * torrc options are loaded. Only for >= v3. */
 void
diff --git a/src/or/hs_common.h b/src/or/hs_common.h
index d1bc5ac7ef..64bf89f398 100644
--- a/src/or/hs_common.h
+++ b/src/or/hs_common.h
@@ -52,6 +52,30 @@
 /* The time period rotation offset as seen in prop224 section [TIME-PERIODS] */
 #define HS_TIME_PERIOD_ROTATION_OFFSET (12 * 60) /* minutes */
 
+/* Prefix of the onion address checksum. */
+#define HS_SERVICE_ADDR_CHECKSUM_PREFIX ".onion checksum"
+/* Length of the checksum prefix minus the NUL terminated byte. */
+#define HS_SERVICE_ADDR_CHECKSUM_PREFIX_LEN \
+  (sizeof(HS_SERVICE_ADDR_CHECKSUM_PREFIX) - 1)
+/* Length of the resulting checksum of the address. The construction of this
+ * checksum looks like:
+ *   CHECKSUM = ".onion checksum" || PUBKEY || VERSION
+ * where VERSION is 1 byte. This is pre-hashing. */
+#define HS_SERVICE_ADDR_CHECKSUM_INPUT_LEN \
+  (HS_SERVICE_ADDR_CHECKSUM_PREFIX_LEN + ED25519_PUBKEY_LEN + sizeof(uint8_t))
+/* The amount of bytes we use from the address checksum. */
+#define HS_SERVICE_ADDR_CHECKSUM_LEN_USED 2
+/* Length of the binary encoded service address which is of course before the
+ * base32 encoding. Construction is:
+ *    PUBKEY || CHECKSUM || VERSION
+ * with 1 byte VERSION and 2 bytes CHECKSUM. The following is 35 bytes. */
+#define HS_SERVICE_ADDR_LEN \
+  (ED25519_PUBKEY_LEN + HS_SERVICE_ADDR_CHECKSUM_LEN_USED + sizeof(uint8_t))
+/* Length of 'y' portion of 'y.onion' URL. This is base32 encoded and the
+ * length ends up to 56 bytes (not counting the terminated NUL byte.) */
+#define HS_SERVICE_ADDR_LEN_BASE32 \
+  (CEIL_DIV(HS_SERVICE_ADDR_LEN * 8, 5))
+
 /* Type of authentication key used by an introduction point. */
 typedef enum {
   HS_AUTH_KEY_TYPE_LEGACY  = 1,
@@ -64,6 +88,11 @@ void hs_free_all(void);
 int hs_check_service_private_dir(const char *username, const char *path,
                                  unsigned int dir_group_readable,
                                  unsigned int create);
+void hs_build_address(const ed25519_public_key_t *key, uint8_t version,
+                      char *addr_out);
+int hs_address_is_valid(const char *address);
+int hs_parse_address(const char *address, ed25519_public_key_t *key_out,
+                     char *checksum_out, uint8_t *version_out);
 
 void rend_data_free(rend_data_t *data);
 rend_data_t *rend_data_dup(const rend_data_t *data);
diff --git a/src/test/hs_build_address.py b/src/test/hs_build_address.py
new file mode 100644
index 0000000000..7be9c8b85a
--- /dev/null
+++ b/src/test/hs_build_address.py
@@ -0,0 +1,37 @@
+import sys
+import hashlib
+import struct
+import base64
+
+# Python 3.6+, the SHA3 is available in hashlib natively. Else this requires
+# the pysha3 package (pip install pysha3).
+if sys.version_info < (3, 6):
+    import sha3
+
+# Test vector to make sure the right sha3 version will be used. pysha3 < 1.0
+# used the old Keccak implementation. During the finalization of SHA3, NIST
+# changed the delimiter suffix from 0x01 to 0x06. The Keccak sponge function
+# stayed the same. pysha3 1.0 provides the previous Keccak hash, too.
+TEST_VALUE = "e167f68d6563d75bb25f3aa49c29ef612d41352dc00606de7cbd630bb2665f51"
+if TEST_VALUE != sha3.sha3_256(b"Hello World").hexdigest():
+    print("pysha3 version is < 1.0. Please install from:")
+    print("https://github.com/tiran/pysha3https://github.com/tiran/pysha3")
+    sys.exit(1)
+
+# Checksum is built like so:
+#   CHECKSUM = SHA3(".onion checksum" || PUBKEY || VERSION)
+PREFIX = ".onion checksum".encode()
+# 32 bytes ed25519 pubkey.
+PUBKEY = ("\x42" * 32).encode()
+# Version 3 is proposal224
+VERSION = 3
+
+data = struct.pack('15s32sb', PREFIX, PUBKEY, VERSION)
+checksum = hashlib.sha3_256(data).digest()
+
+# Onion address is built like so:
+#   onion_address = base32(PUBKEY || CHECKSUM || VERSION) + ".onion"
+address = struct.pack('!32s2sb', PUBKEY, checksum, VERSION)
+onion_addr = base64.b32encode(address).decode().lower()
+
+print("%s" % (onion_addr))
diff --git a/src/test/test_hs_service.c b/src/test/test_hs_service.c
index 17772f1df0..e081b7f2f3 100644
--- a/src/test/test_hs_service.c
+++ b/src/test/test_hs_service.c
@@ -207,6 +207,85 @@ test_hs_ntor(void *arg)
   tt_mem_op(client_hs_ntor_rend_cell_keys.ntor_key_seed, OP_EQ,
             service_hs_ntor_rend_cell_keys.ntor_key_seed,
             DIGEST256_LEN);
+ done:
+  ;
+}
+
+static void
+test_validate_address(void *arg)
+{
+  int ret;
+
+  (void) arg;
+
+  /* Address too short and too long. */
+  setup_full_capture_of_logs(LOG_WARN);
+  ret = hs_address_is_valid("blah");
+  tt_int_op(ret, OP_EQ, 0);
+  expect_log_msg_containing("has an invalid length");
+  teardown_capture_of_logs();
+
+  setup_full_capture_of_logs(LOG_WARN);
+  ret = hs_address_is_valid(
+           "p3xnclpu4mu22dwaurjtsybyqk4xfjmcfz6z62yl24uwmhjatiwnlnadb");
+  tt_int_op(ret, OP_EQ, 0);
+  expect_log_msg_containing("has an invalid length");
+  teardown_capture_of_logs();
+
+  /* Invalid checksum (taken from prop224) */
+  setup_full_capture_of_logs(LOG_WARN);
+  ret = hs_address_is_valid(
+           "l5satjgud6gucryazcyvyvhuxhr74u6ygigiuyixe3a6ysis67ororad");
+  tt_int_op(ret, OP_EQ, 0);
+  expect_log_msg_containing("invalid checksum");
+  teardown_capture_of_logs();
+
+  setup_full_capture_of_logs(LOG_WARN);
+  ret = hs_address_is_valid(
+           "btojiu7nu5y5iwut64eufevogqdw4wmqzugnoluw232r4t3ecsfv37ad");
+  tt_int_op(ret, OP_EQ, 0);
+  expect_log_msg_containing("invalid checksum");
+  teardown_capture_of_logs();
+
+  /* Non base32 decodable string. */
+  setup_full_capture_of_logs(LOG_WARN);
+  ret = hs_address_is_valid(
+           "????????????????????????????????????????????????????????");
+  tt_int_op(ret, OP_EQ, 0);
+  expect_log_msg_containing("can't be decoded");
+  teardown_capture_of_logs();
+
+  /* Valid address. */
+  ret = hs_address_is_valid(
+           "p3xnclpu4mu22dwaurjtsybyqk4xfjmcfz6z62yl24uwmhjatiwnlnad");
+  tt_int_op(ret, OP_EQ, 1);
+
+ done:
+  ;
+}
+
+static void
+test_build_address(void *arg)
+{
+  int ret;
+  char onion_addr[HS_SERVICE_ADDR_LEN_BASE32 + 1];
+  ed25519_public_key_t pubkey;
+
+  (void) arg;
+
+  /* The following has been created with hs_build_address.py script that
+   * follows proposal 224 specification to build an onion address. */
+  static const char *test_addr =
+    "ijbeeqscijbeeqscijbeeqscijbeeqscijbeeqscijbeeqscijbezhid";
+
+  /* Let's try to build the same onion address that the script can do. Key is
+   * a long set of very random \x42 :). */
+  memset(&pubkey, '\x42', sizeof(pubkey));
+  hs_build_address(&pubkey, HS_VERSION_THREE, onion_addr);
+  tt_str_op(test_addr, OP_EQ, onion_addr);
+  /* Validate that address. */
+  ret = hs_address_is_valid(onion_addr);
+  tt_int_op(ret, OP_EQ, 1);
 
  done:
   ;
@@ -326,6 +405,10 @@ struct testcase_t hs_service_tests[] = {
     NULL, NULL },
   { "e2e_rend_circuit_setup", test_e2e_rend_circuit_setup, TT_FORK,
     NULL, NULL },
+  { "build_address", test_build_address, TT_FORK,
+    NULL, NULL },
+  { "validate_address", test_validate_address, TT_FORK,
+    NULL, NULL },
 
   END_OF_TESTCASES
 };