Black-Box Analysis of the Block-Cipher-Based Hash-Function Constructions from PGV

J. Black^{∗}  P. Rogaway ^{†}  T. Shrimpton ^{‡}

May 31, 2002

An abridged version, reference [2], appears as Advances in Cryptology – CRYPTO ’02, Lecture Notes in Computer Science, Vol. ????, M. Yung, ed., Springer-Verlag. This is the full version.

Abstract

Preneel, Govaerts, and Vandewalle [7] considered the 64 most basic ways to construct a hash function H: {0, 1}^{∗} → {0, 1}^{n} from a block cipher E: {0, 1}^{n} × {0, 1}^{n} → {0, 1}^{n}. They regarded 12 of these 64 schemes as secure, though no proofs or formal claims were given. The remaining 52 schemes were shown to be subject to various attacks. Here we provide a formal and quantitative treatment of the 64 constructions considered by PGV. We prove that, in a black-box model, the 12 schemes that PGV singled out as secure really are secure: we give tight upper and lower bounds on their collision resistance. Furthermore, by stepping outside of the Merkle-Damgård approach to analysis, we show that an additional 8 of the 64 schemes are just as collision resistant (up to a small constant) as the first group of schemes. Nonetheless, we are able to differentiate among the 20 collision-resistant schemes by bounding their security as one-way functions. We suggest that proving black-box bounds, of the style given here, is a feasible and useful step for understanding the security of any block-cipher-based hash-function construction.

Key words: Block ciphers, cryptographic hash functions, modes of operation, proving security.

∗ Department of Computer Science/171, University of Nevada, Reno, Nevada, 89557, USA. E-mail:

jrblack@cs.colorado.edu WWW: www.cs.colorado.edu/~jrblack/

† Department of Computer Science, University of California, Davis, California, 95616, USA; and Department of Computer Science, Faculty of Science, Chiang Mai University, 50200 Thailand. E-mail:

rogaway@cs.ucdavis.edu WWW: www.cs.ucdavis.edu/~rogaway/

‡ Department of Electrical and Computer Engineering, University of California, Davis, California, 95616, USA. Email: teshrim@ucdavis.edu WWW: www.ece.ucdavis.edu/~teshrim/

Contents

1 Introduction 1

2 Definitions 6

3 Collision Resistance of the Group-1 Schemes 8

4 Collision Resistance of the Group-2 Schemes 9

5 Matching Attacks on Collision Resistance 10

6 Security of the Schemes as OWFs 12

References 13

A Fatal Attacks on Five of PGV’s B-Labeled Schemes 14

B Two Notions of Inversion Resistance 14

C Proofs 15 C.1 Proof of Lemma 3.2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15 C.2 Proof of Claim 4.2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17 C.3 Proof of Claim 4.3 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17 C.4 Proof of Lemma 5.2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19 C.5 Proof of Theorem 5.3 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22 C.6 Proof of Lemma 6.2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23 C.7 Proof of Theorem 6.4 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23 C.8 Proof of Lemma 6.5 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23 C.9 Proof of Theorem 6.6 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24 C.10 Proof of Theorem 6.7 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25 C.11 Proof of Theorem 6.8 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25

1 Introduction

Background. The most popular collision-resistant hash-functions (eg., MD5 and SHA-1) iterate a compression function that is constructed from scratch (i.e., one that doesn’t use any lower-level cryptographic primitive). But there is another well-known approach, going back to Rabin [8], wherein one makes the compression function out of a block cipher. This approach has been less widely used, for a variety of reasons. These include export restrictions on block ciphers, a preponderance of 64-bit block lengths, problems attributable to “weak keys”, and the lack of popular block ciphers with per-byte speeds comparable to that of MD5 or SHA-1. Still, the emergence of the AES has somewhat modified this landscape, and now motivates renewed interest in finding good ways to turn a block cipher into a cryptographic hash function. This paper casts some fresh light on the topic.

The PGV paper. We return to some old work by Preneel, Govaerts, and Vandewalle [7] that considered turning a block cipher E: {0, 1}^{n} × {0, 1}^{n} → {0, 1}^{n} into a hash function H: ({0, 1}^{n})^{∗} → {0, 1}^{n} using a compression function f: {0, 1}^{n} × {0, 1}^{n} → {0, 1}^{n} derived from E. For v a fixed n-bit constant, PGV considers all 64 compression functions f of the form f(h_{i−1}, m_{i}) = E_{a}(b) ⊕ c where a, b, c ∈ {h_{i−1}, m_{i}, h_{i−1} ⊕ m_{i}, v}. Then define the iterated hash of f as:

function H (m_{1} ⋯ m_{ℓ})
for i ← 1 to ℓ do h_{i} ← f (h_{i−1}, m_{i})
return h_{ℓ}

Here h_{0} is a fixed constant, say 0^{n}, and |m_{i}| = n for each i ∈ [1..ℓ]. Of the 64 such schemes, the authors of [7] regard 12 as secure. Another 13 schemes they classify as backward-attackable, which means they are subject to an identified (but not very severe) potential attack. The remaining 39 schemes are subject to damaging attacks identified by [7] and others.

Some missing results. The authors of [7] focused on attacks, not proofs. All the same, it seems to be a commonly held belief that it should be possible to produce proofs for the schemes they regarded as secure. Indeed [7] goes so far as to say that “For each of these schemes it is possible to write a ‘security proof’ based on a black box model of the encryption algorithm, as was done for the Davies-Meyer scheme [by Winternitz [11]]”. This latter paper uses a black-box model of a block cipher—a model dating back to Shannon [9]—to show that the scheme we will later call H_{5} is secure in the sense of preimage-resistance. Specifically, [11] shows that any algorithm (with E and E^{−1} oracles) that always finds a preimage under H_{5} for a fixed value y ∈ {0, 1}^{n} will necessarily make at least 2^{n−1} expected oracle queries.

The model introduced by Winternitz for analyzing block-cipher-based hash functions was subsequently used by Merkle [6]. He gives black-box model arguments for H_{1}, and other functions, and considers questions of efficiency and concrete security. The black-box model of a block cipher has also found use in other contexts, such as [4, 5]. But, prior to the current work, we are unaware of any careful analysis in the literature, under any formalized model, for the collision-resistance of any block-cipher-based hash-function.

Summary of our results. This paper takes a more proof-centric look at the schemes from PGV [7], providing both upper and lower bounds for each. Some of our results are as expected, while others are not.

First we prove collision-resistance for the 12 schemes singled out by PGV as secure (meaning those marked “✓” or “FP” in [7]). We analyze these group-1 schemes, {H_{1}, …, H_{12}}, within the Merkle-Damgård paradigm. That is, we show that for each group-1 scheme H_{ı} its compression function f_{ı} is already collision resistant, and so H_{ı} must be collision resistant as well.

PGV’s backward-attackable schemes (marked “B” in [7]) held more surprises. We find that eight of these 13 schemes are secure, in the sense of collision resistance. In fact, these eight group-2 schemes, {H_{13}, …, H_{20}}, are just as collision-resistant as the group-1 schemes.

Despite having essentially the same collision-resistance, the group-1 and group-2 schemes can be distinguished based on their security as one-way functions: we get a better bound on inversionresistance for the group-1 schemes than we get for the group-2 schemes. Matching attacks (up to a constant) demonstrate that this difference is genuine and not an artifact of the security proof.

The remaining 44 = 64−20 hash functions considered by PGV are completely insecure: for these group-3 schemes one can find a (guaranteed) collision with two or fewer queries. This includes five of PGV’s backward-attackable schemes, where [7] had suggested a (less effective) meet-in-the-middle attack (see Appendix A).

Other surprises emerged in the mechanics of carrying out our analyses. Unlike the group-1 schemes, we found that the group-2 schemes could not be analyzed within the Merkle-Damgård paradigm; in particular, these schemes are collision resistant even though their compression functions are not. We also found that, for one set of schemes, the “obvious attack” on collision resistance needed some subtle probabilistic reasoning to rigorously analyze.

The security of the 64 PGV schemes is summarized in Figures 1 and 2, which also serve to define the different hash functions H_{ı} and their compression functions f_{ı}. Figure 3 gives a more readable description of f_{1}, …, f_{20}. A high-level summary of our findings is given by the following chart. The model (and the meaning of q) will be described momentarily.

PGV Category  Our Category  Collision Bound OWF Bound
✓or FP (12 schemes)  group-1: H_{1..12} (12 schemes)  Θ(q^{2}/2^{n})  Θ(q/2^{n})
group-2: H_{13..20} (8 schemes)  Θ(q^{2}/2^{n})  Θ(q^{2}/2^{n})

B (13 schemes)

group-3 (44 schemes)  Θ(1)  Θ(1)

F, P, or D (39 schemes)

Black-box model. Our model is the one dating to Shannon [9] and used for works like [4, 5, 11]. Fix a key-length κ and a block length n. An adversary A is given access to oracles E and E^{−1} where E is a random block cipher E: {0, 1}^{κ} × {0, 1}^{n} → {0, 1}^{n} and E^{−1} is its inverse. That is, each key k ∈ {0, 1}^{κ} names a randomly-selected permutation E_{k} = E(k, ·) on {0, 1}^{n}, and the adversary is given oracles E and E^{−1}. The latter, on input (k, y), returns the point x such that E_{k}(x) = y.

For a hash function H that depends on E, the adversary’s job in attacking the collision resistance of H is to find distinct M, M′ such that H(M) = H(M′). One measures the optimal adversary’s chance of doing this as a function of the number of E or E^{−1} queries it makes. Similarly, the adversary’s job in inverting H is to find an inverse under H for a random range point Y ∈ {0, 1}^{n}. (See Section 2 for a justification of this definition.) One measures the optimal adversary’s chance of doing this as a function of the total number of E or E^{−1} queries it makes.

ı ȷ  h_{i} =  CR low-bnd  CR up-bnd IR low-bnd IR up-bnd
1  E_{m_{i}}(m_{i}) ⊕ v  1  1  a
2  E_{h_{i−1}}(m_{i}) ⊕ v  1  1  b
13 3  E_{w_{i}}(m_{i}) ⊕ v  .3q(q−1)/2^{n}  3q(q+1)/2^{n}  0.15q^{2}/2^{n}  9(q+3)^{2}/2^{n} c
4  E_{v}(m_{i}) ⊕ v  1  1  a
5  E_{m_{i}}(m_{i}) ⊕ m_{i}  1  1  a
1 6  E_{h_{i−1}}(m_{i}) ⊕ m_{i} .039(q−1)(q−3)/2^{n} q(q+1)/2^{n}  0.4q/2^{n}  2q/2^{n}  d
9 7  E_{w_{i}}(m_{i}) ⊕ mi  .3q(q−1)/2^{n}  q(q+1)/2^{n}  0.6q/2^{n}  2q/2^{n}  e
8  E_{v}(m_{i}) ⊕ m_{i}  1  1  a
9  E_{m_{i}}(m_{i}) ⊕ h_{i−1}  1  1  f
10 E_{h_{i−1}}(m_{i}) ⊕ h_{i−1}  1  1  b
11 11 E_{w_{i}}(m_{i}) ⊕ h_{i−1}  .3q(q−1)/2^{n}  q(q+1)/2^{n}  0.6q/2^{n}  2q/2^{n}  e
12  E_{v}(m_{i}) ⊕ h_{i−1}  1  1  b
13  E_{m_{i}}(m_{i}) ⊕ w_{i}  1  1  f
3 14 E_{h_{i−1}}(m_{i}) ⊕ w_{i} .039(q−1)(q−3)/2^{n} q(q+1)/2^{n}  0.4q/2^{n}  2q/2^{n}  d
14 15  E_{w_{i}}(m_{i}) ⊕ w_{i}  .3q(q−1)/2^{n}  3q(q+1)/2^{n}  0.15q^{2}/2^{n}  9(q+3)^{2}/2^{n} c
16  E_{v}(m_{i}) ⊕ w_{i}  1  1  f
15 17  E_{m_{i}}(h_{i−1}) ⊕ v  .3q(q−1)/2^{n}  3q(q+1)/2^{n}  0.15q^{2}/2^{n}  9(q+3)^{2}/2^{n} c
18 E_{h_{i−1}}(h_{i−1}) ⊕ v  1  1  a
16 19  E_{w_{i}}(h_{i−1}) ⊕ v  .3q(q−1)/2^{n}  3q(q+1)/2^{n}  0.15q^{2}/2^{n}  9(q+3)^{2}/2^{n} c
20  E_{v}(h_{i−1}) ⊕ v  1  1  a
17 21 E_{m_{i}}(h_{i−1}) ⊕ m_{i}  .3q(q−1)/2^{n}  3q(q+1)/2^{n}  0.15q^{2}/2^{n}  9(q+3)^{2}/2^{n} c
22 E_{h_{i−1}}(h_{i−1}) ⊕ m_{i}  1  1  b
12 23 E_{w_{i}}(h_{i−1}) ⊕ m_{i}  .3q(q−1)/2^{n}  q(q+1)/2^{n}  0.6q/2^{n}  2q/2^{n}  e
24  E_{v}(h_{i−1}) ⊕ m_{i}  1  1  b
5 25 E_{m_{i}}(h_{i−1}) ⊕ h_{i−1}  .3q(q−1)/2^{n}  q(q+1)/2^{n}  0.6q/2^{n}  2q/2^{n}  e
26 E_{h_{i−1}}(h_{i−1}) ⊕ h_{i−1}  1  1  a
10 27 E_{w_{i}}(h_{i−1}) ⊕ h_{i−1}  .3q(q−1)/2^{n}  q(q+1)/2^{n}  0.6q/2^{n}  2q/2^{n}  e
28 E_{v}(h_{i−1}) ⊕ h_{i−1}  1  1  a
7 29 E_{m_{i}}(h_{i−1}) ⊕ w_{i}  .3q(q−1)/2^{n}  q(q+1)/2^{n}  0.6q/2^{n}  2q/2^{n}  e
30 E_{h_{i−1}}(h_{i−1}) ⊕ w_{i}  1  1  b
18 31 E_{w_{i}}(h_{i−1}) ⊕ w_{i}  .3q(q−1)/2^{n}  3q(q+1)/2^{n}  0.15q^{2}/2^{n}  9(q+3)^{2}/2^{n} c
32  E_{v}(h_{i−1}) ⊕ w_{i}  1  1  b

