Subject: [Cfrg] MACs: to truncate or not to truncate?

From: Florent Bersani <[email-masked]>
Date: Fri, 16 Apr 2004 16:26:27 +0200

Hi,

Sorry to bother you with a somewhat naive question I stumbled across
while trying to work on an EAP method (EAP is RFC 2284 revised by
2284bis) .

In short, many modes of operation of block ciphers that provide
authentication (e.g. OMAC) allow for a variable MAC tag length. Yet,
recommendation on how to choose the tag length does not seem to be
given - apart perhaps very briefly in the first draft of NIST SP
800-38b Table 2. Maybe such a recommendation is deemed to be trivial or
a matter of taste... Unfortunately for the profane and young engineer I
am, this point is not totally trivial and I would be more than happy if
you could confirm (or correct) my current understanding:

For instance with OMAC1 and AES-128 (the assumption here is hence that
I am using a 128 bit key and 128 bit block cipher - whether this is
appropriate or not could be discussed in another naive question ;-)),
the recommended tag length would be 96 bits (the choice had to be made
between 1 and 128).

Indeed

Truncating appears to be a good idea (but we should not truncate
below 64)

96 bits should provide enough security margin against the MAC
guessing attack

96 bits is aligned on 32 bit boundaries ;-)

Any feedback would be most welcome,

Florent

The reference I consulted before daring to turn to the CFRG are:

"Handbook of Applied Cryptography" by Menezes et al.:  "Remark
9.60 (truncated MAC outputs) Exhaustive attack may,
depending on the unicity distance of the MAC, be precluded
(information-theoretically) by using less than n bits of the final
output as the m-bit MAC. (This must be traded off against an increase
in the probability of randomly guessing the MAC: 2^−m.) For m = 32 and
E
= DES, an exhaustive attack reduces the key space to about 224
possibilities. However, even for m < n, a second text-MAC pair
almost
certainly determines a unique MAC key."

