8
$\begingroup$

I work on ethereum and other blockchain technologies. And seeing that quantum pc's are someday going to see the light I have some questions / doubts.

I was wondering if hash functions are strong enough to hold up against quantum computers (that in the future will be reality I think seeing things like IBM-Q)

Obviously, cryptosystems like ElGamal, RSA or other cryptosystems based on modular exponentiation and the impossibility of solving the discrete logarithm will fail against quantum adversaries because (as I understood) once the period of the multiplicative body generator (for DSA) or the additive body (ECDSA) is found, you can polarize the qbits in order to extract the solution (obviously I'm not an expert so I don't know if I'm right)

I read this post but I was hoping for a bit more of an insight to understand better all of this in-depth.

So my question: How well do hash functions hold up against adversaries with (large-scale) quantum computers?

$\endgroup$
  • 2
    $\begingroup$ Look for papers on how Grover's algorithm affects hash functions. The gist of it is that preimage resistance is reduced to $2^{n/2}$ and collision resistance is reduced to $2^{n/3}$. $\endgroup$ – forest May 20 '18 at 12:21
  • 2
    $\begingroup$ @forest Only if you use wildly unrealistic cost models for quantum computers, far beyond the currently unrealistic model that large-enough quantum computers exist at all. The best generic collision search algorithm is still the classical van Oorschot–Wiener algorithm. See cr.yp.to/papers.html#collisioncost for details. $\endgroup$ – Squeamish Ossifrage May 20 '18 at 18:14
  • 1
    $\begingroup$ I edited the question so now I don't ask for any documentation/lectures.. We are here to share knowledge, not disturb ourselves. $\endgroup$ – CPereez19 May 20 '18 at 19:17
  • 2
    $\begingroup$ @CPereez19 Chatted with SqueamishOssiphrage and SEJPM which helped pulling this on topic. Reopened accordingly, Sorry for that bump in the road. $\endgroup$ – e-sushi May 20 '18 at 19:29
  • 1
    $\begingroup$ @forest This is independent of the scalability of bits vs. qubits. The asymptotically best known collision search algorithms, if bits and qubits or bit operations and qubit operations cost equally, work on bits with no quantum assistance. $\endgroup$ – Squeamish Ossifrage May 21 '18 at 1:57
12
$\begingroup$

This depends on what kind of hash function you mean and what kind of security you want.

  • Poly1305 is an almost-universal hash family, which, when used with a uniform random key for a single message, has forgery probability for messages of $L$ bits bounded by $2^{-106}\cdot \lceil L/128\rceil$. This means that an adversary, given $(m, a)$ where $a = \operatorname{Poly1305}_k(m)$ for a uniform random choice of $k$ unknown to the adversary, has probability $2^{-106}\cdot \lceil L/128\rceil$ of forging a pair $(m', a')$ where $m \ne m'$.

    This forgery probability is independent of any bounds on the attacker's computational costs, so a quantum adversary has no advantage over a classical adversary to forge universal hash authenticators without knowing the key. However, while the collision probability of Poly1305 as a universal hash family is negligible, an adversary who knows the key can trivially find collisions: Poly1305 is not collision-resistantmore on the distinction between collision probability and collision resistance.

  • SHA-256 is conjectured to be collision-resistant. This means, loosely, that it is hard to find a pair of distinct messages $m \ne m'$ such that $\operatorname{SHA256}(m) = \operatorname{SHA256}(m')$. There is actually no formalization of this concept, only of keyed collision-resistant hash families because, by a simple technique of counting pigeons and holes, we know that collisions exist in SHA-256, so any trivial algorithm that is hard-coded to print one will succeed with essentially zero cost. We just don't know those algorithms, so the best we can do is generic collision search.

    The state of the art in classical generic collision search, the van Oorschot–Wiener algorithm, is actually cheaper than any of the proposed quantum algorithms for generic collision search. There may be breakthroughs in generic quantum collision search algorithms, or someone may find specialized cryptanalysis of SHA-256 that works only on quantum computers (e.g., see below about exotic constructions). But in the current state of the public literature, classical collision searches already appear cheaper than any known quantum collision searches would be even in the unbelievable scenario that qubit operations became as cheap as bit operations.

  • HMAC-SHA256 is conjectured to be a pseudorandom function family, sometimes loosely called a ‘keyed hash’. You might use these to make bearer tokens that passed as HTTP cookies in a web application, e.g. $t = m \mathbin\Vert \operatorname{HMAC-SHA256}_k(m)$ where $m$ is the message ‘the bearer of this token is allowed to write cat pictures to the database between 2018-05-18 and 2018-05-25’ and $k$ is a uniform random secret key known only to the application server.

    For an adversary to forge bearer tokens, their best known strategy given current cryptanalysis of HMAC-SHA256 is to recover $k$ by a generic preimage search on the function $k \mapsto \operatorname{HMAC-SHA256}_k(m)$ for a known message $m$. Actually the adversary might have $t_0 = \operatorname{HMAC-SHA256}_{k_0}(m)$, $t_1 = \operatorname{HMAC-SHA256}_{k_1}(m)$, etc., for many different services handing out bearer tokens, and is happy to recover one of the uniform random secret keys $k_i$.

    The same applies to, e.g., ciphertexts with one-time pads generated by the Salsa20 hash function (which is emphatically not collision-resistant), or AES ciphertexts with the function $k \mapsto \operatorname{AES256}_k(0)$; although AES is a pseudorandom permutation family, the best generic attack is essentially the same.

    The state of the art in classical generic preimage search to find any one of $n$ keys among $2^b$ possibilities with probability $p$ is Oechslin's rainbow tables on a parallel machine, with the computational cost of about $p\cdot 2^b/n$ evaluations of the hash if parallelized at least $q \geq n^2$ ways in the time for $p \cdot 2^b/nq \leq p \cdot 2^b/n^3$ evaluations of the hash.

    The state of the art in quantum generic preimage search is Grover's algorithm, which for a single-target attack can find one key among $2^b$ possibilities with high probability $p$ with the computational cost of about $2^{b/2}\sqrt{p}$ evaluations of the hash in quantum superposition on a quantum computer. This would be a stunning improvement if qubit operations were ever made as cheap as bit operations.

    Grover's algorithm can be parallelized by running many quantum computers on different parts of the search space, but the time advantage of parallelizing Grover's is modest: parallelized $k$ ways, it runs in the time of about $2^{b/2} \sqrt{p/k}$ evaluations of the hash in quantum superposition on a single quantum computer: an array of $k$ quantum computers gives only a factor of $\sqrt{k}$ time improvement over than a single quantum computer. The parallel Grover machine can also be modified to find a preimage for any one of $n \ll k$ targets in the time of $2^{b/2} \sqrt{p/n^{1/2}k}$ quantum evaluations of the hash, at the total cost of $2^{b/2} \sqrt{p/n^{1/2}}$ including communication costs—only a very modest factor of $n^{1/4}$ improvement in cost over a single target.

    The bounds on single-target parallel Grover are proven to be optimal for a generic quantum algorithm, so unless something about the structure of HMAC-SHA256 lends itself to better specialized quantum cryptanalysis, in our current model of quantum computers these costs will not get better (but see below about exotic constructions). It seems unlikely that multi-target parallel Grover variants can cost much less than $2^{b/2} \sqrt{p/n}$, if the $2^{b/2} \sqrt{p/n^{1/2}}$ figure including communication costs is not already optimal.

  • SHA-256 is conjectured to be preimage-resistant. There is actually, again, no formalization of fixed preimage-resistant hash functions, only keyed preimage-resistant hash families (our own potato's summary), but the intuitive idea is that if you're challenged with a hash $h$, it should be hard for you to find a message $m$ such that $m = \operatorname{SHA256}(m)$.

    If $h$ is 8a798890fe93817163b10b5f7bd2ca4d25d84c52739a645a889c173eee7d9d3d, and you know that $m$ was drawn from one of the strings ‘yes’ or ‘no’, then it is easy to find $m$. This is a generic preimage search too, but it is worth mentioning as qualitatively different from the case of HMAC-SHA256 with a uniform random key because the input space is small and highly structured.

    Still, the adversary's best known strategy for finding a message $m$ given a hash $h$ is essentially the same as the adversary's best known strategy for finding a key $k$ given a bearer token $t = m \mathbin\Vert \operatorname{HMAC-SHA256}_k(m)$ and a known message $m$: generic preimage search with parallel rainbow tables or Grover's algorithm. Just remember that highly structured messages or messages drawn from nonuniform distributions—especially, e.g., human-chosen passwords—may make the adversary's job substantially easier.

  • Exotic constructions with specialized cryptanalysis. These applications of Grover's algorithm and generic search strategies apply to any hash function without knowledge of its structure beyond how to evaluate it. Nobody has found anything in the structures of SHA-256, Salsa20, BLAKE2, etc., that would admit faster quantum cryptanalysis. Universal hash families like Poly1305 and GHASH have forgery and collision probabilities that are independent of the attacker's computational budget, so neither a thousand suns nor a real live quantum computer would change them. But here are some examples of constructions that do have quantum-vulnerable structure:

    • Collision search. If $n$ is a public 2048-bit product of two uniform random 1024-bit primes $p$ and $q$, then for uniform random $y \in (\mathbb Z/n\mathbb Z)^\times$ the function $H\colon x \mapsto y^x \bmod n$ of 2048-bit integers to 2048-bit integers is collision-resistant as long as the RSA problem is hard. But on a quantum computer, Shor's algorithm can find the order $k$ of $y$ modulo $n$ at modest cost in qubit operations, and then trivially compute the collisions $y^0 \equiv y^k \pmod n$, $y^1 \equiv y^{k + 1} \pmod n$, etc. Similar considerations apply to other factoring-based collision-resistant hash families like VSH.

      (Shor's algorithm can also factor $n$ at modest cost in qubit operations, at which point it is trivial to find collisions because the order $k$ always divides $\operatorname{lcm}(p - 1, q - 1)$.)

    • Preimage search. If $p$ is the 2048-bit prime modulus of RFC 3526 Group #14 and $g$ is any primitive root modulo $p$, the function $H\colon x \mapsto g^x \bmod p$ is preimage-resistant as long as the finite-field discrete log problem problem in $\mathbb Z/p\mathbb Z$ is hard: finding a preimage is exactly solving the finite-field discrete log problem in a group where it is conjectured to be hard. But given $h = g^x$, if we can find a period $(\delta, \gamma)$ of the function $f\colon (a, b) \mapsto g^a h^{-b} = g^{a - b x}$ then we have $$g^{a - b x} = g^{a + \delta - (b + \gamma) x}$$ for all $a$ and $b$ including zero, so that $0 \equiv \delta - \gamma x \pmod q$ and thus $x \equiv \delta \gamma^{-1} \pmod q$ where $q$ is the order of $g$. Again, on a quantum computer Shor's algorithm can find such a period and thereby compute the discrete log $x$ of $y$ with base $g$.


    These constructions are of only theoretical interest because they are costlier for legitimate users, they provide no additional security against classical adversaries with current knowledge of cryptanalysis, and they would be much cheaper for quantum adversaries to attack.

$\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.