30
$\begingroup$

In the face of non-quantum attacker, Keccak[r=1088,c=512] with 512 bits of output provides:

  • Collision resistance up to $2^{256}$ operations
  • Preimage resistance up to $2^{256}$ operations
  • Second preimage resistance up to $2^{256}$ operations

In general however, using quantum computing, specifically Grover's Algorithm, hash functions can be attacked more efficiently. Daniel J. Bernstein wrote about quantum attacks against all the second round SHA-3 candidates. However, in that paper, all the attacks against Keccak variants are against truncated hashes with an internal capacity of twice the hash length, for example Keccak[r=1152,c=448] with 224 bits of output.

My question is, if the full 512 bit hash output length of Keccak[r=1088,c=512] is used, does this provide security up to $2^{256}$ operations against quantum attackers using Grover's algorithm, or is security limited to half of the preimage strength, that is, only $2^{128}$ operations?

$\endgroup$
23
$\begingroup$

Unless Keccak has structural weaknesses that I am not aware of, the answer is surprisingly neither 128 nor 256!

Gilles Brassard, Peter Høyer and Alain Tapp describe a sort of quantum birthday attack in their paper "Quantum Cryptanalysis of Hash and Claw-Free Functions" that effectively works by creating a table of size $\sqrt[3]{2^b}$ (versus the $\sqrt{2^b}$ for the classic birthday attack) and then utilizes Grover's algorithm to find a collision.

While the classic birthday attack thus requires ${\mathcal O}\left(\sqrt{2^b}\right)$ time and memory, the quantum birthday attack only requires ${\mathcal O}\left(\sqrt[3]{2^b}\right)$ time and memory.

This means that to provide a $b$ bit security level against quantum adversaries, a hash function must provide at least a $3b$ bit output.

In your case of 512 bit Keccak, your security level would be $170\frac{2}{3}$.

$\endgroup$
  • 4
    $\begingroup$ Seeing as this is the accepted answer, it might be worth mentioning that Daniel J. Bernstein has challenged the claim that the Brassard, Høyer and Tapp attack is actually better for collision-finding than classical algorithms. See here: cr.yp.to/hash/collisioncost-20090517.pdf $\endgroup$ – hakoja Apr 19 '17 at 12:27
  • 3
    $\begingroup$ There's a standard classical attack based on Pollard's $\rho$ that requires $O(\sqrt{2^b})$ time and essentially constant memory, and it can be parallelized, say, $O(2^{b/4})$ ways to run in $O(2^{b/4})$ time (at the same cost $O(2^{b/2})$ in energy, but faster). None of the proposed quantum collision search algorithms to date improve on this bound. $\endgroup$ – Squeamish Ossifrage Feb 28 at 20:39
  • $\begingroup$ The total area*time cost for the BHT algorithm, of course, is $O(2^{2b/3})$, far above the $O(2^{b/2})$ cost attained by $\rho$ at any speed. In other words, the quantum collision search algorithms to date have no additional impact on the choices of security parameters for collision-resistant hash functions because there are much better classical collision search algorithms that already should have determined the parameters. $\endgroup$ – Squeamish Ossifrage Feb 28 at 20:43
  • $\begingroup$ So are you saying that a factor is two missing in the exponent in the big-O notation in the answer, $O(2^{b/3})$ instead of $O(2^{{\textbf{2}}b/3})$? $\endgroup$ – Maarten Bodewes Feb 28 at 21:53
  • $\begingroup$ Quantum area*time cost $O(2^{2b/3})$ is the square of what is claimed, once you count the storage costs; classical area*time cost $O(2^{b/2})$ is the square root of what is claimed, once you eliminate the unnecessary storage costs with a $\rho$-type search instead of a table. $\endgroup$ – Squeamish Ossifrage Feb 28 at 22:46
14
$\begingroup$

In short, the answer is yes, if the full 512 bit hash output length of Keccak[r=1088,c=512] is used, this provides security up to 2256 operations against Grover's quantum algorithm.

Using Grover's algorithm, one can find a preimage of a n-bit hash function in time 2n/2 with a quantum computer. This is a generic attack in the sense that it applies to any n-bit hash function.

For the 256-bit output of Keccak[r=1088,c=512] (or, for that matter, any 256-bit hash function), the quantum attacker can apply Grover generically and find a preimage in time 2128. Similarly, for the full 512-bit output of Keccak[r=1088,c=512], the quantum attacker can apply Grover generically and find a preimage in time 2256. However, Grover can also be applied to recover the c=512 hidden bits, but it provides no advantage: it will also cost time 2256.