HMAC (RFC 2104 or the companion papers available at
http://www-cse.ucsd.edu/users/mihir/papers/hmac.html) by Bellare et
al.: "Remark 4.8 Preneel and van Oorschot  recommend outputting only
half of the bits of the hash output as the authentication tag. This
recommendation is motivated by the fact that forgery attacks are anyway
doable with complexity 2^l/2 through birthday attacks (see Section 6),
and that by outputting only half of the bits these attacks require more
chosen messages. Carrying this recommendation to our constructions
would require the assumption that the compression function with
truncated output (e.g., only the l/2 most significant bits of output)
constitutes a secure MAC. Whether this is acceptable or not depends on
the assumed properties of the particular compression function in use.
(The tradeoff here is that by outputting less bits the attacker has
less bits to predict in a MAC forgery but, on the other hand, the
attacker also learns less about the output of the compression function
from seeing the authentication tags computed by the legitimate
parties.)Applications for which a saving in the MAC length is important
can adopt our constructions with a reduced output of (at least) l/2
bits"

"MDx-MAC and building fast MACs from hash functions" by Preneel
and
van Oorschoot (quoted by HMAC)

A thread of the IPsec mailing list archive
(http://www.netsys.com/ipsec/1997/msg00194.html) started by H. Krawczyk
and containing a very nice summary by Bart Preneel
(http://www.netsys.com/ipsec/1997/msg00202.html)

The pretty recent RFC 3566 specifying "The AES-XCBC-MAC-96
Algorithm and Its Use With IPsec" which contains a discussion in
section 4.3 on truncation and 96 bits: AES-XCBC-MAC produces a 128-bit
authenticator value. AES-XCBC-MAC-96 is derived by truncating this
128-bit value as described in [HMAC] and verified in [XCBC-MAC-2]. For
use with either ESP or AH, a

truncated value using the first 96 bits MUST be supported. Upon
sending, the truncated value is stored within the authenticator field.
Upon receipt, the entire 128-bit value is computed and the

first 96 bits are compared to the value stored in the authenticator
field. No other authenticator value lengths are supported by
AES-XCBC-MAC-96. The length of 96 bits was selected because it is the
default authenticator length as specified in [AH] and meets the
security requirements described in [XCBC-MAC-2]." Unfortunately, I did
not find [XCBC-MAC-2]: Rogaway, Phil, email communications, October
2001 :-(

My main fears are that

I didn't understand right the nice references I read

Some references may be outdated (though I did not find any recent
paper that would infirm them)

_______________________________________________
Cfrg mailing list
[email-masked]
https://www1.ietf.org/mailman/listinfo/cfrg

---

From: Uri Blumenthal <[email-masked]>
Date: Fri, 16 Apr 2004 13:12:57 -0400

The length should be reasonably large so that an attacker cannot guess 
the MAC etc., and at the same time reasonably enough MAC bits should be 
concealed so that the attacker cannot verify his guess of the key. Note 
the word "reasonably".

MAC of 96 bits of 128-bit string is considered OK.

Florent Bersani wrote:

> 800-38b Table 2. Maybe such a recommendation is deemed to be trivial 
> or a matter of taste... Unfortunately for the profane and young 
> engineer I am, this point is not totally trivial and I would be more 
> than happy if you could confirm (or correct) my current understanding:
>
>     * Truncating appears to be a good idea (but we should not truncate
>       below 64)
>     * 96 bits should provide enough security margin against the MAC
>       guessing attack
>     * 96 bits is aligned on 32 bit boundaries ;-)
>
>     * "Handbook of Applied Cryptography" by Menezes et al.: "Remark
>       9.60 (truncated MAC outputs) Exhaustive attack may, depending on
>       the unicity distance of the MAC, be precluded
>       (information-theoretically) by using less than n bits of the
>       final output as the m-bit MAC. (This must be traded off against
>       an increase in the probability of randomly guessing the MAC:
>       2^-m.) For m = 32 and E = DES, an exhaustive attack reduces the
>       key space to about 224 possibilities. However, even for m < n, a
>       second text-MAC pair almost certainly determines a unique MAC key."
>     * HMAC (RFC 2104 or the companion papers available at
>       http://www-cse.ucsd.edu/users/mihir/papers/hmac.html) by Bellare
>       et al.: "Remark 4.8 Preneel and van Oorschot recommend
>       outputting only half of the bits of the hash output as the
>       authentication tag. This recommendation is motivated by the fact
>       that forgery attacks are anyway doable with complexity 2^l/2
>       through birthday attacks (see Section 6), and that by outputting
>       only half of the bits these attacks require more chosen
>       messages. Carrying this recommendation to our constructions
>       truncated output (e.g., only the l/2 most significant bits of
>       output) constitutes a secure MAC. Whether this is acceptable or
>       not depends on the assumed properties of the particular
>       compression function in use. (The tradeoff here is that by
>       outputting less bits the attacker has less bits to predict in a
>       MAC forgery but, on the other hand, the attacker also learns
>       less about the output of the compression function from seeing
>       the authentication tags computed by the legitimate
>       parties.)Applications for which a saving in the MAC length is
>       important can adopt our constructions with a reduced output of
>       (at least) l/2 bits"
>     * "MDx-MAC and building fast MACs from hash functions" by Preneel
>       and van Oorschoot (quoted by HMAC)
>     * A thread of the IPsec mailing list archive
>       (http://www.netsys.com/ipsec/1997/msg00194.html) started by H.
>       Krawczyk and containing a very nice summary by Bart Preneel
>     * The pretty recent RFC 3566 specifying "The AES-XCBC-MAC-96
>       section 4.3 on truncation and 96 bits: AES-XCBC-MAC produces a
>       128-bit authenticator value. AES-XCBC-MAC-96 is derived by
>       truncating this 128-bit value as described in [HMAC] and
>       verified in [XCBC-MAC-2]. For use with either ESP or AH, a
>       sending, the truncated value is stored within the authenticator
>       field. Upon receipt, the entire 128-bit value is computed and the
>       first 96 bits are compared to the value stored in the
>       authenticator field. No other authenticator value lengths are
>       supported by AES-XCBC-MAC-96. The length of 96 bits was selected
>       because it is the default authenticator length as specified in
>       [AH] and meets the security requirements described in
>       [XCBC-MAC-2]." Unfortunately, I did not find [XCBC-MAC-2]:
>       Rogaway, Phil, email communications, October 2001 :-(
>
> My main fears are that
>
>     * I didn't understand right the nice references I read
>     * Some references may be outdated (though I did not find any
>       recent paper that would infirm them)
>
> _______________________________________________ Cfrg mailing list 
> [email-masked] https://www1.ietf.org/mailman/listinfo/cfrg

---

From: Scott Fluhrer <[email-masked]>
Date: Fri, 16 Apr 2004 10:49:56 -0700 (PDT)

> concealed so that the attacker cannot verify his guess of the key. Note

While I agree with the first point, I am a bit confused about the second.
A MAC key will, in general, be used to authenticate several messages.
That being the case, an attacker can still verify his guess of the key,
by checking if that key works with the truncated MACs found in several
captured messages.

For example, consider the case that we have a MAC of 96 bits with a 128
bit string.  Then, if the attacker has two known good message/MAC pairs,
then he can verify a key guess.  If a guessed key generates the correct 96
bit truncated MAC for both messasges, then it is almost certainly the
right key.  In this example, if we assume the MAC acts as a random
function, then there is a probability of about 2**-64 that there exists a
second key that will generate the same two MACs.

---

From: "David A. McGrew" <[email-masked]>
Date: Fri, 16 Apr 2004 11:15:54 -0700

Florent,

> while trying to work on an EAP method (EAP is RFC 2284 revised by 

since it is EAP, I assume that the use of the MAC is for entity 
authentication.  I expect that you don't care about the amount of 
bandwidth taken up by the MAC value, and just want to maximize the 
security that it provides.

Also, if you are writing an Internet Draft, please let us know the 
timetable on which you need to get comments back.

>  For instance with OMAC1 and AES-128 (the assumption here is hence 
> that I am using a 128 bit key and 128 bit block cipher - whether this 
> is appropriate or not could be discussed in another naive question 
> ;-)), the recommended tag length would be 96 bits (the choice had to 
> be made between 1 and 128).

There are really two issues here: 1) what is the security level that 
you need from your MAC, and 2) how do the security properties of the 
MAC degrade as the tag length is reduced.  For OMAC, which is a 
pseudorandom function if I recall correctly, you don't need to worry 
about the second issue.  96 bits is a widely accepted security level 
for MACs, though I don't know of any citation that formally justifies 
this conventional wisdom (perhaps someone else does).

>
>  Indeed
>
> 	‧ 	Truncating appears to be a good idea (but we should not truncate 
> below 64)
> 	‧ 	96 bits should provide enough security margin against the MAC 
> guessing attack
>
> 	‧ 	96 bits is aligned on 32 bit boundaries ;-)

This seems sound to me.  You could always cite some established 
specifications that recommend that tag size.  Though if you don't care 
about how many bits the tags take up, you might consider not truncating 
at all (unless the MAC recommends truncating for a security reason).

Will your specification only cover the use of a single MAC, or do you 
need to write guidelines that will cover the use of any choice of MAC?

>  The reference I consulted before daring to turn to the CFRG are:

Thanks for providing so much background!

David

> 	‧ 	"Handbook of Applied Cryptography" by Menezes et al.:  "Remark 
> 9.60 (truncated MAC outputs) Exhaustive attack may, depending on the 
> unicity distance of the MAC, be precluded (information-theoretically) 
> by using less than n bits of the final output as the m-bit MAC. (This 
> must be traded off against an increase in the probability of randomly 
> guessing the MAC: 2^-m.) For m = 32 and E = DES, an exhaustive attack 
> reduces the key space to about 224 possibilities. However, even for m 
> < n, a second text-MAC pair almost certainly determines a unique MAC 
> key."
> 	‧ 	HMAC (RFC 2104 or the companion papers available at 
> recommendation is motivated by the fact that forgery attacks are 
> anyway doable with complexity 2^l/2 through birthday attacks (see 
> Section 6), and that by outputting only half of the bits these attacks 
> require more chosen messages. Carrying this recommendation to our 
> constructions would require the assumption that the compression 
> function with truncated output (e.g., only the l/2 most significant 
> bits of output) constitutes a secure MAC. Whether this is acceptable 
> or not depends on the assumed properties of the particular compression 
> function in use. (The tradeoff here is that by outputting less bits 
> the attacker has less bits to predict in a MAC forgery but, on the 
> other hand, the attacker also learns less about the output of the 
> compression function from seeing the authentication tags computed by 
> the legitimate parties.)Applications for which a saving in the MAC 
> length is important can adopt our constructions with a reduced output 
> of (at least) l/2 bits"
> 	‧ 	"MDx-MAC and building fast MACs from hash functions" by Preneel 
> 	‧ 	A thread of the IPsec mailing list archive 
> 	‧ 	The pretty recent RFC 3566 specifying "The AES-XCBC-MAC-96 
> 	‧ 	I didn't understand right the nice references I read
>
> 	‧ 	Some references may be outdated (though I did not find any recent

---

From: Florent Bersani <[email-masked]>
Date: Fri, 16 Apr 2004 20:40:56 +0200

Hi David,

Many thanks for your answer!

Some more in-line.

BR,
Florent

David A. McGrew wrote:

> authentication.

Correct and I am also willing to provide a protected communication 
channel thanks to an AEAD mode of operation (EAX for now since, for 
instance, OMAC is already used for entity authentication), thus I have 
another tag length to choose

>   I expect that you don't care about the amount of bandwidth taken up 
> by the MAC value, and just want to maximize the security that it 
> provides.

You are right

> timetable on which you need to get comments back.

The draft I am writing is IMHO totally immature as of now to be worth 
reading. I'll however let you know of it very much in advance when I 
find it decent (with the associated review time-line) and be more than 
happy to get your comments.

FYI, right now, the words "protected communication channel" and my 
background (I believe in avoiding to invent something new when 
unnecessary, especially in cryptography) prompted me to investigate 
thoroughly if the existing protocols (TLS, IKEv2) could not fit... and I 
am still investigating this issue (there is indeed an EAP-TLS RFC which 
could be extended to support password/shared keys thanks to the work 
done in TLS and an EAP IKEv2 I-D is proposed)

> this conventional wisdom (perhaps someone else does).

OK

>
>>
>>  Indeed
>>
>>     ¡E     Truncating appears to be a good idea (but we should not 
>> truncate below 64)
>>     ¡E     96 bits should provide enough security margin against the 
>> MAC guessing attack
>>
>>     ¡E     96 bits is aligned on 32 bit boundaries ;-)
> specifications that recommend that tag size.

Like IPsec AH ;-)

>   Though if you don't care about how many bits the tags take up, you 
> might consider not truncating at all (unless the MAC recommends 
> truncating for a security reason).

That's my whole naive question: if I want the "better" security with my 
tag, what should I do (maybe refine what I mean by "better" security 
;-))? Truncate or not truncate?

> need to write guidelines that will cover the use of any choice of MAC?

Well, I was wondering indeed if such guidelines would not be useful to 
the community, though I was only concerned with my specification... but 
what's been done some place might be useful to others, isn't it? If any 
support (e.g. editing or investigating more deeply the matter), I am 
volunteering to give a hand!

---

From: "The Purple Streak, Hilarie Orman" <[email-masked]>
Date: Fri, 16 Apr 2004 13:43:30 -0600

A 96-bit MAC will have a collision in about 2^48 usages.  That seems too
high for many applications.  If one can guarantee a key change reasonably
often, 96-bits is probably OK.

Why truncate a MAC at all?  This is a murky area.  If there is some
possibility of an attacker obtaininig information that constrains the
key space, truncation is a defense.  But should this happen in a
Properly Designed System?  I'd hope not.

I think that without knowing the exact algorithm used to generate the
MAC, one cannot say much about whether or not truncation is a help or
hindrance.  It is an interesting question for theorists, but I think
that IETF guidance should be that the value should not be truncated to
less than 128 bits unless there's a good reason, and in no case less
than 96 bits.

Hilarie

---

From: Gé Weijers <[email-masked]>
Date: Fri, 16 Apr 2004 13:22:19 -0700

Florent,

It's all a matter of simple counting. Assuming the key of the MAC 
function is long enough to make brute-force search infeasible, and the 
MAC is a good PRF you just determine:

   1. the level of security you want to achieve, e.g. the chance of the
      adversary getting access should be less than, say, one in a 1000
      million (10**9)
   2. the number of guesses the adversary can make during the lifetime
      of the key, e.g. 100 guesses per second for 5 years, about
      15778800000 guesses

You then simply multiply the two, and see how many bits you need: 10**9 
* 15778800000 = 15778800000000000000. log_2(15778800000000000000) = 
63.77, so 64 bits should do it for guessing attacks. The overly prudent 
engineer then could add some bits to compensate for mistakes in his 
assumptions :-)

The other types of known attacks do not seem very relevant:

    * brute force key search does not depend on the size of the MAC value
    * shortcut attacks require you to capture 2^(n/2) valid
      authentication exchanges, which means that you'd be
      reauthenticating at dizzying rates, and your adversary needs to
      have more than a zettabyte (10^21 bytes) worth of storage by the
      time you store and index all that. This is mindboggingly unrealistic.
    * even if someone would come up with a birthday or other attack
      against the MAC with complexity O(2^(n-2)) you're likely safe for
      a long time.

 From a practical point of view anything from 64 bits on is large enough 
that the bad guys will think of a different way to get you (such as 
bribe your sysadmin).

Ge'

-- 
Gé Weijers                          mailto:[email-masked]
Installation and Linux Group        Tel: (877)240-7611 x69536
Sun Microsystems, Inc.              Fax: (877)240-7611
=== Expressed opinions are my own, I do not speak for Sun ===

---

From: Scott Fluhrer <[email-masked]>
Date: Fri, 16 Apr 2004 14:31:12 -0700 (PDT)

On Fri, 16 Apr 2004, The Purple Streak, Hilarie Orman wrote:

> high for many applications.

What is the significance of a MAC collision?  If the attacker knows that
two messages A and B were both generated by the sender and happen to have
the common MAC value M, what can he do with that information?

Another approach that an attacker could try is to take 2^48 valid
messages A_i with MAC tags M_i.  If he always has a pile of 2^48 bogus
messages B_j, then there is likely to be a pair of messages A_i,B_j that
have a common MAC value.  However. since he doesn't have the MAC key, he
can't determine which ones they might be.  He might grab MACs M_i, attach
them to random B_j's and hope to get lucky, but that doesn't have any
advantage over picking MACs at random.

> If one can guarantee a key change reasonably

-- 
scott

---

From: [email-masked] (David Wagner)
Date: Fri, 16 Apr 2004 21:07:33 +0000 (UTC)

>high for many applications.

Why?  Collisions aren't a problem for a MAC; you can't use them to
break the message authentication property.  A MAC is different from
an unkeyed hash in this respect.

(Now, *internal* collisions are indeed a problem, due to the Wiener
and van Oorschot attack.  Consequently, a hash with a 96-bit internal
chaining value would be a questionable choice.  However, I presume
we're talking about taking a MAC with a large internal chaining variable,
like MD5-HMAC or SHA1-HMAC, and truncating its output.  In that case,
truncating to 96 bits should be fine.)

>is an interesting question for theorists, but I think

I disagree.  Truncating SHA1-HMAC to 96 bits is fine, and there's
no reason to spread fear or uncertainty about it.

(One can even prove that it's fine, under reasonable assumptions about
the SHA1 internal compression function.  Under appropriate assumptions,
SHA1-HMAC is a PRF, and truncating a PRF is harmless.)

---

From: Greg Rose <[email-masked]>
Date: Sat, 17 Apr 2004 08:17:54 +1000

>often, 96-bits is probably OK.

While I agree with the correctness of your comment, I'm not at all sure 
that it represents a problem. For most usages of MACs, collisions simply 
aren't a threat. After all, a collision just means that the attacker gets 
to substitute a message that has the same MAC tag, when he was already able 
to substitute a (recorded) message that had a different MAC tag.

Similarly, the probablility of a forgery succeeding doesn't depend on 
collisions, so a k-bit MAC still gives a 2^k protection.

Of course if Florent had presented a threat analysis ;-), we might be able 
to tell whether collisions represent a threat or not. If they do, 96 bits 
is clearly inadequate. But I'd go so far as to say that in almost all cases 
collisions are not a threat to usage of MAC functions.

