hs_pow: Modify challenge format, include blinded HS id

This is a protocol breaking change that implements nickm's
changes to prop 327 to add an algorithm personalization string
and blinded HS id to the EquiX challenge string for our onion
service client puzzle.

This corresponds with the spec changes in torspec!130,
and it fixes a proposed vulnerability documented in
ticket tor#40789.

Clients and services prior to this patch will no longer
be compatible with the proposed "v1" proof-of-work protocol.

Signed-off-by: Micah Elizabeth Scott <beth@torproject.org>

2 files changed, 103 insertions, 47 deletions

diff --git a/src/test/test_hs_pow.c b/src/test/test_hs_pow.c
index 909a2b569e..072fbacff4 100644
--- a/src/test/test_hs_pow.c
+++ b/src/test/test_hs_pow.c
@@ -264,6 +264,7 @@ test_hs_pow_vectors(void *arg)
     uint32_t validated_effort;
     int expected_retval;
     const char *seed_hex;
+    const char *service_blinded_id_hex;
     const char *nonce_hex;
     const char *sol_hex;
     const char *encoded_hex;
@@ -272,6 +273,7 @@ test_hs_pow_vectors(void *arg)
       /* All zero, expect invalid */
       1, 0, -1,
       "0000000000000000000000000000000000000000000000000000000000000000",
+      "1111111111111111111111111111111111111111111111111111111111111111",
       "00000000000000000000000000000000", "00000000000000000000000000000000",
       "01"
       "00000000000000000000000000000000"
@@ -282,67 +284,74 @@ test_hs_pow_vectors(void *arg)
       /* Valid zero-effort solution */
       0, 0, 0,
       "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa",
-      "55555555555555555555555555555555", "fd57d7676238c0ad1d5473aa2d0cbff5",
+      "1111111111111111111111111111111111111111111111111111111111111111",
+      "55555555555555555555555555555555", "4312f87ceab844c78e1c793a913812d7",
       "01"
       "55555555555555555555555555555555"
       "00000000" "aaaaaaaa"
-      "fd57d7676238c0ad1d5473aa2d0cbff5"
+      "4312f87ceab844c78e1c793a913812d7"
     },
     {
       /* Valid high-effort solution */
       1000000, 1000000, 0,
       "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa",
-      "16505855555555555555555555555555", "bf2c2d345e5773b5c32ec5596244bdbc",
+      "1111111111111111111111111111111111111111111111111111111111111111",
+      "59217255555555555555555555555555", "0f3db97b9cac20c1771680a1a34848d3",
       "01"
-      "16505855555555555555555555555555"
+      "59217255555555555555555555555555"
       "000f4240" "aaaaaaaa"
-      "bf2c2d345e5773b5c32ec5596244bdbc"
+      "0f3db97b9cac20c1771680a1a34848d3"
     },
     {
       /* Reject replays */
       1000000, 0, -1,
       "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa",
-      "16505855555555555555555555555555", "bf2c2d345e5773b5c32ec5596244bdbc",
+      "1111111111111111111111111111111111111111111111111111111111111111",
+      "59217255555555555555555555555555", "0f3db97b9cac20c1771680a1a34848d3",
       "01"
-      "16505855555555555555555555555555"
+      "59217255555555555555555555555555"
       "000f4240" "aaaaaaaa"
-      "bf2c2d345e5773b5c32ec5596244bdbc"
+      "0f3db97b9cac20c1771680a1a34848d3"
     },
     {
       /* The claimed effort must exactly match what's in the challenge */
       99999, 0, -1,
       "86fb0acf4932cda44dbb451282f415479462dd10cb97ff5e7e8e2a53c3767a7f",
-      "cdd49fdbc34326d9d2f18ed277469c63", "7f153437c58620d3ea4717746093dde6",
+      "bfd298428562e530c52bdb36d81a0e293ef4a0e94d787f0f8c0c611f4f9e78ed",
+      "2eff9fdbc34326d9d2f18ed277469c63", "400cb091139f86b352119f6e131802d6",
       "01"
-      "cdd49fdbc34326d9d2f18ed277469c63"
+      "2eff9fdbc34326d9d2f18ed277469c63"
       "0001869f" "86fb0acf"
-      "7f153437c58620d3ea4717746093dde6"
+      "400cb091139f86b352119f6e131802d6"
     },
     {
       /* Otherwise good solution but with a corrupted nonce */
       100000, 0, -1,
       "86fb0acf4932cda44dbb451282f415479462dd10cb97ff5e7e8e2a53c3767a7f",
-      "cdd49fdbc34326d9d2f18ed270469c63", "7f153437c58620d3ea4717746093dde6",
+      "bfd298428562e530c52bdb36d81a0e293ef4a0e94d787f0f8c0c611f4f9e78ed",
+      "2eff9fdbc34326d9a2f18ed277469c63", "400cb091139f86b352119f6e131802d6",
       "01"
-      "cdd49fdbc34326d9d2f18ed270469c63"
+      "2eff9fdbc34326d9a2f18ed277469c63"
       "000186a0" "86fb0acf"
-      "7f153437c58620d3ea4717746093dde6"
+      "400cb091139f86b352119f6e131802d6"
     },
     {
       /* Corrected version of above */
       100000, 100000, 0,
       "86fb0acf4932cda44dbb451282f415479462dd10cb97ff5e7e8e2a53c3767a7f",
-      "cdd49fdbc34326d9d2f18ed277469c63", "7f153437c58620d3ea4717746093dde6",
+      "bfd298428562e530c52bdb36d81a0e293ef4a0e94d787f0f8c0c611f4f9e78ed",
+      "2eff9fdbc34326d9d2f18ed277469c63", "400cb091139f86b352119f6e131802d6",
       "01"
-      "cdd49fdbc34326d9d2f18ed277469c63"
+      "2eff9fdbc34326d9d2f18ed277469c63"
       "000186a0" "86fb0acf"
-      "7f153437c58620d3ea4717746093dde6"
+      "400cb091139f86b352119f6e131802d6"
     }
   };
 
   testing_hs_pow_service_t *tsvc = testing_hs_pow_service_new();
   hs_pow_service_state_t *pow_state = tor_malloc_zero(sizeof *pow_state);
   tsvc->service.state.pow_state = pow_state;