In general, the attacker can choose between applying Grover generically or to apply it to find the c hidden bits, and he will choose the fastest option of course.

$\endgroup$
  • $\begingroup$ That is exactly what I thought, but wanted confirmation that I'm not missing some crucial tidbit why it wouldn't be so. Thank you! $\endgroup$ – Nakedible Aug 17 '11 at 20:26
9
$\begingroup$

First, lets get some thing clear over here. The analysis of Grover's algorithm is asymptotic, so it is fairly unfair to perform something as concrete as the setting you have mentioned.
Grover's algorithm gives you an asymptotic upper bound of $O(\sqrt{N})$ for searching in an unsorted array of size $N$ so I have trouble understanding how one can claim that it will require $2^{512}$ operations. To me, from the point of view of analysis, it seems wrong analysis. What you should see is the constant factor in the Grover's algorithm and for that I will refer you to the original paper of Grover's algorithm and work out the mathematics there. You will see that it won't give you the number of operations to be $2^{512}$ for preimage resistance as well, rather it will give you a constant multiplied to it.

However, if you want to make an asymptotic analysis, you cannot have a particular instantiation of a hash function, rather you have to consider a family of hash functions. This is a common mistake people tend to do. In that case, all you know is that the upper bound is $O(\sqrt{N})$ and a lower bound is $\Omega(N^{1/3})$ by S. Aaronson's paper on Quantum lower bounds for the collision and the element distinctness problems.

$\endgroup$
  • 1
    $\begingroup$ Grover's paper describes a specific machine built out of qubits and unitary operations. While it's true that the notation $O(\sqrt N)$ means a set of asymptotic growth curves, Grover's algorithm for finding preimages—and the related BHT and Ambainis algorithms for finding collisions—also has concrete numbers of qubits to implement the machine, and of operations to attain a prescribed success probability or expected number of operations before success. Sweeping this all under the rug of constant factors isn't helpful. $\endgroup$ – Squeamish Ossifrage Mar 18 at 16:45
7
$\begingroup$

Fix a hash function $H\colon \{0,1\}^m \to \{0,1\}^n$ built out of a sponge of capacity $c$.

To raise the cost of both generic collision and generic preimage searches on classical or quantum computers above $2^\lambda$, pick $c = n = 2\lambda$: the capacity and hash length need only be double the security target, no more.

For example, for a 128-bit security level even against a quantum adversary, it suffices to pick $c = n = 256$. Out of an abundance of caution, and partly for political reasons arising from the timing so soon after Snowden and Project BULLRUN[1], NIST chose $c = 2n = 4\lambda$ instead, e.g. $c = 512$ for SHA3-256 giving a 128-bit security level, at substantial—and at the time politically justifiable but now technically regrettable—cost to performance. In contrast, the newer SHAKE128 and SHAKE256 were unhampered by political concerns by virtue of being novel anyway, and follow the $c = 2\lambda$ formula.


If this advice seems at odds with the conventional wisdom that you have to double or triple hash sizes to maintain the same security against quantum adversaries as you had against classical adversaries, let's review the state of the art in generic attacks.

Collision resistance

The conventional wisdom outside cryptographers is that the best you can do classically is create a large table of outputs for random inputs and hope you find a collision eventually by the birthday paradox, which would cost $O(2^{n/2})$ time and $O(2^{n/2})$ space to store the table. But you don't need to store a table—a variant of Pollard's $\rho$[2] can do it in constant space. So the best generic classical collision search algorithm is van Oorschot–Wiener[3] with cost $O(2^{n/2})$, which can be parallelized to give a linear speedup—e.g., parallelize it $O(2^{n/4})$ ways and get an answer in $O(2^{n/4})$ time at the same cost of $O(2^{n/2})$. For a sponge, the same kind of generic birthday attack works on the $c$-bit hidden state at cost $O(2^{c/2})$.