>Properly Designed System?  I'd hope not.

Agreed; truncation of a MAC is usually driven by bandwidth requirements, 
not cryptographic considerations. A MAC is pure overhead...

>less than 128 bits unless there's a good reason, and in no case less

Maybe. Attacks on MACs generally fall into two classes:
1. attacks that can be performed offline, on the NS... err... attacker's 
supercomputer farm. Brute forcing the key is the usual example, unless the 
underlying algorithm is badly broken.
2. Adaptive forgery attacks, which usually require oracle-style assistance 
from the entity being attacked. Now it's pretty much a given that I will 
not add server capacity to a machine that's dropping 99.9% of the incoming 
packets.

I believe that, absent any algorithmic weakness, MACs can be much shorter 
and still provide a formidable barrier to attack. For example, the 
authentication MAC introduced in the old analog mobile phones was only 18 
bits, but where used, it completely stopped all over-the-air fraudulent 
calls. (No, I'm not advocating only 18 bits; but there's a much better 
return on your investment buying lottery tickets, even at 18 bits. The 
brute-force attack on the 64-bit key was more likely to pay off, though.)

For per-packet MACs, I think 96 bits is total overkill. For authentication, 
I'd go for the full 128 bits.

Greg.

Greg Rose                                       INTERNET: [email-masked]
Qualcomm Australia          VOICE:  +61-2-9817 4188   FAX: +61-2-9817 5199
Level 3, 230 Victoria Road,                http://people.qualcomm.com/ggr/
Gladesville NSW 2111    232B EC8F 44C6 C853 D68F  E107 E6BF CD2F 1081 A37C

