# When truncating an AES MAC value by “w” , how do I justify that “w” is still negligible?

I'm taking an online class on cryptography at corsera.org / Stanford, and the professor is explaining that it's OK to truncate an AES MAC to $w$ bits as long as $1/2^w$ is still negligible (say $w > 63$)

• Where did the value $1/2$ come from?

• How is 64 and above negligible?

• What is non-negligible today (5/17/2013) and in the future (5/17/2020)?

-
That's a misuse of the term negligible. Negligibility is defined for functions. (Roughly the function is dominated by the inverse of any polynomial for large enough input values.) No constant non-zero function (such as $2^{-63}$) can ever be negligible. – Maeher May 17 '13 at 15:36
@Maeher, I have a different take. I think it's a perfectly reasonable use of the term. Outside of complexity theory, the standard engineering meaning of the term "negligible" is "so small it can be safely ignored/safely treated as zero". That seems to apply fine here. – D.W. May 18 '13 at 6:13
That may be the case, but in the area of cryptography it is very uncommon to use the term outside of the context of asymptotic security. – Maeher May 18 '13 at 9:57
I learned something new today en.wikipedia.org/wiki/Asymptotic_security – LamonteCristo May 18 '13 at 14:29

One of the factors that determines how hard it is to forge a MAC for a given message is how long the MAC is. If it's 1 bit long, you can definitely produce the correct MAC in two tries.

$2^n$ is the number of possible bit-strings of length $n$; $1/2^n$ is the probability that any random bit-string happens to be the MAC (of length $n$) for a given message and key.

Negligible depends on what you're protecting with your MAC, who your attacker is, and what information / oracles they have access to. In particular, if the attacker has to make some kind of service request to a single point to check that a MAC is valid, $2^{64}$ is an awful lot of requests – this is probably the assumption being made when it was stated that MACs of length 64 or more are secure.

Not all MACS can be truncated safely however. AES-GCM loses more security than expected by truncation, but HMAC is fine.

Given a MAC construction that can be safely truncated, truncating it to 128 bits is unlikely to pose a problem for a long time ($\gg$2020), for any attacker capability.

-
Is it correct for me to think/say "negligible in terms of brute forcing". Does negligible apply to any other attack other than brute forcing? – LamonteCristo May 17 '13 at 16:16
You were doing so well until the last sentence. Poly1305 and AES-GCM cannot be truncated, due to algebraic properties they have despite being information theoretically secure. – Watson Ladd May 17 '13 at 23:34
Thanks Watson, please do edit the answer. – Michael May 18 '13 at 9:53
forgot to ping @Watson for requested edit – Michael Jun 20 '13 at 19:26
csrc.nist.gov/groups/ST/toolkit/BCM/documents/comments/CWC-GCM/… Because of the nature of the polynomial authenticator, there is a security gap that increases for small authenticator sizes. $p(x)$ has $d$ roots, so the chance of picking one is $d/q$ where $q$ is the field size. Here $q=2^k$, and so for small $k$ this is a bigger gap proportionally. – Watson Ladd Jun 23 '13 at 20:14