Can Grover's (or similar) algorithm be used to attack AES-128 when used in cipher modes like CTR? It seems like the answer is no... Also I have a similar question for SHA256 when used for a MAC. It looks like using quantum attacks on SHA256-MAC would only produce only a parallel key that generates a collision for a single MAC value. So the recovered key would be of no real value then right?

The question stems from my use of secure hardware elements for key storage and for AES. The elements support only AES-128-mode and SHA256 MAC. So I am being asked if we should consider updating the modules in future designs. This is an embedded product where cost and power are limited.


Sure, you can use Grover's algorithm to attack AES-128 in CTR mode. Assume the attacker knows a few plaintext blocks and the counter. The AES ciphertext blocks that are generated by encrypting this counter and XOR'ing it with the plaintext. In that case the input and output of the AES-128 block cipher are known and Grover's attack can be applied (as if AES-ECB was used).

Similarly SHA-256 in HMAC mode could well fall for Grover's attack. But Grover's attack only halves the security of the symmetric algorithms. That means that for SHA-256 you would still be left with 128 bits of security for most situations.

However, SHA-512 is actually faster on 64 bit architectures than SHA-256, so it seems a good idea to use that if you can spare the space (and otherwise SHA-512/256 exists as well). Note that later Intel and AMD CPUs may contain Intel SHA-1 and SHA-256 instructions that offer hardware accelleration. So the performance of SHA-256 is much higher, easily beating SHA-512, if those instructions are utilized.

So yes, AES-128 could fall to Grover's attack and although HMAC-SHA256 is considered pretty secure, it does make sense to at least design your protocol in such a way that future updates to the protocol are a possibility. Although there is no pressing need to change from AES-128 or HMAC-SHA256, in general you want your algorithms to be configurable for different versions of the protocol.

The only reason to switch now is to make sure that captured sessions cannot be decrypted in the future. In that case you may also have to look at the way the session keys are calculated. Asymmetric algorithms, for instance, are much more vulnerable to QC crypt-analysis. So if you're dealing with that level of confidentiality you should switch to AES-256 as soon as possible.

  • $\begingroup$ Could you describe the attack on SHA256 MAC more. The attack on AES-128-CTR makes sense after thinking about it more, but I'm still not clear on SHA. So if the attacker knows message and MAC for MAC = H(key | m[32]). Wouldn't the attacker only find a key' but not key? And yes I mean MAC not HMAC. The hardware module enforces the length limit so length extension is not possible so the module just uses MAC to save time and power. $\endgroup$ – big_fish_small_pond Oct 15 '18 at 20:25
  • $\begingroup$ I don't have an explicit attack on HMAC-SHA256 based on Grover's attack. I therefore said "could", only to continue explaining that it doesn't matter since attacks with a complexity of $2^{128}$ are practically impossible. Now AES-128 is vulnerable, so if you want to protect against attacks in the far future, you should definitely switch to AES-256. $\endgroup$ – Maarten Bodewes Oct 16 '18 at 8:41
  • $\begingroup$ Related question: Which MAC scheme is quantum resistant?. Feel free to ask a separate question on how Grover's algorithm could be used on HMAC - I'm kind of curious myself as well, but I would have to read up on it first. $\endgroup$ – Maarten Bodewes Oct 16 '18 at 8:43
  • 1
    $\begingroup$ "However, SHA-512 is actually faster on 64 bit architectures than SHA-256" On my Ryzen laptop SHA-256 is about five times faster (!) than SHA-512. $\endgroup$ – Fanael Oct 16 '18 at 16:16
  • 1
    $\begingroup$ @forest I'm using sha256rnds2, which is an instruction that does two SHA-256 rounds, my CPU simply has hardware accelerated SHA-256 but not SHA-512. $\endgroup$ – Fanael Oct 20 '18 at 22:13

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.