---

From: "The Purple Streak, Hilarie Orman" <[email-masked]>
Date: Fri, 16 Apr 2004 16:16:34 -0600

>  the common MAC value M, what can he do with that information?

An attacker could corrupt the integrity of a system by playing back a
value in a context not expected by the victim.  If the victim is using
MACs as an index, he'll take the bogus value.  This assumes the victim
is not aware of the collision, because he only keeps a subset of
the MACs.

Hilarie

---

From: Jack Lloyd <[email-masked]>
Date: Fri, 16 Apr 2004 18:40:07 -0400

> is not aware of the collision, because he only keeps a subset of

How is this different from a simple message replay?

-J

---

From: [email-masked] (David Wagner)
Date: Sat, 17 Apr 2004 01:41:31 +0000 (UTC)

The Purple Streak, Hilarie Orman wrote:
>value in a context not expected by the victim.

That's only exploitable if the attacker can predict in advance which
pair of messages will cause a collision.  With an unkeyed hash, the
attacker can predict.  With a MAC, the attacker can't (at least, not
using the standard birthday attack).  Therefore, birthday attacks are
not a problem for MACs.  There is no problem with using a 96-bit MAC,
if the MAC is otherwise secure.

---

From: [email-masked]
Date: Sat, 17 Apr 2004 13:51:36 -0400

