# Practical quantum attacks on SHA256 MAC and HMAC

Is SHA256 MAC (or HMAC) vulnerable to any quantum attacks?

Game setup:

The attacker's goal is to produce a valid MAC to be accepted by other devices in the ecosystem. The ecosystem consists of many devices with a shared secret key (named "key). The attacker can query an oracle with messages and get MACs. The oracle only accepts 32 byte messages. Oracle queries are rate limited to 10ms. Can the attacker find "key" so that he can produce valid MACs faster than any classical attack.

MAC = H(message[32] | key[32])

• How does title's "practical" translate in the body? Isn't any quantum attack entirely theoretical, since none was ever made?
– fgrieu
Oct 16, 2018 at 17:56
• @fgrieu The previous question was about Grover's algorithm. I indicated that I didn't exactly know if HMAC would be vulnerable to that - I assume it is, but assumption... So I guess the question is: are there any known algorithms - such as Grover's algorithm - that would significantly bring down the security of HMAC-SHA256 assuming a quantum computer is available. We cannot do any better than that unless somebody builds a full functioning QC... Oct 16, 2018 at 21:39
• "practical" was used because oracle queries are rate limited so if the attack required 2^64 queries it is not practical. However if the attack doesn't require many queries to the oracle then oracle speed is irrelevant Oct 17, 2018 at 15:31

There are two points. First the MAC you are using is not HMAC and the way you construct it (first message than key as input without any padding) is only ok if you assume that a) the SHA2 compression function is a random oracle and that b) verifiers check that messages are no longer than 32 bytes. Otherwise one can forge messages at the cost of an intermediate inner state collision without learning key. Hence, it might be a safer choice to put key first, an even safer choice to additionally pad key to the block length (64 byte), and the safest choice to use HMAC from the start.

Second, quantum attacks: Of course you can run grover against this: Just collect, say three (message, tag)-pairs and build an oracle out of it that for a key $$k$$ outputs 1 if it maps all three messages to the respective tags. This function is a boolean function as needed by Grover. Hence, you can break this in $$\mathcal{O}(2^{128})$$ queries to SHA2. How long this actually takes is a different story and depends on the size of the quantum circuit to implement the boolean function.

Note that the rate limitation does not help in any way here as we only need sufficiently many pairs that there exists only one solution $$k$$ with sufficiently high probability.

Add-on: What is the probability that a key that works for two message tag pairs works for a third?

If we model $$SHA2-256(m \| k) = t$$ as a random function and assume we obtained pairs $$(m_1,t_1), (m_2,t_2)$$ which were computed using some key $$k$$ then the probability that a given key $$k' \neq k$$ maps $$m_1$$ to $$t_1$$ is $$2^{-256}$$. The probability that $$k'$$ maps $$m_1$$ to $$t_1$$ AND $$m_2$$ to $$t_2$$ is $$2^{-(2*256)}$$ and so on. (Here the 256 comes from the output length).

The probability that $$k'$$ does not map $$m_1$$ to $$t_1$$ AND $$m_2$$ to $$t_2$$ is $$(1-2^{-(2*256)})$$. The probability that all possible $$2^{256}-1$$ keys $$k'\neq k$$ do not map $$m_1$$ to $$t_1$$ AND $$m_2$$ to $$t_2$$ is $$(1-2^{-(2*256)})^{2^{256}-1}$$ (here the outer 256 exponent comes from the size of the key space). So, the probability that there exists a key $$k'$$ that maps $$m_1$$ to $$t_1$$ AND $$m_2$$ to $$t_2$$ is
$$1-(1-2^{-(2\cdot 256)})^{2^{256}-1} \approx \frac{2^{256}-1}{2^{2\cdot 256}}\approx 2^{-256}.$$

• ... the chance that we find an issue with the SHA-2 algorithm itself is much higher than the chance that we'll ever be able to perform $2^{128}$ operations of anything, parallel or not. We cannot prove SHA-256 secure, not even when it is used within HMAC, although it still looks pretty successful in defeating attacks so far. Oct 16, 2018 at 22:21
• The MAC is implemented by a hardware module which our software can only pass a 32 byte message and it returns a MAC. The message is internally combined in the chip with other information including the key. Oct 17, 2018 at 15:06
• I still have a question on attacking the MAC key. If you get [MAC1, MAC2] using message[1], [2] from the oracle and then use your quantum computer to find a key that matches both MACs what is the probability that key works for message[i] and MAC[i]? Its not clear to me this resolves to O(2^128). Don't need the format math but a little more logic why it is. The actual hashed data is defined by the chip (ATECC508A) and is this H(key[32] | message[32] | otherdata[20]) = MAC. otherdata is fixed value. Oct 17, 2018 at 15:26