Figure 1: Summary of results. Column 1 is our number ı for the function (we write f_{ı} for the compression function and H_{ı} for its induced hash function). Column 2 is the number from [7] (we write f̂_{ȷ} and Ĥ_{ȷ}). Column 3 defines f_{ı}(h_{i−1}, m_{i}) and f̂_{ȷ}(h_{i−1}, m_{i}). We write w_{i} for m_{i}⊕h_{i−1}. Columns 4–7 give our collisionresistance and inversion-resistance bounds. Column 8 comments on collision-finding attacks: (a) H(M) is determined by the last block only; two E queries; (b) Attack uses two E queries and one E^{−1} query;

(c) Attack uses q/2 E queries and q/2 E^{−1} queries; (d) Attack given by Theorem 5.1; (e) Attack given by Theorem 5.3; (f) H(M) independent of block order; two E queries; (g) Attack uses (at most) two E queries. We do not explore inversion resistance for schemes that are trivially breakable in the sense of collision resistance.

ı ȷ  h_{i} =  CR low-bnd  CR up-bnd IR low-bnd IR up-bnd
19 33  E_{m_{i}}(w_{i}) ⊕ v  .3q(q−1)/2^{n}  3q(q+1)/2^{n}  0.15q^{2}/2^{n}  9(q+3)^{2}/2^{n} c
34 E_{h_{i−1}}(w_{i}) ⊕ v  1  1  b
35  E_{w_{i}}(w_{i}) ⊕ v  1  1  g
36  E_{v}(w_{i}) ⊕ v  1  1  b
20 37 E_{m_{i}}(w_{i}) ⊕ m_{i}  .3q(q−1)/2^{n}  3q(q+1)/2^{n}  0.15q^{2}/2^{n}  9(q+3)^{2}/2^{n} c
4 38 E_{h_{i−1}}(w_{i}) ⊕ m_{i} .039(q−1)(q−3)/2^{n} q(q+1)/2^{n}  0.4q/2^{n}  2q/2^{n}  d
39 E_{w_{i}}(w_{i}) ⊕ m_{i}  1  1  g
40  E_{v}(w_{i}) ⊕ m_{i}  1  1  g
8 41 E_{m_{i}}(w_{i}) ⊕ h_{i−1}  .3q(q−1)/2^{n}  q(q+1)/2^{n}  0.6q/2^{n}  2q/2^{n}  e
42 E_{h_{i−1}}(w_{i}) ⊕ h_{i−1}  1  1  b
43 E_{w_{i}}(w_{i}) ⊕ h_{i−1}  1  1  g
44 E_{v}(w_{i}) ⊕ h_{i−1}  1  1  b
6 45 E_{m_{i}}(w_{i}) ⊕ w_{i}  .3q(q−1)/2^{n}  q(q+1)/2^{n}  0.6q/2^{n}  2q/2^{n}  e
2 46 E_{h_{i−1}}(w_{i}) ⊕ w_{i} .039(q−1)(q−3)/2^{n} q(q+1)/2^{n}  0.4q/2^{n}  2q/2^{n}  d
47 E_{w_{i}}(w_{i}) ⊕ w_{i}  1  1  g
48  E_{v}(w_{i}) ⊕ w_{i}  1  1  g
49  E_{m_{i}}(v) ⊕ v  1  1  a
50  E_{h_{i−1}}(v) ⊕ v  1  1  a
51  E_{w_{i}}(v) ⊕ v  1  1  g
52  E_{v}(v) ⊕ v  1  1  a
53  E_{m_{i}}(v) ⊕ m_{i}  1  1  a
54 E_{h_{i−1}}(v) ⊕ m_{i}  1  1  b
55  E_{w_{i}}(v) ⊕ m_{i}  1  1  g
56  E_{v}(v) ⊕ m_{i}  1  1  a
57 E_{m_{i}}(v) ⊕ h_{i−1}  1  1  f
58 E_{h_{i−1}}(v) ⊕ h_{i−1}  1  1  a
59 E_{w_{i}}(v) ⊕ h_{i−1}  1  1  g
60  E_{v}(v) ⊕ h_{i−1}  1  1  a
61  E_{m_{i}}(v) ⊕ w_{i}  1  1  f
62 E_{h_{i−1}}(v) ⊕ w_{i}  1  1  b
63  E_{w_{i}}(v) ⊕ w_{i}  1  1  g
64  E_{v}(v) ⊕ w_{i}  1  1  b

Figure 2: Summary of results, continued. See the caption of Figure 1 for an explanation of the entries in this table.

[figure: >; >; >; ∨; ∨; f_{2}; h_{i−1}; m_{i}; h_{i}; f_{6}; h_{i}; m_{i}; h_{i−1}; h_{i}; m_{i}; h_{i−1}; f_{10}; >; >; ∨; f_{3}; m_{i}; h_{i−1}; h_{i}; f_{11}; m_{i}; h_{i}; h_{i−1}; f_{7}; h_{i}; h_{i−1}; m_{i}; >; ∨; ∨; h_{i}; f_{4}; h_{i}; h_{i−1}; m_{i}; m_{i}; h_{i−1}; f_{12}; h_{i−1}; f_{8}; h_{i}; m_{i}; >; >; m_{i}; h_{i−1}; f_{14}; h_{i}; m_{i}; h_{i−1}; h_{i}; ∨; f_{15}; v; m_{i}; h_{i−1}; f_{13}; v; h_{i}; ∨; ∨; ∨; h_{i}; m_{i}; h_{i−1}; f_{16}; v; h_{i}; h_{i−1}; m_{i}; f_{17}; h_{i−1}; m_{i}; h_{i}; f_{18}; ∨; ∨; h_{i−1}; h_{i}; m_{i}; f_{20}; h_{i−1}; h_{i}; m_{i}; f_{19}; v; f_{1}; m_{i}; f_{9}; m_{i}; h_{i−1}; h_{i}; h_{i−1}; h_{i}; f_{5}; m_{i}; h_{i−1}; h_{i}; ∨]

Figure 3: The compression functions f_{1}, …, f_{20} for the 20 collision-resistant hash functions H_{1}, …, H_{20}. A hatch marks the location for the key.

Discussion. As with [7], we do not concern ourselves with MD-strengthening [3, 6], wherein strings are appropriately padded so that any M ∈ {0, 1}^{∗} may be hashed. Simple results establish the security of the MD-strengthened hash function H^{∗} one gets from a secure multiple-of-block-length hash-function H. All of our attacks work just as well in the presence of MD-strengthening.

It is important not to read too much or too little into black-box results. On the one hand, attacks on block-cipher-based hash-functions have usually treated the block cipher as a black box. Such attacks are doomed when one has strong results within the black-box model. On the other hand, the only structural aspect of a block cipher captured by the model is its invertibility, so one must be skeptical about what a black-box-model result suggests when using a block cipher with significant structural properties, such as weak keys. With a block cipher like AES, one hopes for better. We point out that the black-box model is considerably sharper than treating the block cipher as a random function E: {0, 1}^{κ+n} → {0, 1}^{n}. Such a model should be avoided because many attacks on block-cipher-based hash-functions do use the adversary’s ability to compute E_{k}^{−1}. Overall, we see the black-box model as an appropriate first step in understanding the security of block-cipher-based hash-functions. Of course it would be nice to make due with standard assumptions, such as the block cipher being a pseudorandom function, but that assumption is insufficient for our purposes, and no sufficient assumption has been proposed.

Future directions. Though we spoke of AES as rekindling interest in block-cipher-based hashfunction designs, we do not address what we regard as the most interesting practical problem in that vein: namely, how best to use an n-bit block cipher to make a hash function with output length larger than n bits. (Many people see n = 128 bits as an inadequate output length for a hash function, particularly in view of [10].) The current work does not answer this question, but it does lay the groundwork for getting there.

2 Definitions

Basic notions. Let κ, n ≥ 1 be numbers. A block cipher is a map E: {0, 1}^{κ} × {0, 1}^{n} → {0, 1}^{n} where, for each k ∈ {0, 1}^{κ}, the function E_{k}(·) = E(k, ·) is a permutation on {0, 1}^{n}. If E is a block cipher then E^{−1} is its inverse, where E_{k}^{−1}(y) is the string x such that E_{k}(x) = y. Let Bloc(κ, n) be the set of all block ciphers E: {0, 1}^{κ} ×{0, 1}^{n} → {0, 1}^{n}. Choosing a random element of Bloc(κ, n) means that for each k ∈ {0, 1}^{κ} one chooses a random permutation E_{k}(·).

A (block-cipher-based) hash function is a map H: Bloc(κ, n) × D → R where κ, n, c ≥ 1, D ⊆ {0, 1}^{∗}, and R = {0, 1}^{c}. The function H must be given by a program that, given M, computes H^{E}(M) = H(E, M) using an E-oracle. Hash function f: Bloc(κ, n) × D → R is a compression function if D = {0, 1}^{a} × {0, 1}^{b} for some a, b ≥ 1 where a + b ≥ c. Fix h_{0} ∈ {0, 1}^{a}. The iterated hash of compression function f: Bloc(κ, n) × ({0, 1}^{a} × {0, 1}^{b}) → {0, 1}^{a} is the hash function H: Bloc(κ, n) × ({0, 1}^{b})^{∗} → {0, 1}^{a} defined by H^{E}(m_{1} ⋯ m_{ℓ}) = h_{ℓ} where h_{i} = f^{E}(h_{i−1}, m_{i}). Set H^{E}(ε) = h_{0}. If the program for f uses a single query E(k, x) to compute f^{E}(m, h) then f (and its iterated hash H) is rate-1. We often omit the superscript E to f and H.

We write x ←^{$} S for the experiment of choosing a random element from the finite set S and calling it x. An adversary is an algorithm with access to one or more oracles. We write these as superscripts.

Collision resistance. To quantify the collision resistance of a block-cipher-based hash function H we instantiate the block cipher by a randomly chosen E ∈ Bloc(κ, n). An adversary A is given oracles for E(·, ·) and E^{−1}(·, ·) and wants to find a collision for H^{E}—that is, M, M′ where M ≠ M′ but H^{E}(M) = H^{E}(M′). We look at the number of queries that the adversary makes and compare this with the probability of finding a collision.

