How long should a HMAC cryptographic key be?

Question

In the top answer to this question the answerer says 'with a sufficently long key'.

I am using a SHA1-HMAC (may switch to SHA256-HMAC) algorithm to verify cookies sent to clients as authentication tokens haven't been tampered with. The cryptographic keys are rotated with a new one being generated every 24 hours. Keys are valid for 3 days (i.e. there are 3 keys used to sign cookies active at any one time) meaning if a user doesn't login for 3 days then there authentication token is invalidated.

I am using 32 character long random alphanumeric strings as the cryptographic keys, would this be considered 'sufficiently long enough'?

Answer 1

Hashes and therefore HMAC do not take alphanumeric characters as input. You'd first have to convert the textual "key" into bits. I've put "key" in quotes because keys for HMAC should consist of bits in the first place.

The recommendation for HMAC is (indeed) that the key size is identical to the output size (and the intermediate state for Merkle–Damgård based hashes). Now lets presume that the characters in the key are completely random and that a large enough alphabet is used, say base 64. In that case you'd have 32 * 6 = 192 bits of randomness. That's larger than the required 160 bits of randomness.

If we'd use a single byte per character encoding such as ASCII or Windows-1252 then you'd get 32 bytes. This is much smaller than the ipad or opad used in HMAC. This means that additional hashing is not required before XOR'ing the key with ipad or opad. You would even be able to use UTF-16 as long as you don't use characters that require more than 2 bytes to encode. Anything longer than 64 bytes will require an additional hash calculation.

---

Below the security requirements for the key, taken from section 3 of RFC 2104: HMAC: Keyed-Hashing for Message Authentication:

The key for HMAC can be of any length (keys longer than B bytes are first hashed using H). However, less than L bytes is strongly discouraged as it would decrease the security strength of the function. Keys longer than L bytes are acceptable but the extra length would not significantly increase the function strength. (A longer key may be advisable if the randomness of the key is considered weak.)

Keys need to be chosen at random (or using a cryptographically strong pseudo-random generator seeded with a random seed), and periodically refreshed. (Current attacks do not indicate a specific recommended frequency for key changes as these attacks are practically infeasible. However, periodic key refreshment is a fundamental security practice that helps against potential weaknesses of the function and keys, and limits the damage of an exposed key.)

Where H is of course the hash function, B the block size (64 bytes for SHA-1) and L the intermediate/output size (160 bits or 20 bytes).

---

Notes:

• HMAC doesn't break in any terrible way if your key has somewhat less entropy; anything above 128 bits is probably OK.
• Switching to SHA-256 is a good idea, even though it is not required to replace SHA-1 from a theoretical standpoint.

Answer 2

I am using 32 character long random alphanumeric strings as the cryptographic keys

First, I would suggest generating the keys differently. Cryptographic keys are not like passwords. There are specific requirements for the format of a cryptographic key, which depends on the algorithm.

In the case of AES, HMAC, and most other symmetric algorithms, the key should be a sequence of bytes (e.g. a byte[]) from a cryptographically secure random number generator. Most programming languages have an easy way of doing this, e.g. you can generate a 32-byte key with os.urandom(32) in Python or crypto.randomBytes(32) in Node.js.

It's not strictly necessary to use this approach with HMAC; HMAC can accept keys that are not uniformly random. There are benefits, however, to doing things properly. First, it's simpler than using a custom password generator (and simpler means less opportunity for bugs). Second, it makes it easy to measure the security level of the key (e.g. a 128-bit random key by definition has 128 bits of entropy). Third, it's more secure: when used with a proper random key, it's sufficient if HMAC is a secure PRF. When used with a password-like key instead, the PRF assumption is not sufficient, and we must rely instead on proofs in the keyed random oracle model. Using HMAC with password-like keys invalidates the assumptions used in many commonly cited security proofs.

TL;DR use a CSPRNG to generate random bytes, and use those bytes as the HMAC key.

Now, how long should that key be? 32 bytes (256 bits) is long enough, and any longer than that probably isn't useful.

Generally, cryptographic systems target a 128-bit security level (100 bits is a rough upper bound on what the combined resources of the entire human race might be able to crack with a brute force attack in a year, which still leaves a comfortable security margin). NIST suggests that an $n$-bit key has an $n$-bit security level (with some caveats, see source, p.14), but I disagree with this assessment.

NIST's recommendation is only accurate when a system is considered in isolation. If an attacker has many possible targets (e.g. many different companies that are worth attacking), she may be able to use a multitarget attack to crack multiple keys simultaneously, or a few keys using far less effort. For example, if the attacker knows $m$ and $\text{HMAC}(k_i, m)$ for $i$ from $1$ to $2^{40}$, and the keys $k_i$ are 128 bits each, cracking one of those keys will take about $2^{128-40}=2^{88}$ operations, implying a security level of 88 bits!

It's straightforward to defend against this attack. If you want $n$-bit security, use $2n$-bit HMAC keys. Since a 128-bit security level is best practice, use 256-bit (32-byte) keys.