Back in 1995 I helped design a system in which we used secret key MACs to
validate URLs, so web clients couldn't mess with our servers' minds.
We used 128 bit MACs, and XOR'd the halves together to get to 64 bits
and XOR'd the halves again to get to 32 bits.  Was that a bad design
or just pointless?  Was the result better or worse than truncating to
32 or 64 bits?  We didn't expect to get more than 32 or 64 bits of protection.

If it matters, we used MD5 with HMAC and 128 bit keys.

-Larry

---

From: "The Purple Streak, Hilarie Orman" <[email-masked]>
Date: Mon, 19 Apr 2004 10:17:11 -0600

>  if the MAC is otherwise secure.

Depends on what you mean by exploitable.  Simply getting any invalid
data accepted by the victim is enough to corrupt some systems.

Hilarie

---

From: "David A. McGrew" <[email-masked]>
Date: Mon, 19 Apr 2004 13:56:57 -0700

Hilarie,

I think that there's some confusion here because you have a model in 
mind that is different from the conventional one used with MACs;  I 
mean the one in which there is a tag generation function and a tag 
verification function, and the latter takes as inputs the secret key, a 
message, an authentication tag, and maybe a nonce.  If I understand you 
correctly, you have in mind a model in which an authentication tag is 
used as a 'shorthand' for the entire message.  In this system, there 
wouldn't be a verification function, but instead a lookup function, 
which takes as inputs a key and an authentication tag, and which 
returns the message corresponding to the tag.  Is this right?  Such a 
system would require collision resistance, as you point out.   But then 
again, it is different from the typical use of a MAC.

