By Opal Wright

Among the cryptographic missteps we see at Trail of Bits, “let’s build our own tool out of a hash function” is one of the most common. Clients have a problem along the lines of “we need to hash a bunch of different values together” or “we need a MAC” or “we need a key derivation function for passwords,” and the closest tool at hand is a hash function.

These needs are often met with what could be called “YOLO” constructions: ad-hoc functions that “solve” the instant problem in a way that’s obvious, straightforward, and usually wrong.

The fact is, these problems are harder than they seem. For us, it can be frustrating to see home-rolled solutions over and over in the products clients bring us because the problems have already been solved. So let’s discuss a few of the YOLO constructions we frequently see, what’s wrong with them, and what to do instead.

YoloMultiHash

This is the most common YOLO construction we see at Trail of Bits. Clients often use this when they have complex data structures or arrays of values and need to turn them into a Fiat-Shamir transcript.

The YOLO construction

Given a hash function H and a set of messages M̂ = {M₁,M₂,…,M_n}, select a separator string S, and compute YoloMultiHash(M̂) = H(M₁‖S‖M₂‖S‖…‖S‖M_n).

The problem

The issue we run into here is ambiguous encoding.

What happens if the messages can contain the separator S as a substring? Suppose the message M_i contains S as a substring. Split M_i into M_i = M′_i‖S‖ M′′_i and define M̃ = {M₁,…,M′_i,M′′_i,…,M_n}. Then we have YoloMultiHash(M̂) = YoloMultiHash(M̃). That’s two semantically distinct inputs that lead to the same hash value. This is akin to breaking the collision resistance requirement of a good hash function, which is a Very Bad Thing (^tm).

This is not a hypothetical issue, either: it has been used to break the security of widely used libraries.

The better options

Instead of using YoloMultiHash, use a function that’s designed for hashing multiple independent values into a single result. The most well-known example of this would be TupleHash, defined in SP800-185. Several other hash functions support or make it easy to support similar functionality; the BLAKE3 specification, for instance, describes the process for creating “stateful hash objects” that can be used this way.

Alternatively, get better at serializing your data. If you’re trying to serialize a data structure, there are great options like Protocol Buffers, CBOR, and BCS. These all produce unambiguous encodings of your data, meaning that structures with different values won’t lead to the same hash input. As a rule of thumb, if you’re feeding structured data into a hash function, it should be in a format that can be converted losslessly back into the original data structure.

(Note that, while many serialization methods will create unambiguous encodings, they don’t all necessarily produce unique encodings. For instance, JSON is largely insensitive to changes in whitespace and element ordering, so using JSON serializations produced by different libraries could lead to different hashes. Be careful!)

YoloMAC

The YOLO construction

Given a key K and a message M, compute YoloMAC(K,M) = H(K‖M). Sometimes folks will throw in a salt value or customization string S to let them do domain separation—something like YoloMAC(K,M,S) = H(K‖S‖M). It doesn’t really change the nature of the attacks below, so we’re just going to go with the simplified version here.

The first problem

The first problem with YoloMAC is well-known: length-extension attacks. If H is a Merkle-Damgård hash algorithm, as SHA256 is, then given H(M), an attacker can compute H(M‖X) for any X the attacker chooses. That means that, given YoloMAC(K,M) = H(K‖M), an attacker can compute YoloMAC(K,M‖X), without knowing K or even M.

This may sound silly, but if you have a message that’s being protected using an encrypt-then-MAC construction, using YoloMAC is a real problem. An attacker can append garbage data to the plaintext, updating the MAC to match. Depending on the underlying format, some parsers will attempt to process the garbage data. This can cause messages not to load correctly, crash parsers, or possibly leak timing information that allows an attacker to learn about how the message is being processed.

The second problem

The second problem is similar to the problem with YoloMultiHash: ambiguous encoding. This issue applies whether or not the hash function is susceptible to length extension attacks, so using SHA3 or Skein or BLAKE3 won’t save you here.

