# 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. – SEJPM Dec 5 '16 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. – Richard Thiessen Dec 5 '16 at 19:31
• You're more than clear enough. I just noted one possible interpretation of this construction. Also see this Q. – SEJPM Dec 5 '16 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 '17 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]$.