Opened 3 years ago

Last modified 2 years ago

#25576 new defect

Fix non-standard use of keccak in v3 hidden service code

Reported by: isis Owned by:
Priority: Medium Milestone: Tor: unspecified
Component: Core Tor/Tor Version: Tor:
Severity: Normal Keywords: cryptography, crypto, tor-hs, handshakes
Cc: Actual Points:
Parent ID: Points:
Reviewer: Sponsor:


Currently in src/common/crypto.c there's the following construction:

/** 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. */
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);


  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,
  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);

Our code is currently using it here:

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

1259:crypto_mac_sha3_256(uint8_t *mac_out, size_t len_out,

197:void crypto_mac_sha3_256(uint8_t *mac_out, size_t len_out,

62:  crypto_mac_sha3_256(mac_out, mac_out_len,
551:    crypto_mac_sha3_256(mac, sizeof(mac),

131:    crypto_mac_sha3_256(mac, sizeof(mac),

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 ("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 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 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.

Child Tickets

Change History (1)

comment:1 Changed 2 years ago by cypherpunks

Although it is a non-standard use and KMAC is better for Keccak, an HMAC not using a Merkle-Damgård hash in this case is not a big deal, according to Cryptography on StackExchange:

Thus, the claimed security level of HMAC-SHA3 is the same as the overall maximum attainable security level for HMAC, or any other deterministic iterated MAC construction, with the same effective internal state size.

So the use of HMAC rather than KMAC is safe but unnecessary and requires a little extra computation. In other words, no attack exists which can break HMAC but not KMAC when using SHA-3, despite the invalidated proof.

Last edited 2 years ago by cypherpunks (previous) (diff)
Note: See TracTickets for help on using tickets.