The best generic quantum collision algorithms are advertised to take $O(2^{n/3})$ time, but this ignores the reality that there are costs other than time[4]. The Brassard–Høyer–Tapp algorithm[5] works by building a table of size $O(2^{n/3})$ and then running Grover's algorithm for $O(2^{n/3})$ steps, with an area*time cost of $O(2^{2n/3})$, far costlier than a classical search can be. The Ambainis algorithm[6] can be adapted into a collision search algorithm for similar cost $O(2^{2m/3})$. There are some other variations on the theme but none of them have broken the $O(2^{n/2})$ cost barrier even under the wildly unrealistic premise that qubit operations are as cheap as bit operations and communication is free[7]. For a sponge, the same kind of generic birthday attack works on the $c$-bit hidden state at cost $O(2^{2c/3})$[8].

There is a lower bound $\Omega(2^{n/3})$ on the number of queries a generic quantum algorithm must make to $H$[9], so if there is any advance in this area, it must be dramatic reductions in storage costs.

The best generic (sponge) collision attacks are classical algorithms which can be run today—there is no additional concern from quantum algorithms.

Preimage resistance

The conventional wisdom outside cryptographers is that the best you can do classically is to try an expected $O(2^n)$ inputs before you'll find one that matches. But you can save cost across multiple targets with Oechslin's rainbow tables[10] on a parallel machine[11], attaining a cost of $O(2^n/t)$ in the time for $O(2^n/t^3)$ sequential evaluations of $H$, if parallelized $t^2$ ways to find a preimage for the first of $t$ targets. For a sponge, the same generic preimage attacks apply to recovering the $c$-bit hidden state at cost $O(2^c/t)$ in time $O(2^c/t^3)$.

The best generic quantum preimage algorithm, Grover's algorithm[12], is advertised to take $O(2^{n/2})$ time, and it doesn't take much space, so the area*time cost is a somewhat scary-looking $O(2^{n/2})$—but even if you could evaluate $H$ once per nanosecond sequentially without time for any other computation, it would take half a millennium to get an answer. And Grover, it turns out, doesn't parallelize well or give much of a batch advantage[13]: spending $p$ times as much energy to run Grover on $p$ machines in parallel gives only a factor of $\sqrt{p}$ speedup, so the net cost grows by a factor of $\sqrt{p}$, and a batch attack on $t \ll p$ targets gives only a factor of $t^{1/4}$ speedup. For a sponge, the same generic preimage attacks apply to recovering the $c$-bit hidden state in time $O(2^{c/2})$ with similar costs for parallelism and modest batch advantage.

There is some additional concern for speedups in preimage attacks attainable by quantum computers, but you should also be worried about multi-target batch attacks using classical computers too.

Second-preimage resistance

There's no generic second-preimage attack that works better than a generic preimage attack, and collision resistance implies second-preimage resistance anyway, so there's not much more to say about this.

$\endgroup$
3
$\begingroup$

No, it isn't a trivial question to answer but, I presume that you have read Peter Shor's article on polynomial time prime factorization and discrete logarithms using quantum computers? Essentially, many cryptographic constructs are based on the hardness of these two problems meaning that if they can be solved in polynomial time, then they are essentially broken.

Whether or not this applies to Keccak is another story, however, according to its specification, the expected success of any shortcut attack with a workload equivalent of N calls to KECCAK-f[r+c] or its inverse shall be less than or equal to $1-exp(-N(N+1)2^{-(c+1)})$. They do, however, exclude the weakness that KECCAK-f[r+c] can be described compactly, and executed efficiently.

Also, if you have a look at the Keddak sponge function family web site, it should provide you with the results of the latest cryptographic attacks against Keccak.

$\endgroup$
  • 1
    $\begingroup$ Actually, I was mostly looking an answer that would be a generic attack against Keccak (or actually, against any sponge function built with a permutation), not for a quantum attack that would utilize the structure of the actual Keccak permutation. $\endgroup$ – Nakedible Aug 17 '11 at 20:30
  • $\begingroup$ Shor's algorithm is not relevant to finding generic hash preimages or collisions, not even generic sponge preimages or collisions. $\endgroup$ – Squeamish Ossifrage Mar 18 at 16:45
2
$\begingroup$

Here is a recent paper on quantum security of sponges: Collapsing sponges: Post-quantum security of the sponge construction

We investigate the post-quantum security of hash functions based on the sponge construction. A crucial property for hash functions in the post-quantum setting is the collapsing property (a strengthening of collision-resistance). We show that the sponge construction is collapsing (and in consequence quantum collision-resistant) under suitable assumptions about the underlying block function. In particular, if the block function is a random function or a (non-invertible) random permutation, the sponge construction is collapsing.

I think it does a better job of considering this aspect than anything presented here yet.

$\endgroup$

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.