[tor-bugs] #25576 [Core Tor/Tor]: Fix non-standard use of keccak in v3 hidden service code

[Tor Bug Tracker & Wiki]

#25576: Fix non-standard use of keccak in v3 hidden service code
-------------------------+-------------------------------------------------
     Reporter:  isis     |      Owner:  (none)
         Type:  defect   |     Status:  new
     Priority:  Medium   |  Milestone:  Tor: unspecified
    Component:  Core     |    Version:  Tor: 0.3.0.1-alpha
  Tor/Tor                |   Keywords:  cryptography, crypto, tor-hs,
     Severity:  Normal   |  handshakes
Actual Points:           |  Parent ID:
       Points:           |   Reviewer:
      Sponsor:           |
-------------------------+-------------------------------------------------
 Currently in `src/common/crypto.c` there's the following construction:

 {{{#!C
 /** Compute a MAC using SHA3-256 of <b>msg_len</b> bytes in <b>msg</b>
 using a
  * <b>key</b> of length <b>key_len</b> and a <b>salt</b> of length
  * <b>salt_len</b>. Store the result of <b>len_out</b> bytes in in
  * <b>mac_out</b>. This function can't fail. */
 void
 crypto_mac_sha3_256(uint8_t *mac_out, size_t len_out,
                     const uint8_t *key, size_t key_len,
                     const uint8_t *msg, size_t msg_len)
 {
   crypto_digest_t *digest;

   const uint64_t key_len_netorder = tor_htonll(key_len);

   tor_assert(mac_out);
   tor_assert(key);
   tor_assert(msg);

   digest = crypto_digest256_new(DIGEST_SHA3_256);

   /* Order matters here that is any subsystem using this function should
    * expect this very precise ordering in the MAC construction. */
   crypto_digest_add_bytes(digest, (const char *) &key_len_netorder,
                           sizeof(key_len_netorder));
   crypto_digest_add_bytes(digest, (const char *) key, key_len);
   crypto_digest_add_bytes(digest, (const char *) msg, msg_len);
   crypto_digest_get_digest(digest, (char *) mac_out, len_out);
   crypto_digest_free(digest);
 }
 }}}

 Our code is currently using it here:

 {{{#!sh
 ∃!isisⒶwintermute:(master *$)~/code/torproject/tor ∴ ag
 crypto_mac_sha3_256
 src/test/test_crypto.c
 1105: * are gonna do is test our crypto_mac_sha3_256() function against
 manually
 1121:  crypto_mac_sha3_256(hmac_test, sizeof(hmac_test),

 src/common/crypto.c
 1259:crypto_mac_sha3_256(uint8_t *mac_out, size_t len_out,

 src/common/crypto.h
 197:void crypto_mac_sha3_256(uint8_t *mac_out, size_t len_out,

 src/or/hs_cell.c
 62:  crypto_mac_sha3_256(mac_out, mac_out_len,
 551:    crypto_mac_sha3_256(mac, sizeof(mac),

 src/or/hs_intropoint.c
 131:    crypto_mac_sha3_256(mac, sizeof(mac),

 src/or/hs_ntor.c
 94:  crypto_mac_sha3_256(ntor_key_seed, sizeof(ntor_key_seed),
 100:  crypto_mac_sha3_256(ntor_verify, sizeof(ntor_verify),
 126:  crypto_mac_sha3_256(rend_cell_auth, sizeof(rend_cell_auth),
 }}}

 So it looks like only the v3 hidden service code?

 This looks like a perfectly reasonable construction, and I believe other
 people do this too, except Ian has pointed out to me (in the context of
 #24988) that

 > The security proof of HMAC *relies* on the underlying hash function
 being Merkle-Damgård.

 I went back to the original '96 paper
 ([http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.134.8430
 ""Keying Hash Functions for Message Authentication""], search for
 "Iterated Constructions" and read from there on) to read the security
 proof, and it does in fact rely upon the collision resistance of the
 underlying ''compression function'', which obviously we don't have when
 using a sponge construction. So while this looks like a perfectly
 reasonable construction, there isn't actually any security proof for its
 collision resistance. Further, note that the `crypto_mac_sha3_256()`
 doesn't take any domain separators other than the key, which we probably
 should be doing all the time no matter what.

 Also the construction is not using the full state space of the keys, due
 to `htonll()` being used to pad the MAC key to a fixed-length of 64 bits,
 whereas the rate of the Keccak[512] function underlying the SHA3-256
 construction is 1088 bits, which are getting padded with `0` bits in
 length of the excess capacity of 512 bits to equal the block size of 1600.
 A nicer construction would be to ensure that the key is at least 1088
 bits, which is what KMAC does with the `bytepad(encode_string(X), 136)`
 part.

 When using Keccak, I believe the correct/standard construction for a MAC
 is KMAC (specification
 [https://nvlpubs.nist.gov/nistpubs/SpecialPublications/NIST.SP.800-185.pdf
 here]) with domain separators (a.k.a. in that publication "customisation
 strings") which uses SHAKE under-the-hood. (It might also be okay to use
 KangarooTwelve if we needed/wanted a parallelisable XOF, for some reason.)

 For a key `K`, message `X`, requested output length `L`, and domain
 separator `S`, the pseudocode is:

 {{{
 KMAC256(K, X, L, S):
 Validity Conditions: len(K)<2²⁰⁴⁰ and 0 ≤ L < 2²⁰⁴⁰ and len(S) < 2²⁰⁴⁰

 1. newX = bytepad(encode_string(K), 136) || X || right_encode(L).
 2. return cSHAKE256(newX, L, “KMAC”, S).
 }}}

 -----

 Setting as "Tor: Unspecified" because this probably can't reasonably be
 fixed without a new HS version, and at that point we might also want to
 revisit things like how we're doing a bunch of
 [https://trac.torproject.org/projects/tor/ticket/22006#comment:13 super
 expensive computations] to validate on the fly (including all over the
 place in the control protocol) that there's no 8-torsion component in v3
 HS server public keys.

--
Ticket URL: <https://trac.torproject.org/projects/tor/ticket/25576>
Tor Bug Tracker & Wiki <https://trac.torproject.org/>
The Tor Project: anonymity online