David

---

From: [email-masked] (David Wagner)
Date: Mon, 19 Apr 2004 21:32:17 +0000 (UTC)

The Purple Streak, Hilarie Orman wrote:
>David Wagner writes:
>>  pair of messages will cause a collision.
>

No, it doesn't.

Look, work out the details.  Try it.  You'll find that with a
96 bit MAC, there's no way an attacker can trick the victim into
accepting invalid data, unless the attacker sends about 2^96 packets.

Here's my definition of exploitable: If the receiver ever accepts
(as valid) any data that was not actually transmitted or authorized
by the sender, then the scheme is broken.  This is a very conservative
definition.  For instance, if you can get the victim to accept invalid
data, you've broken the MAC.  And, even under this strong definition,
birthday collisions pose no threat.

Summary: Birthday attacks are not a problem.  Truncating SHA1-HMAC
to 96 bits is safe and reasonable.

---

From: Alex Alten <[email-masked]>
Date: Tue, 20 Apr 2004 00:30:05 -0700

At 08:17 AM 4/17/2004 +1000, Greg Rose wrote:

>For per-packet MACs, I think 96 bits is total overkill. For 
>authentication, I'd go for the full 128 bits.

Heck, 32 bits is probably more than good enough for a per-packet MAC, when 
it's in-flight life-time is usually less than a second.

- Alex

--

Alex Alten
[email-masked]
925-425-9601

---

From: Florent Bersani <[email-masked]>
Date: Tue, 20 Apr 2004 16:33:31 +0200

Well, since I am (very) new to cryptography, please consider my reply 
with the utmost caution! (*)

 From a theoretical point of view, if you MAC is a PRF, then xor-folding 
will do no harm to this property, hence your MAC security bound (which 
is classically related to the PRF advantage, see e.g. Mihir Bellare, Joe 
Kilian, and Phillip Rogaway, "The security of the cipher block chaining 
message authentication code", Journal of Computer and System Sciences 
(JCSS), vol. 61, no. 3, Dec 2000, pp. 362-399. Earlier version in CRYPTO 
'94. Available at http://www.cs.ucdavis.edu/~rogaway/papers/index.html) 
will only degrade as if you truncated the MAC, i.e. AdcMAC <= AdvPRF + 
2**(-taglength)

 From a practical point of view, I bet that the effect of your 
xor-folding regarding shortcut attacks (internal collision) is quite 
similar to truncation (making internal collision search require more 
chosen messages).

Hope this helps,

Florent

(*) Two reasons made me reply:
1) No expert had replied so far
2) It is a good opportunity to see if I have started to understood my 
reading ;-)

