Davies-Meyer Transform

The Davies-Meyer Transform

Compression hash functions with fixed-length inputs can be constructed from block ciphers using the Davies-Meyer transform. In particular, given a block cipher $(\text{Enc},\text{Dec})$ with key-length $n$ and block length $l$, we can build a compression function $h(\text{input}:\text{str}[\text{fixed }n+l])\to \text{str}[\text{fixed }l]$ as follows:

$$h(x):=\text{Enc}(x[\mathrm{0..}n],x[n..l])\oplus x[n..l]$$

Essentially, we parse the $n+l$-bit string $x$ as a key $k:=x[\mathrm{0..}n]$ of length $n$ and a string $y:=x[n..l]$ of length $l$. The encryption algorithm is invoked on the string $y$ with the key $k$ and the resulting “ciphertext” is then XOR-ed with $y$ to produce the hash of $x$.

In practice, one never uses common block ciphers such as AES when implementing Davies-Meyer functions because these ciphers are designed to be fast when encrypting a long message with the same key. However, when combined within the Merkle-Damgård transform Davies-Meyer functions work with relatively short inputs and keys which change for each input. Additionally, common block ciphers have smaller output lengths than is necessary for most hash functions - AES has 128-bit outputs which is a big no no because birthday attacks will be able to find collisions after only $2^{64}$ tries (something feasible on a modern computer). Therefore, block ciphers used for the implementation of Davies-Meyer functions are specifically designed for this very purpose and have outputs of length 512 or even 1024 bits.

Security

It is unknown how to prove that $h$ is collision resistant solely based on the fact that the block cipher $(\text{Enc},\text{Dec})$ uses a pseudorandom permutation. However, we can prove collision resistance if the block cipher is ideal. This means that the cipher uses a truly random permutation - the only way to know the output of $\text{Enc}$ for a specific $y$ and key $k$ is to actually evaluate $\text{Enc}(k,y)$ because every output is equally likely.

Theorem: Davies-Meyer Collision Resistance

If the Davies-Meyer function $h$ is implemented using an ideal block cipher $(\text{Enc},\text{Dec})$, then the probability that any attacker who queries $(\text{Enc},\text{Dec})$ with $q$ queries can find a collision is at most $\frac{q^2}{2^l}$.

PROOF

Since the cipher is ideal, the function $\text{Enc}$ is a truly random permutation, and, in particular, for every key $k\in \mathcal{K}$ the function ${\text{Enc}}_k$ is also a truly random permutation (contrast this to the case of pseudorandom permutations, where this holds true only if the key is uniformly chosen).

The attacker is given oracle access to $(\text{Enc},\text{Dec})$ and tries to find two strings $x\ne x^{\prime }$ such that $h(x)=h(x^{\prime })$. After parsing these strings as $(k,y)$ and $(k^{\prime },y^{\prime })$, the adversary’s goal reduces to finding $(k,y)$ and $(k^{\prime },y^{\prime })$ such that $\text{Enc}(k,y)\oplus y=\text{Enc}(k^{\prime },y^{\prime })\oplus y^{\prime }$.

We assume that the adversary is “smart” in the sense that they never make the same query twice (otherwise they would just be wasting their own time) and that they never query $\text{Dec}$ with a ciphertext whose plaintext they already know, lest they again waste their own time.

Consider the adversary’s $i$-th query. A query to $\text{Enc}(k_i,y_i)$ reveals only the hash $h_i=h(x_i)=h(k_i||y_i)=\text{Enc}(k_i,y_i)\oplus y_i$. Similarly, a query to $\text{Dec}(k_i^{\prime },y_i^{\prime })$, will only reveal the hash $h_i=h(x_i^{\prime })=h(k_i^{\prime }||y_i^{\prime })=y_i\oplus \text{Dec}(k_i,y^{\prime })$. A collision only occurs if $h_i=h_j$ for some $i\ne j$.

Fix $i,j$ with $i>j$. When making the $i$-th query, the value of $h_j$ is already known, since it was obtained in a previous query. A collision occurs only if the adversary queries $\text{Enc}(k_i,y_i)$ and obtains $\text{Enc}(k_i,y_i)=h_j\oplus y_i$ or they query $\text{Dec}(k_i^{\prime },y_i^{\prime })$ and obtain $\text{Dec}(k_i^{\prime },y_i^{\prime })=h_j\oplus y_i^{\prime }$. Each event occurs with probability at most

$$\frac{1}{2^l-(i-1)}$$

This is true because the adversary has already made $i-1$ queries and has therefore made at most $i-1$ previous queries with the same key $k_i$. Since they are not repeating queries, there are (at most) $i-1$ fewer possible inputs the adversary can use for $y_i$. The probability of a collision at the $i$-th step is then the probability that the adversary makes an encryption query and obtains a collision or they make a decryption query and obtain a collision, i.e.

$$\mathrm{Pr}[{\text{Coll}}_{ij}]=\frac{2}{2^l-(i-1)}$$

Since $i\le q<2^{l/2}$ (comparing with the birthday attack), $i$ can be at most $2^{l/2}$ and for sufficiently large $l$, we have $2^l\gg 2^{l/2}$ which gives

$$\mathrm{Pr}[{\text{Coll}}_{ij}]\le \frac{2}{2^l}$$

The probability of a collision in $q$ queries can be expressed as

$$\mathrm{Pr}[{\text{Coll}}_q]=\mathrm{Pr}\left[\bigcup _{j<i\le q}{\text{Coll}}_{ij}\right]$$

By the union bound, we obtain

$$\mathrm{Pr}[{\text{Coll}}_q]\le \sum _{j<i\le q}\mathrm{Pr}[{\text{Coll}}_{ij}]$$

The number of distinct pairs $i,j$ which satisfy $j<i\le q$ is exactly $\left(\genfrac{}{}{0ex}{}{q}{2}\right)$ which is upper bounded by $\frac{q^2}{2}$. Ultimately, we have that

$$\mathrm{Pr}[{\text{Coll}}_q]\le \sum _{j<i\le q}\mathrm{Pr}[{\text{Coll}}_{ij}]\le \frac{q^2}{2}\mathrm{Pr}[{\text{Coll}}_{ij}]=\frac{q^2}{2^l}$$