Say you have a message M and a 256-bit key K = K1‖K2, where K1 and K2 are 128 bits each. Let’s suppose we compute C1 = YoloMAC(K,M) = H(K1‖K2‖M).

Now let’s define M′ = K₂‖M and compute our MAC using K₁ as our key: C₂ = YoloMAC(K₁,M′) = H(K₁‖M′)=H(K₁‖K₂‖M) = C₁. We’ve just found two different message/key pairs that produce the same MAC.

Depending on the flexibility of the underlying file formats, this flexibility could allow Alice to produce a “root” message M̃ and 128-bit deniability key K̃ such that M̃ parses as a valid PDF file that incriminates Bob in some sort of conspiracy with Alice, but K̃‖M̃ parses as an innocuous JPG file. Alice can negotiate a 128-bit MAC key K with Bob, compute V = YoloMAC(K,K̃‖M̃), and send V and K̃‖M̃ to Bob. Bob validates V and recovers the innocuous JPG file.

Alice contacts the authorities and provides them with convincing records that she sent a message to Bob with MAC V, then provides them with the key K′ = K‖K̃ and message M̃. When the authorities check the authenticity of the incriminating PDF, they see that, in fact, YoloMAC(K‖K̃,M̃) matches the V provided by Alice.

This isn’t a pie-in-the-sky model: practical attacks have been demonstrated using a similar issue with AES-GCM tags.

This problem is particularly common in the case of Keccak, since the Keccak website says:

Unlike SHA-1 and SHA-2, Keccak does not have the length-extension weakness, hence does not need the HMAC nested construction. Instead, MAC computation can be performed by simply prepending the message with the key.

While Keccak doesn’t suffer from the length-extension attacks that HMAC is meant to address, the phrase “simply prepending the message with the key” carries a lot of assumptions about key length and key formatting with it.

The better options

Use HMAC, KMAC, or built-in tools, depending on your hash function.

If you’re using the SHA2 class of hashes (SHA256/384/512/etc.), you need to use HMAC; its design specifically sidesteps length extension attacks. HMAC has been around since the late 1990s; this problem has been solved for a quarter century now. It’s supported in every major cryptographic library. Python even includes it in their standard library. There’s no good reason to be rolling your own solution to this problem.

If you’re using SHA3, use KMAC. KMAC was formalized in 2016, and lots of SHA3 libraries already support it. KMAC also has several useful features:

• It can be used in XOF mode, which is useful in some situations where MACs are also used as masks for sensitive values.
• When not used as an XOF, the output length is integrated into the MAC calculation, so a 192-bit MAC is not just the truncation of a 256-bit MAC.
• It includes customization strings for easy domain separation.

SHA3 is a valid hash function to use with HMAC, but KMAC is faster and more flexible than HMAC-SHA3.

If you’re using BLAKE2 or BLAKE3, there’s already a keyed hashing mode built into the algorithm that you should use. As with SHA3, you can use BLAKE2/BLAKE3 with HMAC, but the keyed hashing approach will offer better performance.

YoloPBKDF

The YOLO construction

Given a password P and a salt S, compute K = YoloPBKDF(S,P) = H(S‖P). Or maybe use H(P‖S) if that boats your float. This key is now suitable for use in cryptographic contexts. Easy-peasy!

If you want to make it really secure, just iterate a bunch of times: set K₀ = P and compute YoloPBKDF_i(S,P) = K_i, where K_i = H(S‖K_i-1).

The problems

At this point, you may be thinking, “Oh, I’ve caught the pattern! It’s an ambiguous encoding!”

And maybe that’s an issue, but that’s not even on the map as a problem in this case.

