Trail of Bits on Thursday released SequenceHash, an open-source construction for securely hashing groups of values together, along with a keyed sister function, SequenceMAC, in what the security firm described as a fix for a problem cryptographers keep getting wrong.
The problem is called multihashing. When a protocol needs to combine several inputs into one hash — “compute the shared authenticator N=Hash(X, Y, Z, A, B),” as the papers put it — developers often just concatenate the inputs and hash the result. From the hash function’s perspective, separate inputs fed in through separate calls are indistinguishable from one long input, and that ambiguity can be exploited. Get it wrong inside a Fiat-Shamir transform, the engine behind most zero-knowledge proofs, and you open the door to forgeries. Given how much cryptocurrency runs on those proofs, the firm’s blog post noted, such mistakes “are sometimes measured in millions of dollars.”
The existing standard answer is TupleHash, defined in a NIST publication, and Trail of Bits called it “great.” But TupleHash works only with Keccak, the function behind SHA3, whose adoption over the past decade the firm described as lackluster. Swap in another hash and important properties like length-extension resistance fall away. Government contractors are in a particular bind: the CNSA 2.0 guidelines mandate SHA384 and SHA512 for nearly everything, which rules Keccak out.
SequenceHash is built to be hash-agnostic, the way HMAC is for authentication codes. It works out of the box with the SHA2 family, BLAKE, RIPEMD and essentially any secure hash, and it guarantees four things the firm itemized in its specification: inputs are encoded unambiguously, so no two different sequences ever produce the same hash input; a double-hash construction blocks length-extension attacks; optional customization strings bind a hash to a particular protocol step to prevent replays; and the keyed mode, SequenceMAC, accepts keys of 32 bytes or longer while avoiding pseudocollision issues present in HMAC. A bonus for implementers: if the same data needs hashing under several customization strings, the inner hash can be computed once and reused.
The construction has limits, and the post stated them plainly. SequenceHash inherits its security from whatever hash a developer picks under it. “SequenceHash and SequenceMAC can’t magically make MD4 or SHA0 secure again,” the firm wrote. It assumes the reader is using something reasonable like SHA256, “not CRC32.”
Alongside the specification — now part of the Community Cryptography Specification Project, an open repository of cryptographic standards — Trail of Bits published reference implementations in Rust, Go and Python, plus a large set of test vectors covering multiple hash functions and including intermediate values so developers can debug their own versions.
The release reflects the firm’s stated disposition: keep hashing what you mean, and meaning what you hash. Or in the company’s own formulation of its mission, “fix software, not bugs.”