Did NIST verify “post-quantum” claims in the SHA3 proposal papers?

Question

I have been reading Bernstein’s “Quantum attacks against Blue Midnight Wish, ECHO, Fugue, Grøstl, Hamsi, JH, Keccak, Shabal, SHAvite-3, SIMD, and Skein” paper from 2010…

This document disproves the claims of preimage resistance for Blue Midnight Wish, ECHO, Fugue, Grøstl, Hamsi, JH, Keccak, Shabal, SHAvite-3, SIMD, and Skein. Specifically, this document presents attacks finding preimages in each of these hash functions using time much, much, much smaller than $2^{224}$: specifically, using only about $2^{112}$ simple operations. The exponent gap is so large that it cannot be explained by the difference between “224 bits” and “approximately 224 bits.”

^{(emphasis mine)}

The most interesting points are …

This is, in particular, a claim of $2^{224}$ preimage resistance for 224-bit Keccak. There is no warning regarding the impact of quantum computers: Keccak claims “preimage resistance,” not merely pre-quantum preimage resistance.

and

Each attack uses approximately $2^{112}$ iterations, disproving the $2^{224}$ preimage-resistance claims for each of these functions. The exact complexity of each iteration, and the required number of qubits, varies somewhat from function to function, but is on a far smaller scale than the $2^{112}$ complexity gap.

This contradicts some of the expectations I had after NIST validated and chose Keccak as the winning SHA3 proposal. Also, it somewhat underlines the correctness of my suspicions related the incorrect “post-quantum sufficient” claims in the Keccak papers. (You might remember my older question where I already suspected another post-quantum claim of Keccak to be incorrect: What exactly is the base for the KECCAK (SHA3) claim that a security strength of 256 bits is “post-quantum sufficient”?)

As a result, I've got two related, yet somewhat different questions:

1. As it stands, Bernstein showed Grover’s algorithm could successfully enable pre-image attacks on SHA3 candidates (including Keccak, the SHA3 finalist) and as far as I learned from the different replies here at Crypto.SE: if it's broken, it's broken… no matter how theoretical or far-fetched the break is, a break is a clear warning sign. Even when I would ignore that, the question remains if the claims of those SHA3 papers can be trusted at all. I mean, I did quite some research but I frequently noticed that claims can not be verified; especially in relation to Keccak. (See my question and answer: Is it possible to actually verify a “sponge function” security claim?)

   Are there any papers that I should know about which contradict the findings of Bernstein’s paper?

2. For the benefit of the doubt, I won't start contemplating if NIST might have been influenced during their SHA3 quest or not, because similar crypto-news has been raving the press too much already. Yet, I wonder why Bernstein’s findings seem to have been ignored and I would like to understand why NIST chose to ignore the fact that most SHA3 proposals might suffer from quantum-attacks.

   Did NIST actually validate any of the proposals for post-quantum security (and related claims in papers) at all, or was quantum computing simply ignored during their SHA3 security assessments? And if quantum was ignored, what was the motivation to do so?

   (Maybe you can point me to references confirming NIST did or did not validate post-quantum aspects… I couldn't find any.)

Answer 1

With any $n$ bit hash it is possible to:

• Find preimages with work $2^n$ on classical computers and $2^{n/2}$ using quantum computers
• Find collisions with work $2^{n/2}$ on classical computers and $2^{n/3}$ using quantum computers

I want to emphasize that these are generic attacks that always work, no matter which concrete hashfunction is used. Grover's algorithm is the quantum mechanical equivalent of classical brute-force.

For sponges (including keccak and cubehash) if $c$ is smaller than $2n$ there are other generic attacks:

• Find preimages with work $2^{c/2}$ on classical computers and $2^{c/3}$ using quantum computers
• Find collisions with work $2^{c/2}$ on classical computers and $2^{c/3}$ using quantum computers

---

Now several authors of SHA-3 candidates simply wrote "preimages with work $2^n$" and "collisions with work $2^{n/2}$" without explicitly stating that these claims only apply to classical computers. The intention of these claims was clearly "no faster than brute-force attacks", but they only spelled it out explicitly for classical computers.

Some authors (like DJB himself) carefully specified the above limits separately for classical computers and quantum computers, and some simply wrote that the "usual security levels apply".

Now DJB argues that since the security level against quantum computers violate the security claims, they're an attack against those hashes. The same attacks apply to cubehash as well, except that they don't violate its security claims.

The paper is the simple observation that some papers didn't mention the generic quantum computer attacks and didn't clearly restrict their claims to classical computers. It's about a really minor sloppiness in those papers, I'd expect every cryptographer to know that these claims don't apply to quantum computers.

The paper does not contain any new attacks or findings, only nitpicks.