2
$\begingroup$

Current computers cannot break reasonably strong hashed passwords, for example 14 CSPRNG-generated alphanumeric characters ($\approx$80 bits of entropy).

Grover's algorithm applies to hash functions as I understand it (mentioned e.g. in this answer), meaning that given any MD5 output of 128 bits, it can find the input (or a collision thereof) in $\sqrt{2^{128}}=2^{64}$ evaluations of the algorithm, provided a computer with enough qubits. If the quantum computer can evaluate MD5 fast enough (or is cheap enough to build enough copies), this would break MD5 completely no matter how strong the user's password was.

Finding a 256-bit random key that was run through a 256-bit (or stronger) hash function would, however, still be well out of reach.

What if the hash function itself is post-quantum secure, e.g. SHA-512, but the input is a password? Is any quantum algorithm known that can find the input in significantly fewer evaluations than a traditional brute force search ($\frac{2^{80}}{2}$ on average for the example above)? Does Grover's algorithm (or any other applicable quantum algorithm) only apply to weakening the hash function itself or can it also search only plausible inputs (a-z, A-Z, 0-9 <=14 characters) to reduce the search space?

To be clear, I understand that any bare hashing function (even with unnecessarily long outputs like SHA-512) is a terrible way to store user passwords and Argon2 or similar should be used, but I thought that memory-hardness and other aspects might make the question too broad or an answer less broadly applicable.

$\endgroup$

1 Answer 1

4
$\begingroup$

Does Grover's algorithm (or any other applicable quantum algorithm) only apply to weakening the hash function itself or can it also search only plausible inputs (a-z, A-Z, 0-9 <=14 characters) to reduce the search space?

Grover's is a general search method - it doesn't know or care how the function is given interprets the input. If you give it a function that interprets the inputs as "(a-z, A-Z, 0-9 <=14 characters)", it'll work with it, with the expected complexity.

On the other hand, the relevant question may be "is using a Quantum Computer make economical sense, as opposed to a GPU farm or some ASICs?" I suggest for the next several decades (that is, until Quantum Computer technology has gone through a number of generations), classical methods will be faster in this instance.

Some of the reasons for this:

  • The cost of a Quantum Computing operation can be expected to be much larger than the cost of the corresponding classical one. This is a constant factor when comparing the two - however, if this constant factor is perhaps a billion or a trillion, it really shouldn't be ignored.

  • Parallelization - classical computer searches (like this one) are perfectly parallizable (which a GPU farm or set of ASICs would take full advantage of). In contrast, Grover's algorithm (or any similar Quantum Oracle search) is not - you do get that the $n^2$ speed up if you can perform $O(n)$ successive operations. However, if you can't wait that long and need to implement multiple Quantum Computers to do the search, well, you don't get that $n^2$ speed up between them. For example, to do the search 100 times faster, you need 10,000 times as many Quantum Computers.

  • Reuse of the key search. With classical computation, we can generate a Rainbow table - generating that table takes about as long as the full search; however once it is done, doing repeated searches on various hashed passwords is cheap. In contrast, running Grover's algorithm will do a search on a single password - if we want to check on another hash, we have to pay for the full search all over again. You could build a Rainbow table on a Quantum Computer, of course; however I don't believe you'd get any Quantum speed up, and I haven't heard of an alternative where you would get a Quantum speed up.

Now, over time, we can reasonably expect the cost of Quantum Computers to go down (and go down faster than the comparative cost of classical computing), and we can expect Quantum Computers to get faster over time (hence requiring less parallelization); I just don't expect either trend to happen over night...

To be clear, I understand that any bare hashing function (even with unnecessarily long outputs like SHA-512) is a terrible way to store user passwords and Argon2 or similar should be used, but I thought that memory-hardness and other aspects might make the question too broad or an answer less broadly applicable.

With our current understanding of the trade-offs inherent within a Quantum Computer (which might be considerably off-base), a memory hard function would be quite painful for a Quantum Computer to deal with. Evaluating such a hash function would appear to require a large Quantum memory, and (as far as we know) that looks to be dreadfully expensive [1].

Grover's algorithm would be applicable (again, it doesn't care what the hash function is); however it would appear to be quite expensive.

So, assuming that our guesses are correct, a memory hard hash function (Argon2) would be even more resistant to Quantum Computing than simple hash functions.


[1]: I believe at least part of the reason is if you have a large Quantum Memory, and access it for an entangled address, you end up performing operations on every single memory cell (or at least, every single cell that might be addressed by the entangled address). In contrast, with a classical memory, you only need to access the cell which is being addressed. If we're talking about a memory with 1,000,000 addressable locations, this means that the Quantum Memory might need to perform 1,000,000x as many operations compared to the classical case.

$\endgroup$
3
  • 1
    $\begingroup$ Could that reasoning be used to support that DSA with a large $p$ (say 8192 bit), 256-bit $q$, and Argon2 as the hash, can be expected to resist the (hypothetical) rise of CRQC longer than ECDSA with secp256r1 and SHA-256? $\endgroup$
    – fgrieu
    Sep 24, 2021 at 20:13
  • 1
    $\begingroup$ @fgrieu: well, with DSA and ECDSA, you'd use Shor's, rather than Grover's, and Shor's doesn't care what the hash is. On the other hand, from what we know of Shor's, ECDSA-P256 would appear to be rather easier than DSA-8192, largely because the elliptic curve operations would likely be cheaper than the corresponding mod p=8192 bit operations (not that I'd want to assume DSA-8192 is Quantum Safe...) $\endgroup$
    – poncho
    Sep 24, 2021 at 20:15
  • $\begingroup$ Thanks for the excellent answer! The speedup part (second bullet point) sounds counterintuitive, but indeed I get the same result if I work it out. For posterity: with some quantum computers (QCs) doing $2^{32}$ operations, each share is $\frac{2^{32}}{QCs}$ operations and each can do its share in $\sqrt{share}$ time. For 2 QCs, that's $2^{15.5}$ time whereas originally it would take 1 QC $2^{16}$ time: a speedup of less than two while using twice as many QCs. With 8 QCs the speedup is only 2.8×. That compounds until at 10'000 QCs, finally the speedup is 100× (each extra QC almost negligible). $\endgroup$
    – Luc
    Sep 24, 2021 at 22:15

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.