Will HMAC resist Grover's algorithm? If not, which MAC scheme will provide post-quantum security?


1 Answer 1


Yes, HMAC with a sufficiently long key will survive Grover's algorithm. Grover's algorithm breaks a cryptosystem with a $n$-bit key using $2^{n/2}$ (quantum) steps of computation. Therefore, in practice, a 128-bit key is likely to survive Grover's algorithm, and a 160-bit key almost surely will.

So, HMAC with a 160-bit key is safe against Grover's algorithm, and HMAC with a 128-bit key is almost certainly safe enough against Grover's algorithm for most purposes -- even assuming someone figures out how to build a working quantum computer.

  • $\begingroup$ does MD5 , SHA1 or SHA256 matter ? $\endgroup$
    – dwayn
    Commented Mar 29, 2013 at 8:11
  • 2
    $\begingroup$ @dwayn: Grover's algorithm really doesn't care what the hash function is. On the other hand, HMAC is often used with a key size that is the same size as the HMAC output; hence HMAC-MD5 would have a 128 bit key, while HMAC-SHA256 would have a 256 bit key. If these key sizes are used, then HMAC-MD5 (with a 128 bit key) might be vulnerable, but that's because of the keysize we often use with HMAC-MD5, and not anything inherent with it. $\endgroup$
    – poncho
    Commented Mar 29, 2013 at 15:04
  • $\begingroup$ @poncho HMAC can't be used with custom length keys ? $\endgroup$
    – dwayn
    Commented Mar 29, 2013 at 17:07
  • 1
    $\begingroup$ @dwayn: of course HMAC can be used with almost any key length you want; that's why I was careful to say "often used". On the other hand, if what you're interested in is attacking HMAC as used within TLS, HMAC-MD5 is potentially vulnerable to Grover's algorithm (because of the 128 bit key), while HMAC-SHA256 is safe (because the key there is 256 bits). Of course, if you're designing your own post-quantum crypto system, what TLS did is quite irrelevant. $\endgroup$
    – poncho
    Commented Mar 29, 2013 at 17:52

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.