How is the MJH double-block-length hash function constructed?

Question

I'm looking for information on the MJH double-block-length hash function, but the best free source I could find is the diagram on page 18 of Efficient hashing using the AES Instruction Set (submitted to the ECRYPT II Hash Workshop 2011).

Is source code available for this function? What are the standard symbols used (M, V, Z) when describing hash functions?

Answer 1

I had a look at the paper introducing the MJH construction (MJH: A Faster Alternative to MDC-2).

It actually presents a different diagram than the one in the paper Efficient hashing using the AES Instruction Set your referenced – there $V_2$ and $M$ are swapped. I'll describe the original one here, and the variation below.

The core of MJH is a compression function, using a similar construction like the JH hash function (one of the SHA-3 finalists), hence the name.

The JH construction

Given a (non-compressing) function $F : \{ 0,1\}^{2n} \to \{0,1\}^{2n}$, we define the compression function $JH[F] : \{0,1\}^{3n} \to \{0,1\}^{2n}$ as $JH[F](V_1, V_2, M) := (Z_1, Z_2)$, with $(X_1, X_2) = (V_1, V_2 \oplus M)$, $(Y_1, Y_2) = F(X_1, X_2)$ and $(Z_1, Z_2) := (Y_1 \oplus M, Y_2)$.

In the JH hash function, F is a specially-made (fixed) permutation.

MJH's $F[\sigma, \theta]$

Given a $n$-bit-blockcipher $E$ with keysize $k = n$, $\sigma : \{0,1\}^{n} \to \{0,1\}^n$ an involution (i.e. $\sigma \circ \sigma = \mathrm{id}$) without fixed point (i.e. $\sigma(X) \neq X$) – an example would be an XOR with a non-zero constant –, and $\theta \in \mathbb{F}_{2^n} \setminus\{0,1\}$ a constant (so multiplication with $\theta$ is another non-trivial permutation).

We define $F[\sigma, \theta] : \{0,1\}^{2n} \to \{0,1\}^{2n}$ as $F(X, K) = (L, R)$, with $L = E_K(X) \oplus X$ and $R := \theta(E_K(\sigma(X)) \oplus \sigma(X) ) \oplus X$.

(The $E_K(X) \oplus X$ part is essentially the Davies-Meyer construction to make it one-way, even if $K$ is known. It is actually used twice here.)

The final Hash function

Combining these ideas, we get our compression function $\tilde F[\sigma, \theta] := JH[F[\sigma, \theta]] : \{0,1\}^{3n} \to \{0,1\}^{2n}$.

We then apply the known Merkle–Damgård caining construction on this compression function, receiving our final hash function $H[\sigma, \theta] = MD[\tilde F[\sigma, \theta]]$.

(This image is from Wikimedia Commons, the others are made by me.)

In practice we now also have to choose some specific $\sigma$ and $\theta$, a specific block cipher, as well as an initialization vector and padding for MD - the security proof still applies for all of them (if the block cipher is good).

Longer key variant

The paper also describes a variant of the compression function to be used when the key length $k$ is greater than the block size $n$. Then we use message blocks of size $k$, and split these blocks into two parts $z, z'$. $z$ (of size $n$)is used as before to be XOR'ed into the left half of the state before encryption and right half after, while $z'$ (of size $k-n$) is appended to the right half of the state to form the key for the block cipher.

By using a larger (hash) block size, this longer variant can be more efficient than the original one.

The variant depicted in Efficient Hashing

For $n = k$, this is the same compression function as the original one, but it is used in a different way in the MD-construction: Here the message blocks are passed in the key position, instead of being XOR'ed into the parts of the state before and after encryption. (This XOR'ing instead uses one half of the original state.)

This gives a more obvious generalization into the $k \geq n$ case, as we don't have to split the message block and compose the key, but simply can pass the longer key to the block cipher.

I didn't check if the proofs given in the MJH paper also apply to this variant, though, and I don't know which version the authors of Efficient Hashing actually measured.