Definition 2.1 (Collision resistance of a hash function) Let H be a block-cipher-based hash function, H: Bloc(κ, n) × D → R, and let A be an adversary. Then the advantage of A in finding collisions in H is the real number

Adv_{H}^{coll}(A) = Pr [E ←^{$} Bloc(κ, n); (M, M′) ←^{$} A^{E,E^{−1}} : M ≠ M′ & H^{E}(M) = H^{E}(M′)] ♢

For q ≥ 1 we write Adv_{H}^{coll}(q) = max_{A}{Adv_{H}^{coll}(A)} where the maximum is taken over all adversaries that ask at most q oracle queries (ie, E-queries + E^{−1} queries). Other advantage functions are silently extended in the same way.

We also define the advantage of an adversary in finding collisions in a compression function f: Bloc(κ, n) × {0, 1}^{a} × {0, 1}^{b} → {0, 1}^{c}. Naturally (h, m) and (h′, m′) collide under f if they are distinct and f^{E}(h, m) = f^{E}(h′, m′), but we also give credit for finding an (h, m) such that f^{E}(h, m) = h_{0}, for a fixed h_{0} ∈ {0, 1}^{c}. If one treats the hash of the empty string as the constant h_{0} then f^{E}(h, m) = h_{0} amounts to having found a collision between (h, m) and the empty string.

Definition 2.2 (Collision resistance of a compression function) Let f be a block-cipher-based compression function, f: Bloc(κ, n) × {0, 1}^{a} × {0, 1}^{b} → {0, 1}^{c}. Fix a constant h_{0} ∈ {0, 1}^{c} and an adversary A. Then the advantage of A in finding collisions in f is the real number

Adv_{f}^{comp}(A) = Pr [E ←^{$} Bloc(κ, n); ((h, m), (h′, m′)) ←^{$} A^{E,E^{−1}} :

((h, m) ≠ (h′, m′) ∧ f^{E}(h, m) = f^{E}(h′, m′)) ∨ f^{E}(h, m) = h_{0}] ♢

Inversion resistance. Though we focus on collision resistance, we are also interested in the difficulty of inverting hash functions. We use the following measure for the difficulty of inverting a hash function at a random point.

Definition 2.3 (Inverting random points) Let H be a block-cipher-based hash function, H: Bloc(κ, n) × D → R, and let A be an adversary. Then the advantage of A in inverting H is the real number

Adv_{H}^{inv}(A) = Pr [E ←^{$} Bloc(κ, n); σ ←^{$} R; M ← A^{E,E^{−1}}(σ) : H^{E}(M) = σ] ♢

The PGV hash functions. Figure 1 and Figure 2 serve to define f_{ı}[n]: Bloc(κ, n) × {0, 1}^{n} × {0, 1}^{n} → {0, 1}^{n} and f̂_{ȷ}[n]: Bloc(κ, n) × ({0, 1}^{n} × {0, 1}^{n}) → {0, 1}^{n} for ı ∈ [1..20] and ȷ ∈ [1..64]. These compression functions induce hash functions H_{ı}[n] and Ĥ_{ȷ}[n]. Usually we omit writing the [n].

Discussion. The more customary formalization for a one-way function speaks to the difficulty of finding a preimage for the image of a random domain point (as opposed to finding a preimage of a random range point). But a random-domain-point definition becomes awkward when considering a function H with an infinite domain: in such a case one would normally have to partition the domain into finite sets and insist that H be one-way on each of them. For each of the functions H_{1}, …, H_{20}, the value H_{ı}^{E}(M) is uniform or almost uniform in {0, 1}^{n} when M is selected uniformly in ({0, 1}^{n})^{m} and E is selected uniformly in Bloc(n, n). Thus there is no essential difference between the two notions in these cases. This observation justifies defining inversion resistance in the manner that we have. See Appendix B.

Definition 2.3 might be understood as giving the technical meaning of preimage resistance. However, a stronger notion of preimage resistance also makes sense, where the range value σ is a fixed point, not a random one, and one maximizes over all such points. Similarly, the usual, randomdomain-point notion for a one-way function (from the prior paragraph) might be understood as a technical meaning of 2nd preimage resistance, but a stronger notion makes sense, where the domain point M is a fixed string, not a random one, and one must maximize over all domain points of a given length. A systematic exploration of different notions of inversion resistance is beyond the scope of this paper.

Conventions. For the remainder of this paper we assume the following significant conventions. First, an adversary does not ask any oracle query in which the response is already known; namely, if A asks a query E_{k}(x) and this returns y, then A does not ask a subsequent query of E_{k}(x) or E_{k}^{−1}(y); and if A asks E_{k}^{−1}(y) and this returns x, then A does not ask a subsequent query of E_{k}^{−1}(y) or E_{k}(x). Second, when a (collision-finding) adversary A for H outputs M and M′, adversary A has already computed H^{E}(M) and H^{E}(M′), in the sense that A has made the necessary E or E^{−1} queries to compute H^{E}(M) and H^{E}(M′). Similarly, we assume that a (collision-finding) adversary A for the compression function f computes f^{E}(h, m) and f^{E}(h′, m′) prior to outputting (h, m) and (h′, m′). Similarly, when an (inverting adversary) A for H outputs a message M, we assume that A has already computed H^{E}(M), in the sense that A has made the necessary E or E^{−1} queries to compute this value. These assumption are all without loss of generality, in that an adversary A not obeying these conventions can easily be modified to given an adversary A′ having similar computational complexity that obeys these conventions and has the same advantage as A.

3 Collision Resistance of the Group-1 Schemes

The group-1 hash-functions H_{1}, …, H_{12} can all be analyzed using the Merkle-Damgård paradigm. Our security bound is identical for all of these schemes.

Theorem 3.1 [Collision resistance of the group-1 hash functions] Fix n ≥ 1 and ı ∈ [1..12]. Then Adv_{H_{ı}[n]}^{coll}(q) ≤ q(q + 1)/2^{n} for any q ≥ 1. ◇

The proof combines a lemma showing the collision-resistance of f_{1}, …, f_{12} with the classical result, stated for the black-box model, showing that a hash function is collision resistant if its compression function is. For completeness, the proof of the following is given in Appendix C.1.

Lemma 3.2 [Merkle-Damgård [3, 6] in the black-box model] Let f be a compression function f: Bloc(n, n) × {0, 1}^{n} × {0, 1}^{n} → {0, 1}^{n} and let H be the iterated hash of f. Then Adv_{H}^{coll}(q) ≤ Adv_{f}^{comp}(q) for all q ≥ 1. ◇ Algorithm SimulateOracles(A, n) Initially, i ← 0 and E_{k}(x) = undefined for all (k, x) ∈ {0, 1}^{n} × {0, 1}^{n} Run A^{?,?}, answering oracle queries as follows: When A asks a query (k, x) to its left oracle:

i ← i + 1; k_{i} ← k; x_{i} ← x; y_{i} ←^{$} \overline{Range}(E_{k}); E_{k}(x) ← y_{i}; return y_{i} to A

When A asks a query (k, y) to its right oracle:

i ← i + 1; k_{i} ← k; y_{i} ← y; x_{i} ←^{$} \overline{Domain}(E_{k}); E_{k}(x_{i}) ← y; return x_{i} to A

When A halts, outputting a string out: return ((x_{1}, k_{1}, y_{1}), ..., (x_{i}, k_{i}, y_{i}), out)

Figure 4: Simulating a block-cipher oracle. Domain(E_{k}) is the set of points x where E_{k}(x) is no longer undefined and \overline{Domain}(E_{k}) = \{0, 1\}^{n} − Range(E_{k}). Range(E_{k}) is the set of points where E_{k}(x) is no longer undefined and \overline{Range}(E_{k}) = \{0, 1\}^{n} − Range(E_{k}).

Lemma 3.3 [Collision resistance of the group-1 compression functions] Fix n ≥ 1 and ı ∈ [1..12]. Then Adv_{f_{ı}[n]}^{comp}(q) ≤ q(q + 1)/2^{n} for any q ≥ 1. ◇

Proof of Lemma 3.3: Fix a constant h_{0} ∈ {0, 1}^{n}. We focus on f = f_{1}; assume that case. Let A^{?,?} be an adversary attacking the compression function f. Assume that A asks its oracles a total of q queries. We are interested in A’s behavior when its left oracle is instantiated by E ←^{$} Bloc(n, n) and its right oracle is instantiated by E^{−1}. That experiment is identical, from A’s perspective, to the one defined in Figure 4. Define ((x_{1}, k_{1}, y_{1}), …, (x_{q}, k_{q}, y_{q}), out) by running SimulateOracles(A, n). If A is successful it means that A outputs (k, m), (k′, m′) such that one of the following holds: (k, m) ≠ (k′, m′) and f(k, m) = f(k′, m′), or else f(k, m) = h_{0}. By our definition of f this means that E_{k}(m) ⊕ m = E_{k′}(m′) ⊕ m′ for the first case, or E_{k}(m) ⊕ m = h_{0} for the second. By our conventions at the end of Section 2, either there are distinct r, s ∈ [1..q] such that (x_{r}, k_{r}, y_{r}) = (m, k, E_{k}(m)) and (x_{s}, k_{s}, y_{s}) = (m′, k′, E_{k′}(m′)) and E_{k_{r}}(m_{r}) ⊕ m_{r} = E_{k_{s}}(m_{s}) ⊕ m_{s} or else there is an r ∈ [1..q] such that (x_{r}, k_{r}, y_{r}) = (m, k, h_{0}) and E_{k_{r}}(x_{r}) = h_{0}. We show that this event is unlikely.

In the execution of SimulateOracles(A, n), for any i ∈ [1..q], let C_{i} be the event that y_{i} ⊕ x_{i} = h_{0} or that there exists j ∈ [1..i − 1] such that either y_{i} ⊕ x_{i} = y_{j} ⊕ x_{j}. In carrying out the simulation of A’s oracles, either y_{i} or x_{i} was randomly selected from a set of at least size 2^{n} − (i − 1), so Pr[C_{i}] ≤ i/(2^{n} − i). By the contents of the previous paragraph, we thus have that Adv_{f[n]}^{comp}(A) ≤ Pr[C_{1} ∨ … ∨ C_{q}] ≤ ∑_{i=1}^{q} Pr[C_{i}] ≤ ∑_{i=1}^{q} \frac{i}{2^{n}−(i−1)} ≤ \frac{1}{2^{n}−2^{n−1}} ∑_{i=1}^{q} i if q ≤ 2^{n−1}. Continuing, our

expression is at most \frac{1}{2^{n−1}} \frac{q(q+1)}{2} = \frac{q(q+1)}{2^{n}}. Since the above inequality is vacuous when q > 2^{n−1}, we may now drop the assumption that q ≤ 2^{n−1}. We conclude that Adv_{f[n]}^{comp}(q) ≤ q(q + 1)/2^{n}.

The above concludes the proof for the case of f_{1}. Compression functions f_{2..12} are similar.

4 Collision Resistance of the Group-2 Schemes

We cannot use the Merkle-Damgård paradigm for proving the security of H_{13..20} because their compression functions are not collision-resistant. Attacks for each compression function are easy to find. For example, one can break f_{17}(h, m) = E_{m}(h) ⊕ m as a compression function by choosing any two distinct m, m′ ∈ {0, 1}^{n}, computing h = E_{m}^{−1}(m) and h′ = E_{m′}^{−1}(m′), and outputting (h, m) and (h′, m′). All the same, hash functions H_{13..20} enjoy almost the same collision-resistance upper bound as H_{1..12}.

Theorem 4.1 [Collision resistance of the group-2 hash functions] Fix n ≥ 1 and ı ∈ [13..20]. Then Adv_{H_{ı}[n]}^{coll}(q) ≤ 3q(q + 1)/2^{n} for all q ≥ 1. ◇

Proof of Theorem 4.1: Fix constants h_{0}, v ∈ {0, 1}^{n}. We prove the theorem for the case of H_{13}, where f(h, m) = f_{13}(h, m) = E_{h ⊕ m}(m) ⊕ v.

