Subject: Re: [Cfrg] UMAC draft changes

From: Ted Krovetz <[email-masked]>
Date: Thu, 15 Sep 2005 14:03:50 -0700

Hi David,

We're happy to make some clarifications.  We think that most points  
that have been raised in recent postings to this list are covered in  
the RFC itself (see the introduction and the extensive ``Security  
considerations'' section). The one point that the RFC does not  
address is timing attacks. We will submit a revision that will  
include some ``warning'' to implementors regarding timing and other  
side-channel attacks.  However, we see nothing in UMAC that makes it  
inherently vulnerable to these attacks.

Let me further clarify some of the issues that you raise.

> 1.  Information about the key may be leaked via timing attacks.   
> The standard fix of implementing a fixed-time comparison will work,  
> and in my opinion should be a MUST for UMAC implementations.

We don't think the spec should mandate any particular implementation  
technique to avoid timing attacks, or any other side-channel attack,  
first because side-channel attacks are so open-ended, and second  
because whether or not a timing attack is a threat is so application  
dependent. Warning about timing attacks seems to us more appropriate  
than mandating any particular counter-measure. As said, we'll add  
such a warning in the RFC.

> Also, Dan Bernstein points out that the POLY64 hash might leak  
> timing information.  It would be good to get some quantification of  
> this, if possible.

There's no ``inherent'' leak in the POLY64 algorithm; it is an  
implementation choice whether or not to try to make running time data- 
independent in this algorithm. The illustrative reference code that  
we provide leaks timing information in its POLY64 implementation, and  
also in its choice of an off-the-shelf AES and memcmp.  This code was  
never intended to mask against timing attacks.  The fact that our  
reference code is open to timing attacks has no bearing on the  
content of a UMAC RFC. We expect that UMAC can be implemented in  
practical ways that eliminate the possibility of timing attacks to  
the same extent that other table-employing mechanisms can do so.

> 2. The security claims don't take into consideration the number of  
> times that AES is evaluated.

Formal statements of UMAC's security (in our papers) include the  
Adv^prf term that implies the A^2/2^129 term if you consider a block  
cipher. In high-level English descriptions, we omit focus or mention  
of the prf-to-prp term delta=A^2/2^129 because it is both well- 
understood (in particular, it is common to virtually all MAC  
functions that involve block-cipher computations) and low-order (if  
the weak link in your MAC algorithm is this term then you are doing  
well!). In particular, the term A^2/2^129 appears to be more an  
artifact of the proof than a real attack threat. This term is widely  
believed to be of no practical consequences in any realistic setting  
(and the results of Shoup and Bernstein prove it for some cases).  
That is especially true if one uses less than 2^64 tags per key,  
which is always the case in practice.

For the sake of illustration, think of 8-byte tags for 2^64 messages.  
Just for the tags themselves (not counting the messages size), you  
have to send 8 * 2^64 bytes.  Over a super-fast 1GigaByte/second  
link, it will take 2^37 seconds or some 4000 years!  Now, not only  
you need the system (and attacker) to run for that time but you also  
need all messages to be MACed with the SAME KEY.  The system doing  
that (and the patient attacker) deserve the break!!

We will consider writing something about this in the security  
considerations.

> 3. The security claims seem to imply that repeat forgeries are not  
> an issue, saying that ``a 1 / 2^60 forging probability means that  
> if an attacker could try out 2^60 MACs, then the attacker would  
> probably get one right.''  Isn't it the case with UMAC that an  
> attacker who can perpetrate a successful forgery would be able to  
> use information from that success to forge more messages?   This  
> issue is especially important because of the presence of short tags  
> in the spec.

This point is explicitly and clearly addressed in the security  
considerations section (which is where such a discussion belongs)  
under the heading of ``Tag lengths and forging probability'' (Sec  
6.2). The text there says:

``It should be pointed out that once an attempted forgery is  
successful, it is possible, in principle, that subsequent messages  
under this key may be forged, too.  This is important to understand  
in gauging the severity of a successful forgery, even though no such  
attack on UMAC is known to date.''

So while it is not known how easy or hard it would be to produce more  
forgeries once a first forgery is found, it is prudent to assume that  
repeat forgeries *are* easy and that initial forgeries should be  
avoided.

UMAC was designed to support different levels of security. A security  
architect should choose a tag length suitable for their application.  
If the number of messages to be authenticated under one key is not  
astronomic and care is given to identify and act on forgery attempts,  
then 64-bit tags are appropriate.  For low-value content, 32-bit tags  
might be appropriate (after all, these have been standard in retail  
banking for years...).  For very high value content, or if one  
anticipates a large number of forgery attempts, UMAC offers a 96-bit  
tag (and even 128-bit tags for the really paranoid). In any case, the  
simple fact that someone could misuse short tags does not mean that  
they should be disallowed.  We have stated our opinion often, and  
still believe it, that 64-bit tags are appropriate for most purposes,  
and if anyone needs more or less, UMAC can accommodate that.

Some other points brought up by Finney and Bernstein:

> UMAC has the property that tags can be verified incrementally, 32  
> bits at a time.

This is true. Because UMAC operates by making independent hash  
iterations, each producing 32-bits, and the results are concatenated,  
it is possible to do fewer iterations than specified in order to  
verify prefixes.  However, by doing so the verifier may provide the  
attacker with information that will reduce the security of longer  
tags.  As mentioned by Dave Wagner, a given key should normally be  
used with tags of one given size.  We will make sure this is said  
quite explicitly in the RFC.

> It is important with these kinds of MACs that the nonce never be re- 
> used for a given key.  However the pad definition function takes a  
> nonce of variable length

We agree, and the second sentence of the ``Nonce considerations''  
subsection says, ``All nonces in an authentication session must be  
equal in length.''

> The hash function is a Pentium-4-optimized-and-other-machines-be- 
> damned complication ...

UMAC is optimized to run well on any processor that supports well 32- 
bit x 32-bit --> 64-bit multiplication. This is a large class of  
processors. As it turns out, the SSE instructions on the Pentium 4  
allows parallel computations of this sort, but it is a gross mis- 
representation that UMAC is ``Pentium-4-optimized-and-other-machines- 
be-damned''.

Regards,
  John Black
  Shai Halevi
  Hugo Krawczyk
  Ted Krovetz
  Phillip Rogaway

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

---

From: "D. J. Bernstein" <[email-masked]>
Date: 17 Sep 2005 11:51:14 -0000

The UMAC draft claims that UMAC ``has been rigorously proven to be
secure,'' and specifically that ``an adversary ... can do no better than
about 1/2^60'' per forgery attempt.

That claim is false. Among other problems, the proven bound on forgery
probabilities includes an A^2/2^129 term, where A is the number of AES
evaluations. UMAC does not require that A be limited to, e.g., 2^34.

The UMAC authors admit that the A^2/2^129 term exists in the proven
forgery-probability bound. They nevertheless attempt to weasel out of
correcting the falsehoods in their draft:

   * They talk about how long it would take for a single sender to
     transmit 2^64 messages. So what? Transmitting 2^34 messages is a
     billion times faster than that.

   * They claim that A^2/2^129 is an ``artifact of the proof.'' What
     they mean, apparently, is that they know their proof produces bad
     bounds, but they think they can do better. So what? The question
     is about what ``has been rigorously proven,'' not about what the
     UMAC authors speculate they might prove in the future.

   * They observe, correctly, that Shoup and I have proven something
     better than A^2/2^129 for many other MACs. So what? The current
     discussion is about UMAC, not those other MACs. Maybe my techniques
     work for UMAC, but maybe they don't. If the UMAC authors want to
     claim that 1/2^60 ``has been rigorously proven'' then they need to
     show us the proof.

   * They claim that the A^2/2^129 term ``is widely believed to be of no
     practical consequences in any realistic setting.'' Even if this is
     true, so what? The question is about what ``has been rigorously
     proven,'' not about what people might believe.

The UMAC security claim is clearly, obviously, indisputably false. When
I pointed this out eight months ago, the UMAC authors didn't attempt to
defend their false claim, but they also didn't fix it; instead they
attempted to distract attention from it, just as they're doing now. The
level of dishonesty here really amazes me.

> astronomic and care is given to identify and act on forgery attempts,  

How, precisely, is one supposed to ``act on forgery attempts''? Close
the connection, allowing trivial denial of service? Generate a new key,
again degrading service and then allowing the attacker to continue with
the new key?

> In any case, the  simple fact that someone could misuse short tags
> does not mean that  they should be disallowed.

Short tags should be disallowed.

> processors.

And where are the benchmarks justifying these multiple-CPU performance
claims? All I see are Pentium 4 benchmarks relying heavily on PMULUDQ.
Unjustified claims of speed aren't as dangerous as unjustified claims of
security, but they're still dishonest.

---D. J. Bernstein, Professor, Mathematics, Statistics,
and Computer Science, University of Illinois at Chicago

---

From: David McGrew <[email-masked]>
Date: Thu, 22 Sep 2005 13:11:30 -0700

Hi Dan,

can you please provide your comments on the UMAC draft as responses  
or additions to the points that I've raised with the UMAC authors (at  
the outset of this thread)?   It will be easier to track topics and  
draft changes this way.  The goal of the research group here is, of  
course, to produce the best possible document.  Specific comments  
about what text you think should be amended or added to the draft are  
the most helpful.  Comments that could be interpreted as being about  
the motives or integrity of others are counterproductive.

thanks,

David and Ran
CFRG co-chairs

---

From: David McGrew <[email-masked]>
Date: Thu, 22 Sep 2005 13:11:21 -0700

Hello CFRG,

I'd like to solicit your input on the UMAC draft (http://www.ietf.org/ 
internet-drafts/draft-krovetz-umac-04.txt) and the issues outlined  
below.  There is a difference of opinion on some of these points, and  
it would be valuable to the group for you to provide your perspective.

If you feel that there is a point that needs to be clarified, or a  
caveat that needs to be made, please go ahead and suggest text that  
you feel is appropriate.

Thanks!

David

On Sep 15, 2005, at 2:03 PM, Ted Krovetz wrote:

> that have been raised in recent postings to this list are covered  
> in the RFC itself (see the introduction and the extensive  
> ``Security considerations'' section). The one point that the RFC  
> does not address is timing attacks. We will submit a revision that  
> will include some ``warning'' to implementors regarding timing and  
> other side-channel attacks.  However, we see nothing in UMAC that  
> makes it inherently vulnerable to these attacks.
>
>> The standard fix of implementing a fixed-time comparison will  
>> work, and in my opinion should be a MUST for UMAC implementations.
>>
>
> We don't think the spec should mandate any particular  
> implementation technique to avoid timing attacks, or any other side- 
> channel attack, first because side-channel attacks are so open- 
> ended, and second because whether or not a timing attack is a  
> threat is so application dependent. Warning about timing attacks  
> seems to us more appropriate than mandating any particular counter- 
> measure. As said, we'll add such a warning in the RFC.
>
>
>> timing information.  It would be good to get some quantification  
>> of this, if possible.
>>
>
> implementation choice whether or not to try to make running time  
> data-independent in this algorithm. The illustrative reference code  
> that we provide leaks timing information in its POLY64  
> implementation, and also in its choice of an off-the-shelf AES and  
> memcmp.  This code was never intended to mask against timing  
> attacks.  The fact that our reference code is open to timing  
> attacks has no bearing on the content of a UMAC RFC. We expect that  
> UMAC can be implemented in practical ways that eliminate the  
> possibility of timing attacks to the same extent that other table- 
> employing mechanisms can do so.
>
>
> Adv^prf term that implies the A^2/2^129 term if you consider a  
> block cipher. In high-level English descriptions, we omit focus or  
> mention of the prf-to-prp term delta=A^2/2^129 because it is both  
> well-understood (in particular, it is common to virtually all MAC  
> artifact of the proof than a real attack threat. This term is  
> widely believed to be of no practical consequences in any realistic  
> setting (and the results of Shoup and Bernstein prove it for some  
> cases). That is especially true if one uses less than 2^64 tags per  
> key, which is always the case in practice.
>
> For the sake of illustration, think of 8-byte tags for 2^64  
> messages. Just for the tags themselves (not counting the messages  
> size), you have to send 8 * 2^64 bytes.  Over a super-fast  
> 1GigaByte/second link, it will take 2^37 seconds or some 4000  
> years!  Now, not only you need the system (and attacker) to run for  
> that time but you also need all messages to be MACed with the SAME  
> KEY.  The system doing that (and the patient attacker) deserve the  
> break!!
>
>> issue is especially important because of the presence of short  
>> tags in the spec.
>>
>
> in gauging the severity of a successful forgery, even though no  
> such attack on UMAC is known to date.''
>
> So while it is not known how easy or hard it would be to produce  
> more forgeries once a first forgery is found, it is prudent to  
> assume that repeat forgeries *are* easy and that initial forgeries  
> should be avoided.
>
> UMAC was designed to support different levels of security. A  
> security architect should choose a tag length suitable for their  
> application. If the number of messages to be authenticated under  
> one key is not astronomic and care is given to identify and act on  
> forgery attempts, then 64-bit tags are appropriate.  For low-value  
> content, 32-bit tags might be appropriate (after all, these have  
> been standard in retail banking for years...).  For very high value  
> content, or if one anticipates a large number of forgery attempts,  
> UMAC offers a 96-bit tag (and even 128-bit tags for the really  
> paranoid). In any case, the simple fact that someone could misuse  
> short tags does not mean that they should be disallowed.  We have  
> stated our opinion often, and still believe it, that 64-bit tags  
> are appropriate for most purposes, and if anyone needs more or  
> less, UMAC can accommodate that.
>
> iterations, each producing 32-bits, and the results are  
> concatenated, it is possible to do fewer iterations than specified  
> in order to verify prefixes.  However, by doing so the verifier may  
> provide the attacker with information that will reduce the security  
> of longer tags.  As mentioned by Dave Wagner, a given key should  
> normally be used with tags of one given size.  We will make sure  
> this is said quite explicitly in the RFC.
>
>
>> It is important with these kinds of MACs that the nonce never be  
>> re-used for a given key.  However the pad definition function  
>> takes a nonce of variable length
>>
>
> UMAC is optimized to run well on any processor that supports well  
> 32-bit x 32-bit --> 64-bit multiplication. This is a large class of  
> representation that UMAC is ``Pentium-4-optimized-and-other- 
> machines-be-damned''.
>
>
> Regards,
>  John Black
>  Shai Halevi
>  Hugo Krawczyk
>  Ted Krovetz
>  Phillip Rogaway
>
>

---

From: Ted Krovetz <[email-masked]>
Date: Thu, 22 Sep 2005 13:26:00 -0700

Hold on...

> I'd like to solicit your input on the UMAC draft (http:// 
> www.ietf.org/internet-drafts/draft-krovetz-umac-04.txt) and the  
> issues outlined below.  There is a difference of opinion on some of  
> these points, and it would be valuable to the group for you to  
> provide your perspective.

We are putting the finishing touches on a revised internet-draft that  
clarifies much of these issues.

In particular:

- We make it clear that POLY is open to timing attacks if an  
implementation is not careful.

- We recommend that prefix verification should not be allowed.

- We clarify that the number of AES calls is not an issue by  
referring to Bernstein's work at http://cr.yp.to/antiforgery/ 
permutations-20050323.pdf (in particular the beautiful Theorem 2.3).

Please hold off on comments until we get the revised draft posted.

Thank you,
Ted Krovetz

---

From: David McGrew <[email-masked]>
Date: Thu, 22 Sep 2005 14:59:01 -0700

Ted,

On Sep 22, 2005, at 1:26 PM, Ted Krovetz wrote:

>> issues outlined below.  There is a difference of opinion on some  
>> of these points, and it would be valuable to the group for you to  
> We are putting the finishing touches on a revised internet-draft  
> that clarifies much of these issues.

That's great.

> permutations-20050323.pdf (in particular the beautiful Theorem 2.3).

Is this a preprint of the "better bounds" work published at Eurocrypt  
this year?

> Please hold off on comments until we get the revised draft posted.

Yes, makes sense.

thanks,

David