23
$\begingroup$

I was reading a paper related to post quantum cryptography. It says that RSA, ECC and ElGamal encryption schemes would be obsolete with the advent of quantum computers. But the hash functions can still be secure. I don't understand how one can unilaterally claim this security when hash functions themselves are not based on any hard problems. (I do have the knowledge of Merkel-Damgård and Keccak construction).

Are there hash functions considered secure just because nobody has come up with a quantum algorithm to solve it? Or are there any reduction to any well known hard problem? It there is please explain the reduction.

$\endgroup$
  • 10
    $\begingroup$ Hash functions have so little mathematical structure (as opposed to asymmetric crypto) that it is generally assumed that no specialized quantum algorithm exists for them (same with other symmetric algorithms). $\endgroup$ – SEJPM Mar 3 '17 at 13:22
  • $\begingroup$ Remember, Hash functions are a fundamentally different beast. Compare putting a book in a safe to copying the first letter of every page as proof you had the book, then burning it. The first has a way to get the book back, the second doesn't no matter how much resources you may have. A lossy algorithm is difficult to reverse beyond just being mathematically difficult, the actual data to reverse it is permanently gone. $\endgroup$ – Vality Mar 3 '17 at 17:51
  • 4
    $\begingroup$ I do not think the hardness of inverting has anything to do with lossiness, as an inverter is only require to find any valid preimage. Lossiness just adds more valid preimages, what really matters is the lack of (easily identifiable/ usable) structure. $\endgroup$ – Geoffroy Couteau Mar 3 '17 at 20:07
  • $\begingroup$ I'm not an expert, but there is a really good answer on this site that talks about how they are difficult to solve for a valid input due to fanout (it helps to visualise the hash as a series of logic gates). With that, and the boolean satisfiability problem, I'd say they are based on hard problems? $\endgroup$ – Doddy Mar 4 '17 at 9:25
  • $\begingroup$ Can you link to this answer? Regarding your remark, what matters is not being based on a hard problem, but having a polynomial time reduction to a problem that we have failed to break. The Merkle-Hellman cryptosystem was based on an NP-hard problem (the knapsack problem), but it was broken nevertheless, and its insecurity does not have any impact on the NP-hardness of the problem it was based on. $\endgroup$ – Geoffroy Couteau Mar 4 '17 at 13:27
31
$\begingroup$

It is a bit dubious to claim that hash functions "are not based on any hard problem": inverting a standard hash function, or finding a collision, is itself a very hard problem.

The point of a reduction is to gather the cryptanalytic effort on a smaller number of hypothesis. The fact that RSA-OAEP is CCA secure under the RSA assumption is not a proof that it is secure, simply an indication that to study its security, it suffices to study the security of the RSA problem. As many other cryptographic primitives can be reduced to the RSA assumption, it saves a considerable cryptanalytic effort.

Now, such reductions usually rely on some nice algebraic properties of mathematical hypothesis, exploiting group structure, self-randomizability, and so on. These properties are common in asymmetric cryptography, because such additional structure is already necessary in the primitives it involves. But in symmetric crypto, on the other hand, such structure is typically avoided. A consequence of that is that you need way smaller primitives (in terms of bit size) to achieve a (conjectured) given security level, but you loose the possibility of reducing many symmetric primitives to a small number of hypothesis.

Still, for the most widely deployed block ciphers and hash functions, the cryptanalytic effort that has been invested on studying their security easily matches the effort invested on "generic hypothesis" such as the discrete logarithm or the factorisation. Therefore, there is no reason to believe that, due to the lack of reductions, inverting SHA256 should be any easier than breaking RSA. In fact, because RSA has so much structure, most experts would probably be way more surprised by an attack that inverts SHA256 than by an attack that breaks RSA. Therefore, the fact that ElGamal and the kind enjoy "reductions" does absolutely not make them more secure - it only establishes links between hardness of different primitives.

That being said, quantum computers are not magical. We cannot say anything for sure about what we can or what we cannot break with them - for all we know, it could be that $P=NP$, and that all of cryptography can be broken using a classical computer. But our current knowledge gives us some intuition on the additional power they give over classical computers. And this intuition can be summed up as follow: it seems to give some additional power, but to still fall short on solving very hard problems (say, NP-complete problems) in reasonable time.

Some problems with a special structure (factorization, discrete log) typically fall in the category of problem for which quantum computers would give a very strong speedup, because they can be reduced to the task of finding the period of some function, which seems hard to do with a classical computer, but not with a quantum one. For unstructured problems, quantum computers seem to provide some non-trivial quadratic speedup, via the use of the Grover algorithm. But a quadratic speedup does not give an attack, it simply indicates that the size of the keys should be increased by a factor two to compensate for this speedup.

