Collision-Resistant Hash Functions

You and a friend each have a copy of a very large file. How can you be sure your files match exactly? Your friend could send their entire copy of the file to you, and you could compare both copies, but this is wasteful and impractical. Wouldn't it be easier if your friend could send some much shorter “fingerprint” of their copy of the file? You could compute the fingerprint of your copy and just compare the fingerprints.

This hypothetical fingerprint function must be deterministic, so that both of you compute the same fingerprint of the same file. Its output should be short, otherwise sending the fingerprint is no better than sending the entire file. Finally, the name “fingerprint” suggests that different files should have different fingerprints. Indeed, this interaction between you and your friend is vulnerable to false-positives: You and your friend might have different copies of the file whose fingerprints happen to be the same, leading you to conclude (wrongly) that the copies are identical. A pair of different inputs with the same fingerprint is called a collision.

In this scenario, we don't care what information the fingerprint leaks about the data (both users already know the data); we don't need the fingerprints to be pseudorandom; we don't need the two users to have any secrets. The only thing we care about is avoiding collisions. Collision resistance is a completely new cryptographic goal, and the focus of this chapter.

10.1. Defining collision resistance

A collision in a function $H$ is a pair $(X,X')$ where $X\ne X'$ but $H(X) = H(X')$. If $H$ has more inputs than possible outputs—and that is indeed the most interesting situation—then collisions are inevitable; this is a simple consequence of the pigeonhole principle. We can't hope for a total absence of collisions; the best we can hope is that collisions are hard to find. We call this property collision resistance.

A hash function usually refers to a function with long inputs and short, fixed-length outputs. When people talk about hash functions, they usually mean a function that supports inputs of arbitrary, variable length. It can also be useful to consider collision resistance of functions with fixed-length inputs (see section 10.4). The important properties are that the function has more inputs than outputs (so collisions do exist), and that the outputs are of a fixed length (often 256 or 512 bits).

A word of warning: Out of all the cryptographic primitives we study in this book, collision-resistant hash functions have the biggest mismatch between theory and practice. In this chapter, I'll try to address the gap as best I can.

First Attempt Formalizing Collision Resistance: It's difficult to formally define collision resistance, because hash functions involve no secrets. Below is a first attempt: We might say that a hash function $H$ is collision-resistant if the following libraries are indistinguishable:

If the libraries are indistinguishable, then comparing two hash outputs (fingerprints) has the same effect as comparing the two strings in their entirety. Consider this chapter's motivating scenario, where you and a friend want to know whether you hold identical copies of a file. $\lib{ideal}$ describes the logical comparison you would like to perform, and $\lib{real}$ describes a much more efficient way of doing it. If the libraries are indistinguishable, then it is safe to perform the more efficient comparison to achieve the same result.

Another way to understand the libraries is to notice that they give different answers only when $X \ne X'$ (so $\subname{compare}$ in $\lib{ideal}$ returns $\myfalse$) but $H(X) = H(X')$ (so $\subname{compare}$ in $\lib{real}$ returns $\mytrue$)—in other words, when $\subname{compare}$ is called on a collision. A calling program that can find any collision (it doesn't matter whether $X$ and $X'$ have any particular meaning or interpretation) will have an easy strategy to distinguish the libraries. So by asking for the libraries to be indistinguishable, we are really asking for collisions to be hard to find.

Unfortunately, this definition falls short because these two libraries can in fact never be indistinguishable, except in the trivial and uninteresting case that $H$ has no collisions at all. The reason is due to subtle technicalities in how we define security: First, Kerckhoffs's principle allows an adversary to depend arbitrarily on the algorithms being attacked. Second, our security definitions care only about the running time of the calling program, and not the time needed to write the calling program's source code.

Suppose a candidate hash function $H$ is chosen, with output length $n$, and consider the following precomputation attack: I evaluate $H$ on any $2^n+1$ distinct inputs and am guaranteed (by the pigeonhole principle) to find a collision $(X,X')$. Then I can write down the source code of an algorithm $\A$: “return $\subname{compare}(X,X')$”, where $X$ and $X'$ are constant strings, hard-coded into this source code. That is, the source code of $\A$ really looks like

for some suitable pair of strings that required exponential time to find. Running this algorithm is fast, certainly polynomial-time. Finding this algorithm is hard, requiring exponential time. But only its running time is relevant when it comes to indistinguishability. This is a polynomial-time algorithm that distinguishes the libraries with advantage 1, so we must conclude that the libraries are not indistinguishable.

The “attack” I just described is successful against any function $H$ that has any collisions at all. These two libraries can never be indistinguishable.

Add a Dash of Salt: To avoid the issues with the previous definition, we modify the interface of a hash function to take an additional argument called a salt. A salt is a string sampled uniformly and used for all calls to the hash function; but, unlike a key, a salt can be made public. We can define collision resistance for a salted hash function as follows:

This security definition is not vulnerable to the kind of precomputation attack described above, thanks to the salt. In definition 10.1.1, the source code of a calling program is allowed to depend arbitrarily on the choice of the hash function $H$, but it cannot depend on the choice of salt $\salt$, because $\salt$ is chosen only after the combined program (calling program + library) starts.

I like to think of salt as a “personalization” string. We can all agree on a good hash function $H$, but each of us can use our own personalized variant $H(\salt,\cdot)$. The adversary can't predict which personalized hash function $H(\salt,\cdot)$ it needs to attack until the start of the execution. Since there are exponentially many possible salts, precomputation is not helpful.

(You might wonder about an adversary program consisting of a huge, hard-coded lookup table that contains, for any salt $\salt$, a precomputed collision in $H(\salt,\cdot)$. Of course, such a lookup table would be exponentially large. For technical reasons, you should think of the “running time” of a program as including the time needed to read/parse the program's description. Thus, this lookup-table-based attack is not considered polynomial-time, no matter how efficiently the huge table can be accessed. By the way, this issue applies to more than just hash functions: Essentially all cryptographic algorithms can be defeated by an exponentially large, precomputed lookup table.)

Brute Force Attacks: A brute-force attack against the collision resistance of a hash function $H$ would compute $H(X_1), H(X_2), \ldots$, for any sequence of distinct $X_i$ strings until it finds $H(X_i) = H(X_j)$ for some $i \ne j$. How long would this attack take, if $H$ has $n$-bit outputs?

$H$ has the best chance of avoiding collisions is if the values $H(X_1), \ldots$ act like independent, uniformly sampled $n$-bit strings. (Any bias away from uniform only increases the chance of a collision.) But in that case, the question becomes: How many independent samples must we take from $\bits^n$ before encountering a repeat? This is exactly the birthday problem! We know that after roughly $2^{n/2}$ samples, there is a good probability of observing a repeat. So a brute-force attack against collision resistance—usually called a birthday attack—has a good probability of success after $2^{n/2}$ steps.

For this reason, if we want a CRHF to have $\secpar$ bits of security—that is, if breaking the hash function is supposed to require roughly $2^\secpar$ effort—then its output length should be at least $n = 2\secpar$. This is why you will (hopefully!) never see a 128-bit hash function in the wild; the most popular hash functions have output length 256, 384, or 512 bits.

Other Security Properties: This chapter focuses on collision resistance, but other properties of hash functions are sometimes relevant:

• One-wayness: Given $\salt$ and $Y$, it should be hard to find an $X$ such that $H(\salt,X) = Y$. This property is especially important when hashing passwords. Pay attention to the distinction between the following problems:

  • Given $\salt$ and $H(\salt,X)$, find $X$.

  • Given $\salt$ and $Y = H(\salt,X)$, find some $X'$ with $H(\salt,X') = Y$.

  It is easy to make a function for which the first problem is hard; just define $H(\salt,X) = \bit0^n$, so that $H(\salt,X)$ gives no information at all about $X$. The second problem is how we define one-wayness.

• Second-preimage resistance: Given $\salt$ and $X$, it should be hard to find $X' \ne X$ such that $H(\salt,X) = H(\salt,X')$. If collision-resistance is about the problem of finding any two people with the same birthday, then second-preimage resistance is about the problem of finding someone with the same birthday as yourself. As such, a brute-force attack against second-preimage resistance requires $O(2^n)$ steps for an $n$-bit hash function.

