Are AES-256's related-key weaknesses exploitable if it is used to build a hash?

Assume it is made a hash based on AES-256 encryption (perhaps because this is hardware-accelerated, but no standard hash is); and it is used the Merkle–Damgård structure, that is padding of the message into $n$ padded message blocks $M_i$ (appending to the message a 1, a minimal number of 0, and the 64-bit message length in bits), and a compression function per the construction of either

1. Davies-Meyer for a 128-bit hash with 256-bit blocks $M_i$, that is
• $H_0$ is set to a 128-bit nothing-up-my-sleeves constant;
• for $i$ from $0$ to $n-1$:
$\text{ }H_{i+1}=\text{AES-256}_{M_i}(H_i)\oplus H_i$
• result is $H_n$;
2. Hirose (FSE 2006) for a 256-bit hash with 128-bit blocks $M_i$, that is
• $G_0$ and $H_0$ are set to a 128-bit nothing-up-my-sleeves constants;
• for $i$ from $0$ to $n-1$ (with $C$ a non-zero nothing-up-my-sleeves 128-bit constant) \text{ }\begin{align*} G_{i+1}&=\text{AES-256}_{H_i||M_i}(G_i)\oplus G_i\\ H_{i+1}&=\text{AES-256}_{H_i||M_i}(G_i\oplus C)\oplus(G_i\oplus C) \end{align*}
• result is $G_n||H_n$.

Notice that in both of these constructions, the message that the adversary can manipulate is entered in the key input of the cipher, making related-key attacks a concern.

Question: In these contexts, are any known or foreseeable AES-256 related-key weaknesses exploitable or seriously threatening?

If yes, do we have other hash constructs where AES (any size) related-key weaknesses would be less of a concern?

Note: For the 128-bit hash we expect an effort comparable to $2^{64}$ encryptions to exhibit a collision (that can be efficiently distributed, see Parallel Collision Search with Cryptanalytic Applications); and $\min(2^{128},2^{129}/n+2^{65})$ encryptions to exhibit a (second) preimage (by a generic attack on Merkle–Damgård hashes attributed to R. D. Dean in his 1999 thesis (section 5.3.1), better exposed and refined by J. Kelsey and B. Schneier in Second Preimages on n-bit Hash Functions for Much Less than 2n Work).
For the 256-bit hash we expect an effort comparable to at least $2^{128}$ encryptions to exhibit a collision, and much more to exhibit a preimage.

-

The most efficient related-key attacks on AES-256 and resulting weaknesses AES-256-based hash functions are summarized in my PhD thesis. Though collision and preimage attacks on hash functions are out of reach yet, the components of these functions still expose some properties that are not expected of good hash functions or random oracles.

Getting to the details, the key schedule of AES-256 allows for numerous related-key differential trails with the most probable one covering as few as 19 S-boxes (page 96) and probability $2^{-119}$. By playing with the first rounds of this trail, one can get various properties of the AES-256-based compression function $$F(IV,M) = AES_{M}(IV)\oplus IV$$ holding with rather high probability.

For example, one can fix values $\Delta I$ and $\Delta M$ and produce a number of pseudo-collisions $\{(IV_i,M_i)\}$ such that for all $i$: $$F(IV_i,M_i) = F(IV_i\oplus \Delta I, M_i\oplus \Delta M).$$

It can be proved that constructing $q$ such pseudo-collisions with the same $(\Delta I,\Delta M)$ requires almost $2^{n}$ work when $q>2$, whereas for AES-256 in the Davies-Meyer mode the complexity is about $q\cdot 2^{67}$.

Though this is not a direct threat to the full hash function, a malicious designer may select an IV to maximize the differential properties of the first round. Among nothing-up-my-sleeve values there must be some that allow for higher-probability differential trails.

-
I notice that one of your paper says from a former one that it has "shown practical attacks on AES-256 in the chosen key scenario, which demonstrates that AES-256 can not serve as a replacement for an ideal cipher in theoretically sound constructions such as Davies-Meyer mode". Can you comment on that? –  fgrieu Apr 14 at 18:20
This means that the Davies-Meyer mode is provably secure if instantiated with ideal cipher (=random cipher). However, we showed that AES-256 exhibits properties that are difficult to construct for an ideal cipher but easier for AES-256. –  Dmitry Khovratovich Apr 15 at 10:58
So the successful attacks on AES-256 invalidates arguments/proof of security based on an ideal cipher model, but do not translate into a direct attack that we know, right? -- About the attack explored in your answer: is the ability for the designer of the hash to choose the $IV$ a significant advantage over what users can do: try $M_0$ at random until the resulting $H_1$ has the desired property? And can you detail what's achieved after hypothetically managing to get $IV$ or $H_1$ to the right value? –  fgrieu Apr 15 at 11:42
1. Right 2. Yes, significant advantage. We can generate a number of weak IVs that would allow differentials of high probability. I can not tell immediately how many and what the probability is, but it can be calculated from the paper. –  Dmitry Khovratovich Apr 15 at 12:10

I don't know of any practical attacks on these schemes that would break collision-resistance or pre-image resistance, but the existence of related-key attacks on AES is still worrisome. The Miyaguchi-Preneel hash construction is better in this sense, because the attacker doesn't directly control anything that goes into the key input.

Miyaguchi-Preneel is shown below. Notice that the message enters the plaintext input to AES, not the key input. The key is driven with the chaining value, which is hard for the attacker to have much control over. Therefore, Miyaguchi-Preneel seems much more robust against related-key attacks on AES. This is an advantage of Miyaguchi-Preneel over Davies-Meyer or Hirose. Unfortunately, Miyaguchi-Preneel only gives a 128-bit hash, and thus is $2\times$ slower than some alternatives. This may make it unattractive in practice.

-
Yes, with AES, Miyaguchi-Preneel seems more robust: the block cipher is in a known-key setup, rather than chosen-key (Davies-Meyer) or a half-chosen-key (Hirose). However, Miyaguchi-Preneel only gives a 128-bit hash (uncomfortably narrow nowadays w.r.t. collision-resistance), and uses 128-bit blocks rather than Davies-Meyer's 256-bit, making it less efficient by a factor like 2. That would be a high performance penalty to endure if we had reasons to believe attacks exploiting AES related-key weaknesses are likely to forever have cost higher than the expected resistance to brute-force attacks. –  fgrieu Apr 14 at 19:31