Finding good ways to derive cryptographic keys from passwords is hard. Really hard. Like, “multi-year international standardization effort” hard. And that’s because converting a password into a key needs to be easy for the person who knows the password, but an absolute nightmare for anybody who doesn’t know it. Cryptography papers discussing how to crack keys generated by YoloPBKDF are practically their own genre: how to optimize hash software for the job, how to build custom hardware to do password cracking, how to cache data in tables for time-memory trade-offs, how to accelerate cracking efforts with graphics cards, how to model password selection, etc. YoloPBKDF isn’t just known to be insecure; cryptologists have been dunking on it for a couple decades at this point.

…yet it still shows up in our security reviews.

For a few bucks an hour, Mallory can rent AWS instances that use GPUs to test hundreds of billions of YoloPBKDF password candidates per second. The memory overhead is negligible: for each password being attacked, there’s just the salt, the hash state, and the password currently being checked. Attacks scale linearly with processor speed and the number of processors available: if Mallory wants to speed up her computations, she can add extra instances, or switch to higher-performance CPUs and GPUs when they become available.

On Alice’s side, her ability to thwart Mallory is only linear: if she switches from YoloPBKDF_t(S,P) to YoloPBKDF_10t(S,P), then Mallory only has to spend about 10 times as much to attack Alice’s passwords at the same rate. If Alice wants to reduce Mallory’s ability to attack her passwords by a factor of a million, then deriving her keys takes a million times as long, which can impose a significant delay for Alice—especially if she mistypes her password.

To give Alice more of an advantage, modern password KDFs impose not only a processing requirement, but also a memory requirement. If you want to derive a key from a password, you’ll need to generate a large array of values in memory, then perform a specific calculation on those values in order to produce the final value.

This memory requirement tips the scales in Alice’s favor. A modern computer has gigabytes of memory, but even a small memory requirement can impose major limitations on Mallory’s ability to do parallel key derivations, requiring her to read and write memory faster than her computer(s) can handle, or placing limits on how many passwords she can test at one time.

For instance, the Argon2d RFC includes a recommended parameter set that imposes a 64-megabyte memory requirement. Suppose Alice derives a key under these parameters. If Alice is deriving her key on a typical laptop with 8 GiB of RAM, 64 MiB is 0.8% of her memory. Alice is using remarkably little in terms of her resources. On the other hand, if Mallory wants to attack Alice’s key by checking a million passwords per second, she’ll need to generate and process 64 terabytes of data every second.

Alice won’t even notice the additional resources needed to generate a key from her password using a memory-hard function, but Mallory now has to marshal incredible resources in order to gain a fraction of the speed she would have if Alice had used YoloPBKDF.

The better options

Use a modern password KDF. The Argon2 family of functions is great, as is scrypt. Either one of them will do the job just fine, and libraries for both are widely available for multiple languages. For folks operating in the FIPS world, doing this can be difficult. NISTSP800-63-3 states the following:

Examples of suitable key derivation functions include Password-based Key Derivation Function 2 (PBKDF2) and Balloon. A memory-hard function SHOULD be used because it increases the cost of an attack.

Balloon has not been approved by NIST, though PBKDF2, which is not memory-hard, has been approved. If you want to make sure you can point to a NIST-approved function, you can use a memory-hard password KDF like Balloon or Argon2 to generate a key K₁ from the password and salt, use PBKDF2 to generate a key K₂ from the password and salt, and finally use a FIPS-approved function like HKDF to combine them into a final key K = HKDF(K₁‖K₂).

Summing up

If you’re not already locked into a hash function, take some time to consider all the ways you’ll be using a hash function, and let that guide you. Newer hash designs are built with cool ideas like multihash and MACs in mind, and if there’s no need to reinvent the wheel, don’t. BLAKE2 and BLAKE3 natively support keyed hashing and MACs, and KMAC is supported in many SHA3 libraries. TupleHash is usually implemented alongside KMAC, and BLAKE2 can be readily adapted for multihashing.

Whatever you need to do with a hash function, you’re probably not the first to need it. A lot of research has been done in this area, and it’s worth putting in the time and effort to find vetted, well-studied solutions to your problems rather than inventing your own.

Related