10.2. Hash functions in the real world

10.2.1. Theory vs. practice

Unsalted Hash Functions: Hash functions that you encounter in the wild are standardized as unsalted functions. They have only a single input argument: a string to be hashed.

Definition 10.1.1 does not capture the collision resistance of an unsalted hash function, and indeed we have seen that it is difficult to place unsalted hash functions on solid footing in provable security. Since real-world hash functions accept inputs of any length, it is best practice to simply prepend salt to the input of an unsalted hash, as $H(\salt \| X)$. It would then be reasonable to conjecture that this method of adding salting to an unsalted $H$ is secure according to definition 10.1.1.

Salt neutralizes precomputation: The precomputation “attack” in section 10.1 is not just an academic technicality. It reflects an important real-world concern about precomputation attacks.

Suppose a server stores hashes of users' passwords, with an unsalted hash function. (We will have more to say about hashing passwords later in this section.) Knowing what hash function the server uses, an adversary can precompute the hash of, say, the trillion most common passwords. Later, after stealing the server's password file, the adversary will be able to instantly identify all users whose passwords are among the trillion most common. All of the hard work of a password-cracking attack can be done beforehand, and it can be shared among adversaries and reused against any server who uses the same unsalted hash. There is even a line of interesting research on specialized data structures called rainbow tables, that can compress enormous collections of precomputed hash outputs.