We define a directed graph G = (V_{G}, E_{G}) with vertex set V_{G} = {0, 1}^{n} × {0, 1}^{n} × {0, 1}^{n} and an arc (x, k, y) → (x′, k′, y′) in E_{G} if and only if k′ ⊕ x′ = y ⊕ v.

Let A^{?,?} be an adversary attacking H_{13}. We analyze the behavior of A when its left oracle is instantiated by E ←^{$} Bloc(n, n) and its right oracle is instantiated by E^{−1}. Assume that A asks its oracles at most q total queries. We must show that Adv_{H_{13}[n]}^{coll}(A) ≤ 3q(q + 1)/2^{n}. Run the algorithm SimulateOracles(A, n). As A executes with its (simulated) oracle, color the vertices of G as follows:

Initially, each vertex of G is uncolored.

When A asks an E-query (k, x) and this returns a value y, or when A asks an E^{−1}-query of (k, y) and this returns x, then: if x ⊕ k = h_{0} then vertex (x, k, y) gets colored red; otherwise vertex (x, k, y) gets colored black.

According to the conventions at the end of Section 2, every query the adversary asks results in exactly one vertex getting colored red or black, that vertex formerly being uncolored.

We give a few additional definitions. A vertex of G is colored when it gets colored red or black. A path P in G is colored if all of its vertices are colored. Vertices (x, k, y) and (x′, k′, y′) are said to collide if y = y′. Distinct paths P and P′ are said to collide if all of their vertices are colored and they begin with red vertices and they end with colliding vertices. Let C be the event that, as a result of the adversary’s queries, there are formed in G some two colliding paths.

Claim 4.2 Adv_{H_{13}[n]}^{coll}(A) ≤ Pr[C] .

Claim 4.3 Pr[C] ≤ 3q(q + 1)/2^{n}.

Claim 4.2 is proven in Appendix C.2 while Claim 4.3 is proven in Appendix C.3. The result for H_{13} now follows by combining the two claims. The proofs for H_{14..20} can be obtained by adapting the proof we have just given (including the contents of the Appendices C.2 and C.3) with the help of Figure 5.

5 Matching Attacks on Collision Resistance

In this section we show that the security bounds given in Sections 3 and 4 are tight: we devise and analyze attacks that achieve advantage close to the earlier upper bounds. Our results are as follows.

ı h_{i} =  (x, k, y) → (x′, k′, y′) if (x, k, y) red if (x, k, y), (x′, k′, y′) collide if
13 E_{w_{i}}(m_{i}) ⊕ v  y ⊕ v = x′ ⊕ k′  x ⊕ k = h_{0} y = y′
14 E_{w_{i}}(m_{i}) ⊕ w_{i} k ⊕ y = x′ ⊕ k′  x ⊕ k = h_{0} k ⊕ y = k′ ⊕ y′
15 E_{m_{i}}(h_{i−1}) ⊕ v y ⊕ v = x′  x = h_{0}  y ⊕ v = x′
16 E_{w_{i}}(h_{i−1}) ⊕ v  y ⊕ v = x′  x = h_{0}  y ⊕ v = x′
17 E_{m_{i}}(h_{i−1}) ⊕ m_{i} k ⊕ y = x′  x = h_{0}  k ⊕ y = k′ ⊕ y′
18 E_{w_{i}}(h_{i−1}) ⊕ w_{i} k ⊕ y = x′  x = h_{0}  k ⊕ y = k′ ⊕ y′
19 E_{m_{i}}(w_{i}) ⊕ v  y ⊕ v = x′ ⊕ k′  x ⊕ k = h_{0} y = y′
20 E_{m_{i}}(w_{i}) ⊕ m_{i} k ⊕ y = x′ ⊕ k′  x ⊕ k = h_{0} k ⊕ y = k′ ⊕ y′

Figure 5: Rules for the existence of arcs, the coloring of a vertex red, and when vertices are said to collide. These notions are used in the proof of Theorem 4.1.

Theorem 5.1 [Finding collisions in H_{1..4}] Let ı ∈ [1..4] and n ≥ 1. Then

Adv_{H_{ı}[n]}^{coll}(q) ≥ 0.039(q − 1)(q − 3)/2^{n}

for any even q ∈ [1..2^{(n−1)/2}]. ◇

Let Perm(n) be the set of all permutations on {0, 1}^{n}. Let P_{q}({0, 1}^{n}) denote the set of all qelement subsets of {0, 1}^{n}. The proof of Theorem 5.1 uses the following technical lemma whose proof appears in Appendix C.4.

Lemma 5.2 Fix n ≥ 1. Then

Pr [π ←^{$} Perm(n); Q ←^{$} P_{q}({0, 1}^{n}) : ∃x, x′ ∈ Q such that x ≠ x′ and
π(x) ⊕ x = π(x′) ⊕ x′] ≥ .039(q − 1)(q − 3)/2^{n}

for any even q ∈ [1..2^{(n−1)/2}]. ◇

Proof of Theorem 5.1: Consider the case H^{E} = H_{1}^{E} and fix h_{0} ∈ {0, 1}^{n}. Let A be an adversary with the oracles E, E^{−1}. Let A select m_{1}, …, m_{q} ←^{$} {0, 1}^{n} and compute y_{j} = E_{h_{0}}(m_{j}) ⊕ m_{j}, j ∈ [1..q]. If A finds r, s ∈ [1..q] such that r < s and y_{r} = y_{s} then it returns (m_{r}, m_{s}); otherwise it returns (m_{1}, m_{1}) (failure). Let π = E_{h_{0}}. By definition π is a uniform element in Perm(n), so we can invoke Lemma 5.2 to see that the probability that A succeeds to find a collision among m_{1}, …, m_{q} under H is at least .039(q − 1)(q − 3)/2^{n}.

This attack and analysis extends to H_{2..4} by recognizing that for each scheme and distinct one-block messages m and m′ we have H^{E}(m) = H^{E}(m′) if and only if π(x) ⊕ x = π(x′) ⊕ x′ where π = E_{h_{0}} and x, x′ are properly defined. For example, for H_{2}^{E} define x = h_{0} ⊕ m and x′ = h_{0} ⊕ m′.

Analysis of collision-finding attacks on H_{5..20} is considerably less technical than for H_{1..4}. The crucial difference is that in each of H_{5..20} the block cipher is keyed in the first round by either the message m, or m ⊕ h_{0}, where h_{0} is a fixed constant. Hence when A hashes q distinct one-block messages it always observes q random values. See Appendix C.5 for a proof of the following.

Theorem 5.3 [Finding collisions in H_{5..20}] Let ı ∈ [5..20] and n ≥ 1. Then Adv_{H_{ı}[n]}^{coll}(q) ≥ 0.3q(q − 1)/2^{n} for any q ∈ [1..2^{n/2}]. ◇

6 Security of the Schemes as OWFs

From the perspective of collision resistance there is no reason to favor any particular scheme from H_{1..20}. However, in this section we show that these schemes can be separated based on their strength as one-way functions. In particular, for an n-bit block cipher, an adversary attacking a group-1 hash function requires nearly 2^{n} oracle queries to do well at inverting a random range point, while an adversary attacking a group-2 hash function needs roughly 2^{n/2} oracle queries to do the same job.

We begin with the theorem establishing good inversion-resistance for the group-1 schemes. The theorem is immediate from the two lemmas that follow it. The first result is analogous to Lemma 3.2. The second result shows that f_{1..12} have good inversion-resistance. All omitted proofs can be found in the appendices.

Theorem 6.1 [OWF security of the group-1 hash functions] Fix n ≥ 1 and ı ∈ [1..12]. Then Adv_{H_{ı}[n]}^{inv}(q) ≤ q/2^{n−1} for any q ≥ 1. ◇

Lemma 6.2 [Merkle-Damgård for inversion resistance] Let f be a compression function having signature f: Bloc(n, n) × {0, 1}^{n} × {0, 1}^{n} → {0, 1}^{n} and let H be the iterated hash of f. Then Adv_{H}^{inv}(q) ≤ Adv_{f}^{inv}(q) for all q ≥ 1. ◇

Lemma 6.3 [Inversion resistance of the group-1 compression functions] Fix n ≥ 1 and ı ∈ [1..12]. Then Adv_{f_{ı}[n]}^{inv}(q) ≤ q/2^{n−1} for any q ≥ 1. ◇

Proof of Lemma 6.3: Fix a constant h_{0} ∈ {0, 1}^{n}. We focus on compression function f^{E} = f_{1}^{E}; assume that case. Let A be an adversary with oracles E, E^{−1} and input σ. Assume that A asks its oracles q total queries.

Define ((x_{1}, k_{1}, y_{1}), …, (x_{q}, k_{q}, y_{q}), out) by running SimulateOracles(A, n). By our conventions at the end of Section 2, if A outputs (h, m) such that E(h, m) ⊕ m = σ then (m, h, E(h, m)) = (x_{i}, k_{i}, y_{i}) for some i ∈ [1..q]. Let C_{i} be the event that (x_{i}, k_{i}, y_{i}) is such that x_{i} ⊕ y_{i} = σ. In carrying out the simulation of A’s oracles, either x_{i} or y_{i} was randomly assigned from a set of at least size 2^{n} − (i − 1), so Pr[C_{i}] ≤ 1/(2^{n} − (i − 1)). Thus Pr[(h, m) ← A^{E,E^{−1}}(z) : E(h, m) ⊕ m = σ] ≤ Pr[C_{1} ∨ … ∨ C_{q}] ≤ ∑_{i=1}^{q} Pr[C_{i}] ≤ ∑_{i=1}^{q} \frac{1}{2^{n}−(i−1)} ≤ \frac{q}{2^{n}−2^{n−1}} if q ≤ 2^{n−1}. Continuing, our expression is at most \frac{q}{2^{n−1}} . Since the above inequality is vacuous when q > 2^{n−1}, we may now drop the assumption that q ≤ 2^{n−1}.

The above concludes the proof for the case of f_{1}. Compression functions f_{2..12} are similar.

We cannot use Lemma 6.2 to prove the security of the group-2 schemes because the associated compression functions are not inversion-resistant. An attack for each is easy to find. For example, consider f_{13}(h, m) = E(h ⊕ m, m) ⊕ v. For any point σ, the adversary fixes k = 0, computes m = E_{0}^{−1}(σ ⊕ v), and returns (m, m), which is always a correct inverse to σ. Still, despite these compression functions being invertible with a single oracle query, there is a reasonable security bound for the group-2 schemes.

Theorem 6.4 [OWF security of the group-2 hash functions] Fix n ≥ 1 and ı ∈ [13..20]. Then Adv_{H_{ı}[n]}^{inv}(q) ≤ 9(q + 3)^{2}/2^{n} for any q > 1. ◇ The proof of Theorem 6.4 appears in Appendix C.7 and makes use of the following lemma, which guarantees that, up to a constant, for messages of length greater than n-bits, the bounds we have computed for collision resistance hold for inversion resistance as well.

Lemma 6.5 [Collision resistance ⇒ inversion resistance] Fix ı ∈ [1..20] and n ≥ 1. Let H̃ = H_{ı}[n] restricted to domain Bloc(n, n) × ⋃_{i≥2}{0, 1}^{in}. Then Advinv ; H̃(q) ≤ 3Adv_{H}^{coll}(q + 2) + q/2^{n−1} for any q ≥ 1. ◇

For the proof of Lemma 6.5 see Appendix C.8.

Finally, we prove that the security bounds given in Theorems 6.1 and 6.4 are tight, by describing adversaries that achieve advantage very close to the upper bounds. The analysis falls into three groupings.

Theorem 6.6 [Attacking H_{1..4} as OWFs] Fix n ≥ 1 and ı ∈ [1..4]. Then Adv_{H_{ı}[n]}^{inv}(q) ≥ 0.4q/2^{n} for any q ∈ [1..2^{n−2}]. ◇

Theorem 6.7 [Attacking H_{5..12} as OWFs] Fix n ≥ 1 and ı ∈ [5..12]. Then Adv_{H_{ı}[n]}^{inv}(q) ≥ 0.6q/2^{n} for any q ∈ [1..2^{n} − 1]. ◇

Theorem 6.8 [Attacking H_{13..20} as OWFs] Fix n ≥ 1 and ı ∈ [13..20]. Then Adv_{H_{ı}[n]}^{inv}(q) ≥ 0.15q^{2}/2^{n} for any even q ∈ [2..2^{n/2}]. ◇

