8
$\begingroup$

I'm implementing a Hash based signature algorithm and this paper recommends the use of $F(X,\mathit{salt})=\operatorname{AES}_\mathit{salt}(X)\oplus X$ as a hard one way function. The salt plays the same role here as it does in password hashing and is a fixed public value that varies across small groups of calculations.

The requirement is that $F$ be preimage resistant. (IE: given $F(X,\mathit{salt})$ attacker can't find $X$ faster than brute force)

Cryptanalysis has been done which rules out AES in contexts where the attacker gets to find approximate solutions to similar equations or gets control of key bits (EX:as hash compression function). In all these cases the attacker has degrees of freedom to work with. Here they don't.

Is $F$ preimage resistant? Can the attacker find $X$ with siginficantly less that $2^{128}$ work?

$\endgroup$
  • $\begingroup$ This appears to be Even-Mansour encryption using AES as the PRP, X as the key, 0 as the message and salt to pick the permutation. $\endgroup$ – SEJPM Dec 5 '16 at 19:12
  • $\begingroup$ @SEJPM My notation is probably unclear. Salt is used as the AES key. The value x is used as input to the block cipher and xored to the resulting output value to make the function one-way. I'm still using backticks and raw text rather than fancy pictures. $\endgroup$ – Richard Thiessen Dec 5 '16 at 19:31
  • 2
    $\begingroup$ You're more than clear enough. I just noted one possible interpretation of this construction. Also see this Q. $\endgroup$ – SEJPM Dec 5 '16 at 19:33
  • $\begingroup$ IIRC the AES key schedule is a problem. You may want to have a look at the Whirpool hash function, it uses primitives from AES but a stronger key schedule. $\endgroup$ – user10653 Dec 17 '17 at 16:38
3
$\begingroup$

This is the Matyas–Meyer–Oseas construction. It was introduced by engineers at IBM in 1985, and analyzed in the ideal cipher model by Black, Rogaway, and Shrimpton in 2002 among all possible iterated compression functions $h_i = f(h_{i-1}, m_i) = E_a(b) \oplus c$ where $a$, $b$, and $c$ are message blocks $m_i$ or chaining values $h_{i-1}$. For this case ($i=1, j=6$, or $a = h_{i-1}$, $b = m_i$, $c = m_i$), in the ideal cipher model, the adversary's probability of finding a preimage after $q$ queries lies in $[0.4 q/2^n, 2q/2^n]$.

Now, AES is not an ideal cipher—at best, it is a pseudorandom permutation family. But it is likely that the related-key attacks of Biryukov and Khovratovich do not substantively affect the security of this scheme when the salt is not under attacker control.

(All the references you need are actually in the paper you cited already, right where it recommends using AES. If you can't follow them because of morally reprehensible academic paywalls, Sci-Hub and LibGen are your friends.)

$\endgroup$
  • $\begingroup$ The page in the first/official link you give includes a download button with the paper for free. That works for all papers from IACR conferences before a certain date, I believe. Keeping track of today's TLD for your alternate source is, well, a task. $\endgroup$ – fgrieu Dec 17 '17 at 18:24
  • $\begingroup$ Are you sure you're not just granted gratis access to Springer from your institution's IP address? Maybe it is publicly available; I didn't bother to check because a lot of Springer isn't. $\endgroup$ – Squeamish Ossifrage Dec 17 '17 at 18:42
  • 2
    $\begingroup$ That's for everyone. By agreement with Springer, papers from a number of IACR conferences are made available for free by Springer after 4 years; that's for Crypto, Eurocrypt, Asiacrypt, FSE, PKC, CHES, TCC; and there's earlier free access to the papers as submitted from IACR after 2 years (at the previous link). $\endgroup$ – fgrieu Dec 17 '17 at 21:08

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.