4
$\begingroup$

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.

Improve this question
$\endgroup$
9
  • $\begingroup$ Do you have padding on the inputs to get them to always be 128 bits long? $\endgroup$ – Paul Uszak Feb 10 at 16:10
  • $\begingroup$ The assumption is that the inputs are always exactly as large as the block size (be it 128, 192 or 256 bits) so the issue of padding isn't very relevant. $\endgroup$ – yellowlive Feb 10 at 16:13
  • $\begingroup$ Are you sure? 10, 100 and 1000 inputs can all be considered $ \ngtr 2^{128} -1$, yet they're different but the same if not padded. BTW: AES is always a 128 bit block... $\endgroup$ – Paul Uszak Feb 10 at 16:23
  • 1
    $\begingroup$ Are you aware that the construction you gave is not compressing? $\endgroup$ – Michal Feb 10 at 16:41
  • $\begingroup$ Are all the xs meant to be the same? $\endgroup$ – Paul Uszak Feb 10 at 16:49
2
$\begingroup$

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.

Improve this answer
$\endgroup$
0
$\begingroup$

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:-

comp

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.

Improve this answer
$\endgroup$
3
  • $\begingroup$ It seems like my intention was to simply define a hash, not a compression function? x is intended to be a single input. I recall now that AES block size is always 128 bits (confusion on my side). Basically your answer is saying that if this was supposed to be a true compression function (using the modification you gave), it wouldn't be a good one. But that was not the intention. It was supposed to define a hash (one input, one output). I guess I'll have to change the title? $\endgroup$ – yellowlive Feb 10 at 17:28
  • $\begingroup$ @yellowlive Well this is the place to thrash that stuff out :-) Was the answer useful to you otherwise? $\endgroup$ – Paul Uszak Feb 10 at 18:30
  • 1
    $\begingroup$ I used the term "one-way compression function" but I guess simply meant "one-way function". I assumed that "compression" was a term used to describe how a one to one psuedo-random function is converted to a one-way function. I understand now "compression" was actually more about how inputs are chained together. I do feel most readers have understood my true intention. I'm not sure this answer is useful because it doesn't provide insight about the security aspects of the construction as a single-block hash for the purposes of proof-of-work (the original intention). $\endgroup$ – yellowlive Feb 10 at 18:41

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.