The proofs for the above three theorems are found in Appendices C.9, C.10, and C.11, respectively.

Acknowledgments

Thanks to the anonymous reviewers for helpful comments and references.

John Black received support from NSF CAREER award CCR-0133985. This work was carried out while John was at the University of Nevada, Reno.

Phil Rogaway and his student Tom Shrimpton received support from NSF grant CCR-0085961 and a gift from CISCO Systems. Many thanks for their kind support.

References

[1] M. Bellare, J. Kilian, and P. Rogaway. The security of cipher block chaining message authentication code. Journal of Computer and System Sciences, 61(3):362–399, 2000.

[2] J. Black, P. Rogaway, and T. Shrimpton. Black-box analysis of the block-cipher-based hashfunction constructions from PGV. In Advances in Cryptology – CRYPTO ’02, volume ??? of Lecture Notes in Computer Science. Springer-Verlag, 2002. Proceedings version of this paper.

[3] I. Damgård. A design principle for hash functions. In G. Brassard, editor, Advances in Cryptology – CRYPTO ’89, volume 435 of Lecture Notes in Computer Science. Springer-Verlag, 1990.

[4] S. Even and Y. Mansour. A construction of a cipher from a single pseudorandom permutation. In Advances in Cryptology – ASIACRYPT ’91, volume 739 of Lecture Notes in Computer Science, pages 210–224. Springer-Verlag, 1992.

\begin{matrix}ȷ & M_{c} \\ 39 & h_{0} ⊕ c ∥ E_{c}(c) ⊕ h_{0} \\ 40 & h_{0} ⊕ c ∥ E_{v}(c) ⊕ h_{0} \\ 43 & h_{0} ⊕ c ∥ E_{c}(c) ⊕ h_{0} ⊕ c \\ 55 & h_{0} ⊕ c ∥ E_{c}(v) ⊕ h_{0} \\ 59 & h_{0} ⊕ c ∥ E_{c}(v) ⊕ h_{0} ⊕ c \end{matrix}

Figure 6: Messages that collide under the five weak “backward attackable” schemes in [7]. For any c ∈ {0, 1}^{n}, Ĥ_{ȷ}(M_{c}) = h_{0} for all five schemes listed.

[5] J. Kilian and P. Rogaway. How to protect DES against exhaustive key search. Journal of Cryptology, 14(1):17–35, 2001. Earlier version in CRYPTO ’96.

[6] R. Merkle. One way hash functions and DES. In G. Brassard, editor, Advances in Cryptology – CRYPTO ’89, volume 435 of Lecture Notes in Computer Science. Springer-Verlag, 1990.

[7] B. Preneel, R. Govaerts, and J. Vandewalle. Hash functions based on block ciphers: A synthetic approach. In Advances in Cryptology – CRYPTO ’93, Lecture Notes in Computer Science, pages 368–378. Springer-Verlag, 1994.

[8] M. Rabin. Digitalized signatures. In R. DeMillo, D. Dobkin, A. Jones, and R. Lipton, editors, Foundations of Secure Computation, pages 155–168. Academic Press, 1978.

[9] C. Shannon. Communication theory of secrecy systems. Bell Systems Technical Journal, 28(4):656–715, 1949.

[10] P. van Oorschot and M. Wiener. Parallel collision search with cryptanalytic applications. Journal of Cryptology, 12(1):1–28, 1999. Earlier version in ACM CCS ’94.

[11] R. Winternitz. A secure one-way hash function built from DES. In Proceedings of the IEEE Symposium on Information Security and Privacy, pages 88–90. IEEE Press, 1984.

A Fatal Attacks on Five of PGV’s B-Labeled Schemes

In [7] there are a total of 13 schemes labeled as “backward attackable.” We have already shown that eight of these, H_{13..20}, are collision resistant. But the remaining five schemes are completely insecure; each can be broken with two queries. Consider, for example, H = Ĥ_{39}, constructed by iterating the compression function f = f̂_{39} defined by f^{E}(h_{i−1}, m_{i}) = E_{m_{i} ⊕ h_{i−1}}(m_{i} ⊕ h_{i−1}) ⊕ m_{i}. For any c ∈ {0, 1}^{n} the strings (h_{0} ⊕ c) ∥ (E_{c}(c) ⊕ h_{0}) hashes to h_{0}, and so it so it takes only two queries to produce a collision. Variants of this attack, break the schemes Ĥ_{40}, Ĥ_{43}, Ĥ_{55} and Ĥ_{59} defined in Figure 1. See Figure 6 for the attacks.

B Two Notions of Inversion Resistance

We defined Adv_{H}^{inv} by giving the adversary a random range point σ ∈ {0, 1}^{n} and asking the adversary to find an H-preimage for σ. The usual definition for a one-way function has one choose a random domain point M, apply H, and ask then ask the adversary to invert the result.

Definition B.1 (Conventional definition of a OWF) Let H be a block-cipher-based hash function, H: Bloc(κ, n) × D → R, and let ℓ be a number such that {0, 1}^{ℓ} ⊆ D. Let A be an adversary. Then the advantage of A in inverting H on the distribution induced by applying H to a random ℓ-bit string is the real number

Adv_{H}^{owf}(A, ℓ) = Pr [E ←^{$} Bloc(κ, n); M ←^{$} ({0, 1}^{n})^{ℓ}; σ ← H^{E}(M);

M′ ← A^{E,E^{−1}}(σ) : H^{E}(M′) = σ] ♢

For q ≥ 0 a number, Adv_{H}^{owf}(q, ℓ) is defined in the usual way, as the maximum value of Adv_{H}^{owf}(A, ℓ) over all adversaries A that ask at most q queries.

Though the Adv^{owf} and Adv^{inv} measures can, in general, be far apart, it is natural to guess that they coincide for “reasonable” hash-functions like H_{1..20}. In particular, one might think that the random variable H_{ı}^{E}(M) is uniformly distributed in {0, 1}^{n} if M ←^{$} {0, 1}^{nℓ} and E ←^{$} Bloc(n, n). Interestingly, this is not true. For example, experiments show that when E ←^{$} Bloc(2, 2) and M ←^{$} {0, 1}^{4} the string H_{1}^{E}(M) takes on the value 00 more than a quarter of the time (in fact, 31.25% of the time) while each of the remaining three possible outputs (01, 10, 11) occur less than a quarter of the time (each occurs 22.91\overline{6}% of the time). Still, for H_{1..20}, the two notions are close enough that we have used Definition 2.3 as a surrogate for Definition B.1. The result is as follows.

Lemma B.2 Fix n ≥ 1 and ı ∈ [1..20]. Then for any q, ℓ ≥ 1,

|Adv_{H_{ı}[n]}^{inv}(q) − Adv_{H_{ı}[n]}^{owf}(q, ℓ)| ≤ ℓ/2^{n−1} ♢

Proof of Lemma B.2: Consider the case for H = H_{1}. The proof is a “game argument,” as in [5]. Consider Games 1 and 2, both defined in Figure 7. The probability that A outputs 1 in game 1 is exactly Adv_{H}^{inv}(A), while the probability that A outputs 1 in game 2 is exactly Adv_{H}^{owf}(A). Furthermore, Games 1 and 2 are identical except for the statement that follows the conditional setting of bad to true. Thus |Adv_{H}^{inv}(A) − Adv_{H}^{owf}(A)| is at most the probability that bad gets set to true in Game 1. This value is at most 2ℓ/2^{n}. The result follows, and extends in the natural way for the other hash functions.

C Proofs

C.1 Proof of Lemma 3.2

Let A be a collision-finding adversary for H that takes two oracles, E, E^{−1}. We construct from A a collision-finding adversary B for f. Adversary B also takes oracles E, E^{−1}. Let B run A. When A makes an E (resp., E^{−1}) query, B forwards it to E (resp., E^{−1}) and returns to A the result. For i ∈ [1..q], we say that the ith triple is (x_{i}, k_{i}, y_{i}) if A’s ith oracle query was an Equery of (k_{i}, x_{i}) and this returned y_{i}, or else A’s ith oracle query was an E^{−1}-query (k_{i}, y_{i}) and this returned x_{i}. Algorithm B records the list of triples. Eventually A halts with an output (M, M′) = (m_{1} ⋯ m_{a}, m′_{1} ⋯ m′_{b}).

Have B compute H(M) and H(M′). According to our conventions, all of the necessary queries for B to use in this computation are already recorded in B’s list of triples, so no new oracle calls are needed to compute H(M) and H(M′).

Initialization:

for all (k, x) ∈ {0, 1}^{n} × {0, 1}^{n} do E(k, x) ← undefined

bad ← false; m_{1}, …, m_{ℓ−1} ←^{$} {0, 1}^{n}

for i ← 1 to ℓ − 1 do if E(h_{i−1}, m_{i}) = undefined then E(h_{i−1}, m_{i}) ←^{$} \overline{Range}(E(h_{i−1}, ·)) h_{i} ← E(h_{i−1}, m_{i}) ⊕ m_{i}

σ ←^{$} {0, 1}^{n}; m_{ℓ} ←^{$} {0, 1}^{n}

if E(h_{ℓ−1}, m_{ℓ}) ≠ undefined then bad ← true [output previously determined] if Game2 then σ ← E(h_{ℓ−1}, m_{ℓ}) ⊕ m_{ℓ}

if there is an i ∈ [1..ℓ − 1] where E(h_{i−1}, m_{i}) = σ ⊕ m_{ℓ} then bad ← true [output uniform over reduced set] if Game2 then σ ←^{$} \overline{Range}(E(h_{i−1}, ·))

h_{ℓ} ← E(h_{ℓ−1}, m_{ℓ}) ← σ ⊕ m_{ℓ}

Adversarial execution:

Run A^{?,?}(σ):

• When A asks a query (k, x) to its left oracle:

if E(k, x) = undefined then y ←^{$} \overline{Range}(E(k, ·)), E(k, x) ← y; else y ← E(k, x) return y to A.

• When A asks a query (k, y) to its right oracle:

if ∃ z such that E(k, z) = y then x ← z

else x ←^{$} \overline{Domain}(E(k, ·)); E(k, x) ← y;

return x to A.

• Eventually A halts, outputting string M′ = m′_{1}m′_{2} ⋯ m′_{ℓ′} Testing:

for i = 1 to ℓ′ do h_{i} ← E(h_{i−1}, m′_{i}) ⊕ m′_{i} if h_{ℓ′} = σ then return 1 else return 0

Figure 7: Definition of Game 1 (when Game2 = false) and Game 2 (when Game2 = true).

Adversary B inspects its list of triples to see if there exists distinct (x, k, y) and (x′, k′, y′). If so, B outputs this pair of points. Otherwise, B inspects its list of triples to see if there exists a triple (x, k, h_{0}). If so, B outputs (k, x), (k, x).

We claim that B succeeds whenever A succeeds. By symmetry, we can assume without loss of generality that a ≥ b. If H(M) = H(M′), then h_{a} = f(h_{a−1}, m_{a}) = f(h′_{b−1}, m′_{b}) = h′_{b}. (Primed variables are understood to be associated to H(M′).) If h_{a−1} ≠ h′_{b−1}, or m_{a} ≠ m′_{b}, then we is done. Otherwise, h_{a−1} = f(h_{a−2}, m_{a−1}) = f(h′_{b−2}, m′_{b−1}) = h′_{b−1}. Again, if h_{a−2} ≠ h′_{b−2} or m_{a−1} ≠ m_{b−1}, then we are done. Proceeding in this way, we must find some values α ∈ [1, a] and β ∈ [1, b] such that either h_{α} = f(h_{α−1}, m_{α}) = f(h′_{β−1}, m′_{β}) = h′_{β}, or h_{α} = h_{0}.

C.2 Proof of Claim 4.2

Suppose that the adversary A outputs colliding messages M = m_{1} ⋯ m_{a} and M′ = m′_{1} ⋯ m′_{b}; that is, H^{E}(M) = H^{E}(M′) for the simulated oracle E. We show that, necessarily, there are two colliding paths.