---

From: [email-masked] (David Wagner)
Date: Tue, 20 Apr 2004 16:54:07 +0000 (UTC)

>it's in-flight life-time is usually less than a second.

The time-of-flight of a packet shouldn't matter.  The relevant time
constant is the lifetime of the system, measured in packets.  If I
can send 2^32 packets to your system within its lifetime, and if you
use a 32-bit MAC, I can probably cause one invalid packet to be accepted.
Either you do the security analysis to figure out whether that's acceptable,
or you make your MAC large enough that you don't have to worry about
invalid packets being accepted.

---

From: Henrick Hellström <[email-masked]>
Date: Wed, 21 Apr 2004 23:14:59 +0200

Alex Alten wrote:

>>   (1-2^-31) * v > 2^-31 * c
>>
>> where:
>>
>>   v: the value of sending packets with a 32 bit MAC instead of a larger
>>   c: the expect loss associated with acceptance of a forge packet.
> 
> 
> Unfortunately v and c are usually hard to specify with any precision.

No, I don't think it is.

Suppose, for instance, that I am sending bills to the head office over a 
DSL line and I pay a fixed amount each month to my ISP. The value of c 
is determined by the total amount we have on the account we use for 
paying these bills. The value of v is zero since there is no cost 
associated with the difference between using a 32 bit MAC and using a 
128 bit MAC. The inequality is false.

The inequality might have been true if I had used a dial-up connection. 
It would be fairly simple calculation to make.

---

From: Alex Alten <[email-masked]>
Date: Thu, 22 Apr 2004 02:42:03 -0700

>invalid packets being accepted.

Right.  It's a a classic security vs engineering tradeoff.  If one needs to 
protect 2^32
packets in the lifetime of the system then use a larger MAC.  Otherwise don't
transmit more than, say, 2^16 packets.

--

Alex Alten

---

From: Alex Alten <[email-masked]>
Date: Wed, 21 Apr 2004 13:55:54 -0700

At 03:56 PM 4/20/2004 +0200, Henrick Hellström wrote:
>Alex Alten wrote:
>>Heck, 32 bits is probably more than good enough for a per-packet MAC, 
>>when it's in-flight life-time is usually less than a second.
>
>The "in-flight life-time" is irrelevant, given that a truncated MAC is 
>used. The only question is if the following inequality is true:
>
>The thing is that v might be (practically) zero (if there are no direct 
>transmission costs and transmission time is not an issue), and that 
>entails that the inequality is false even if c is relatively small. Or in 
>plain English: If sending a 128 bit MAC isn't a problem, then just do it.

If you are sending something like 10,000 packets per second down a
TCP/IP data link, then a small MAC is ok, especially just for access
control.  Also a 128-bit MAC may cost too much time per packet or
use up too much packet header space, the usual engieering vs security
tradeoffs.

- Alex
--

Alex Alten

---

From: Greg Rose <[email-masked]>
Date: Thu, 22 Apr 2004 23:50:59 +1000

At 02:42 AM 4/22/2004 -0700, Alex Alten wrote:
>Right.  It's a a classic security vs engineering tradeoff.  If one needs 
>to protect 2^32

But you seem to have missed the whole thrust of the discussion... no such 
birthday limit applies. And anyway, "good" packets don't count. The 
lifetime of the system should be limited by the number of "bad" packets the 
attacker gets to send before being kneecapped; that's why ATM cards can get 
away with 4 digit PINs. If there's some way to throttle failed attempts, 
relatively small MACs might well suffice. That's why you need the threat 
analysis.

Greg.

---

From: Daniel Brown <[email-masked]>
Date: Thu, 22 Apr 2004 11:35:48 -0400

> to 96 bits is safe and reasonable.

Just curious, can somebody summarize (again?) answers to: 

a) Are there any security advantages to truncating an (H)MAC value (say to 
96 bits), or is it just a performance advantage?  (I've seen arguments 
that not using all MAC bits hides something from some adversaries, is this 
so?)

b) Is truncating to 80 bits also "safe and reasonable", just like 96 bits? 

c) When speaking of security levels, e.g. 80-bit vs 128-bit, what level 
does SHA1-HMAC-96 have?  Does SHA1 limit security of HMAC to 80 bits? If 
not, does 96-bit truncation limit security to 96 bits?  If not, does 
SHA1-HMAC-96 have 128 or 160 bits of security?

