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)?

  • 3
    $\begingroup$ 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. $\endgroup$ – Maeher May 17 '13 at 15:36
  • $\begingroup$ @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. $\endgroup$ – D.W. May 18 '13 at 6:13
  • $\begingroup$ 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. $\endgroup$ – Maeher May 18 '13 at 9:57
  • 1
    $\begingroup$ I learned something new today en.wikipedia.org/wiki/Asymptotic_security $\endgroup$ – goodguys_activate 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.

  • $\begingroup$ 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? $\endgroup$ – goodguys_activate May 17 '13 at 16:16
  • 1
    $\begingroup$ 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. $\endgroup$ – Watson Ladd May 17 '13 at 23:34
  • $\begingroup$ forgot to ping @Watson for requested edit $\endgroup$ – Michael Jun 20 '13 at 19:26
  • $\begingroup$ @WatsonLadd Do you have some reference for this observation on AES-GCM? $\endgroup$ – Paŭlo Ebermann Jun 23 '13 at 10:44
  • 1
    $\begingroup$ 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. $\endgroup$ – Watson Ladd Jun 23 '13 at 20:14

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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