If the hash function is salted, and the salts are stored with the password file—that is to say, the adversary doesn't know the salts until obtaining the password file—then precomputation is useless. The adversary can't precompute any candidate password hashes before knowing what salt to use.

If the server hashes all users' passwords with the same salt (including the case of no salt), then an adversary can attack a large number of victims for the price of one. Every time the adversary tests a candidate password $P$ by computing $H(S,P)$, there is a potential to learn that $P$ is the password of any user who uses salt $S$. On the other hand, if the server uses a different salt for each user, then an adversary must choose which user it wants to attack; attacking two victims requires twice the effort as attacking one.

Recommendations: The most common standardized hash functions are from the Secure Hash Algorithm (SHA) family. SHA-1 is an unsalted Merkle-Damgård (section 10.4) hash with 160-bit output, but has been deprecated as a standard in 2011 and should no longer be used. Attacks against SHA-1 were discovered, which can generate collisions with roughly $2^{64}$ effort. Remember, a good $n$-bit hash function should require roughly $2^{n/2}$ effort to find a collision.

SHA-2 is a family of unsalted Merkle-Damgård hashes, with a variety of output lengths, the most common of which are SHA-256 and SHA-512. SHA-3 is the leading state-of-the-art hash, standardized in 2015. Notably, it is not a Merkle-Damgård hash, but uses a methodology called the sponge construction, which we discuss later in chapter 12. SHA-3 is a family of hashes with varying output lengths from 224 to 512 bits.

10.2.2. Hashing passwords

One of the most common uses of hash functions is for password-based authentication. Here we briefly review various methods of authenticating using a password.

In the clear: The worst way to handle passwords is for the server to store them in the clear. We usually compare authentication methods by considering what happens when an adversary compromises the server's storage. If the server stores passwords in the clear, then an adversary who compromises the server immediately learns the passwords of all users, with no effort.

Encrypting passwords sounds like a better idea, but it isn't. In order to verify a user's password, the server must have a way to decrypt these encrypted passwords. Thus, the server must also store the decryption key. Encryption achieves nothing when ciphertexts are stored alongside the key. Don't encrypt passwords!