+  tsvc->service.desc_current = service_descriptor_new();
   pow_state->rend_request_pqueue = smartlist_new();
 
   char *mem_op_hex_tmp = NULL;
@@ -353,6 +362,7 @@ test_hs_pow_vectors(void *arg)
   const unsigned num_vectors = sizeof vectors / sizeof vectors[0];
   for (unsigned vec_i = 0; vec_i < num_vectors; vec_i++) {
     const int expected_retval = vectors[vec_i].expected_retval;
+    const char *service_blinded_id_hex = vectors[vec_i].service_blinded_id_hex;
     const char *seed_hex = vectors[vec_i].seed_hex;
     const char *nonce_hex = vectors[vec_i].nonce_hex;
     const char *sol_hex = vectors[vec_i].sol_hex;
@@ -368,10 +378,19 @@ test_hs_pow_vectors(void *arg)
     };
     int retval;
 
+    tt_int_op(strlen(service_blinded_id_hex), OP_EQ, 2 * HS_POW_ID_LEN);
     tt_int_op(strlen(seed_hex), OP_EQ, 2 * HS_POW_SEED_LEN);
     tt_int_op(strlen(nonce_hex), OP_EQ, 2 * sizeof solution.nonce);
     tt_int_op(strlen(sol_hex), OP_EQ, 2 * sizeof solution.equix_solution);
 
+    tt_assert(tsvc->service.desc_current);
+    ed25519_public_key_t *desc_blinded_pubkey =
+        &tsvc->service.desc_current->desc->plaintext_data.blinded_pubkey;
+
+    tt_int_op(base16_decode((char*)desc_blinded_pubkey->pubkey,
+                            HS_POW_ID_LEN, service_blinded_id_hex,
+                            2 * HS_POW_ID_LEN),
+                            OP_EQ, HS_POW_ID_LEN);
     tt_int_op(base16_decode((char*)pow_state->seed_previous, HS_POW_SEED_LEN,
                             seed_hex, 2 * HS_POW_SEED_LEN),
                             OP_EQ, HS_POW_SEED_LEN);
@@ -382,6 +401,7 @@ test_hs_pow_vectors(void *arg)
                             sol_hex, 2 * HS_POW_EQX_SOL_LEN),
                             OP_EQ, HS_POW_EQX_SOL_LEN);
 
