Will HMAC resist Grover's algorithm? If not, which MAC scheme will provide post-quantum security?
$\begingroup$
$\endgroup$
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
4
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.
-
-
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$– ponchoCommented Mar 29, 2013 at 15:04
-
$\begingroup$ @poncho HMAC can't be used with custom length keys ? $\endgroup$– dwaynCommented 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$– ponchoCommented Mar 29, 2013 at 17:52