Unsalted hash: For a user with password $P$, the server can store the value $h = H(P)$, where $H$ is a hash function. When a user attempts to log in, it presents a password $P'$ and the server can check whether $H(P') == h$.

This method of authentication is far superior to storing passwords in the clear. An adversary who compromises the server learns only the hashed passwords, and must expend some effort to recover the actual passwords: It must compute $H(P')$ for many password guesses $P'$. However, when the hash function is unsalted, as we discussed above:

• The adversary's effort can be precomputed, before compromising the server's storage.

• The adversary's effort can be reused for many victims. Attacking $n$ users requires no more effort than attacking one.

Salted hash: For a user with password $P$, the server can store both a user-specific salt $S$ and the value $h = H(S,P)$. When a user attempts to log in, it presents a password $P'$ and the server can retrieve that user's salt $S$ and check whether $H(S,P') == h$.

Salted passwords ensure that the adversary must expend unique effort to attack each user: The effort must happen after compromising the server, and each victim/user requires separate effort. If you authenticate using passwords, always use salt!

Specialized Password-Hashing Functions: Typical collision-resistant hash functions like SHA-2 and SHA-3 are designed to be fast. But password hashing is one realm where it's better to be slow! If a server's collection of password hashes is leaked, then the only thing standing between an adversary and a victim's password is the speed at which the adversary can compute hashes of candidate passwords. Making a password hash a hundred or even a thousand times slower than SHA-3 would have minimal effect on the user experience (authentication would still require mere milliseconds ) but would make an adversary's task a thousand times more expensive.

A simple way to make a hash function slower is to iterate it many times; for example, if $H$ denotes a standard CRHF like SHA-3, then the server might hash its passwords using $H(\salt, H(\salt, \cdots H(\salt, P)\cdots ))$, with a few thousand $H$'s. However, this may not slow down an adversary as much as you might expect, because a determined adversary can build special-purpose hardware that can evaluate $H$ thousands or even millions of times faster than the general-purpose CPU that you and I use to evaluate $H$. This is not a hypothetical prospect: Some hash functions are used in proof-of-work cryptocurrency, which incentivizes people to build special-purpose hardware for computing hashes as fast as possible (trillions per second).

A more recent trend is to favor password hashing functions that require a large amount of memory rather than just computation time. There is no obvious way to build memory that is specialized for password hashing, in the same way one can build processors specialized for hashing. When it comes to memory technology, adversaries and users are on a more equal footing. A recent competition selected Argon2 as a standard for password hashing that is designed to consume significant memory.

10.3. Composing collision-resistant functions

In this section, we develop intuition about collision resistance by exploring successful and unsuccessful methods of combining CRHFs.

Below is an erroneous way to combine CRHFs, in the style of CBC-MAC. We show the case of 2 rounds of CBC.

Claim 10.3.2 (Insecurely combining CRHFs using CBC-MAC)

Let $H$ be a hash function with $n$ output bits. The following function $H^2 : \bits^\secpar \times \bits^{2n} \to \bits^n$ is not collision-resistant:

$H^2(\salt, X_1 \| X_2)$:

// $X_1, X_2$ exactly $n$ bits

$Y := H(\salt, X_1) \oplus X_2$

$Z := H(\salt, Y)$

$\qquad$

10.4. The Merkle-Damgård construction

If we have a collision-resistant hash function with fixed input length, can we use it to build one with variable input length? This section describes a recipe for doing so, called the Merkle-Damgård construction after its creators.

As a warm-up, let us first show how to increase the input length of a collision-resistant function from $2n$ bits to $3n$ bits.

Claim 10.4.1 (Increasing the input size of a fixed-input-length CRHF)

Let $H : \bits^\secpar \times \bits^{2n} \to \bits^n$ be a salted CRHF. Then the following function $H^* : \bits^\secpar \times \bits^{3n} \to \bits^n$ is also collision-resistant:

$H^*(\salt,X_1 \| X_2 \| X_3)$:

// each $X_i$ is exactly $n$ bits

$Y := H(\salt, X_1 \| X_2)$

$Z := H(\salt, Y \| X_3 )$

return $Z$

$\quad$

Claim 10.4.1 describes a valid approach to increase the input length of a collision-resistant function, which can be generalized in the natural way to increase the input length by any amount. However, the approach works only for fixed input lengths; it does not provide collision resistance for variable-length inputs. The situation is similar to that of CBC-MAC.

Claim 10.4.2 (Insecurity for variable-length inputs)

Let $H : \bits^\secpar \times \bits^{2n} \to \bits^n$ be a salted hash function. For any fixed $\ell$, the following function $H^* : \bits^\secpar \times \bits^{\ell n} \to \bits^n$ is is a secure fixed-input-length CRHF, if $H$ is. However, $H^*$ is not a secure variable-input-length CRHF, even if $H$ is:

$H^*(\salt,X_1 \| X_2 \| \cdots \| X_\ell)$:

// each $X_i$ exactly $n$ bits long

$Y_1 := X_1$

for $i=2$ to $\ell$:

$Y_i := H(\salt, Y_{i-1} \| X_i)$

return $Y_\ell$

$\quad$

Fortunately, the fix for claim 10.4.2 is simple. Just add an additional block, containing the length of the input (encoded in binary). This process is called Merkle-Damgård padding. We can even support inputs whose length is not a multiple of $n$, by appropriately padding the input with $\bit0$s:

In this setting, “compression” doesn't have its typical meaning as in other parts of computer science (where we expect there to be a decompression algorithm). Here, it just refers to the fact that inputs are longer than outputs.

$Y_0$ is called the Merkle-Damgård initialization vector (IV). It's a traditional feature of the construction, but not strictly necessary for our collision-resistance proof.

10.4.1. Merkle-Damgård in practice

Construction 10.4.3 and its proof are written in terms of a salted hash function, built from a salted compression function.

Until recently, the vast majority of real-world hash functions were unsalted Merkle-Damgård functions; the most popular standards include MD5 (MD here stands for message digest, not Merkle-Damgård), SHA1, SHA2 (SHA stands for secure hash algorithm). Collisions have been found in MD5 and SHA1. SHA2 is still in widespread use, but is being phased out in favor of its successor SHA3, which does not use the Merkle-Damgård paradigm (for reasons discussed in the next section).

Claim 10.4.4 can be interpreted as justification for the general design principle of Merkle-Damgård hash functions. We proved its security in a way that makes sense even for real-world unsalted hash functions: Given any collision in the hash function, it is possible to easily find a collision in its compression function.

10.5. PRFs from Merkle-Damgård: Length extension, NMAC, and HMAC

Suppose the only cryptographic algorithm you have available is an unsalted Merkle-Damgård hash function $H^*$ and you would like to implement a variable-length PRF. This section discusses several possible approaches, and some important pitfalls.

10.5.1. Length-extension attacks

We usually incorporate salt into an unsalted hash function by prepending it to the input, as $H(\salt \| X)$. For the purpose of collision resistance, the salt is allowed to be public. But it is natural to wonder what happens if we keep the salt private and interpret it as a secret key. Could the result be a secure variable-input-length PRF? Unfortunately, the answer is no when the hash function has the Merkle-Damgård structure.

The attack works by using $F(\key,X)$ to predict $F(\key, \subname{mdpad}(K\|X)\|X')$. It is an attack against pseudorandomness, but not against collision-resistance. There is no reason to expect that the two inputs used in this attack ($\key \|X$ and $\key \|X \|L \| X'$) are a collision in the length-extension attack.

10.5.2. Hash-then-PRF

As a stepping stone to the next constructions, we show that a fixed-input-length PRF can be promoted into a variable-input-length PRF by first hashing its input.

Claim 10.5.2 (Hash-then-PRF)

Let $H^*$ be a variable-input-length salted CRHF with output length $n$, and $F$ be a PRF with (fixed) input length $n$. Then the following function $F'$ is a secure variable-input-length PRF:

$F'(\key_1 \| \key_2, X) = F\bigl(\key_2, H^*(\key_1, X)\bigr)$

$\qquad$

One interesting feature of this construction is that part of the PRF key ($\key_1$) is used as a salt for the hash function. A salt is allowed to be public for the sake of collision resistance, but in this case it remains secret since a PRF key is secret. Chapter 11 explores how this construction may be optimized by taking advantage of the fact that it keeps the salt secret.

10.5.3. NMAC and HMAC

Recall the motivation for this section: to construct a variable-length PRF using only an implementation of an unsalted Merkle-Damgård hash function. In this section, let $H^*$ be the hash function, with compression function $H$.

The NMAC construction uses the following recipe:

1. Build a salted CRHF from an unsalted Merkle-Damgård hash function.

2. Build a fixed-input-length PRF from an unsalted Merkle-Damgård hash function.

3. Combine these two primitives using the hash-then-PRF construction (claim 10.5.2).

Recall that the Merkle-Damgård construction uses an initialization vector (IV), which we have usually just taken to be all-zeros, and which is some specific string in a standardized hash function. In step 1 of NMAC, we use the salt as the IV; thus, NMAC requires an implementation of the Merkle-Damgård function that lets the user specify a particular IV. Not all implementations may support nonstandard IVs, but we will address this issue a bit later. We write $H^*_{\textsf{iv}}(S,X)$ to denote the Merkle-Damgård hash of $X$, using $S$ as the IV.

For step 2 of NMAC, we simply assume that $H^*_{\textsf{iv}}$ is a fixed-input-length PRF on inputs of one block, treating the IV/salt as the PRF key. If you are nervous about treating a Merkle-Damgård hash as a PRF in light of claim 10.5.1, remember: These length-extension attacks apply only when using Merkle-Damgård as a variable-input-length PRF. It can still be reasonable to assume that a Merkle-Damgård hash is a secure PRF for a fixed input length.

Combining these steps gives us the full NMAC construction:

Because NMAC is an instance of the hash-then-PRF paradigm, we have the following:

HMAC: What if you have an implementation of a Merkle-Damgård hash $H$ that does not allow you to specify a particular IV? HMAC is a variant of NMAC designed for this case.

Suppose the NMAC keys $\key_1, \key_2$ are derived from a single key $\key^*$ in a special way:

where $P_1$ and $P_2$ are some fixed constants, $IV$ is the fixed IV of the standardized, unsalted Merkle-Damgård hash, and $H$ is its compression function. (In the HMAC standard, $P_1$ and $P_2$ are the hexadecimal strings $\bit{5c5c5c}\cdots$ and $\bit{363636}\cdots$.)

This value of $\key_1$ is precisely what the first round of the standard-IV, unsalted hash $H^*$ computes, when the first block of its input is $\key^* \oplus P_1$. In fact, we have:

In other words, if NMAC keys are chosen this way, then we can evaluate NMAC using an implementation of $H^*$ with its standard, fixed IV. The result is HMAC:

In this picture, the highlighted parts show HMAC deriving NMAC keys $\key_1$ and $\key_2$ from a common $\key^*$.

There is actually a slight difference between $H^*_{\textsf{iv}}( \key_1, X)$ and $H^*\bigl( (\key^* \oplus P_1) \| X \bigr).$ If $X$ has length $L$, then the former computation will add Merkle-Damgård length padding $L$, but the latter computation will add length padding $L+n$ — it “sees” an input that is one block longer than $X$. But the details of the Merkle-Damgård padding do not seem relevant to the assumptions on $H$ that NMAC requires; presumably the assumptions are equally valid when an extra $n$ is always added to the length padding.

Thus, assuming that the following function $G$ is a PRG:

then HMAC is indistinguishable from NMAC—or, at least a variant of NMAC that adds an extra $n$ to its length padding.

Exercises

1. A birthday attack on collision resistance invokes the hash function $2^{n/2}$ times. But the attack also needs to realize when it has seen a collision, and output the values that lead to the collision. How would you implement a birthday attack so that its total, overall running time is $O(2^{n/2})$, not just the number of calls to $H$ it makes?

2. Let $H$ be a salted hash function with $n$ bits of output, $n$-bit salt, and variable-length input. Suppose that whenever $X$ is $n$ bits long we have $H(\salt,X) = X \oplus \salt$. Thus, it is guaranteed that there are no collisions among $n$-bit inputs. Show that $H$ cannot be collision-resistant in general.

3. If $X$ and $Y$ are strings of the same length, write $X \sqsubseteq Y$ to mean that $X$ encodes an integer that is less than or equal to that of $Y$. Suppose $H$ is a hash function with the following property: For all $m$ and $X,Y \in \bits^m$, if $X \sqsubseteq Y$ then $H(\salt, X) \sqsubseteq H(\salt,Y)$. Show that $H$ cannot be collision-resistant.

4. Suppose $H$ is a CRHF and define the new function

   $H'(\salt, X_1 \| X_2) = H(\salt,X_1) \oplus H(\salt,X_2).$

   Here $X_1$ and $X_2$ are the same length. Is $H'$ also a CRHF? Either prove or describe an attack.

5. Let $F^\pm$ be a PRP with blocklength $n$. Prove that CBC-MAC (below), using an all-zeros IV and the salt as the PRP key, is not a CRHF:

   $H(\salt, X_1 \| \cdots \| X_\ell)$:

   // each $X_i$ is exactly $n$ bits

   $Y_0 := \bit0^n$

   for $i =1$ to $\ell$:

   $Y_i := F(\salt, X_i \oplus Y_{i-1})$

   return $Y_\ell$

6. h$\star$ Let $H$ be a CRHF with $n$ output bits, and define the following function:

   $H^*(\salt, X_1 \| \cdots \| X_\ell)$:

   // each $X_i$ is exactly $n$ bits

   $Y := \bit0^n$

   for $i =1$ to $\ell$:

   $Y := Y \oplus H(\salt, X_i \| i)$

   return $Y$

   The function has variable input length, so $\ell$ can be any value. In $H(\salt, X_i \| i)$, integer $i$ is encoded as a $\secpar$-bit string. Show that $H^*$ is not a variable-length collision-resistant hash function.

   Interpret $\bits^n$ as an $n$-dimensional vector space, so that each output of $H$ is a vector in that space. With enough such vectors, you can find nontrivial linear dependencies.

7. Let $F$ be a secure PRP with blocklength and key size $\secpar$.

   1. Show how to efficiently find a collision in the (unsalted) function $H(X \| Y) = F(X,Y)$.

   2. Show how to efficiently find a collision in the (unsalted) function $H(X \| Y) = F(X,Y) \oplus X$.

   3. Show how to efficiently find a collision in the (unsalted) function $H(X \| Y) = F(X \oplus Y,Y) \oplus X \oplus Y$.

8. Let $H$ be a salted hash function with $n$ output bits. Show how to efficiently find a collision in the following function $H' : \bits^\secpar \times \bits^{2n} \to \bits^n$:

   $H'(\salt, X \| Y)$:

   $Z := H(\salt, X) \oplus Y$

   return $H(\salt, Z) \oplus X$

9. Prove the first half of claim 10.4.2. For any fixed $\ell$, the function $H^*$ described there is a secure CRHF for inputs of fixed length $\ell n$.

10. Let $H : \bits^\secpar \times \bits^{2n+1} \to \bits^n$ be a salted hash function with fixed input length. Prove that if $H$ is collision-resistant, then the following salted hash function $H^*$ is collision-resistant for variable-length inputs that are multiples of the blocklength:

    $H^*(\salt, X_1 \| \cdots \| X_\ell)$:

    // each $X_i$ exactly $n$ bits

    $b := \bit0$

    $Y_1 := X_1$

    for $i=2$ to $\ell$:

    $Y_i := H(\salt, b \| Y_{i-1} \| X_i)$

    $b := \bit1$

    return $Y_\ell$

11. 1. In an AEAD scheme, it is convenient to compute a hash of the pair of strings $(A,\ctxt)$ where $A$ is the associated data and $\ctxt$ is the CPA ciphertext. Let $H$ be a CRHF. Show that the following function $H'$ is not collision-resistant for pairs of strings:

       $H'\bigl(\salt, (A,\ctxt) \bigr) = H(\salt, A \| \ctxt).$

       Describe how to construct two distinct pairs $(A,\ctxt) \ne (A',\ctxt')$ that collide under $H'$.

    2. Propose a better method to hash pairs of strings and prove that it is collision-resistant.

12. Construction 10.4.3 presents the Merkle-Damgård construction based on a compression function with $2n$ input bits and $n$ output bits. Describe how to modify the construction to support a compression function with $n+t$ input bits and $n$ output bits, for any $t>0$.

13. Let $H^*$ be a Merkle-Damgård hash function with compression function $H$.

    1. Describe how to find (with good probability) four distinct strings of the form

       $X\|Y, \quad X\|Y', \quad X'\|Y, \quad X'\|Y',$

       that all hash to the same output under $H^*$, using running time $\sim 2 \cdot 2^{n/2}$.

    2. Describe how to find $2^d$ distinct messages that all hash to the same output under $H^*$, using running time $O(d 2^{n/2})$.

    3. Suppose $H^*_1$ is a Merkle-Damgård hash function, and $H^*_2$ is some other hash function, not necessarily Merkle-Damgård, both with $n$ output bits. Define the new function

       $H'(\salt_1 \| \salt_2,X) = H^*_1(\salt_1,X) \| H^*_2(\salt_2,X).$

       Since $H'$ has outputs of length $2n$, it is tempting to think that it could offer $n$ bits of security (i.e., that collisions in $H'$ require $2^n$ effort).

       Show how to find a collision in $H'$ in running time only $O(n 2^{n/2})$. Your attack should not assume anything about $H^*_2$.

14. Let $H^*$ be an unsalted hash function with output length $n$, and let $\textsf{CTR}$ denote CTR-mode encryption (construction 8.5.4). Show that the following scheme is not CCA-secure:

    $\Enc(\key, \ptxt)$:

    $Y := H^*(\ptxt)$

    $\ctxt := \textsf{CTR}.\Enc(\key, \ptxt \| Y)$

    return $\ctxt$

    $\Dec(\key, \ctxt)$:

    // $Y$ = last $n$ bits

    $\ptxt \| Y := \textsf{CTR}.\Dec(\key,\ctxt)$

    if $Y \ne H^*(\ptxt)$: return $\myerr$

    return $\ptxt$

15. Let $H^*$ be an unsalted Merkle-Damgård hash, and define $H'(X) = \overline{ H^*(X) }$ (i.e., the bitwise complement of $H^*(\salt,X)$). Show how to modify the length-extension attack from section 10.5.1 to work against $H'$.

16. There are two natural ways to incorporate salt into an unsalted Merkle-Damgård hash function: (1) prepend it to the input; (2) use the salt as the IV, instead of the standardized IV value. NMAC uses the latter method.

    In the text we showed that method (1) does not lead to a secure variable-input-length PRF if you interpret the salt as the PRF key. Show that the same holds for method (2).

17. Prove that HMAC is collision-resistant if we treat the key as a public salt, under the same assumptions that make HMAC a secure PRF.