Equivalent key size between HMAC and AES?

Question

I have seem comparison between AES and RSA, e.g., AES 128 bit key is equivalent to RSA modulus 3072 bits. Is there such comparison between AES key size and HMAC?

Answer 1

NIST specifies the paired hash digest size beat least twice the key size of AES, therefore:

• AES-128 is paired with at least SHA-256 or SHA-512/256

• AES-192 is paired with at least SHA-384

• AES-256 is paired with SHA-512

• SHA3 hash functions will be added to the list in the future

The reason being that the collision and preimage resistance of the hash function are not weaker than the AES key strength. Don't be the weak link in the chain if you will.

When used with HMAC or as part of a digital signature scheme, the security strength is generally not less than half the digest size, which means digests twice the size of the block cipher key. As poncho notes the state size of the hash is also relevant, in all cases the state size for these functions is at least twice the digest size, so that should also not be the weak link.

Additionally in a digital signature scheme based on ECC (with prime curves), the same 2X security generally applies, a 256-bit curve gives 128-bit security, so a curve operation on a hash will have the security of either the hash or the curve, whichever is weaker. Having them be the same size ensures the same security level. NIST specifies several curves to match the standard security strengths.

All of these strengths assume there is no shortcut attack on the hash, and for the SHA-2 family, none are known on the full hash function when used in a scheme aware of its limitations (such as a length extension attack).

Answer 2

Well, there are two potential key recovery attacks against HMAC (assuming a reasonable hash function):

• Brute force the key; that is, take a valid (Message, MAC) pair, and try every possible key, and look for a key that gives that MAC for that Message

• Brute force the internal hashing state immediately after processing the IPAD/OPAD; here, you would take a valid (Message, MAC) pair, and try every possible key, and look for a key that gives that MAC for that Message

Now, for first attack would take $O(2^k)$ time (for a key size of $k$); the second attack would take $O(2^{2n})$ time (if the hash function had an internal state size of $n$ bits).

With realistic key sizes and hash functions, $2^k < 2^{2n}$; hence the best attack is an exhaustive search of the key space; this gives us the same approximate strength as AES for a given key size.