Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It only takes a minute to sign up.
Sign up to join this community
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?
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.