d) In some schemes, e.g. DHAES and KEM-DEM, the MAC serves an auxiliary 
role to provide confidentiality, i.e. IND-CCA2 security.  Extreme MAC 
truncating, say to 32 bits, undermines IND-CCA2 security, doesn't it? 
(Maybe IND-CCA1 is not affected?) Does this carry over to any other uses 
of a MAC?

Thanks in advance,

        Dan

---

From: [email-masked] (David Wagner)
Date: Thu, 22 Apr 2004 18:41:51 +0000 (UTC)

Ok, here are my opinions.

Daniel Brown  wrote:
>96 bits), or is it just a performance advantage?

I don't know of any significant security advantages to truncating
SHA1-HMAC, assuming SHA1 has no weaknesses.  (If SHA1 does have
weaknesses, we should change hash functions, not try to patch it
up with truncation.)

>b) Is truncating to 80 bits also "safe and reasonable", just like 96 bits? 

It is as safe and reasonable as any ideal 80-bit MAC.  If an 80-bit
MAC is good enough for your application, then SHA1-HMAC-80 should be
good enough.

As you know, if you shorten the MAC too much, it will become feasible
to forge packets.  The exact length needed will depend on a detailed
threat analysis of your particular system.

>SHA1-HMAC-96 have 128 or 160 bits of security?

What do you mean by "security level"?  Some might consider the notion of a
"security level" a little bit of an oversimplification.

Anyway, the answer will depend on what kind of attack you're worried
about.  Let me assume you're using SHA1-HMAC-96 with a 160-bit key.
Then the best key-recovery attack known takes about 2^160 work.  The best
message-forgery attack known needs to send about 2^96 packets.  So,
if I had to pick a number, I'd say that calling it "96-bit security"
probably is the least distortion.

But, that doesn't mean that you can directly compare SHA1-HMAC-40 to a
scheme with a 40-bit key.  2^40 offline trial encryptions may well be
a lot cheaper to perform than sending 2^40 packets, so SHA1-HMAC-40
(with a 160-bit key) might be stronger than a scheme with a 40-bit key.

>truncating, say to 32 bits, undermines IND-CCA2 security, doesn't it? 

Yes.

>Does this carry over to any other uses of a MAC?

Yes.  Almost any time you want confidentiality, you really need a MAC
(whether you realize it or not).  Therefore, truncating the MAC will
likely undermine confidentiality.

For instance, IPSec requires that if you use encryption, you should also
use a MAC.  That's for a very good reason: Bellovin found all sorts of
nasty attacks if you omit the MAC.  Therefore, truncating IPSec's MAC to,
say, 32 bits would be a real mistake; it would put both integrity and
confidentiality at risk.

---

From: Daniel Brown <[email-masked]>
Date: Fri, 23 Apr 2004 17:11:46 -0400

David, William: thanks so much for the answers. 

I have more questions.

> probably is the least distortion.

Is it fair to extend your reasoning to say that HMAC-SHA1-160 has "160-bit 
security" and HMAC-SHA1-80 has "80-bit security"? If so, does HMAC-SHA1-80 
with AES-128 undermine 128-bit confidentiality, whereas HMAC-SHA1-160 does 
not? 

William's attack on HMAC-SHA1-160 uses only 2^80 MAC generation queries to 
find a MAC forgery, right? If so,  does HMAC-SHA1-160 have at most "80-bit 
security"?  Or, can we use a different "exchange rate" for online queries, 
so that the 2^80 MAC generation queries are regarded as a "160-bit" cost 
in the attack? 

The security level of HMAC-SHA1 may well depend on the "exchange rate" 
between off-line and on-line work (as well as MAC generation vs 
verification queries, and treatment of failed verifications), but wouldn't 
a conservative, and maybe "oversimplified", answer would take the worst 
security rating over all exchange rates?  I agree that a more aggressive 
rating could be used with application-specific detailed threat analysis.

Has anybody ever formally studied the security of HMAC-SHA1-80 vs 
HMAC-SHA1-160, or is it just "folklore" that one is better than, as good 
as, or worse than the other? 

Anyway, am I right to infer that "80-bit security" is the most 
conservative rating for both HMAC-SHA1-80 and HMAC-SHA1-160?  What's the 
most conservative rating for HMAC-SHA1-96 or HMAC-SHA1-128?  What are the 
ratings under other "reasonable", but more aggressive, exchange rates? Is 
there a simple characterization of some useful situations when these more 
aggressive ratings are safe to use (instead of going through an analysis 
for every application)?

> say, 32 bits would be a real mistake; it would put both integrity and

So, the suggestions on this mailing list to a 32-bit MAC for per-packet 
protection may be inappropriate if the packet payloads are encrypted, but 
may be fine if the packets are plaintext?