How can a collision be generated in this hash function by inverting the encryption?

Question

This is from Joan Daemen's Doctoral thesis

Per page 64 (or PDF page 79)

4.7.1 Our approach

Our goal is the design of simple and portable unkeyed and keyed cryptographic hash functions that are hermetic.The basic principle of our approach is derived from the compression function of an early version of MD4. The operation of this compression function can be described as encrypting in an invertible way the 128-bit chaining state $d^{i−1}$ to $d^i$ with $m^i$ as a key,or

(4.4): $d^i = f_{MD4}(d^{i−1}, m^i)$

In a later version this compression function was modified by adding $d^{i−1}$ to the "encryption result" :

(4.5): $d^i = d^{i−1} + f_{MD4}(d^{i−1}, m^i) \bmod 2^{128}$

It can be seen that for the compression function (4.4) collisions can be generated by simply inverting the encryption

2 Questions

1. What does hermetic mean in this context?

2. How exactly can you generate a collision by inverting the encryption?

Answer 1

4.4

Merkle–Damgård construction requires a one-way compression function and the common way is to use a block cipher. If you initiate with the simple way;

$$d^i = f_{MD4}(d^{i−1}, m^i)$$ then the message is the key.

Now, consider that we want to find a collision. Take an arbitrary $h$ as the output of the hash function, take two arbitrary but different message blocks $m^2_1$ and $m^2_2$, and decrypts the $h$ for each;

$$ m_1^1 = f_{MD4}^{-1}(h, m_1^2)$$

$$ m_2^1 = f_{MD4}^{-1}(h, m_2^2)$$

Since we used a block-cipher and that is a permutation and each key is select a different permutation from all possible permutations we expect that $m_1^1 \neq m_2^1$ with high probability. Then we find two inputs that have the same hash value. Note that we can find meaningful messages with this approach. If the $m_1^1 = m_2^1$ the choose another $h$ value to begin.

4.5

$$d^i = d^{i−1} + f_{MD4}(d^{i−1}, m^i) \bmod 2^{128}$$

This is the Davies-Mayer construction and its security is proven under the ideal cipher model. SHA-1 and SHA-2 are using this construction.

This construction has a problem with the block cipher, too that one can find a fixed point; that is $h = E(h,m)$ by setting $h=0$. There is no practical attack on this, though.

Block ciphers can have related keys that don't make a problem during the encryption since we are expected to select uniformly random keys. In the hash function, though, this makes a problem and therefore we use a special block cipher for those like SHACAL-1 for SHA-1 and SHACAL-2 for SHA-2 series.

---

Ideal-cipher model: Consider the set $\mathcal{B}$ as all possible $k$-bit key and $n$-bit block-sized block-ciphers. Then, in the Ideal-cipher model, a block-cipher $E \stackrel{R}{\leftarrow}\mathcal{B}$ is being chosen uniformly from $\mathcal{B}$. For each key, there are $2^n!$ permutations. Each key defines a permutation therefore there are ${2^n!}^{2^k}$ possible block ciphers. When we instantiate our black box, it becomes some particular block-cipher. Consider the AES-128 is one choose from $2^{2^263}$ that one can choose. Note that in 2005 Black showed that "a blockcipher-based hash function that is provably-secure in the ideal-cipher model but trivially insecure when instantiated by any blockcipher".

Answer 2

What does hermetic mean in this context?

As per section 3.5.5 of the paper (which goes into further detail):

Definition 3.4
A cryptographic scheme is hermetic with respect to some application if it does not have weaknesses that are exploitable in that application and are not present for the majority of corresponding super cryptographic schemes.
Definition 3.5
A cryptographic scheme is hermetic if it is hermetic with respect to all conceivable applications.

Informally,a cipher or hash function is hermetic if its internal structure cannot be exploited in any application.

I've not seen the term used before myself.

---

How exactly can you generate a collision by inverting the encryption?

Function 4.4 is invertible. So in order to create an input, we simply need to take the desired output and run the function in reverse.