Let P = (x_{1}, k_{1}, y_{1}) → ⋯ → (x_{a}, k_{a}, y_{a}) where, for each i ∈ [1..a], x_{i} = m_{i}, k_{i} = h_{i−1} ⊕ x_{i}, y_{i} = E_{k_{i}}(x_{i}), and h_{i} = y_{i} ⊕ v. (Recall that h_{0} and v are fixed constants.) Similarly, let P′ = (x′_{1}, k′_{1}, y′_{1}) → ⋯ → (x′_{b}, k′_{b}, y′_{b}) where, for each i ∈ [1..b], x′_{i} = m′_{i}, k′_{i} = h′_{i−1} ⊕ x′_{i}, y′_{i} = E_{k_{i}}(x′_{i}), and h′_{i} = y′_{i} ⊕ v, and where h′_{0} = h_{0}. We claim that P and P′ are colliding paths.

According to our conventions, A makes all of the queries necessary to compute H(M) and H(M′). So, for each i ∈ [1..a], A must have made either an E-query (k_{i}, x_{i}) or an E^{−1}-query (k_{i}, y_{i}). Similarly, for each i ∈ [1..b], A must have made either an E-query (k′_{i}, x′_{i}) or an E^{−1}-query (k′_{i}, y′_{i}). We can conclude then that P and P′ are colored. Moreover, x_{1} ⊕ k_{1} = h_{0} and x′_{1} ⊕ k′_{1} = h′_{0} so each of P and P′ starts with a red node.

If a ≠ b, then clearly P and P′ are distinct. Consider a = b and M ≠ M′. (If M = M′, then M and M′ do not collide.) There is some i ∈ [1..a] such that m_{i} ≠ m′_{i}, and so (x_{i}, k_{i}, y_{i}) ≠ (x′_{i}, k′_{i}, y′_{i}).

Finally, if M and M′ collide we have h_{a} = h′_{b}, and hence y_{a} = y′_{b}. This completes the proof of the Claim.

C.3 Proof of Claim 4.3

Let C_{i} be the event that C occurs by the i-th query. Define C_{0} be the null event. Then Pr[C] = ∑_{i=1}^{q} Pr[C_{i}|\overline{C}_{i−1} ∧ … ∧ \overline{C}_{0}]. Given \overline{C}_{i−1} ∧ … ∧ \overline{C}_{0}, the event C_{i} occurs in one of four ways. To make the discussion of these cases more clear, we define a little more notation. Let Arc(i, j) be the event that there exists in G vertices (x_{i}, k_{i}, y_{i}) and (x_{j}, k_{j}, y_{j}), and y_{i} ⊕ v = x_{j} ⊕ k_{j}. Let Red(i) be the event that there exists in G vertex (x_{i}, k_{i}, y_{i}) and x_{i} ⊕ k_{i} = h_{0}. Let Collide(i, j) be the event that there exists in G vertices (x_{i}, k_{i}, y_{i}) and (x_{j}, k_{j}, y_{j}), and y_{i} = y_{j}.

Case 1: A vertex (x_{i}, k_{i}, y_{i}) is colored on the i-th query, and there exists in G arcs (x_{r}, k_{r}, y_{r}) → (x_{i}, k_{i}, y_{i}) and (x_{i}, k_{i}, y_{i}) → (x_{j}, k_{j}, y_{j}), where (x_{r}, k_{r}, y_{r}) and (x_{j}, k_{j}, y_{j}) were colored on the r-th and j-th queries, r, j < i, respectively.

This event requires Arc(r, i) ∧ Arc(i, j) be true. If C_{i} occurs via an E-query (k_{i}, x_{i}), then y_{i} is a random value from a set of size at least 2^{n} − (i − 1). Then

Pr[Arc(r, i) ∧ Arc(i, j)] = Pr[Arc(i, j)|Arc(r, i)] Pr[Arc(r, i)]
≤ Pr[Arc(i, j)|Arc(r, i)] ≤ \frac{i − 1}{2^{n} − (i − 1)}

Alternatively, if C_{i} occurs in this case via an E^{−1}-query (k_{i}, y_{i}), then x_{i} is a random value from a set of size at least 2^{n} − (i − 1). Then

Pr[Arc(i, j) ∧ Arc(r, i)] = Pr[Arc(r, i)|Arc(i, j)] Pr[Arc(i, j)]
≤ Pr[Arc(r, i)|Arc(i, j)] ≤ \frac{i − 1}{2^{n} − (i − 1)} .

Case 2: A vertex (x_{i}, k_{i}, y_{i}) is colored red on the i-th query, and there exists in G an arc (x_{i}, k_{i}, y_{i}) → (x_{j}, k_{j}, y_{j}), where (x_{j}, k_{j}, y_{j}) was colored on the j-th query, j < i.

This event requires that Arc(i, j) and Red(i). If this occurs via an E-query (k_{i}, x_{i}), then y_{i} is a random value from a set of size at least 2^{n} − (i − 1). Then

Pr[Arc(i, j) ∧ Red(i)] = Pr[Arc(i, j)|Red(i)] Pr[Red(i)]
≤ Pr[Arc(i, j)|Red(i)] ≤ \frac{i − 1}{2^{n} − (i − 1)} .

Alternatively, if C_{i} occurs in this case via an E^{−1}-query (k_{i}, y_{i}), then x_{i} is a random value from a set of size at least 2^{n} − (i − 1). Then

Pr[Arc(i, j) ∧ Red(i)] = Pr[Red(i)|Arc(i, j)] Pr[Arc(i, j)]
≤ Pr[Red(i)|Arc(i, j)] ≤ \frac{i − 1}{2^{n} − (i − 1)} .

Case 3: A vertex (x_{i}, k_{i}, y_{i}) is colored on the i-th query, and there exists in G an arc (x_{j}, k_{j}, y_{j}) → (x_{i}, k_{i}, y_{i}) and a vertex (x_{r}, k_{r}, y_{r}), where (x_{j}, k_{j}, y_{j}) and (x_{r}, k_{r}, y_{r}) were colored on the j-th and r-th queries, r, j < i, respectively, and (x_{i}, k_{i}, y_{i}) agrees with (x_{r}, k_{r}, y_{r}).

This event requires that Arc(j, i) and Collide(i, r). If this occurs via an E-query (k_{i}, x_{i}), then y_{i} is a random value from a set of size at least 2^{n} − (i − 1). Then

Pr[Arc(j, i) ∧ Collide(i, r)] = Pr[Collide(i, r)|Arc(j, i)] Pr[Arc(j, i)]
≤ Pr[Collide(i, r)|Arc(j, i)] ≤ \frac{i − 1}{2^{n} − (i − 1)} .

Alternatively, if C_{i} occurs in this case via an E^{−1}-query (k_{i}, y_{i}), then x_{i} is a random value from a set of size at least 2^{n} − (i − 1). Then

Pr[Arc(j, i) ∧ Collide(i, r)] = Pr[Arc(j, i)|Collide(i, r)] Pr[Collide(i, r)]
≤ Pr[Arc(j, i)|Collide(i, r)] ≤ = \frac{i − 1}{2^{n} − (i − 1)} .

Case 4: A vertex (x_{i}, k_{i}, y_{i}) is colored red on the i-th query, and there exists in G an arc (x_{i}, k_{i}, y_{i}) → (x_{i}, k_{i}, y_{i}).

This event requires that Red(i) ∧ Arc(i, i) is true. If this occurs via an E-query (k_{i}, x_{i}), then y_{i} is a random value from a set of size at least 2^{n} − (i − 1). Then

Pr[Red(i) ∧ Arc(i, i)] = Pr[Arc(i, i)|Red(i)] Pr[Red(i)]
≤ Pr[Arc(i, i)|Red(i)] ≤ \frac{1}{2^{n} − (i − 1)} .

Alternatively, if C_{i} occurs via an E^{−1}-query (k_{i}, y_{i}), then x_{i} is a random value from a set of size at least 2^{n} − (i − 1). Then

Pr[Red(i) ∧ Arc(i, i)] = Pr[Red(i)|Arc(i, i)] Pr[Arc(i,])
≤ Pr[Red(i)] ≤ \frac{1}{2^{n} − (i − 1)} .

Combining all cases, we have

Pr[C] ≤ ∑_{i=1}^{q} \frac{3(i − 1)}{2^{n} − (i − 1)} + \frac{1}{2^{n} − (i − 1)} ≤ 3 ∑_{i=1}^{q} \frac{i}{2^{n} − (i − 1)} ≤ \frac{3q(q + 1)}{2^{n}}

C.4 Proof of Lemma 5.2

Before beginning the proof we sketch the ideas involved. The basic idea is to lower-bound the probability that two distinct input blocks m_{1} and m_{2} will collide under the function π(m) ⊕ m (ie, π(m_{1}) ⊕ m_{1} will equal π(m_{2}) ⊕ m_{2}) where π is a random permutation. The straightforward approach is to write out an experiment where we let the message blocks be 0, 1, 2, … written as n-bit strings, and then incrementally fill-in the permutation π by choosing range values which observe the permutivity requirements on π (cf. SimulateOracles(·, ·)). Then one would hope to count up the minimum number of collisions in π(m_{i}) ⊕ m_{i} for each i ∈ [1..q]. If this worked, it would provide a straightforward solution to our problem, but unfortunately there is a technical problem where the pool of consumed range points might have a nonempty intersection with the collection of points which would cause a collision, thereby lowering the chance of a collision (because some collision-causing values cannot be chosen as our next range point).

This difficulty greatly increases the complexity of the proof. So instead of the above approach we do the following: instead of choosing the one-block messages 0, 1, 2, …, we choose random input blocks, and then lower-bound the probability that at least half of these inputs will not cause the problem mentioned above. We then restrict our attention to these inputs and use a straightforward counting argument to obtain a lower bound for them, yielding an overall lower bound.

In order to make the following argument more digestible, we extract some of the key steps into four lemmas, which are stated and proven first. Then we present the proof of the main lemma, using the prior four.

Lemma C.1 Let r be a positive even integer and let E_{1}, ⋯, E_{r} be r independent events where Pr[E_{i}] ≥ 1/2 for all i ∈ [1..r]. Let H be the event that at least r/2 of the events E_{1}, ⋯, E_{r} occur. Then Pr[H] ≥ 1/2. ◇

Lemma C.2 Let D and E be events with Pr[D | E] ≤ p and Pr[E] ≥ 1/2. Then Pr[D] ≤ (p + 1)/2. ◇

Proof of Lemma C.2: Let h = Pr[E]. We have

Pr[D] = Pr[D | E] Pr[E] + Pr[D | \overline{E}] Pr[\overline{E}] ≤ ph + (1 − h) = 1 + h(p − 1).

And since h ≥ 1/2 and (p − 1) is nonpositive, we know that h(p − 1) is maximized for h = 1/2. Therefore 1 + h(p − 1) ≤ 1 + (p − 1)/2 = (p + 1)/2.

Lemma C.3 Fix positive integers N and q ≤ \sqrt{2N} with q even. Define a function t: [0..q − 1] × {0, 1} → ℝ as

