SHA-384, HMAC and HKDF for the TLS 1.3 key schedule

Status: built. Not independently reviewed. Sub-issue 4 (#201) of the self-contained TLS 1.3 client (#197). The client’s key schedule (RFC 8446 §7.1) is HKDF over the suite’s hash: SHA-256 for TLS_CHACHA20_POLY1305_SHA256, and SHA-384 if a SHA-384 suite is ever added. Building it found that every hash in std trapped on a message of 64 KiB, and so did ed25519.sign; §2 covers that, the fix, and the two documents it corrects. §8 lists what is not done, including the cancho-hooks half of #201. §9 (#446) keeps a key’s padded blocks hashed, so an HMAC under a key used again hashes no pad again, and HKDF and the TLS key schedule use it.

1. Where it lives

The hash is named by its digest length: 32 means SHA-256 and 48 means SHA-384. Anything else is refused with hash-unsupported. That is the number HKDF and the key schedule already carry (Hash.length), so a second name for the same choice would only be a chance for the two to disagree.

crypto.sha256 / sha384 / sha512(message, digest)            one-shot, as before
crypto.sha{256,384,512}_{init,update,final}(state, ...)     streaming
hmac.sha256(key, msg, out)   hmac.sha384(...)   hmac.mac(hash_len, ...)
hmac.init / update / final(hash_len, state, ...)            streaming
hkdf.extract(hash_len, salt, ikm, prk)
hkdf.expand(hash_len, prk, info, okm)
hkdf.expand_label(hash_len, secret, label, context, okm)    RFC 8446 §7.1
hkdf.derive_secret(hash_len, secret, label, transcript_hash, out)

An output’s length is the length of the slice the caller passes, so there is no second length to contradict it. derive_secret takes the transcript’s hash, not the messages: the transcript hash runs for the whole handshake, so its state belongs to the caller (#205). It is the streaming SHA-256 state below.

Every HMAC and HKDF function answers 0 or a negative code, and hkdf.refusal_tag(code) names it. Each code corresponds to one rule a caller can act on:

A length outside the structure is refused rather than truncated into some other, valid structure. The hashes keep their old contract (docs/crypto.md §4): an output buffer that is too short traps on its bounds check. That is a mistake in a program, and no input can cause it.

2. The 64 KiB trap, and the streaming hash that removes it

crypto.sha256 built its padded copy of the whole message in an arena: alloc_slice[m](padded_len, ...). An arena is one 64 KiB chunk, and asking it for more traps (docs/defined-behaviour.md). So SHA-256 of 65,536 bytes trapped (SIGILL, status 132), and so did SHA-512. ed25519.sign trapped earlier, at 65,000 bytes, because it copied prefix || msg into an arena before hashing. Measured, not inferred:

sha256 of 1,000 / 65,000 / 65,536 / 70,000 bytes of `a`:  exit 0 / 0 / 132 / 132
ed25519.sign of 1,000 / 65,000 / 70,000 bytes:            exit 0 / 132 / 132

This corrects three claims made in place:

• docs/crypto.md §4 implied sha256 hashes any message.
• docs/sha512.md §3 said the length field is exact “for every message this language can hold”. The length field was right; the message never reached it.
• cancho-hooks src/sign.cho boxes its ipad || message copy on the heap because “a payload can be 64 KiB and an arena is not”. It then passes that copy to crypto.sha256, which copied it into an arena again. A delivery whose signed content is 65,536 bytes or more would trap the service (§7).

The fix is a streaming hash. A state is a [int] the caller owns: the eight running words, the byte count, the buffer, and the message schedule. update compresses whole blocks straight from the caller’s slice, and copies only a partial block into the buffer. final pads inside the buffer. The one-shot functions are init, update and final on a state in one small arena (1.1 KiB for SHA-256, 1.7 KiB for SHA-512), so they hash any length. ed25519.sign and verify stream prefix, R, A and the message into one state rather than concatenating them. HMAC and HKDF are built on the same states, so nothing in this slice allocates in proportion to its input.

The schedule and buffer live in the state, not in an arena per call. The first version of the streaming code opened an arena in update, in final, and in each compress (for the message schedule w), as the old code did. That made a 64-byte SHA-256 cost 19 µs against the old 10.7 µs, because every arena is a malloc. Moving the buffer and the schedule into the caller’s state removed every allocation but the one-shot wrapper’s. §6 has the numbers: the same 64-byte hash now takes 0.99 µs.

3. Secrets

HMAC and HKDF run over secret keys: the PSK, the ECDHE shared secret, and every traffic secret. The rule from docs/chacha20.md §3 applies here too: no branch and no memory index may depend on a secret.

• SHA-256’s additions are now wrapping_add under the mask. docs/crypto.md §2 had reasoned that a checked + under mask32 never traps, which is true. But the check is still an overflow test on the hashed key’s words, so it is gone.
• not32 is now x ^ 0xffffffff, where it was 0xffffffff - x. The value is the same on [0, 2^32), but the subtraction was checked and the XOR is not.
• The object code was read. scripts/chacha20_branches.py, with function names, disassembles compress, compress512, rotr32, rotr64, lshr64, low_mask64, mask32 and not32 from the LLVM build of tests/programs/kdf_driver.cho. Every conditional jump goes to a bounds trap, except six loop back-edges. Those compare the round counter with 64 or 80, or a byte offset with 512 or 640. There are also three compares of a shift amount with a constant (the low_mask64(63) case of docs/sha512.md §2), and every shift amount is a constant at its call site. None reads the data being hashed. Before the not32 change, compress had an overflow jump (jo) after a subtraction on the round word e; after it, there is none.
• HMAC’s branches are on public lengths. It branches on the key’s length (hashed first, or padded) and on the hash’s block size. The key is padded to a block. The ipad block is cleared before its arena ends, and the opad block stays in the caller’s state until final clears it. Corrected (#446, §9): the state now keeps the outer hash’s eight words after the opad block, not the block, and final clears them; both padded blocks are cleared before init‘s region ends. HKDF-Expand clears its last T(i). All of these are best effort, for the reasons in docs/chacha20.md §3.2. The hash states’ own buffers and schedules, which hold key-derived words, are not cleared. Corrected (region-chunk-cache.md §3.1): those in a region are now, since every region’s bytes are cleared when it ends.
• Not claimed: constant time measured statistically (that is #208), or anything about the Cranelift backend’s object code.

4. Checked, not assumed

tests/programs/kdf_driver.cho drives every function from standard input. crates/cancho/tests/conformance/kdf.rs runs it in cargo test, offline.

4.1 SHA-2: NIST CAVP

Every case of the byte-oriented CAVP response files (tests/vectors/cavp/, NIST’s files as pyca’s cryptography_vectors carries them):

All pass. The long-message file for SHA-512 (1.7 MB) is left out: the SHA-384 file runs the same compression and the same streaming code, and the differential (§4.3) covers SHA-512 at up to 200 KiB. Beyond the files, the test also checks:

• FIPS 180-4’s million-a examples for all three hashes, streamed;
• 65,536 and 200,000 bytes, one-shot, which trapped before (§2);
• every length from 0 to 300 bytes, one-shot and streamed in pieces of 1, 7, 63, 64, 65, 127, 128 and 129 bytes, all equal.

tests/accept/ed25519_long.cho signs 70,000 bytes. The signature equals OpenSSL’s and verifies, and a tampered one does not.

4.2 HMAC, HKDF and the TLS 1.3 key schedule

All 62 rows of tests/vectors/kdf.txt pass on both backends (59 when this was written; #205 added RFC 8448’s three application-stage secrets):

• RFC 4231: HMAC-SHA256 and HMAC-SHA384, test cases 1–4, 6 and 7. Case 5, the truncated tag, is missing from the transcription used.
• RFC 5869: A.1 to A.3, extract and expand separately, PRK included. Plus a 1,200-byte HKDF output from pyca’s vectors.
• The TLS 1.3 key schedule from three sources.
  • RFC 8448 §3, the “Simple 1-RTT Handshake”. The early secret, the derived secrets, the handshake secret, both handshake traffic secrets with their keys and IVs, the server’s finished key, the master secret and the resumption master secret. The RFC’s text was not reachable from the machine this was written on, so these values were written down from the RFC. Each was kept only if Python’s hmac/hashlib reproduces it from the trace’s own inputs. The client and server application traffic secrets and the exporter secret did not reproduce from the transcript hash as written, so one of the two was written wrong. They were left out rather than “fixed” to match. Settled since, in #205 (docs/tls-core.md §6.1): AWS s2n-tls transcribes RFC 8448 §3 in tests/unit/s2n_tls13_secrets_rfc8448_test.c, with the transcript hash through the server’s Finished (9608102a…). The three secrets reproduce from it in Python, and they are now rows of kdf.txt. So was every other value in that file, from the X25519 keys onwards. The values first remembered were not kept, so which of the two was written wrong is not known.
  • NIST ACVP’s TLS-v1.3-KDF-RFC8446 case, as Go’s crypto/tls TestACVPVectors carries it. This is a PSK handshake, and it covers every secret from the early traffic secret to the resumption master secret, the application traffic secrets included.
  • OpenSSL’s test/tls13secretstest.c, the draft-06 vectors that OpenSSL’s TLS 1.3 passes. They cover every traffic secret, key and IV for both sides.

Wycheproof, every case (tests/vectors/wycheproof/):

• For HMAC, a truncated tag is compared with the front of the full tag, and every modified tag differs from it.
• For HKDF, every valid case gives its output. The three oversized requests per hash are refused with hkdf-length-too-large, and the largest legal size (255 * hash_len) is accepted.

Every refusal tag in §1 is reached by its own case, and none writes its output. The edges just inside each limit are accepted:

• an output of exactly 255 * hash_len;
• a 249-byte label with a 255-byte context;
• outputs of zero bytes.

4.3 Against OpenSSL and Python

scripts/kdf_differential.py compares against Python’s hashlib and hmac (OpenSSL’s digests underneath), pyca’s HKDF (OpenSSL’s EVP_KDF), and RFC 8446’s HkdfLabel built in Python. Each round checks eight things:

• SHA-256, SHA-384 or SHA-512, one-shot and streamed in random pieces. One round in fifty uses 64 to 200 KiB, past the old trap.
• HMAC-SHA256 and HMAC-SHA384, with keys of 0 to 300 bytes, which crosses both block sizes.
• A whole HKDF under each hash, with the output size up to the RFC’s maximum on one round in twenty.
• An Expand-Label under each hash, with random labels and contexts.

5. Mutants

scripts/kdf_mutants.py builds 19 mutants of the three files, as local modules beside the driver. It runs each against the evidence of §4: the vector table, the CAVP short and Monte Carlo files, every Wycheproof case, the streamed-against-one-shot cases, the refusal edges, and 1,000 differential rounds. 19 mutants, 19 killed, in 23 seconds.

What the run found:

• A buffered SHA-512 byte dropped survived every fixed vector. Fixed vectors are hashed in one call, so the code that fills a partly full buffer never runs. Only the differential’s random pieces killed it. The cargo test’s streamed-against-one-shot cases now cover that path, the mutant script runs them too, and the mutant is killed there.
• Three hkdf mutants were killed by a trap, not by a wrong answer. With the 255 * HashLen check loosened, or a 250-byte label allowed, byte_of(256) traps building the counter or the length byte. The language’s checked conversion stood behind the missing refusal, so even without the check no input could produce wrong bytes. But a trap is not a refusal (“no input may reach a panic”), so the checks stay, and the refusal test is what pins them.

6. Cost

One core of an Intel Xeon at 2.80 GHz, LLVM backend, median of 5. The time is the difference between 1 call and many. “Before” is main‘s std/crypto.cho from before this change, and hooks’ hmac_sha256 over it, built beside the new code in one program.

The small-message gain is §2’s arenas. The old code opened four for a 64-byte message (the state, the padded copy, and one per block, of which there are two), and the new code opens one. A TLS 1.3 key schedule is a few dozen HMAC calls over short inputs, so tens of microseconds. A webhook signature over a 1 KiB body costs about 10 µs.

7. cancho-hooks

#201 asks for cancho-hooks to use this HMAC instead of its own (src/sign.cho), and for its tests/sign_test.py to still pass against the reference Standard Webhooks library. That is a second repository, pinned to a compiler revision (cancho.toml), and the revision has to contain std.hmac. So it lands after this change: a PR on cancho-hooks that deletes sign.hmac_sha256, calls hmac.sha256, moves the pin, and records the 64 KiB trap of §2 with a test that reaches it.

8. Not done here

• The hooks switch (§7). It follows this change’s merge, as its own PR on cancho-hooks.
• RFC 8448’s application traffic secrets (§4.2). Added by #205 from s2n-tls’s transcription of the RFC (§4.2).
• A statistical timing test. That is #208.
• SHA-512 long messages from CAVP. They are covered by SHA-384’s file and the differential, not by NIST’s own file (§4.1).
• CI for the differential and mutant scripts. Both need Python’s cryptography. Everything else runs in cargo test.
• An independent review. That is #209.

9. A key’s pads hashed once (#446)

Built, with the SHA-256 builtin (sha256-builtin.md), as lever D4 of tls-performance.md §10.8.

9.1 What was asked

hmac.init hashed the key’s inner padded block on every call, and final the outer one, and each opened a region for its buffers. HKDF-Expand-Label calls HMAC with the same key several times in a key schedule: the handshake secret gives three secrets, each traffic secret a key and an IV. tls-performance.md §10.4 measured hmac.init at 9.9% of a full server handshake inclusive, 8.1 points of it the regions’ memory, so at most 1.8 points were the two compressions; the regions were A1’s to remove (§10.11) and the compressions this section’s.

9.2 What a prepared key is

After K0 XOR ipad and K0 XOR opad (RFC 2104 §2) each fill exactly one block, the inner and the outer hash are each eight words and a count of one block. A prepared key is those sixteen words: hmac.prepared_len(hash_len) is 16 for SHA-256 and SHA-384 alike (SHA-384’s words are SHA-512’s, 64 bits each, in an int each).

hmac.prepare(hash_len, prepared, key)            the two pads hashed once (a region, for the scratch state)
hmac.init_prepared(hash_len, state, prepared)    an HMAC started from it: two copies of eight words, no compression
hmac.mac_prepared(hash_len, prepared, msg, out)  one tag under it (one region, the state's)
hmac.keep(hash_len, state, prepared)             the prepared key of a state `init` has just started
hmac.forget(prepared)                            cleared
hkdf.prepare(hash_len, secret, prepared)         `hmac.prepare`, with HKDF-Expand's PRK-length refusal
hkdf.expand_label_prepared(...), hkdf.derive_secret_prepared(...)
hkdf.prepared_len(hash_len), hkdf.forget(prepared)

std.crypto gives the operations this needs, with no other knowledge of its layout leaving it: sha256_save (the eight words of a state at a block boundary; -1 and nothing written if bytes are waiting), sha256_resume (a state that goes on from them after a given number of bytes), sha256_finish (the padding, the digest left as the running words) and sha256_update_words (big-endian words fed at a word boundary), and the sha512_ four.

The HMAC state changed with it. It was the hash state and then the outer padded block, block_len words kept for final to hash; it is now the hash state, the outer hash’s eight words, and eight words for the inner digest, so hmac.state_len is the hash state’s length plus 16 (154 for SHA-256, 234 for SHA-384, from 202 and 346). init hashes both pads, keeping the outer words, so a plain HMAC still costs two pad compressions, now both in init. final opens no region and writes nothing but the tag: it finishes the inner hash (sha256_finish, the padding without the bytes out), keeps its digest words in the state, resumes the outer hash from the kept words, feeds it the digest as words (sha256_update_words; sha512_ for SHA-384, six 64-bit words), finishes into out, and clears the sixteen words. (The first version wrote the inner digest into the caller’s out and hashed it from there; the timing test found that it made the time depend on whether out already held the same bytes, sha256-builtin.md §8.4.)

9.3 Where a key is used again

• hkdf.expand prepares its PRK once (from the state its init just made, hmac.keep) and starts every T(i) from it, so an output of n digests hashes the pads once, not n times. Its regions went from one a call plus two a block (init’s and final’s) to two a call; expand_label from four a call to two.
• The TLS key schedule, kept minimal (packages/tls): tls_slot.traffic_keys derives a traffic key and an IV from one secret, so it prepares the secret once and expands both labels from it; and the server’s and the client’s handshake secrets (handshake_secrets in server.cho, the same block in client.cho) prepare the handshake secret once for its three Derive-Secrets. Nothing else in the package changed, and nothing new is kept in a slot: each prepared key lives in the calling function’s region and is cleared before it ends (and the region itself is cleared when it ends, region-chunk-cache.md §3), so tls.residue has nothing new to count, and the pool’s checks that it stays 0 pass unchanged.
• Not changed: the master secret’s three Derive-Secrets are in three functions that run at different points of the handshake (keeping a prepared master secret would mean keeping it in the slot); the Finished keys and the binder are used once each; TLS 1.2’s PRF (record.cho, which #447 and #448 are changing) calls hmac.init with one secret in a loop and is the next user if it matters.

9.4 Tested

conformance/kdf.rs runs every HMAC, Expand-Label and Derive-Secret row of tests/vectors/kdf.txt and every Wycheproof HMAC case again under a prepared key, on both backends; the driver (tests/programs/kdf_driver.cho, ops P, Q, R) also checks that a tag from mac_prepared equals one streamed after init_prepared in pieces of 1 to 129 bytes, and that a prepared secret gives the same label twice. The prepared functions’ refusals each have a row. scripts/kdf_differential.py adds a prepared HMAC and a prepared Expand-Label to every round, against Python’s hmac; scripts/kdf_mutants.py has mutants of the resume, the kept words, the copies and the words fed (sha256-builtin.md §8.2). What it cost and saved is sha256-builtin.md §8.5.