1
$\begingroup$

I implemented AES-128 in CBC mode + HMAC-SHA-256 but it seems to me that 256 bit HMAC is more than necessary.

Can I truncate the output of HMAC-SHA-256 to a desired bit length?

And what is the minimum required length of it to match the security level of AES-128?

$\endgroup$
7
  • $\begingroup$ Yes, you can truncate the output of HMAC-SHA256, but one has to wonder: why? $\endgroup$ Oct 3, 2016 at 6:11
  • $\begingroup$ @Stephen Tousetfor that's for the sake of decreasing storage and network transfer costs. Assume that my app sends snippets of encrypted data over the internet constantly. $\endgroup$
    – user40602
    Oct 3, 2016 at 6:22
  • $\begingroup$ And what about minimum HMAC length? $\endgroup$
    – user40602
    Oct 3, 2016 at 6:24
  • $\begingroup$ Storage and network costs are on the order of cents per gigabyte. A billion untruncated HMACs will cost you a few dollars. The time it takes you just to implement anything as a result of answers to this question is likely to cost you what many trillions of untruncated HMACs would in bandwidth and storage costs. Is such a security tradeoff really worth your time and effort? $\endgroup$ Oct 3, 2016 at 6:39
  • $\begingroup$ @Stephen Touset ok I already decided to not truncate the hash, but please answer my the questions more scientifically if you can so I can learn something new that might be of use in some other time and place. Specifically I want to know what should be the minimum length of MAC tag to match the security level desired. How should we calculate it and why? $\endgroup$
    – user40602
    Oct 3, 2016 at 6:53

1 Answer 1

4
$\begingroup$

Can I truncate the output of HMAC-SHA256 to a desired bit length?

Yes, in fact, it's quite common to do so...

what is the minimum required length of it to match the security level of AES128?

Now, that's a hard question; I'll try to try to explain some of the reasons why it is subtle.

To break the privacy of an AES encrypted session, the hard part of the attack is performing a huge number of $X$ operations, where the huge number depends on the AES key size, and desired success probability (that is, the probability that the attack is actually successful); if we assume a 128 bit AES key, and a minimum acceptable success probability of $2^{-\delta}$, then the attacker will need to do at least $2^{128-\delta}$ $X$ operations. To break the integrity of an HMAC protected session (ignoring brute force attacks on the HMAC key), the hard part of the attack is performing a huge number of $Y$ operations, where the huge number depeonds on the transmitted HMAC size, and desired success probability; if we truncate the HMAC tag to $N$ bits, this requires at least $2^{N-\delta}$ $Y$ operations.

What's so hard about that? Well, the issue is that the cost of an $X$ operation and the cost of a $Y$ operation is not easily comparable; in most cases, a $Y$ operation is far costlier than an $X$; any analysis that ignores that is (IMHO) a gross oversimplification.

To break privacy, what we do is grab some ciphertext; the $X$ operation consists of selecting an AES key, and checking if that key works with the ciphertext (sometimes, it's a bit more complex than that, but that's the general idea).

To break integrity (again, ignoring brute force attacks on the HMAC key; we'll assume that key is at least 128 bits, so we can ignore that attack), what we do is format some ciphertext (which presumably decrypts to something the attacker would like inject), the $Y$ operation consists of selecting an HMAC tag value, sending the forged message and the HMAC tag value to the legitimate decryptor Bob, and seeing if Bob is fooled.

What's the difference between these two attacks? In the AES attack, once we've received the ciphertext, the attacker can perform the $X$ operation (the trial decryptions) without any interaction with the systems under attack; our attacker can rent out a large cloud space, grab a large botnet, or throw a large FPGA/ASIC farm at the problem, and we have no idea. In addition, this attack can be performed even when the session is over; the privacy concerns depend on how long the data will stay sensitive, and that's a property of the data, not the cryptography.

In contrast, in the HMAC attack, we need to get Bob (the legitimate receiver) involved for every single tag we come up with. If Bob will refuse to check no more than $2^{20}$ tags per second (possibly because that's the limit of what his hardware can do), there's absolutely nothing an attacker can do to speed up the attack. In fact, if Bob is reading the encrypted message from a storage device, well, he'll realize the storage device has been corrupted after a HMAC failure (which means that we get to do exactly one $Y$ operation. In addition, even if Alice and Bob use using the HMAC to protect encryption communication, Bob might just notice that the last billion messages all had invalid tags, and so might be able to deduce he's under attack. Thirdly, this attack can only be done while the session is up; once Alice and Bob have shut down the connection and are no longer communicating, we can no longer try to fool Bob.

Now, if we take the oversimplification that $X$ and $Y$ are approximately the same cost, then it's obvious from the above argument that 128 bit HMAC tags are quite sufficient (and we should use larger HMAC tags only if the larger tags are of essentially no cost). However, by the above argument, HMAC tags can be safely truncated even more; exactly how far it would be safe would depend on the details of the system.

$\endgroup$
1
  • $\begingroup$ and what about offline attacks? suppose I encrypt some files with AES128+HMAC and store them somewhere. I don't want some guy be able to modify my file even blindly that can't be detected. Is birth day paradox relevant here too? I mean we nead at least 256 bit HMAC to achieve the same security level as AES128. $\endgroup$
    – user40602
    Oct 4, 2016 at 5:08

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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