I was watching this video by veritasium, https://www.youtube.com/watch?v=-UrdExQW0cs I'm curious on whether or not a quantum computer could break a hash function.
I'm not really sure how hash functions work, any help would be appreciated. Please don't throw any complicated terms at me, I'm not very educated in this topic.
TL/DR - some hash functions are insecure against a quantum computer, but many other commonly used hash functions are likely not broken with a quantum computer.
Indeed there are some cryptographic hash functions based on number-theoretical problems, such as $x^2\pmod N$, that can be exponentially broken with a quantum computer. Here, $N$ is the product of two large prime numbers $N=p_1\times p_2$, and $x$ is a binary representation of the string to be hashed. Knowledge of the secret pair $(p_1,p_2)$ is enough to invert the hash; a quantum computer could run Shor's algorithm to factor $N$ and hence learn the pair $(p_1,p_2)$.
But, as explained by @Callum, many commonly used cryptographic hash functions such as SHA256 are only known to be susceptible to brute-force style attacks. A quantum computer does give a speedup against such brute-force attacks, but "only" a square-root, Grover style speedup.
It's an interesting problem to know precisely how much structure is needed to get an exponential speedup to crack hash functions.
Hash functions work by taking an input message $x$ and obscuring the message so that the output $y=H(x)$ is such that the contents of $x$ are hidden from potential adversaries. To give an example $x$ could be a password which is hashed before being stored in a database.
There are several properties a useful hash function should have but perhaps the most obvious is that $H$ is hard to invert. This provides security as an adversary cannot simply undo the hash and read the message.
You can imagine performing some sort of brute force attack on hashed data (see this paper) by essentially evaluating $H$ on many possible input messages until some condition is satisfied. For instance if we know what a hashed password looks like we can try out many possible passwords under a certain length and try to get a matching hash.
Some unstructured search problems can in theory receive a quadratic speedup from Grover’s algorithm. So in the case of password cracking perhaps you could get a speedup in the brute force search with Grover's algorithm.
I should emphasise that even if you could speed up this brute force search the gain is not at all like the near exponential speedup from cracking RSA with Shor's algorithim. So overall I would be a bit skeptical of how useful this gain would be in practice for real world attacks on hashing.
