Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

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

share|improve this question
add comment

1 Answer 1

up vote 4 down vote accepted

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.

share|improve this answer
    
does MD5 , SHA1 or SHA256 matter ? –  dwayn Mar 29 '13 at 8:11
2  
@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
1  
@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
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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