Hash functions are rather unstructured, so we currently do not see how to get more than a quadratic speedup over a classical computer to attack one. Therefore, we currently conjecture that a hash function with 256 bits of classical security would still have 128 bits of quantum security. For collision resistance, quantum computers provide an even less impressive speedup: the birthday attack gives a $O(\sqrt{n})$ attack, and it's quantum version seems only to make this attack $O(n^{1/3})$.

$\endgroup$
  • 3
  • 6
    $\begingroup$ I did not know this article, thank you for sharing it :) If I understand right, the point is that using a quantum computer will not be as cost-effective as using massively parallel classical computers for collision-finding; I was not really looking at speed or cost, but rather at the theoretical complexity of the problem in the classical and in the quantum world. In any case, it strengthens my point and it's always nice to learn something :) $\endgroup$ – Geoffroy Couteau Mar 3 '17 at 14:37
  • $\begingroup$ Actually, security properties of iterated hash functions often can be reduced to security properties of the used compression function. (Or in the case of sponge functions, to the properties of the used permutation.) $\endgroup$ – Paŭlo Ebermann Mar 4 '17 at 10:54
  • 1
    $\begingroup$ Sure, and it is indeed a very active research field in symmetric crypto - proving indistinguishability, indifferentiability to a random oracle, or collision-resistance of symmetric primitives built on top of "smaller" primitives. But I assumed that it was not the point of OP's question and focused on the case of the underlying fixed size input primitives. $\endgroup$ – Geoffroy Couteau Mar 4 '17 at 11:17
  • $\begingroup$ @SEJPM I don't understand this article, if he is saying that RSA is not threatened by quantum computing what was Mr Rivest talking about in the numberphiles interview? $\endgroup$ – daniel May 15 '17 at 9:58
6
$\begingroup$

Common hash functions are based on combinatorial problems. Very coarsely, (future) quantum computers are claimed to be able to solve combinatorial problems with effort (at worst) $O(2^{k/2})$ for $k$ unknown bits, versus $O(2^k)$ for classical computers. Thus quantum computer do not imply the doom of security of all hashes; at worse, it implies doubling some security parameters.

I trust SHA-512 against all kinds of computers more than I trust SHA-256 against classical ones.

$\endgroup$
-6
$\begingroup$

A hash is just a symmetric cipher run in a loop, encrypting the input using a key also from the same input, and often with extra stuff sprinkled in as you go (e.g. prime remainders in SHA-2).

I'm no expert, but whether or not any hash is quantum-resistant boils down entirely to whether or not the symmetric cipher chosen for the hash is.

The SHA-2 cipher is secret (classified), so only the NSA (who invented SHA) know if it's quantum-resistant or not.

$\endgroup$
  • 3
    $\begingroup$ Um, how can the cipher be secret if the entire algorithm is known? Why would a hash rely on a symmetric cipher? Yes, some hashes are and symmetric ciphers and hashes have a lot in common, but does that mean that a hash must rely on an underlying block cipher? $\endgroup$ – Maarten Bodewes Dec 15 '17 at 16:07
  • $\begingroup$ Hi Maarten. See Merkle–Damgård to learn up on how all modern hash mechanisms are constructed. Once you're clear on how and why they use symmetric ciphers, you can research which one's used in SHA if you like, or if you're good at reverse engineering, maybe you can look at the SHA code and work out which one it is? (I doubt that though - this is NSA-designed - the actual cipher they used is almost certainly classified) $\endgroup$ – Anon Coward Dec 16 '17 at 22:48
  • 3
    $\begingroup$ Merkle–Damgård is not the only method of generating a modern hash; for instance Keccak / SHA-3 is not a Merkle–Damgård hash. $\endgroup$ – Maarten Bodewes Dec 16 '17 at 23:04
  • 2
    $\begingroup$ This is so wrong I don't even know where to start. So, I'll limit myself to passing on the friendly advice to read up on SHA-2 as well as the Merkle–Damgård construction it uses. Related papers are widely available to the general public and — in contrast to your claims — by no means secret or classified in any way. While doing your research, you'll soon notice there is a huge difference between a cipher (aka encryption algo) and a Merkle–Damgård construction. TL;DR: I fully agree with @MaartenBodewes' comments. $\endgroup$ – e-sushi May 20 '18 at 19:00
  • 1
    $\begingroup$ @AnonCoward Since the cipher is only used internally in SHA-2, it does not have a name. However, when you extract it, you have a cipher called SHACAL-2, which is public. The cipher used may have been based on a cipher which is classified, but the block cipher in SHA-2 is public. $\endgroup$ – forest Jul 15 '18 at 3:23

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy