Subject: [saag] How long should a MAC be?

From: Phillip Hallam-Baker <[email-masked]>
Date: Wed, 11 Jul 2012 21:07:16 -0400

Yeah, yeah, digests, birthday attack, yadda yadda.

But! A MAC is not a digest, it is an authentication mechanism. If I
use HMAC-SHA256 with a 128 bit key, I am going to have no more than
128 bits of ergodicity in my output. So what is the justification for
presenting more than 128 bits?

Now I guess someone can argue (OK they will) that HMAC-SHA256 with a
256 bit key produces a full 256 bits of ergodicity in the output. But
given that we have agreed on 128 bits as 'sufficient' for encryption
keys (well for the lifetime of this universe at least) why then demand
up to 512 for authentication?

I know that there are perfectly good reasons for using AES-256, it is
not really the possibility of brute forcing the key that is the issue
so much as the fact that AES-512 has many more rounds than AES-128 and
is stronger. And when someone like Adi Shamir suggests AES might be a
little over-optimized, well I listen.

What this comes down to is that I think we need a HMAC-SHA128 and
maybe people who are really looking for 256 bits of authentication
should be cutting HMAC-SHA512 in two...

Just a thought.

-- 
Website: http://hallambaker.com/

---

From: Eric Rescorla <[email-masked]>
Date: Wed, 11 Jul 2012 18:37:14 -0700

> presenting more than 128 bits?

I am unaware of one, provided, of course, that the MAC is in fact
as strong as its output length. Obviously, if there are weaknesses
in the MAC, all bets are off. Certainly one could design MACs that
were secure at 256 bits but not 128 [0] but I don't know of any
evidence that HMAC-SHA256 is such a MAC.

-Ekr

[0] Consider the MAC HMAC-SHA-256X which is produced by taking
the HMAC-SHA256 output and zeroing the first 128 bits.

---

From: Nico Williams <[email-masked]>
Date: Wed, 11 Jul 2012 20:49:41 -0500

Phillip,

Kerberos uses 96-bit HMAC-SHA1 for the AES 'enctypes' (ciphersuites).
See RFC3962, where nothing much is said about the MAC length (but
RFC2104 does have text on truncation of HMAC); you might want to ask
the authors of RFC3962 and/or other RFCs that also use truncated MACs.

In order to foil a MAC (forge a message) an attacker would have to
compute not only a modification of the MACed text that collides with
the original, but collides with the original under the same secret key
presumed not known to the attacker.  Moreover, an attack on the MAC is
requires interaction with the receiver, while hash collision attacks
are off-line.  This is much harder than looking for a mere hash
collision.  Also there's no question of recovering plaintext from the
MAC (particularly if you encrypt-then-MAC) without pre-image attacks,
and as long as the MAC and encrypt keys are not the same (such that
key recovery attacks on the MAC can't be used to attack the
ciphertext).

I think this means that effective MAC sizes can be somewhat shorter
than the MAC keys, at least if what you're concerned about is
forgeries.  As for key recovery attacks, any such attack with less
complexity than forgery will be... a better forgery attack in the
first place; on the flip side forgery attacks facility
better-than-brute-force key recovery attacks, so the key had better
not be the same as, say, encryption keys.  The active forgery attacks
on HMAC require 2^(L/2) messages assuming a strong hash function and
where L is the hash output length in bits, which I think means you
want L to be longer than 64 bits.  In some protocols (if you re-key
often, say) I think you can get away with significantly shorter MACs,
and UMAC-32 has been used.

In short, yes, I think you can get away with shorter-than-key-length
MACs, and still retain meaningful security, with the caveats that MAC
keys should be different from encryption keys, and if the MAC is
really short, then you should probably have additional defenses in the
protocol and/or implementation to protect against active forgery
attacks.

Nico
--

---

From: Phillip Hallam-Baker <[email-masked]>
Date: Thu, 12 Jul 2012 09:54:27 -0400

Quite, I suspect that if people really had the motivation that they
could brute force 64 bit keys right now, 80 bits of a strong cipher is
almost certainly safe even against heroic measures. But most of us
want to have something of a safety margin.

It is easy to show how 96 bits is likely to be more than adequate for
IPSEC. It is only being used for transport layer integrity checking.
Even if an attacker could break 96 bits, it is hard to imagine a case
where it would be worth doing so for a single packet and even if it
was worth doing, the break would have to be accomplished in the time
before the IP connection timed out.

That logic does not apply to Kerberos type schemes unless the tickets
are relatively short lived, that is days rather than years.

I know that the fashion has been to use public key for long lived
keys, but there are advantages to limiting the number of public key
operations to the bare minimum necessary to establish a trust context.
Public key operations are very hard to implement in ways that avoid
potential leakage of the key. Symmetric operations are much less
leaky. It is much harder to spot a single gate flipping on a 64 bit
CPU than a modular multiplication being performed during a modular
exponentiation.

On Thu, Jul 12, 2012 at 7:54 AM, Peter Gutmann
<[email-masked]> wrote:
> Nico Williams <[email-masked]> writes:
>
>>Kerberos uses 96-bit HMAC-SHA1 for the AES 'enctypes' (ciphersuites). See
>>RFC3962, where nothing much is said about the MAC length (but RFC2104 does
>>have text on truncation of HMAC); you might want to ask the authors of
>>RFC3962 and/or other RFCs that also use truncated MACs.
>
> There really ought to be some FAQ on this because it keeps on coming up: 96-
> bit MACs are used for IPsec cargo-cult purposes, because 96 bits was all that
> would fit in an IPsec header.  Other protocols blindly copied it on the
> assumption that the number 96 had some sort of magical properties.
>
> Please keep this response on file for when the question comes up again in
> 12-18 months.
>
> Peter.
>

---

From: Richard L. Barnes <[email-masked]>
Date: Thu, 12 Jul 2012 15:15:03 -0400

> presenting more than 128 bits?

The 128 bits of entropy (FTFY) might not be evenly distributed though the output bits of the MAC function.  You would need to evaluate the algorithm to determine the entropy each section of the output in order to determine which portion of the output is sufficient.

--Richard

---

From: Eric Rescorla <[email-masked]>
Date: Thu, 12 Jul 2012 16:00:22 -0700

> The 128 bits of entropy (FTFY) might not be evenly distributed though the output bits of the MAC function.  You would need to evaluate the algorithm to determine the entropy each section of the out…

This is of course true, but if that were true for a given MAC. it
would likely imply that the MAC was
weaker than the design strength.

-Ekr

---

From: Dan Brown <[email-masked]>
Date: Thu, 12 Jul 2012 23:32:29 +0000

Maybe some of the HMAC security proofs don't work if HMAC is truncated.  We could ask CFRG or Bellare.

----- Original Message -----
From: Phillip Hallam-Baker [mailto:[email-masked]]
Sent: Wednesday, July 11, 2012 09:07 PM
To: [email-masked] <[email-masked]>
Subject: [saag] How long should a MAC be?

Just a thought.

-- 
Website: http://hallambaker.com/
_______________________________________________
saag mailing list
[email-masked]
https://www.ietf.org/mailman/listinfo/saag

---------------------------------------------------------------------
This transmission (including any attachments) may contain confidential information, privileged material (including material protected by the solicitor-client or other applicable privileges), or constitute non-public information. Any use of this information by anyone other than the intended recipient is prohibited. If you have received this transmission in error, please immediately reply to the sender and delete this information from your system. Use, dissemination, distribution, or reproduction of this transmission by unintended recipients is not authorized and may be unlawful.

---

From: Eric Rescorla <[email-masked]>
Date: Thu, 12 Jul 2012 16:38:41 -0700

Given that Bellare is a co-author on RFC 2104 and 2104 describes truncation,
I would certainly be sad to learn truncation wasn't OK.

-Ekr

---

From: Dan Brown <[email-masked]>
Date: Thu, 12 Jul 2012 23:51:05 +0000

I expect truncation is OK. My point was that a truncated MAC is perhaps not (as) provably secure (because extra assumptioms may be needed).

Maybe 2104 does not mandate truncation for this very reason.

----- Original Message -----
From: Eric Rescorla [mailto:[email-masked]]
Sent: Thursday, July 12, 2012 07:38 PM
To: Dan Brown
Cc: [email-masked] <[email-masked]>; [email-masked] <[email-masked]>
Subject: Re: [saag] How long should a MAC be?

-Ekr

---

From: Hugo Krawczyk <[email-masked]>
Date: Thu, 12 Jul 2012 21:05:47 -0400

> I would certainly be sad to learn truncation wasn't OK.

No reason to be sad, Eric.

The text for HMAC truncation in RFC 2104 (see below) still holds.
Confidence in this mechanism is even stronger today given the proofs (and
practical acceptance) of HMAC as a pseudo-random function [1,2,3]. This
means that any subset of t bits from HMAC's output should be
computationally indistinguishable from t random bits, therefore suitable
for MAC (the security should be considered the minimum between the length
of the MAC and the security of HMAC, typically given by half the size of
the hash length).

[1] M. Bellare, R. Canetti, and H. Krawczyk, "Keying Hash Functions for
Message Authentication", Crypto 1996.

[2] M. Bellare, R. Canetti, and H. Krawczyk, "Pseudorandom Functions
Revisited: The Cascade Construction", Proceedings of FOCS'96.

[3] M. Bellare "New Proofs for NMAC and HMAC: Security without
Collision-Resistance", Crypto 2006.

Here is the original text from the RFC

 5. Truncated output

   A well-known practice with message authentication codes is to
   truncate the output of the MAC and output only part of the bits
   (e.g., [MM, ANSI]).  Preneel and van Oorschot [PV] show some
   analytical advantages of truncating the output of hash-based MAC
   functions. The results in this area are not absolute as for the
   overall security advantages of truncation. It has advantages (less
   information on the hash result available to an attacker) and
   disadvantages (less bits to predict for the attacker).  Applications
   of HMAC can choose to truncate the output of HMAC by outputting the t
   leftmost bits of the HMAC computation for some parameter t (namely,
   the computation is carried in the normal way as defined in section 2
   above but the end result is truncated to t bits). We recommend that
   the output length t be not less than half the length of the hash
   output (to match the birthday attack bound) and not less than 80 bits
   (a suitable lower bound on the number of bits that need to be
   predicted by an attacker).

Hugo

> > This transmission (including any attachments) may contain confidential
> information, privileged material (including material protected by the
> solicitor-client or other applicable privileges), or constitute non-public
> information. Any use of this information by anyone other than the intended
> recipient is prohibited. If you have received this transmission in error,
> please immediately reply to the sender and delete this information from
> your system. Use, dissemination, distribution, or reproduction of this
> transmission by unintended recipients is not authorized and may be unlawful.

---

From: Dan Brown <[email-masked]>
Date: Fri, 13 Jul 2012 01:21:10 +0000

So, in terms of security levels, does what RFC 2104 says mean that HMAC-SHA256 provides 256-bit security, while truncating to 128 bits provides 128-bit security? Or does HMAC-SHA256 only provide 128 security?

From: Hugo Krawczyk [mailto:[email-masked]]
Sent: Thursday, July 12, 2012 09:05 PM
To: Eric Rescorla <[email-masked]>
Cc: Dan Brown; [email-masked] <[email-masked]>; [email-masked] <[email-masked]>
Subject: Re: [saag] How long should a MAC be?

The text for HMAC truncation in RFC 2104 (see below) still holds. Confidence in this mechanism is even stronger today given the proofs (and practical acceptance) of HMAC as a pseudo-random function [1,2,3]. This means that any subset of t bits from HMAC's output should be computationally indistinguishable from t random bits, therefore suitable for MAC (the security should be considered the minimum between the length of the MAC and the security of HMAC, typically given by half the size of the hash length).

[1] M. Bellare, R. Canetti, and H. Krawczyk, "Keying Hash Functions for Message Authentication", Crypto 1996.

[2] M. Bellare, R. Canetti, and H. Krawczyk, "Pseudorandom Functions Revisited: The Cascade Construction", Proceedings of FOCS'96.

[3] M. Bellare "New Proofs for NMAC and HMAC: Security without Collision-Resistance", Crypto 2006.

 5. Truncated output

Hugo

On Thu, Jul 12, 2012 at 4:32 PM, Dan Brown <[email-masked]<mailto:[email-masked]>> wrote:
> From: Phillip Hallam-Baker [mailto:[email-masked]<mailto:[email-masked]>]
> To: [email-masked]<mailto:[email-masked]> <[email-masked]<mailto:[email-masked]>>
> [email-masked]<mailto:[email-masked]>
> [email-masked]<mailto:[email-masked]>
_______________________________________________
saag mailing list
[email-masked]<mailto:[email-masked]>
https://www.ietf.org/mailman/listinfo/saag