t(i, j) = \{ \begin{matrix}\frac{N−2i}{N−i} & if j = 1 \\ 1 & if j = 0 \end{matrix}

For any binary sequence J = (j_{0}, j_{1}, ⋯, j_{q−1}) in {0, 1}^{q}, define a function T: {0, 1}^{q} → ℝ as T (J) = ∏_{i=0}^{q−1} t(i, j_{i}). Then T (J) is maximum for J = (j_{0}, ⋯, j_{q−1}) where j_{i} = 1 for i ∈ [0..q/2 − 1] and j_{i} = 0 when i ∈ [q/2..q − 1]. Furthermore T (J) ≤ 1 − 0.079q(q − 2)/N. ◇ Proof of Lemma C.3: The lemma states that if we write out the product

\frac{N}{N} · \frac{N − 2}{N − 1} · \frac{N − 4}{N − 2} ⋯ \frac{N − 2q + 2}{N − q + 1}

and we then would like to maximize the product after eliminating exactly half of the terms listed, we should eliminate the right-most half. This follows immediately from the fact that the terms above strictly decrease from left to right. That is, (N − 2a)/(N − a) > (N − 2b)/(N − b) whenever a < b and a, b ∈ [0..q − 1]. Since we must choose exactly q/2 terms to include in our product, choosing any but the first q/2 terms would not maximize the product since we could remove a smaller term and replace it with a larger term, increasing the overall product.

To obtain the upper bound stated in the last sentence of the lemma, we use the fact that for x ∈ [0, 1] we have e^{−x} ≥ 1 − x and (1 − 1/e)x ≤ 1 − e^{−x}. Let T = ∏_{i=0}^{q/2−1}(N − 2i)/(N − i), which we have already shown to be the maximum value of T (J). Using the first fact above we have that

T ≤ ∏_{i=0}^{q/2−1} e^{−i/(N−i)} ≤ ∏_{i=0}^{q/2−1} e^{−i/N} = e^{− ∑_{i=0}^{q/2−1} i/N} = e^{−q(q−2)/8N}.

Using the second fact above along with the fact that q ≤ \sqrt{2N} gives us that

e^{−q(q−2)/8N} ≤ 1 − (1 − \frac{1}{e}) \frac{q(q − 2)}{8N} ≤ 1 − \frac{0.079q(q − 1)}{N}.

This completes the proof.

Lemma C.4 Fix integers n > 0 and i > 0 with i ≤ 2^{(n−1)/2}. Let U = [0..2^{n} − 1]. Let A = {a_{1}, ⋯, a_{i}} and X = {x_{1}, ⋯, x_{i}} be any subsets of U each with i elements. Let B = {a_{k} ⊕ x_{k}: k ∈ [1..i]} = {b_{1}, ⋯, b_{m}}, where m ≤ k. Finally, let C = {a_{j} ⊕ b_{k} : j ∈ [1..i], k ∈ [1..m]}. Then

Pr_{x ∈ U\X}[x ∈ C] ≤ 1/2. ♢

Proof of Lemma C.4: Since each b_{k} is formed by a_{k} ⊕ x_{k} with k ∈ [1..i], we know there are at most i^{2} possible values in C. Now say b_{k} is formed by a_{k} ⊕ x_{k} with k ∈ [1..i]; notice that any value in C formed by a_{k} ⊕ b_{k} = a_{k} ⊕ (a_{k} ⊕ x_{k}) = x_{k} will not be hit by x since x_{k} ∉ U\X. Therefore we may bound the probability above by noticing that there are at most i^{2} − i values of x which might be contained in C. This gives us the bound

\frac{i^{2} − i}{|U\X|} = \frac{i^{2} − i}{2^{n} − i} ≤ \frac{2^{n−1} − 2^{(n−1)/2}}{2^{n} − 2^{(n−1)/2}}

where the last step follows from the fact that i ≤ 2^{(n−1)/2}. Next we cancel above and below by 2^{(n−1)/2} and use the fact that (a − 1)/(b − 1) < a/b, whenever a and b are positive with a < b, to obtain

\frac{2^{n−1} − 2^{(n−1)/2}}{2^{n} − 2^{(n−1)/2}} = \frac{2^{(n−1)/2} − 1}{2^{(n+1)/2} − 1} < \frac{2^{(n−1)/2}}{2^{(n+1)/2}} = 1/2.

This completes the proof.

Proof of Lemma 5.2: Assume that q is an even integer. We view the contents of π and Q as being incrementally determined during the process of the probabilistic experiment described in the lemma statement. We will view Q as initially empty and π as initially undetermined, and then at each step we will incrementally fill in these values until Q contains q elements and π(x) is determined for every x ∈ Q. Let us state this more precisely. We will let Q_{i} represent the intermediate state of Q at the i-th step, and π_{i} represent the function π at the i-th step. To begin, let Q_{0} be the empty set and let π_{0}(x) = undefined for all x ∈ U, where undefined is some distinguished value indicating that we have not yet determined some range value. When X is a set, we write π(X) to mean the set of values {π(x) : x ∈ X}.

At the i-th step of our procedure, 0 < i ≤ q, we choose a random x_{i} ∈ U\Q_{i−1} and set Q_{i} = Q_{i−1} ∪ {x_{i}}. Then we choose a random a_{i} ∈ U\π_{i−1}(Q_{i−1}) and define π_{i} as π_{i−1} with the modification that π_{i}(x_{i}) = a_{i}. At the end of this procedure we have that Q = Q_{q} is a cardinality q subset of P_{q}({0, 1}^{n}) and that π_{q} is a permutation on the points Q, as required.

For any i ∈ [1..q], define B_{i} = {π_{i}(x_{i}) ⊕ x_{i} : x_{i} ∈ Q_{i}}. So B_{i} is the set of hash function outputs we are concerned with here: we wish to bound the probability that no collisions will occur among the elements of B_{i}. However, as we shall see shortly, a difficulty arises if, during the (i + 1)-st step, any elements in B_{i} and π_{i}(Q_{i}) XOR to x_{i+1}. We avoid this difficulty by conditioning on the event that this does not happen. For notational convenience, define the Boolean function bad(π_{i}(Q_{i}), B_{i}, x_{i+1}) to be true if there exists a value a ∈ π_{i}(Q_{i}) and b ∈ B_{i} such that a ⊕ b = x_{i+1}. Let’s now bound the probability that bad(π_{i}(Q_{i}), B_{i}, x_{i+1}) is true when choosing x_{i+1}.

Let \overline{E_{i}} be the event that bad(π_{i−1}(Q_{i−1}), B_{i−1}, x_{i}) is true, and suppose we are at step i of our procedure. But we are precisely in the setting of Lemma C.4, which tells us that Pr[\overline{E_{i}}] ≤ 1/2, and therefore Pr[E_{i}] ≥ 1/2. Since this is true for all i ∈ [1..q], we have q events, each with probability 1/2. Let event H denote the event that at least half of the E_{i} occur; we may invoke Lemma C.1 to see that Pr[H] ≥ 1/2. Henceforth we condition on this event so that we may assume there exists a set of q/2 indices I = {i_{1}, ⋯, i_{q/2}} such that bad(π_{i_{j}−1}(Q_{i_{j}−1}), B_{i_{j}−1}, x_{i_{j}}) is false for all i_{j} ∈ I.

We now focus on these values x_{i_{j}} for i_{j} ∈ I for which our bad function is false. We will upper-bound the probability of a lack of collision on just these inputs to π by counting up the number of ways a choice of x_{i_{j}} could cause a collision in π(·) ⊕ (·). The probability of no collision when x_{i_{j}} was chosen, given none had occurred so far, is now simple to compute: there were 2^{n} − 2i_{j} values which would not cause a collision when x_{i_{j}} was chosen from a pool of 2^{n} − i_{j} values. And we know the intersection between these sets is empty because we have assumed that bad(π_{i_{j}−1}(Q_{i_{j}−1}), B_{i_{j}−1}, x_{i_{j}}) was false. Therefore, the probability is simply (2^{n} − 2i_{j})/(2^{n} − i_{j}).

We wish to upper-bound the overall probability that no collisions occur for Q under π(·) ⊕ (·). Let D_{i} be the event that no collision occurred in the i-th step of our experiment above. We therefore need to upper-bound Pr[D_{q}]. Let us first upper-bound Pr[D_{q} | H]. We know

Pr[D_{q} | H] = Pr[D_{q} | D_{q−1} ∧ H] ⋯ Pr[D_{1} | H]

and the i-th term in the expansion is bounded either by (2^{n}−2i)/(2^{n}−i) or 1 depending on whether or not i ∈ I. Since we wish an upper bound, Lemma C.3 tells us we may maximize the above by taking I = {0, ⋯, q/2 − 1}. It further tells us that the maximum value attained by Pr[D_{q} | H] will be at most 1 − 0.079q(q − 2)/2^{n}. And since Pr[H] ≥ 1/2 we may now bound Pr[D_{q}] by invoking Lemma C.2 to see

Pr[D_{q}] ≤ \frac{(1 − .079q(q − 2)/2^{n}) + 1}{2} ≤ 1 − .039\frac{q(q − 2)}{2^{n}}.

Finally, we note that the probability of having a collision is at least one minus the above quantity, thus

Pr[\overline{D}_{q}] ≥ .039\frac{q(q − 2)}{2^{n}}.

This completes the proof.

C.5 Proof of Theorem 5.3

Consider H_{5}^{E} and fix a constant h_{0} ∈ {0, 1}^{n}. The total number of queries, q, is given. We construct adversary A, which has oracles E, E^{−1}, as follows. Let A compute y_{i} = E_{i}(h_{0}) ⊕ h_{0}, i ∈ [1..q]. (Where necessary, regard i as an n-bit string.) If A finds i, j ∈ [1..q] such that y_{i} = y_{j} it returns (m_{i}, m_{j}). If A is unable to find such an i then it returns (m_{1}, m_{1}) (failure).

We now analyze A so constructed. Notice that y_{i} is a random value for each i ∈ [1..q]. Let p be the probability that there is at least an i and a j such that 1 ≤ j < i ≤ q and either y_{i} = y_{j}, or that there is an i ∈ [1..q] such that y_{i} = h_{0}. We wish to upperbound p. To do this we examine the complementary quantity 1 − p. Specifically, we define D_{i}, i ∈ [1, …, q] be the event that there does not exist an 1 ≤ j < i such that y_{i} = y_{j}. Note that Pr[D_{1}] = 1, and that if D_{i} occurs then y_{1}, …, y_{i} are distinct. Then we have

Pr[D_{i+1}|D_{i}] = \frac{2^{n} − i}{2^{n}} = 1 − \frac{i}{2^{n}} .

The probability of no collisions after the qth hash is

1 − p = Pr[D_{q}] = ∏_{i=1}^{q−1} Pr[D_{i+1}|D_{i}] = ∏_{i=1}^{q−1} (1 − \frac{i}{2^{n}} )

We note that i/2^{n} ≤ 1, and use the inequality 1 − z ≤ e^{−z} for all 0 ≤ z ≤ 1 for each term in the product, so that

1 − p ≤ ∏_{i=1}^{q−1} e^{−i/2^{n}} = e^{−q(q−1)/2^{n+1}}.

Since q ≤ 2^{n/2} we know that q(q − 1)/2^{n+1} ≤ 1. Using the fact that 1 − e^{−z} ≥ (1 − e^{−1})z for all 0 ≤ z ≤ 1, we obtain after rearranging

p ≥ (1 − \frac{1}{e}) · \frac{q(q − 1)}{2^{n+1}}.

This attack and analysis extends to the remaining schemes in H_{5..20} because in each case the block cipher key in the first compression function call is either m or m ⊕ h_{0} where h_{0} is a constant. For example, to prove the bound for H_{6}, the adversary A computes y_{i} = E_{i}(h_{0} ⊕ i) ⊕ h_{0} ⊕ i for i ∈ [1..q] and returns values as described in the attack for H_{5}^{E}. The remaining schemes are handled analogously.

Let A be an adversary for H: adversary A takes oracles E, E^{−1} and an input σ and, when successful, it outputs M such that H^{E}(M) = σ. We construct an adversary B for f: adversary B takes oracles E, E^{−1} and an input σ and, when successful, it outputs (h, m) such that f^{E}(h, m) = σ. Adversary B works as follows. It runs A on σ. When A makes an E (resp., E^{−1}) query, adversary B forwards the query to its E (resp., E^{−1}) oracle and returns to A the result. During this process, for each i ∈ [1..q], we say that the ith triple is (x_{i}, k_{i}, y_{i}) if A’s ith oracle query was an E-query of (k_{i}, x_{i}) and this returned y_{i}, or else A’s ith oracle query was an E^{−1}-query (k_{i}, y_{i}) and this returned x_{i}. Adversary B records the list of triples. Eventually A halts with an output M = m_{1} ⋯ m_{a}. At that point we have B compute H^{E}(M): for i ← 1 to a set h_{i} ← f^{E}(h_{i−1}, m_{i}). According to our conventions, all of the necessary E_{k}(x) values that B needs will already be in B’s list of triples—no new oracle calls are needed to compute H^{E}(M). Now if h_{a} = f^{E}(h_{a−1}, m_{a}) = σ then B outputs (h_{a−1}, m_{a}) and wins its experiment; otherwise it outputs (h_{0}, m_{1}) and does not win. Clearly B succeeds whenever A succeeds.

C.7 Proof of Theorem 6.4

Consider the case of H^{E} = H_{13}^{E}. Fix constants h_{0}, v ∈ {0, 1}^{n}. Let A be an adversary with oracles E, E^{−1} and input σ. Assume that A asks these oracles at most q total queries and then inverts H at σ. Suppose that the inverse provided by A is always a message M with more than two blocks. Then by Lemma 6.5 and Theorem 4.1 we’d have that Adv_{H}^{inv}(q) ≤ 3Adv_{H}^{coll}(q+2)+q/2^{n−1} ≤ 9(q+2)(q+ 3)/2^{n} + q/2^{n−1} ≤ 9(q + 3)^{2}/2^{n}. So suppose instead that the inverse provided by A is always a message M having a single block. Then run ((x_{1}, k_{1}, y_{1}), …, (x_{q}, k_{q}, y_{q}), out) ← SimulateOracles(A, n) and suppose that A returns an m ∈ {0, 1}^{n} such that H(m) = σ then E(h_{0} ⊕ m, m) ⊕ v = σ. By our convention, it must be the case that (m, h_{0} ⊕ m, E(h_{0} ⊕ m, m)) = (x_{i}, k_{i}, y_{i}) for some i ∈ [1..q]. Let C_{i} be the event that (x_{i}, k_{i}, y_{i}) is such that x_{i} ⊕ k_{i} = h_{0} and y_{i} = σ ⊕ v.

In carrying out the simulation of A’s oracles either x_{i} or y_{i} is randomly assigned from a set of at least size 2^{n} − (i − 1), and so Pr[C_{i}] ≤ 1/(2^{n} − (i − 1)). Consequently, Adv_{H[n]}^{inv}(A) ≤ Pr[C_{1} ∨…∨C_{q}] ≤ ∑_{i=1}^{q} Pr[C_{i}] ≤ ∑_{i=1}^{q} \frac{1}{2^{n}−(i−1)} ≤ \frac{q}{2^{n}−2^{n−1}} if q ≤ 2^{n−1}. Continuing, our expression is at most q/2^{n−1}. Since the above inequality is vacuous when q > 2^{n−1}, we may now drop the assumption that q ≤ 2^{n−1}. This bound is inferior to that obtained when M is two or more blocks. The actual advantage of A is a weighted sum of the two advantages computed, which concludes the proof for hash function H_{13}. The remaining cases are similar.

C.8 Proof of Lemma 6.5

Let I be an adversary that attacks H̃ = H̃_{ı}[n] in the inversion-resistance sense and assume that I makes q oracle queries. We construct a collision-finding adversary A for H as follows. Let A select M ←^{$} {0, 1}^{2n} and compute σ = H̃(M). By our assumption that H is rate-1, this requires 2 queries to A’s left oracle, E. Adversary A now runs I on σ. When I makes a query to its left (resp., right) oracle, adversary A forwards the query to its own left (resp., right) oracle, and returns to I the result. When I halts with output M′, adversary A returns (M, M′).

We now analyze the advantage of adversary A. There are at most 2^{n} −1 points σ ∈ {0, 1}^{n} that can have a unique preimage under H̃. Hence there are at least 2^{2n} − 2^{n} + 1 messages M ∈ {0, 1}^{2n} 1. σ ←^{$} {0, 1}^{n}; win ← false; for all x ∈ {0, 1}^{n} do π(x) ← undefined

2. for i = 1 to q do

3. x_{i} ←^{$} {0, 1}^{n}; y_{i} ←^{$} {0, 1}^{n}

4. if π(x_{i}) ≠ undefined then y ← π(x_{i}) [maintain permutivity of π]

5. else if y_{i} ∈ Range(π) then y_{i} ←^{$} \overline{Range}(π) [maintain permutivity of π]

6. π(x_{i}) ← y_{i}

7.  z_{i} ← y_{i} ⊕ x_{i}  [put a ball in bin labeled z]
8.  if z_{i} = σ then win ← true  [win if a ball goes in the desired bin]

Figure 8: Pseudocode for a game equivalent to that played by the adversary in the proof of Theorem 6.6. If win is set to true then the adversary has succeeded in inverting the randomly-chosen range point σ under H_{1}.

that hash to range points having at least two preimages. Let N_{σ} be the number of preimages of σ. Since A has at least a 1/2 chance of inverting H̃ at σ when N_{σ} = 1, we have that

Adv_{H}^{coll}(A) = Pr[M′ ≠ M|N_{σ} ≥ 2] · Pr[N_{σ} ≥ 2] · Advowf ; H̃(I)
≥ \frac{1}{2} · \frac{2^{2n} − 2^{n} + 1}{2^{2n}} · Advowf ; H̃(I)
≥ \frac{3}{8}Adv_{H̃[n]}^{owf}(I)

where the last inequality is true because (2^{2n} − 2^{n} + 1)/2^{2n} is maximized when n = 1. Rearranging terms, we conclude that Advowf ; H̃(q) ≤ 8/3 · Adv_{H}^{coll}(q + 2) ≤ 3Adv_{H}^{coll}(q + 2). By Lemma B.2 we conclude that Advinv ; H̃(q) ≤ 3Adv_{H}^{coll}(q + 2) + q/2^{n−1}.

C.9 Proof of Theorem 6.6

We consider the case of H^{E} = H_{1}^{E}. Fix a constant h_{0} ∈ {0, 1}^{n}. Let q > 0 be given. We construct an adversary A with two oracles E, E^{−1}, taking input σ, which works as follows. First A chooses q random strings m_{1}, …, m_{q} ∈ {0, 1}^{n}. Then for each i ∈ [1..q], the adversary computes y_{i} = H^{E}(m_{i}) = E_{h_{0}}(m_{i}) ⊕ m_{i}. If there is some i ∈ [1..q] such that y_{i} = σ then A outputs m_{i}; otherwise, A outputs m_{1} (failure).

We now analyze the chance that A succeeds. Consider the following game which models exactly the attack used by A against H. Let there be N = 2^{n} bins labeled by strings in {0, 1}^{n}. Choose a permutation π uniformly from the set of all permutations on {0, 1}^{n}. For i ∈ [1..q], select x ←^{$} {0, 1}^{n} and place a ball in the bin labeled by π(x) ⊕ x. Let D(N, q) be the expected number of bins containing at least one ball at the end of this game. Then for a uniformly selected σ in {0, 1}^{n}, the probability that a ball is in the bin labeled by σ at the end of this game is D(N, q)/N. Clearly, the chance that A inverts a uniformly chosen range point under H is exactly this, as well.

We claim that if q ≤ N/4 then D(N, q) ≥ 7q/16. To show this, we consider the pseudocode in Figure 8.

Let us examine statements 2–7 more closely. Since q ≤ N/4, either of the then-clauses in statements 4 or 5 is executed in any particular loop with probability at most 1/4 + 1/4 = 1/2, and so an expected r ≥ q/2 of the values z_{i} are uniform in {0, 1}^{n}. Notice that executing statements 4 or 5 never decreases the number of distinct z_{i}, and so for the purposes of lowerbounding D(N, q) we can consider the simplified code for j = 1 to q/2 do z_{j} ←^{$} {0, 1}^{n} which places q/2 uniform balls into N bins. At the time of the selection of bin z_{j} for ball j there are already at most N/8 bins full. Hence, with probability at least 7/8 ball j goes into an empty bin (labeled z_{j}), and so we expect that at least 7q/16 bins contain a ball. We conclude then that Adv_{H}^{inv}(A) ≥ (7/16) q/2^{n}. The remaining cases H_{2..4} are handled analogously.

C.10 Proof of Theorem 6.7

We consider the case of H^{E} = H_{5}^{E}. Fix a constant h_{0} ∈ {0, 1}^{n}. Let q > 0 be given. We construct an adversary A^{E,E^{−1}}, taking input σ, which works as follows. For each i ∈ [1..q], the adversary computes y_{i} = E_{i}(h_{0}) ⊕ h_{0}, where each i is taken as an n-bit string. If there is some i ∈ [1..q] such that y_{i} = σ then A outputs the string i; otherwise, A outputs the string 1 (failure).

Let D_{i} be the event that y_{j} ≠ σ for all j ∈ [1..i]. According to our block cipher model each y_{i} is an independently random value. Hence Pr[D_{i}] = (1 − 1/2^{n})^{i} for each i ∈ [1..q]. We have then that Adv_{H_{5}[n]}^{inv}(A) = 1−Pr[D_{q}] = 1−(1 − 1/2^{n})^{q} = 1−(1 − 1/2^{n})^{2^{n}q/2^{n}} ≥ 1−e^{−q/2^{n}} ≥ (1−e^{−1})(q/2^{n}) ≥ .6q/2^{n}. where we have used the facts that (1−1/x)^{x} < 1/e for all x > 0 and that 1−e^{−x} ≥ (1−e^{−1})x for all x ∈ [0, 1].

This proof approach works to prove the same bound for each of the schemes H_{5..12} because in each of these the block-cipher key is distinct for each message hashed and therefore induces independent random outputs as required by the analysis above.

C.11 Proof of Theorem 6.8

We consider the case H^{E} = H_{13}^{E}. For simplicity, we further consider the case where h_{0} = 0^{n} (the proof can be easily adapted for other values). We prove the bound by describing and analyzing a meet-in-the-middle attack.

We construct an adversary A with two oracles E, E^{−1} and input σ. Adversary A executes as follows: let A compute y_{i} = E_{i}(i) ⊕ v for i ∈ [1..q/2] (where i is encoded as an n-bit string). Let F = {y_{1}, …, y_{q/2}}. Define a function g : {0, 1}^{n} × {0, 1}^{n} → {0, 1}^{n} by g(k, y) = E_{k}^{−1}(y ⊕ v) ⊕ k. Let A compute the set B = {g(q/2+1, σ), ⋯, g(q, σ)} using q/2 further oracle queries. If A finds a string s ∈ F ∩B, where s = E_{j}(j) ⊕ v = E_{ℓ}^{−1}(σ ⊕ v) ⊕ ℓ for some j ∈ [1 .. q/2] and ℓ ∈ [(q/2+1) .. q], then treating j and ℓ as strings, A outputs the two-block message (j ∥ E_{j}(j) ⊕ v ⊕ ℓ) otherwise it outputs the string 1 (failure). Notice that if s does exist in F ∩ B that H(j ∥ E_{j}(j) ⊕ v ⊕ ℓ) = σ.

We now analyze the probability that A will succeed by giving a lower-bound on the probability that F ∩ B will be non-empty. Notice that while A runs, the keys for each invocation of E are distinct. This means that in our model the values in sets F and B are uniform independent n-bit strings. Therefore we need only lower-bound the probability that throwing q/2 blue balls and q/2 red balls randomly into 2^{n} bins results in a red-blue collision.

Let C denote the event that after throwing all q balls we have a bin containing at least two balls (regardless of color). Let C_{M} denote the event that there are only monochromatic collisions after throwing q balls (in other words, C_{M} denotes the event that C has occurred but for any pair of balls sharing a bin, they are either both blue or both red). Finally, let C_{B} denote a bichromatic collision (ie, the event that there is some red ball and some blue ball sharing the same bin). So C is the disjoint union of C_{M} and C_{B}, or Pr[C] = Pr[C_{M}] + Pr[C_{B}].

Next we claim that for any even q > 1 we have Pr[C_{B}] > Pr[C_{M}]. This claim is justified by a straightforward combinatorial argument: consider any configuration of q uncolored balls lying in 2^{n} bins where two balls share a bin. If we color these two balls blue, then there are \binom{q−2}{q/2−2} ways to color the remaining balls. However, if we color one ball red and the other blue, there are \binom{q−2}{q/2−1} ways to color the remaining balls. The latter number is larger than the former since (q/2 − 2)!(q/2)! > (q/2 − 1)!(q/2 − 1)!. This immediately implies our claim.

Since q ≤ 2^{n/2} we know Pr[C] ≥ .3q^{2}/2^{n} (for a proof see, for example, Appendix A of [1]). Therefore Pr[C_{B}] > Pr[C_{M}] implies Pr[C_{B}] > .15q^{2}/2^{n}, completing the proof.

Since the function g used in the proof above can be extracted from each scheme H_{13..20} by examining the corresponding round function f_{13..20}, and since the above proof did not depend on the actual definition of g, we can extend the attack and analysis above to each of these schemes, obtaining the same bound.