☆ Universal Hash Functions

A standard collision-resistant hash function is designed to be safe even when its salt is public. But we sometimes encounter situations that require collision resistance, where it is possible to keep the hash function's salt private. If the salt can be private, is it possible to use a simpler kind of hash function?

This chapter introduces universal hash functions, which are a private-salt variant of standard collision-resistant hash functions. Universal hash functions are indeed simpler objects: Their security guarantee is simpler, and in practice they are typically more efficient than CRHFs. There are even some universal hash functions whose security can be proven unconditionally.

11.1. Defining universal hash functions

We present two very different, yet equivalent, definitions for security of a universal hash function (UHF). The first definition is much simpler and easier to use when proving that a construction is a secure UHF. The second definition is more convenient when proving security of a construction that uses a secure UHF.

This definition can be thought of as a very simple attack scenario. The adversary gets just one chance to find a collision $(X,X')$ with respect to the UHF key. The adversary knows nothing about the choice of key. In fact, the key is chosen after $X$ and $X'$ are chosen.

The second definition involves an interesting way to think about collision resistance in terms of dictionary data structures. The goal of a dictionary is to provide, for each different $X$, a unique place to store data associated with $X$. Imagine two ways of implementing a dictionary:

1. Data that is associated with $X$ is stored in position $\prftable[X]$. This is the “obvious” way to use a dictionary.

2. Data that is associated with $X$ is stored in position $\prftable[U(\key,X)]$.

In the absence of collisions in $U$, each distinct item $X$ has its own unique place $\prftable[U(\key,X)]$ in the data structure, and everything will work as expected. On the other hand, if $(X,X')$ is a collision in $U$, then items associated with $X$ and $X'$ both want to be stored in the same place in the data structure, causing a conflict.

So one way to say that collisions are hard to find is to demand that these two ways of implementing a dictionary data structure are indistinguishable:

As mentioned earlier, the two definitions are equivalent.

When we prove security of UHF constructions in this chapter, it is more convenient to prove that they satisfy definition 11.1.1. When we use a UHF to construct something else, it is more convenient to use the fact that they satisfy definition 11.1.2. To justify the results in this chapter, it is therefore enough to prove only the forward direction of claim 11.1.3 (definition 11.1.1 $\Rightarrow$ definition 11.1.2). The other direction is more of theoretical interest, and left as an exercise.

Proof idea: The main challenge of this proof is to reconcile important distinctions between the two security definitions. The $\lib{dict-real}$ library from definition 11.1.2 implicitly makes many comparisons of hash outputs under the same key, but definition 11.1.1 involves only a single comparison under a key. Also, $\lib{dict-real}$ chooses a UHF key $\key$ at the beginning of time, whereas definition 11.1.1 chooses it after the potential collision $(X,X')$ is chosen.

The main idea in the proof is to treat hash collisions as a bad event, and then move all of the bad-event logic to the end of time. That way, the UHF key can be chosen at the end of time, after all UHF inputs have been fixed. Next, we can bound the probability of the bad event using the union bound:

The individual collision events are not independent, since they all involve the same $\key$, but they do not need to be independent to apply the union bound. Finally, each term of the form $\PR{ (X,X') \text{ collide under } \key }$ describes a situation that is captured by definition 11.1.1. Namely, a pair of inputs is fixed and then $\key$ is chosen uniformly. Thus, each probability in this sum is negligible, and so is the bad-event probability.

Note: If $(X_1, X_1')$ and $(X_2, X_2')$ are different pairs in $\mathcal{X}$, then their collision events $U(\key,X_1) == U(\key,X'_1)$ and $U(\key,X_2) == U(\key,X'_2)$ are not necessarily independent. But the union bound does not require the separate events to be independent.

How is a UHF different than a PRF? In a PRF, we require the outputs to be pseudorandom, while in a UHF they only need to avoid collisions. The outputs of a PRF are shown to the adversary, which is our way of saying “it is safe to use PRF outputs however you like.” The outputs of a UHF remain hidden from the adversary: Think about how the adversary does not see the intermediate values $U(\key,X)$ in $\lib{dict-real}$ of definition 11.1.2. You can interpret the UHF definition as saying, “It is safe to use UHF outputs to check whether two UHF inputs are equal, and nothing else.”

11.2. Universal hash paradigm for PRFs

We motivated UHFs by thinking about them as CRHFs where the salt is private. One situation with private salts is the hash-then-PRF construction in section 10.5.2, which used a CRHF to convert a fixed-input-length PRF into a variable-input-length one. Indeed, we can replace the CRHF in this construction by a UHF:

Construction 11.2.1 (UH-PRF)

Let $U$ be a UHF with output length $\secpar$, and let $F$ be a PRF with input length $\secpar$. Then UH-PRF is defined as the following function $F^*$:

$F^*\bigl((\key_1,\key_2),X\bigr)$:

$H := U(\key_1, X)$

$Y := F(\key_2, H)$

return $Y$

$\qquad$

The input domain of $F^*$ is the same as that of $U$ (usually all strings, or all block-aligned strings), and its output length is the same as that of $F$.

11.2.1. Handling non-block-aligned data

Construction 11.2.1 results in a variable-input-length PRF that inherits its input domain from the component UHF. What happens if the UHF supports only block-aligned data, but we want a PRF that supports arbitrary-length data?

One natural approach is to add padding, similar to how this is handled in encryption (section 8.6). Padding indeed works fine for this purpose, but remember that padding always increases the length of the data. In particular, if the data already is a multiple of the blocklength, then a block consisting entirely of padding must be added.

There is a clever way to avoid the extra padding block in the UH-PRF construction. The idea is to use different keys for the final PRF, depending on whether the input was block-aligned or not.

Exercise 11.7 asks you to prove security of this construction.

11.3. CBC-MAC is a UHF

We introduced CBC-MAC in section 6.6, and warned that it is not secure as a variable-input-length PRF. In this section we show that CBC-MAC is, however, secure as a variable-input-length UHF. It can therefore be promoted to a variable-input-length PRF in a simple way, using construction 11.2.1.

11.3.1. Variable-input PRFs using CBC-MAC as a UHF

Knowing that CBC-MAC is a UHF, we can compose it with a (fixed-input-length) PRF following the recipe of construction 11.2.1 to obtain a variable-input-length PRF. We now discuss a few ways to instantiate this recipe.

Of course, CBC-MAC itself is built from a fixed-input-length PRF, and it is reasonable to use the same PRF in both roles: both as the primary component of CBC-MAC and the final step of the UH-PRF recipe. It is important to use independent keys for these two different uses of a single PRF.

ECBC applies two consecutive PRF calls in its last block. The first of these can be eliminated:

Another variation on this theme, called CMAC, is discussed in exercise 11.13.

11.4. Poly-UHF: An unconditionally secure UHF

Some UHF constructions can be proven secure unconditionally. Their security doesn't depend on the security of an underlying PRF, like the UHF constructions from previous sections.

The main idea behind unconditionally secure UHFs is to interpret the input string as coefficients of a polynomial, and treat the UHF key as a point on which to evaluate that polynomial. Essentially, to compute the UHF output for a string $M$ under a key $\key$:

• Chop $M$ into blocks $M = M_{d-1} \| M_{d-2} \| \cdots \| M_0$, of equal and suitable size. To make things simpler, we'll assume that $M$ is block-aligned.

• Evaluate the degree-$d$ polynomial

  $X^d + M_{d-1} X^{d-1} + M_{d-2} X^{d-2} + \cdots + M_1 X^1 + M_0$

  at the point $X = \key$, working mod $\pmod$. Here $\pmod$ is a prime that can be public, even known to the adversary. Use the output of the polynomial as the UHF output.

The reason for writing the subscripts in descending order, and starting from $d-1$, is that it is convenient for an algorithmic optimization that will be discussed later. The reason we interpret $M$ as a polynomial with leading coefficient 1 is that it ensures different $M, M'$ correspond to different polynomials. Without this convention, leading blocks of zeros have no effect; two different strings $M$ and $M'$ could correspond to the same polynomial, if they differ only in leading zero-blocks.

Poly-UHF can be specified in more detail as the following:

Horner's method: There is an elegant way to evaluate a polynomial at some particular point, given a list of its coefficients. The idea is summarized in the following example:

More generally, if we write $\subname{polyeval}(X, c_d, \ldots, c_0)$ to denote the value $c_d X^d + \cdots c_1 X + c_0$, then it satisfies the following recurrence:

This recursive formula can be converted into an iterative algorithm, by working from the inside out:

$\subname{polyeval}(X, c_d, \ldots, c_1, c_0)$:

$Y := c_d$

for $i=d-1$ down to 0:

$Y := X Y + c_i$

return $Y$

$\quad$

This simple method for evaluating a polynomial is called Horner's method. We can write the poly-UHF algorithm using Horner's method as:

Since the final output is needed mod $\pmod$, we can reduce the intermediate result mod $\pmod$ after each iteration of the loop.

11.4.1. GHASH and GCM encryption

Even when $\pmod$ is a favorable prime, it can still be awkward to deal with reduction-mod-$\pmod$ on a computer that prefers to work with powers of 2. However, there is a way to define “addition” and “multiplication” operations over the set $\bits^n$, which has the necessary algebraic properties for poly-UHF to work. The algebraic structure is called a field. Fields with a finite number of elements are sometimes called Galois fields after their discoverer. (Galois is a French name, pronounced gal-wah.) Some bonus content about fields can be found in appendix B.

GHASH is a variant of Poly-UHF based on arithmetic in Galois fields (the G is for Galois). GHASH is used in GCM (Galois counter mode) encryption, the most popular standardized AEAD mode. GCM is an instance of encrypt-then-MAC (construction 9.5.1), with CTR mode as the encryption scheme, and GHASH as the UHF underlying its MAC.

Exercises

1. Prove the other direction of claim 11.1.3, that definition 11.1.2 implies definition 11.1.1.

2. Prove that every secure CRHF is also a secure UHF, interpreting the CRHF salt as the UHF key.

3. Prove that every secure PRF with $\secpar$ output bits is also a secure UHF.

4. Prove that if $U$ is a secure UHF with output length $\secpar$ bits, then $U'(\key,X) = U(\key,X) \oplus \key$ is also a secure UHF.

5. We say that $H : \bits^\secpar \times \bits^* \to \bits^n$ is almost-xor-universal (AXU) if, for all strings $X \ne X$ and all $\Delta \in \bits^n$,

   $\PR{ H(\key,X) \oplus H(\key,X') = \Delta } \text{ is negligible,}$

   where the probability is over the uniform choice of $\key$ from $\bits^\secpar$. In other words, for all $X \ne X'$ and $\Delta$, the following block of code outputs $\mytrue$ with negligible probability:

   $\key \gets \bits^\secpar$

   return $H(\key,X) \oplus H(\key,X') == \Delta$

   1. Prove that if $H$ is AXU, then the function $U(\key, X\|Y) = H(\key,X) \oplus Y$ is a secure UHF ($Y$ is $n$ bits).

   2. Prove that CBC-MAC is AXU.

   3. Show that Poly-UHF (as we have defined it) is not AXU. Use addition-mod-$p$ instead of xor in the security definition of AXU.

   4. Suggest a slight variant of Poly-UHF that is AXU and prove its security.

6. Let $U$ be a secure UHF that supports only block-aligned inputs, and let $\textsf{Pad}$ be a padding function (definition 8.6.1). Prove that the function $U'(\key,X) = U(\key,\textsf{Pad}(X))$ is a secure UHF, supporting arbitrary-length inputs.

7. Prove claim 11.2.3 (security of UH-PRF for non-block-aligned inputs).

8. Theorem 7.3.4 proves that a 3-round keyed Feistel cipher (section 7.3) construction is a secure PRP if each of its round functions is a PRF. Suppose we replace the first function with a simpler function $H$, such that $U(\key, X \| Y) = X \oplus H(\key,Y)$ is a secure UHF (i.e., $H$ is AXU; see exercise 11.5). In other words:

   $\mathbb{F}\Bigl( \key_1\|\key_2 \|\key_3, ~ X_0 \| X_1 \Bigr)$:

   $X_2 := X_0 \oplus \hl{H}(\key_1, X_1)$ // ${} = U(\key_1, X_0 \| X_1)$

   $X_3 := X_1 \oplus F(\key_2, X_2)$

   $X_4 := X_2 \oplus F(\key_3, X_3)$

   return $X_3 \| X_4$

   Prove that the resulting construction is a secure PRP.

9. h Let $F$ be a secure PRF with input and output length $\secpar$. Prove that the following function is also a secure PRF with input length $2\secpar$:

   $H\bigl( \key_1\| \key_2 \| \key_3, X_1 \| X_2 \bigr) = F\bigl(\key_3, F(\key_1,X_1) \oplus F(\key_2, X_2)\bigr).$

   It is an instance of UH-PRF.

10. h$\star$ Let $F$ be a secure PRF with input and output length $\secpar$. Prove that the following function is also a secure variable-length PRF:

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

    $Y := \bit 0^\secpar$

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

    $\key_i := F(\key,i)$

    $Y := Y \oplus F( \key_i, X_i)$

    $\key^* := F(\key, 0)$

    return $F(\key^*, Y)$

    It is an instance of UH-PRF.

11. Let $\Sigma$ be an encryption scheme. Let $H$ be a keyed function and define $U(\key,C\|A) = C \oplus H(\key,A)$, where the output of $H$ is padded with zeros (on the left, say) if its length is different from $C$. For example, if $C = \bit{01010101}$ and $H(\key,A) = \bit{111}$ then $C \oplus H(\key,A)$ means $\bit{01010}\hl{\bit{010}}$.

    Prove that if $\Sigma$ is a secure AE, and $U$ is a secure UHF (i.e., $H$ is AXU; see exercise 11.5), then the following scheme is a secure AEAD:

    $\begin{aligned} \K &= \Sigma.\K \times \bits^\secpar \\ \M &= \Sigma.\M \\ \C(\ell) &= \Sigma.\C(\ell) \end{aligned}$

    $\Enc\bigl( (\key_e,\key_m), \hl{A,} \ptxt \bigr)$:

    $\ctxt := \Sigma.\Enc(\key_e, \ptxt)$

    $T := H(\key_m, A)$

    // pad $T$ with zeros as needed:

    return $\ctxt \oplus T$

    $\Dec\bigl( (\key_e,\key_m), \hl{A,} \ctxt \bigr)$:

    $T := H(\key_m, A)$

    // pad $T$ with zeros as needed:

    $\ctxt' := \ctxt \oplus T$

    return $\Sigma.\Dec(\key_e, \ctxt' )$

    Connect the situation in this construction to exercise 11.5.

12. Let $\Sigma$ be a secure AEAD scheme that supports fixed-length associated data $\A = \bits^\secpar$. Let $U$ be a secure UHF that supports arbitrary-length inputs. Prove that the following construction is also a secure AEAD, supporting arbitrary-length associated data:

    $\begin{aligned} \K &= \Sigma.\K \times \bits^\secpar \\ \M &= \Sigma.\M \\ \C(\ell) &= \Sigma.\C(\ell) \\ \A &= \bits^* \end{aligned}$

    $\Enc\bigl( (\key_e,\key_u), A, \ptxt \bigr)$:

    $A' := U(\key_u, A)$

    return $\Sigma.\Enc(\key_e, A',\ptxt)$

    $\Dec\bigl( (\key_e,\key_u), A, \ctxt \bigr)$:

    $A' := U(\key_u, A)$

    return $\Sigma.\Dec(\key_e, A',\ctxt)$

13. h CMAC is a variant of CBC-MAC, in which we xor the last block with an independent key $\key_2$. In other words, CMAC is equivalent to plain CBC-MAC applied to $X_1 \| X_2 \| \cdots \| (X_\ell \oplus \key_2)$. CMAC has the convenient property that all of its calls to $F$ use the same key $\key_1$.

    $F'\bigl( \key_1 \| \key_2, X_1 \| X_2 \| \cdots \| X_\ell \bigr)$:

    $Y := \bit 0^\secpar$

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

    $Y := F( \key_1, Y \oplus X_i )$

    $Y := F( \key_1, Y \oplus X_\ell \hl{\oplus \key_2} )$

    return $Y$

    

    1. Prove that if $F$ is a secure PRF, then $F(\key_1, \cdot)$ and $F(\key_1, \key_2 \oplus \cdot)$ behave like two independent random functions. In other words, prove that the following two libraries are indistinguishable:

       $\key_1 \gets \bits^\secpar$

       $\key_2 \gets \bits^\secpar$

       $\prfquery_1(X)$:

       return $F(\key_1, X)$

       $\prfquery_2(X)$:

       return $F(\key_1, \key_2 \oplus X)$

       $\indist$

       $\prfquery_1(X)$:

       if $\prftable_1[X]$ undefined:

       $\prftable_1[X] \gets \bits^\secpar$

       return $\prftable_1[X]$

       $\prfquery_2(X)$:

       if $\prftable_2[X]$ undefined:

       $\prftable_2[X] \gets \bits^\secpar$

       return $\prftable_2[X]$

    2. Prove that CMAC is a secure variable-input-length PRF if $F$ is a secure PRP.

    CMAC can be reframed as an instance of UH-PRF.

14. CBC-MAC invokes the underlying PRF on input $Y_{i-1} \oplus X_i$. Suppose we instead use $Y_{i-1} \| X_i$ as input; this will require a PRF with input length $2\secpar$ and output length $\secpar$.

    Prove that the resulting function is a secure variable-length UHF if $F$ is a secure PRF:

    $F'( \key, X_1 \| X_2 \| \cdots \| X_\ell )$:

    $Y_0 := \bit 0^\secpar$

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

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

    return $Y_\ell$

    $\qquad$

15. Show that ECBC (construction 11.3.2), FCBC (construction 11.3.3) and CMAC (exercise 11.13) are not secure CRHFs: If their key is made public like a salt, then it is possible to efficiently compute collisions.

16. Poly-UHF interprets its input string as the coefficients of a polynomial, always fixing the leading coefficient to 1. Suppose the leading coefficient is not fixed and we interpret input $M_{d-1} \| \cdots \| M_0$ as the polynomial $M_{d-1} X^{d-1} + \cdots + M_1 X + M_0$. Show that the resulting variant of Poly-UHF is not a secure UHF.

17. 1. Give an example of a nonzero polynomial of degree $d$ that has more than $d$ roots over $\Z_{2^\secpar}$. Ideally, your polynomial should have $2^{\secpar-1}$ roots.

    2. Describe a concrete attack against poly-UHF mod $2^\secpar$ that produces a collision with constant probability (e.g., 1/2).

18. h Below is a simplified version of Poly1305, which is a variant of poly-UHF:

    $\begin{aligned} \pmod &= 2^{130}-5 \\ \secpar &= 128 \end{aligned}$

    $\textsf{Poly1305}(\key, M_d \| M_{d-1} \| \cdots \| M_1)$:

    // each $M_i$ is exactly $\secpar$ bits, interpreted as an integer in $\{0, \ldots, 2^{128}-1\}$

    return $\Bigl[ \bigl( \key^{d+1} + M_{d} \key^{d} + M_{d-1} \key^{d-1} + \cdots + M_1 \key \bigr) \pct \pmod \Bigr] \pct 2^{128}$

    For the purposes of this exercise, Poly1305 includes two important changes relative to construction 11.4.1: (1) It interprets the input as coefficients of a polynomial whose constant coefficient is zero, so the subscripts $M_i$ are shifted by one compared to construction 11.4.1. (2) After evaluating this polynomial mod $\pmod$, the result is further reduced mod $2^{128}$.

    This exercise explores the security of these changes.

    1. Speaking more abstractly, let $\pmod > 2^\secpar$ be a prime, and define $k = \lceil p / 2^\secpar \rceil$. For example, with $\secpar = 128$, Poly1305 has $k = 4$. Let $A$ and $B$ be integers in the range $\{0, \ldots, p-1\}$. Argue that there is a set $\mathcal{S}$, with $|\mathcal{S}| \le 2k+1$, such that:

       $A \equiv_{2^\secpar} B \implies A - B \in \mathcal{S}.$

       The expression $A-B$ refers to subtraction over the integers (no modular reduction).

    2. Let $Q(X)$ and $Q'(X)$ be distinct polynomials, of degree at most $d$, both with constant coefficient 0. Prove that when $\key$ is chosen uniformly from $\Z_\pmod$,

       $\PR{ Q(\key) \pct \pmod \equiv_{2^\secpar} Q'(\key) \pct \pmod } \le \frac{(2k+1)d}{\pmod}.$

       Where did you use the fact that $Q$ and $Q'$ have constant coefficient 0?

    $\begin{aligned} & Q(\key) \pct \pmod \equiv_{2^\secpar} Q'(\key) \pct \pmod \\ \implies & (Q(\key) \pct \pmod) - (Q'(\key) \pct \pmod) \in \mathcal{S} \\ \implies & \exists s \in \mathcal{S} : (Q(\key) \pct \pmod) - (Q'(\key) \pct \pmod) = s \\ \implies & \exists s \in \mathcal{S} : Q(\key) - Q'(\key) \equiv_\pmod s.\end{aligned}$

19. Show that Poly-UHF is not a secure CRHF: If its key is made public like a salt, then it is possible to efficiently compute collisions.

20. Show that Poly-UHF is not a secure PRF.

21. 1. Suppose you are given two block-aligned strings $\ptxt$ and $\ptxt'$ and two poly-UHF keys $\key$ and $\key'$. Show how to efficiently compute blocks $A$ and $A'$ such that:

       $\textsf{PolyUHF}(\key, \ptxt \| A) = \textsf{PolyUHF}(\key', \ptxt' \| A').$

    2. Let $\Sigma$ denote the authenticated encryption scheme obtained by applying Encrypt-then-MAC to

       • CTR-mode encryption; and

       • UH-PRF MAC, using poly-UHF as the underlying UHF.

       Describe how to compute a single ciphertext $\ctxt$ and two keys $\key, \key'$ such that $\Sigma.\Dec(\key, \ctxt) \ne \Sigma.\Dec(\key',\ctxt)$, and neither decryption results in $\myerr$. Can you make the two resulting plaintexts meaningful?