---

From: Hugo Krawczyk <[email-masked]>
Date: Thu, 12 Jul 2012 23:37:18 -0400

RFC 2104 doesn't say what the security of SHA256 (or of any other function)
is.

There is one fact, however, that does not depend on the underlying function
(or even on HMAC): a MAC tag of length t, even a perfect one, does not give
more than t bits of security  as the attacker can guess the MAC value with
probability 2^{-t} (and of course the attacker's advantage increases
linearly with the number of MACed messages or the number of possible
guesses by the attacker).

Hugo

On Thu, Jul 12, 2012 at 9:21 PM, Dan Brown <[email-masked]> wrote:

>  So, in terms of security levels, does what RFC 2104 says mean that
> HMAC-SHA256 provides 256-bit security, while truncating to 128 bits
> provides 128-bit security? Or does HMAC-SHA256 only provide 128 security?
>
>
>
>  *From*: Hugo Krawczyk [mailto:[email-masked]]
> *Sent*: Thursday, July 12, 2012 09:05 PM
> *To*: Eric Rescorla <[email-masked]>
> *Cc*: Dan Brown; [email-masked] <[email-masked]>; [email-masked] <
> [email-masked]>
> *Subject*: Re: [saag] How long should a MAC be?
>

---

From: Dan Brown <[email-masked]>
Date: Fri, 13 Jul 2012 17:28:28 +0000

Regarding HMAC security levels, NIST says [4] that HMAC-SHA1 provides 128 bit security and HMAC-SHA256 provides 256-bit security (presumably with a 256-bit key).

Hugo, would you agree?  Are these levels supported by proofs?  Do the recent SHA-1 collision-algorithms affect this?

In your reference [1], Remark 4.8 discusses truncation, but seems to suggest equivalent security for a half-length truncated HMAC, citing from Section 6 a 128-bit (birthday) attack on HMAC-SHA256 (regardless of truncation).  Section 6 would suggest that un-truncated HMAC-SHA256 can only provide 128-bit security.   But, on the other hand, this attack requires obtaining 2^128 MAC tags, so the attack is very impractical.  Is the attack so impractical that one can ignore and deem HMAC-SHA256 as providing 256-bit security (as NIST does)?

Regarding provable security, as it understand it, the proof in [1] and Remark 4.6, implies that truncated HMAC is secure if the truncated compression function is a secure as MAC.  The MAC-security of the (truncated) compression function itself is not proven (or is it later in Bellare’s follow-up work?), but of course we may still have confidence in it.

Also, hasn’t the weak collision resistance property, upon which [1] relies, for SHA-1 been undermined?

Menezes and Koblitz [5, Section 4] note that the advantage of tag truncation in some cases might not be as much as previously thought.

***

Phillip originally asked about the need for HMAC-SHA256, and specifically mentioning the MAC tag length, but his question could also be taken as a question for the need for 256-bit security vs. 128-bit security.  Let’s suppose that 128-bit security is sufficient.  Some reasons for opting for a higher security level (at least for HMAC) include the following.

-Margin of error, in case the algorithms end up being weaker than one would think (e.g. MD5, SHA-1).

-Resistance to quantum computers (either now or in the future).  Future adversaries cannot forge MACs today, but if all the keys are 128 bits, they can, at a cost about 2^64 quantum computer steps, recover a MAC keys from the message and tag, and then recover the master key from the MAC is often derived, and then recover the encryption key, and thereby compromise any of today’s ciphertexts that they have stored.

-Multi-user security (see [5, Sections 2.2 and 4], reduces the security bits by the log of the number of users.

***

Based on the considerations above, and general prudence, for 128-bit security and HMAC (if one cannot use an alternative MAC, e.g. CMAC), I’d recommend HMAC-SHA256, but with a key larger than 128 bits (to address multi-user attacks).  It seems just fine to me truncate to 128 bits (i.e. my intuition says the margin of error provided by that SHA-256 using 256 bits instead of 128, i.e. a wide pipe, during the internal computations, is sufficient.)

References

[4] http://csrc.nist.gov/publications/nistpubs/800-57/sp800-57_part1_rev3_general.pdf

[5] http://eprint.iacr.org/2012/074

Appendix

Just for fun: if one allows super-long messages defined by a formula, then active HMAC forgery is easy. (Martijn Stam showed me this, hope I got it right.)  Let B be any message block.  Let n = 2^256, integer (with ^ = exponentiation).  Let M = B^n, bit string (with ^ = repeated concatentation).  Let M’ = B^(n+n!),  (with ! = factorial).  Of course, these messages are absurdly long, and illegally long for most definitions of HMAC, and infeasible to compute the HMAC tags of.  Anyway, notice that HMAC(K,M) = HMAC(K,M’), for all keys K.  To see this, think about Pollard rho.  Starting from the key, each block B applies the same function.  The n iterations move this function into a cycle.  The extra n! cycles wrap around the cycle.  For the active forgery, get the MAC signer to compute the T=HMAC(K,M).  Then present the T and M’ to a MAC verifier, who will accept T as valid even though the MAC signer never authenticated M’.  By the way, proofs must resist such absurdities, which I think they all do rather easily, by limiting the message length or number of compression function queries.

Sorry for the length of this email.

Daniel Brown

Research In Motion Limited

From: [email-masked] [mailto:[email-masked]] On Behalf Of Hugo Krawczyk
Sent: Thursday, July 12, 2012 11:37 PM
To: Dan Brown
Cc: [email-masked]; [email-masked]; [email-masked]
Subject: Re: [saag] How long should a MAC be?

RFC 2104 doesn't say what the security of SHA256 (or of any other function) is.

There is one fact, however, that does not depend on the underlying function (or even on HMAC): a MAC tag of length t, even a perfect one, does not give more than t bits of security  as the attacker can guess the MAC value with probability 2^{-t} (and of course the attacker's advantage increases linearly with the number of MACed messages or the number of possible guesses by the attacker).

Hugo
On Thu, Jul 12, 2012 at 9:21 PM, Dan Brown <[email-masked]<mailto:[email-masked]>> wrote:
So, in terms of security levels, does what RFC 2104 says mean that HMAC-SHA256 provides 256-bit security, while truncating to 128 bits provides 128-bit security? Or does HMAC-SHA256 only provide 128 security?

From: Hugo Krawczyk [mailto:[email-masked]<mailto:[email-masked]>]
Sent: Thursday, July 12, 2012 09:05 PM
To: Eric Rescorla <[email-masked]<mailto:[email-masked]>>
Cc: Dan Brown; [email-masked]<mailto:[email-masked]> <[email-masked]<mailto:[email-masked]>>; [email-masked]<mailto:[email-masked]> <[email-masked]<mailto:[email-masked]>>
Subject: Re: [saag] How long should a MAC be?

 5. Truncated output

---

From: Paul Hoffman <[email-masked]>
Date: Fri, 13 Jul 2012 11:02:30 -0700

> Regarding HMAC security levels, NIST says [4] that HMAC-SHA1 provides 128 bit security and HMAC-SHA256 provides 256-bit security (presumably with a 256-bit key). 

This is a possibly incorrect reading of that document. The table you are referring to, Table 3 on page 65, also says HMAC-SHA1 provides 80 and 112 bits of strength. A better reading of the table is that HMAC-SHA1 provides at least 128 bits, but fewer than 192 bits, of strength. Notice that NIST did not put in a row for 160 bits.

--Paul Hoffman

---

From: Hugo Krawczyk <[email-masked]>
Date: Fri, 13 Jul 2012 20:17:27 -0400

See below.

On Fri, Jul 13, 2012 at 1:28 PM, Dan Brown <[email-masked]> wrote:

>  Regarding HMAC security levels, NIST says [4] that HMAC-SHA1 provides
> 128 bit security and HMAC-SHA256 provides 256-bit security (presumably with
> a 256-bit key).  ****
>
> ** **
>
> Hugo, would you agree?  Are these levels supported by proofs?  Do the
> recent SHA-1 collision-algorithms affect this?
>

I am not an expert in cryptanalysis so I would not express an opinion on
the  current strength of any particular function.
What the NIST text seems to indicate is the strength of the keyed
compression function underlying the SHA family when used as a PRF. This
security is usually conjectured to be the same as the length of the hash
(which is both the length of the key and the output of the compression
function). Hence 160 bits for SHA-1, 256 for SHA2-256, etc. Cryptanalysis
in last years has shown that this level of "perfect security" may be a bit
optimistic but nothing, as far as I know, that would require a major review
of these numbers (but, as said, this is not my area of expertise)

As for proofs, they all relate the strength of HMAC to the strength of the
underlying compression function. The security degrades quadratically with
respect to the number of applications of the (compression) function, hence
the birthday-type bounds that you mention below.

> ****
>
> ** **
>
> In your reference [1], Remark 4.8 discusses truncation, but seems to
> suggest equivalent security for a half-length truncated HMAC, citing from
> Section 6 a 128-bit (birthday) attack on HMAC-SHA256 (regardless of
> truncation).  Section 6 would suggest that un-truncated HMAC-SHA256 can
> only provide 128-bit security.   But, on the other hand, this attack
> requires obtaining 2^128 MAC tags, so the attack is very impractical.  Is
> the attack so impractical that one can ignore and deem HMAC-SHA256 as
> providing 256-bit security (as NIST does)?****
>
> **
>

If you have an application (e.g., the use of HMAC as PRF in TLS or IKE)
that has a small worst-case bound on the number of same-key calls to the
PRF  then you may be less concerned about the quadratic degradation, but if
you foresee 2^50 such uses with HMAC-SHA1 then security reduces to 60 bits.

**
>
> Regarding provable security, as it understand it, the proof in [1] and
> Remark 4.6, implies that truncated HMAC is secure if the truncated
> compression function is a secure as MAC.  The MAC-security of the
> (truncated) compression function itself is not proven (or is it later in
> Bellare’s follow-up work?), but of course we may still have confidence in
> it.****
>
> **
>

There is no assumption or reliance on a truncated compression function. The
compression function is always used in non-truncated form (in particular
this is the case in all the iterations of this function underlying an HMAC
computation). Only the final output is truncated.

>  **
>
> Also, hasn’t the weak collision resistance property, upon which [1]
> relies, for SHA-1 been undermined?****
>
> **
>

The proof of Bellare 2006 does not rely on weak collision resistance.

>  **
>
> Menezes and Koblitz [5, Section 4] note that the advantage of tag
> truncation in some cases might not be as much as previously thought.
>

Their note is specific to the potential benefits of truncation for the
multi-user case. It does not imply anything on more common settings as
those that (I guess) motivated this thread in the first place.

Finally, in relation to your conclusions below, I'd note that the
theoretical treatment of HMAC (or the underlying NMAC scheme) does assume a
key of a size equal to the hash length which is the size of keys to the
underlying keyed compression function. Hence SHA-256 should use keys of
size 256. Moreover, I have never seen a setting where keying SHA-256 with
128 bits is easier in any way than keying it with 256 bits, so I see no
reason to entertain 128-bit keys for SHA-256 even at the
pragmatic/practical level.

Hugo

> ****
>
> ** **
>
> *******
>
> ** **
>
> Phillip originally asked about the need for HMAC-SHA256, and specifically
> mentioning the MAC tag length, but his question could also be taken as a
> question for the need for 256-bit security vs. 128-bit security.  Let’s
> suppose that 128-bit security is sufficient.  Some reasons for opting for a
> higher security level (at least for HMAC) include the following.****
>
> ** **
>
> -Margin of error, in case the algorithms end up being weaker than one
> would think (e.g. MD5, SHA-1).****
>
> ** **
>
> -Resistance to quantum computers (either now or in the future).  Future
> adversaries cannot forge MACs today, but if all the keys are 128 bits, they
> can, at a cost about 2^64 quantum computer steps, recover a MAC keys from
> the message and tag, and then recover the master key from the MAC is often
> derived, and then recover the encryption key, and thereby compromise any of
> today’s ciphertexts that they have stored.  ****
>
> ** **
>
> -Multi-user security (see [5, Sections 2.2 and 4], reduces the security
> bits by the log of the number of users.****
>
> ** **
>
> *******
>
> ** **
>
> Based on the considerations above, and general prudence, for 128-bit
> security and HMAC (if one cannot use an alternative MAC, e.g. CMAC), I’d
> recommend HMAC-SHA256, but with a key larger than 128 bits (to address
> multi-user attacks).  It seems just fine to me truncate to 128 bits (i.e.
> my intuition says the margin of error provided by that SHA-256 using 256
> bits instead of 128, i.e. a wide pipe, during the internal computations, is
> sufficient.)****
>
> ** **
>
> References****
>
> ** **
>
> [4]
> http://csrc.nist.gov/publications/nistpubs/800-57/sp800-57_part1_rev3_general.pdf
> ****
>
> ** **
>
> [5] http://eprint.iacr.org/2012/074****
>
> ** **
>
> ** **
>
> Appendix****
>
> ** **
>
> Just for fun: if one allows super-long messages defined by a formula, then
> active HMAC forgery is easy. (Martijn Stam showed me this, hope I got it
> right.)  Let B be any message block.  Let n = 2^256, integer (with ^ =
> exponentiation).  Let M = B^n, bit string (with ^ = repeated
> concatentation).  Let M’ = B^(n+n!),  (with ! = factorial).  Of course,
> these messages are absurdly long, and illegally long for most definitions
> of HMAC, and infeasible to compute the HMAC tags of.  Anyway, notice that
> HMAC(K,M) = HMAC(K,M’), for all keys K.  To see this, think about Pollard
> rho.  Starting from the key, each block B applies the same function.  The n
> iterations move this function into a cycle.  The extra n! cycles wrap
> around the cycle.  For the active forgery, get the MAC signer to compute
> the T=HMAC(K,M).  Then present the T and M’ to a MAC verifier, who will
> accept T as valid even though the MAC signer never authenticated M’.  By
> the way, proofs must resist such absurdities, which I think they all do
> rather easily, by limiting the message length or number of compression
> function queries.****
>
> ** **
>
> Sorry for the length of this email.****
>
> ** **
>
> Daniel Brown****
>
> Research In Motion Limited ****
>
> ** **
>
> ** **
>
> ****
>
> ** **
>
> *From:* [email-masked] [mailto:[email-masked]] *On Behalf Of *Hugo
> Krawczyk
> *Sent:* Thursday, July 12, 2012 11:37 PM
> *To:* Dan Brown
> *Cc:* [email-masked]; [email-masked]; [email-masked]
>
> *Subject:* Re: [saag] How long should a MAC be?****
>
>  ** **
>
> There is one fact, however, that does not depend on the underlying
> function (or even on HMAC): a MAC tag of length t, even a perfect one, does
> not give more than t bits of security  as the attacker can guess the MAC
> value with probability 2^{-t} (and of course the attacker's advantage
> increases linearly with the number of MACed messages or the number of
> possible guesses by the attacker).
>
> Hugo****
>
> On Thu, Jul 12, 2012 at 9:21 PM, Dan Brown <[email-masked]> wrote:***
> *
>
>  ****
>  ****
> Here is the original text from the RFC****
>
>  5. Truncated output****
>
> ** **
>
>    A well-known practice with message authentication codes is to****
>
>    truncate the output of the MAC and output only part of the bits****
>
>    (e.g., [MM, ANSI]).  Preneel and van Oorschot [PV] show some****
>
>    analytical advantages of truncating the output of hash-based MAC****
>
>    functions. The results in this area are not absolute as for the****
>
>    overall security advantages of truncation. It has advantages (less****
>
>    information on the hash result available to an attacker) and****
>
>    disadvantages (less bits to predict for the attacker).  Applications****
>
>    of HMAC can choose to truncate the output of HMAC by outputting the t****
>
>    leftmost bits of the HMAC computation for some parameter t (namely,****
>
>    the computation is carried in the normal way as defined in section 2****
>
>    above but the end result is truncated to t bits). We recommend that****
>
>    the output length t be not less than half the length of the hash****
>
>    output (to match the birthday attack bound) and not less than 80 bits****
>
>    (a suitable lower bound on the number of bits that need to be****
>
>    predicted by an attacker). ****
>
> Hugo****
>
> ** **
>
>
> https://www.ietf.org/mailman/listinfo/saag****
>
> ** **
>
>
> transmission by unintended recipients is not authorized and may be
> unlawful. ****
>
> ** **