+    ed25519_pubkey_copy(&tsvc->service_ip->blinded_id, desc_blinded_pubkey);
     memcpy(solution.seed_head, pow_state->seed_previous, HS_POW_SEED_HEAD_LEN);
 
     /* Try to encode 'solution' into a relay cell */
@@ -468,6 +488,7 @@ test_hs_pow_vectors(void *arg)
   tor_free(decrypted);
   trn_cell_introduce1_free(cell);
   trn_cell_introduce_encrypted_free(enc_cell);
+  service_descriptor_free(tsvc->service.desc_current);
   testing_hs_pow_service_free(tsvc);
   hs_pow_remove_seed_from_cache(NULL);
 }
diff --git a/src/test/test_hs_pow_slow.c b/src/test/test_hs_pow_slow.c
index e7d1311cee..e21eee3395 100644
--- a/src/test/test_hs_pow_slow.c
+++ b/src/test/test_hs_pow_slow.c
@@ -21,6 +21,7 @@
 
 static int
 testing_one_hs_pow_solution(const hs_pow_solution_t *ref_solution,
+                            const ed25519_public_key_t *service_blinded_id,
                             const uint8_t *seed)
 {
   int retval = -1;
@@ -52,7 +53,8 @@ testing_one_hs_pow_solution(const hs_pow_solution_t *ref_solution,
         sol_buffer.equix_solution[variant / 2 % HS_POW_EQX_SOL_LEN]++;
       }
 
-      tt_int_op(expected, OP_EQ, hs_pow_verify(s, &sol_buffer));
+      tt_int_op(expected, OP_EQ,
+                hs_pow_verify(service_blinded_id, s, &sol_buffer));
     }
   }
 
@@ -77,109 +79,136 @@ test_hs_pow_vectors(void *arg)
     uint32_t effort;
     const char *solve_rng_hex;
     const char *seed_hex;
