#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
_______________________________________________ tor-bugs mailing list tor-bugs@lists.torproject.org https://lists.torproject.org/cgi-bin/mailman/listinfo/tor-bugs