# One way function built from AES?

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?

• 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. Dec 5, 2016 at 19:12
• @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. Dec 5, 2016 at 19:31
• You're more than clear enough. I just noted one possible interpretation of this construction. Also see this Q. Dec 5, 2016 at 19:33
• 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.
– user10653
Dec 17, 2017 at 16:38

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.)

• 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.
– fgrieu
Dec 17, 2017 at 18:24
• 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. Dec 17, 2017 at 18:42
• 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).
– fgrieu
Dec 17, 2017 at 21:08