# Which MAC scheme is quantum resistant?

will HMAC survive Grover algorithm ? if not then which MAC scheme provide post-quantum security ?

-

## 1 Answer

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.

-
does MD5 , SHA1 or SHA256 matter ? –  dwayn Mar 29 '13 at 8:11
@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. –  poncho Mar 29 '13 at 15:04
@poncho HMAC can't be used with custom length keys ? –  dwayn Mar 29 '13 at 17:07
@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. –  poncho Mar 29 '13 at 17:52