+    const char *service_blinded_id_hex;
     const char *nonce_hex;
     const char *sol_hex;
   } vectors[] = {
     {
       0, "55555555555555555555555555555555",
       "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa",
-      "55555555555555555555555555555555", "fd57d7676238c0ad1d5473aa2d0cbff5"
+      "1111111111111111111111111111111111111111111111111111111111111111",
+      "55555555555555555555555555555555", "4312f87ceab844c78e1c793a913812d7"
     },
     {
       1, "55555555555555555555555555555555",
       "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa",
-      "55555555555555555555555555555555", "703d8bc75492e8f90d836dd21bde61fc"
+      "1111111111111111111111111111111111111111111111111111111111111111",
+      "55555555555555555555555555555555", "84355542ab2b3f79532ef055144ac5ab"
+    },
+    {
+      1, "55555555555555555555555555555555",
+      "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa",
+      "1111111111111111111111111111111111111111111111111111111111111110",
+      "55555555555555555555555555555555", "115e4b70da858792fc205030b8c83af9"
     },
     {
       2, "55555555555555555555555555555555",
       "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa",
-      "56555555555555555555555555555555", "c2374478d35040b53e4eb9aa9f16e9ec"
+      "1111111111111111111111111111111111111111111111111111111111111111",
+      "55555555555555555555555555555555", "4600a93a535ed76dc746c99942ab7de2"
     },
     {
       10, "55555555555555555555555555555555",
       "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa",
-      "5c555555555555555555555555555555", "b167af85e25a0c961928eff53672c1f8"
+      "1111111111111111111111111111111111111111111111111111111111111111",
+      "56555555555555555555555555555555", "128bbda5df2929c3be086de2aad34aed"
     },
     {
       10, "ffffffffffffffffffffffffffffffff",
       "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa",
-      "02000000000000000000000000000000", "954e4464715842d391712bb3b2289ff8"
+      "1111111111111111111111111111111111111111111111111111111111111111",
+      "01000000000000000000000000000000", "203af985537fadb23f3ed5873b4c81ce"
     },
     {
       1337, "7fffffffffffffffffffffffffffffff",
       "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa",
-      "eaffffffffffffffffffffffffffffff", "dbab3eb9045f85f8162c482d43f7d6fc"
+      "4111111111111111111111111111111111111111111111111111111111111111",
+      "01000000000000000000000000000000", "31c377cb72796ed80ae77df6ac1d6bfd"
     },
     {
-      31337, "00410000000000000000000000000000",
+      31337, "34a20000000000000000000000000000",
       "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa",
-      "23410000000000000000000000000000", "545ddd60e33bfa73ec75aada68608ee8"
+      "1111111111111111111111111111111111111111111111111111111111111111",
+      "36a20000000000000000000000000000", "ca6899b91113aaf7536f28db42526bff"
     },
     {
-      100, "6b555555555555555555555555555555",
+      100, "55555555555555555555555555555555",
       "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa",
-      "6b555555555555555555555555555555", "7e14e98fed2f35a1b293b39d56b260e9"
+      "1111111111111111111111111111111111111111111111111111111111111111",
+      "56555555555555555555555555555555", "3a4122a240bd7abfc922ab3cbb9479ed"
     },
     {
-      1000, "0e565555555555555555555555555555",
+      1000, "d3555555555555555555555555555555",
       "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa",
-      "0e565555555555555555555555555555", "514963616e0b986afb1414afa88b85ff"
+      "1111111111111111111111111111111111111111111111111111111111111111",
+      "d4555555555555555555555555555555", "338cc08f57697ce8ac2e4b453057d6e9"
     },
     {
-      10000, "80835555555555555555555555555555",
+      10000, "c5715555555555555555555555555555",
       "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa",
-      "89835555555555555555555555555555", "7a5164905f8aaec152126258a2462ae6"
+      "1111111111111111111111111111111111111111111111111111111111111111",
+      "c8715555555555555555555555555555", "9f2d3d4ed831ac96ad34c25fb59ff3e2"
     },
     {
-      100000, "fd995655555555555555555555555555",
+      100000, "418d5655555555555555555555555555",
       "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa",
-      "fd995655555555555555555555555555", "8b27f2664340bc88dd5335821a68f5ff"
+      "1111111111111111111111111111111111111111111111111111111111111111",
+      "428d5655555555555555555555555555", "9863f3acd2d15adfd244a7ca61d4c6ff"
     },
     {
-      1000000, "15505855555555555555555555555555",
+      1000000, "58217255555555555555555555555555",
       "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa",
-      "16505855555555555555555555555555", "bf2c2d345e5773b5c32ec5596244bdbc"
+      "1111111111111111111111111111111111111111111111111111111111111111",
+      "59217255555555555555555555555555", "0f3db97b9cac20c1771680a1a34848d3"
     },
     {
       1, "d0aec1669384bfe5ed39cd724d6c7954",
       "c52be1f8a5e6cc3b8fb71cfdbe272cbc91d4d035400f2f94fb0d0074794e0a07",
-      "d0aec1669384bfe5ed39cd724d6c7954", "9e062190e23b34a80562818b14cf4ae5"
+      "bfd298428562e530c52bdb36d81a0e293ef4a0e94d787f0f8c0c611f4f9e78ed",
+      "d1aec1669384bfe5ed39cd724d6c7954", "462606e5f8c2f3f844127b8bfdd6b4ff"
     },
     {
       1, "b4d0e611e6935750fcf9406aae131f62",
       "86fb0acf4932cda44dbb451282f415479462dd10cb97ff5e7e8e2a53c3767a7f",
-      "b4d0e611e6935750fcf9406aae131f62", "a01cf4457a016488df4fa45f0864b6fb"
+      "bfd298428562e530c52bdb36d81a0e293ef4a0e94d787f0f8c0c611f4f9e78ed",
+      "b4d0e611e6935750fcf9406aae131f62", "9f3fbd50b1a83fb63284bde44318c0fd"
     },
     {
       1, "b4d0e611e6935750fcf9406aae131f62",
       "9dfbd06d86fed8e12de3ab214e1a63ea61f46253fe08346a20378da70c4a327d",
-      "b5d0e611e6935750fcf9406aae131f62", "5944a260423392780f10b25b7e2502d3"
+      "bec632eb76123956f99a06d394fcbee8f135b8ed01f2e90aabe404cb0346744a",
+      "b4d0e611e6935750fcf9406aae131f62", "161baa7490356292d020065fdbe55ffc"
     },
     {
       1, "40559fdbc34326d9d2f18ed277469c63",
       "86fb0acf4932cda44dbb451282f415479462dd10cb97ff5e7e8e2a53c3767a7f",
-      "40559fdbc34326d9d2f18ed277469c63", "31139564ca5262a4f82b9385b2832fce"
+      "bfd298428562e530c52bdb36d81a0e293ef4a0e94d787f0f8c0c611f4f9e78ed",
+      "40559fdbc34326d9d2f18ed277469c63", "fa649c6a2c5c0bb6a3511b9ea4b448d1"
     },
     {
-      10000, "70559fdbc34326d9d2f18ed277469c63",
+      10000, "34569fdbc34326d9d2f18ed277469c63",
       "86fb0acf4932cda44dbb451282f415479462dd10cb97ff5e7e8e2a53c3767a7f",
-      "72559fdbc34326d9d2f18ed277469c63", "262c6c82025c53b69b0bf255606ca3e2"
+      "bfd298428562e530c52bdb36d81a0e293ef4a0e94d787f0f8c0c611f4f9e78ed",
+      "36569fdbc34326d9d2f18ed277469c63", "2802951e623c74adc443ab93e99633ee"
     },
     {
-      100000, "c0d49fdbc34326d9d2f18ed277469c63",
+      100000, "2cff9fdbc34326d9d2f18ed277469c63",
       "86fb0acf4932cda44dbb451282f415479462dd10cb97ff5e7e8e2a53c3767a7f",
-      "cdd49fdbc34326d9d2f18ed277469c63", "7f153437c58620d3ea4717746093dde6"
+      "bfd298428562e530c52bdb36d81a0e293ef4a0e94d787f0f8c0c611f4f9e78ed",
+      "2eff9fdbc34326d9d2f18ed277469c63", "400cb091139f86b352119f6e131802d6"
     },
     {
-      1000000, "40fdb1dbc34326d9d2f18ed277469c63",
+      1000000, "5243b3dbc34326d9d2f18ed277469c63",
       "86fb0acf4932cda44dbb451282f415479462dd10cb97ff5e7e8e2a53c3767a7f",
-      "4cfdb1dbc34326d9d2f18ed277469c63", "b31bbb45340e17a14c2156c0b66780e7"
+      "bfd298428562e530c52bdb36d81a0e293ef4a0e94d787f0f8c0c611f4f9e78ed",
+      "5543b3dbc34326d9d2f18ed277469c63", "b47c718b56315e9697173a6bac1feaa4"
     },
   };
 
   const unsigned num_vectors = sizeof vectors / sizeof vectors[0];
   for (unsigned vec_i = 0; vec_i < num_vectors; vec_i++) {
     const char *seed_hex = vectors[vec_i].seed_hex;
+    const char *service_blinded_id_hex = vectors[vec_i].service_blinded_id_hex;
     const char *solve_rng_hex = vectors[vec_i].solve_rng_hex;
     const char *nonce_hex = vectors[vec_i].nonce_hex;
     const char *sol_hex = vectors[vec_i].sol_hex;
@@ -191,11 +220,16 @@ test_hs_pow_vectors(void *arg)
       .effort = vectors[vec_i].effort,
     };
 
