Single-block hash construction based on a block cipher with two fixed keys

Question

Let k1, k2 be two arbitrary fixed keys (nothing-up-my-sleeve values like "foo" and "bar") and E_k1 and E_k2 be the corresponding encryption functions of a block cipher. x is a single input value (same value is fed to both E_k1 and E_k2).

Define a hash as follows:

H(x) = E_k1(x) xor E_k2(x)

This hash is meant to be used exclusively for proof-of-work purposes. The input size is assumed to exactly match the block size. There is no significant issue with the risk non-trivial collisions. The construction was intentionally designed to include only encryption operations, not key-scheduling (for optimization reasons). This makes it different than common constructions like Davies–Meyer, Matyas–Meyer–Oseas or Miyaguchi–Preneel.

Wikipedia says:

Black, Cochran and Shrimpton have shown that it is impossible to construct a one-way compression function that makes only one call to a block cipher with a fixed key.

This one uses two fixed keys, so it leaves the option it is good enough.

The underlying cipher is intended to be AES-128 or AES-256.

The question is: do you know of papers that have tried to analyze this type of construction? Can you give some of your own insights?

Edit: The intention was to define a hash. I misunderstood the idea of "compression function". I have changed the title now.

Answer 1

This construction is well-known as XORP = "XOR of independent permutations". In your case the permutations are obtained by invoking a block cipher $E$ with different keys.

If $E$ is an ideal cipher, and $k_1, k_2$ are distinct (fixed, public) keys, then $E_{k_1}(\cdot)$ and $E_{k_2}(\cdot)$ are independent, ideal permutations. Ideal permutation means that everyone has oracle access to these permutations as well as their inverses.

The right question to ask here is:

If $\pi_1$ and $\pi_2$ are independent ideal permutations, is $\textsf{XORP}(x) = \pi_1(x) \oplus \pi_2(x)$ indifferentiable from a random oracle?

"Indifferentiable" means that $\textsf{XORP}$ looks like a random oracle, even to a distinguisher who has access to the underlying $\pi_1, \pi_2$ (and their inverses), which is the case here.

The answer to the question is yes, XORP is indifferentiable from a random oracle. See:

Srimanta Bhattacharya, Mridul Nandi: Full Indifferentiable Security of the Xor of Two or More Random Permutations Using the $\chi^2$ Method (Eurocrypt 2018)

Notably, XORP is secure beyond the birthday bound. If the permutations are on $n$-bit strings, then an adversary who makes $q$ oracle queries can distinguish XORP from a random oracle with probability at most $q/2^n$, instead of $q^2/2^n$.

In summary: $x \mapsto \textsf{AES}_{k_1}(x) \oplus \textsf{AES}_{k_2}(x)$ is a very strong one-way function, under the assumption that AES is an ideal cipher.

Aside: if $k_1$ and $k_2$ are independently random and private, then the question is whether $x \mapsto \textsf{PRP}_{k_1}(x) \oplus \textsf{PRP}_{k_2}(x)$ a pseudorandom function. This is much simpler since the distinguisher does not get direct access to the individual PRPs. Of course the answer here is also yes.

Answer 2

Function $H$ must be defined as $H(x_1, x_2) = E_{k_1}(x_1) \oplus E_{k_2}(x_2)$ where $x_1, x_2$ are separate inputs for it to be compressive. That's not to say that $x_1 = x_2$ cannot happen by chance, but they must be from separate streams if you will. Compression in this case means a loss of information whereby less bits are output by the 'compressor' than are input. In your case, two blocks in (256 bits), one block out (128 bits). You can clearly see that in the case of the Davies–Meyer construction, where two streams converge and only a single stream of half the combined width emerges. The creates the 'one way' aspect. As:-

A 128 bits of information have been 'compressed' out of existence. And without padding the inputs to $H$, multiple inputs will hash to the same value as 10, 100 and 1000 all look the same when fitted into a 128 bit block. That opens the door for many kinds of attack on the function. Dedicated hash functions do this as part of their architecture.

PS. AES has a fixed block width of 128 bits. 128, 192 and 256 are values associated with AES's key length. Fix this lot, and it will be a compressive one way hash. But not optimum.