Trail of Bits Unveils SequenceHash and SequenceMAC for Secure Multihashing

Trail of Bits has addressed a common but often overlooked challenge in cryptography with the introduction of SequenceHash and its sister function, SequenceMAC. These new cryptographic constructions are designed to securely hash multiple values together, providing developers with a more flexible and robust solution for multihashing tasks. The primary goal is to mitigate security risks arising from ambiguous input encodings, a problem particularly relevant in advanced cryptographic applications like zero-knowledge proofs and the Fiat-Shamir transform.

Unlike NIST's TupleHash, which is tied to a specific hash algorithm, SequenceHash and SequenceMAC are designed to be algorithm-agnostic. This means they can be readily used with a wide array of common and secure cryptographic hash functions, including SHA256, SHA384, SHA512, BLAKE, and RIPEMD. This flexibility allows developers to leverage existing cryptographic infrastructure and choose the hash function that best suits their security and performance needs, without being locked into a single standard. SequenceMAC further supports keys of 32 bytes or longer, accommodating a broad range of security requirements.

The need for secure multihashing arises in numerous cryptographic scenarios. A fundamental example is when a protocol requires hashing several distinct inputs together, such as Hash(X, Y, Z, A, B). A naive approach of simply concatenating these inputs and hashing the result can lead to severe security vulnerabilities. For instance, if inputs are not clearly delimited, an attacker might be able to manipulate the input stream, leading to unexpected hash outputs or forgeries, especially in sensitive applications like zero-knowledge proofs.

This problem is particularly acute in the context of zero-knowledge proofs, where the Fiat-Shamir transform is a critical component. Errors in multihashing within these proofs can introduce the risk of forgeries, which, in financial applications like cryptocurrencies, can translate into significant monetary losses. Beyond zero-knowledge proofs, multihashing is essential for authenticating collections of variable-sized objects, such as files within an archive, multiple cryptocurrency transactions, or even composite data like a user's name.

Furthermore, multihashing plays a crucial role in generating cryptographic commitments. In protocols where one party commits to a secret value before revealing it, a clear separation between the secret and any blinding values is necessary. Ambiguity in this separation can allow a commitment to be opened in multiple ways, undermining the integrity of the protocol. The current landscape for solving this problem is fragmented, with developers employing diverse and sometimes insecure methods.

Trail of Bits highlights the "wild west" nature of current multihashing implementations, citing examples like using separator characters that might appear in the data itself, or complex, inefficient encoding schemes. Many implementations also suffer from inconsistencies, such as length-encoding some inputs but not others. While tools like Merlin and decree exist for specific use cases like Fiat-Shamir transforms, a general-purpose, secure, and easy-to-use solution has been lacking.

To address this gap, Trail of Bits has released open-source implementations of SequenceHash and SequenceMAC in Rust, Go, and Python. These implementations are accompanied by a comprehensive set of test vectors covering multiple hash functions and intermediate values, designed to aid developers in debugging and verifying their own implementations. The specification itself is now part of the Community Cryptography Specification Project (C2SP), promoting wider adoption and standardization.

SequenceHash and SequenceMAC are built upon the security of the underlying hash functions they employ. They do not magically enhance the security of inherently weak algorithms like MD4 or SHA0. Therefore, users are advised to select robust hash functions such as SHA256 for their security needs. By providing a standardized, flexible, and secure approach to multihashing, Trail of Bits aims to reduce the likelihood of critical vulnerabilities in cryptographic protocols and enhance the overall security posture of software relying on these techniques.