+    tt_int_op(strlen(service_blinded_id_hex), OP_EQ, 2 * HS_POW_ID_LEN);
     tt_int_op(strlen(seed_hex), OP_EQ, 2 * sizeof input.seed);
     tt_int_op(strlen(solve_rng_hex), OP_EQ, 2 * sizeof rng_bytes);
     tt_int_op(strlen(nonce_hex), OP_EQ, 2 * sizeof solution.nonce);
     tt_int_op(strlen(sol_hex), OP_EQ, 2 * sizeof solution.equix_solution);
 
+    tt_int_op(base16_decode((char*)input.service_blinded_id.pubkey,
+                            HS_POW_ID_LEN, service_blinded_id_hex,
+                            2 * HS_POW_ID_LEN),
+                            OP_EQ, HS_POW_ID_LEN);
     tt_int_op(base16_decode((char*)input.seed, HS_POW_SEED_LEN,
                             seed_hex, 2 * HS_POW_SEED_LEN),
                             OP_EQ, HS_POW_SEED_LEN);
@@ -223,7 +257,8 @@ test_hs_pow_vectors(void *arg)
     tt_mem_op(&solution.equix_solution, OP_EQ, &output.equix_solution,
               sizeof output.equix_solution);
 
-    tt_int_op(testing_one_hs_pow_solution(&output, input.seed), OP_EQ, 0);
+    tt_int_op(testing_one_hs_pow_solution(&output, &input.service_blinded_id,
+                                          input.seed), OP_EQ, 0);
   }
 
  done: