Subject: [Cfrg] Re: universal MACs

From: Ted Krovetz <[email-masked]>
Date: Wed, 19 Jan 2005 10:33:35 -0800

A few responses to Bernstein's comments:

> The reason that cryptographers normally don't bother counting forgeries
> after the first one is that cryptographers normally choose parameter
> sizes to prevent the first forgery. There's a big difference in 
> security
> between 60 bits and 100 bits!

Two principle goals on which UMAC was designed are (i) high speed, and 
(ii) provable security of around 2^{-60} forgery probability per 
message. With throughput, in many circumstances, of around 1 cpu cycle 
per byte authenticated, UMAC clearly achieves goal (i). As for (ii), 
UMAC *does* achieve a forgery probability of 2^{-60} per message, with 
options for a 2^{-30} and 2^{-90} mode, if desired. All are safe if 
used appropriately. If you anticipate sending a huge number of 
messages, then you should use the higher security version, or re-key 
occasionally. If you will be authenticating a moderate number of 
messages, then UMAC is appropriate without any worries regarding 
rekeying.

> The problem is that AES was actually designed to be
> indistinguishable from a uniform random _permutation_. In other words,
> if AES is secure, then delta is B(B-1)/2^129, where B is the number of
> blocks fed through AES. This number B can be rather large!

If one is concerned about the UMAC analysis treating AES as a random 
function rather than a random permutation, then this means that B 
should be chosen to not get too high. Letting B get no larger than 2^40 
would keep this concern from dominating the analysis. In other words, 
rekey at least once every 2^40 messages, and this concern goes away.

> As one final security note, I'm bothered by the time variability of the
> POLY(64) algorithm inside UMAC.

This is not a specification or analysis issue. An implementation could 
easily mask such timing differentials if there was concern regarding 
timing attacks.

> Suggested fixes to UMAC: stop promoting MACs at a breakable security
> level, notably UMAC-32 and UMAC-64

UMAC, and in general other MACs with similar forgery probability, is 
safe if used appropriately. Don't use MACs with moderate bit security 
for a huge number of messages without rekeying. But, if you want very 
high speeds, and don't intend to authenticate a huge number of 
messages, then UMAC may be most appropriate.

> Once UMAC has caught up to the state of the art security-wise

Some might disagree with this premise. We take the (perhaps more 
enlightened) view that bit security is not "one size fits all", and 
that UMAC's provision of a choice between 30, 60 and 90 bits of 
security makes for a versatile and fast authentication tool.

Ted Krovetz
Computer Science Department
California State University, Sacrammento

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

---

From: "D. J. Bernstein" <[email-masked]>
Date: 20 Jan 2005 05:12:09 -0000

Ted Krovetz writes:
> An implementation could easily mask such timing differentials

But your public implementation doesn't. Masking would take extra work.
Have you measured the slowdown? Have you analyzed how much information
is leaked by implementations that don't go to this extra effort?

  [ permutations vs. functions ]
> Letting B get no larger than 2^40 would keep this concern from
> dominating the analysis.

Let's check the numbers here. Assume that AES is secure; that a UMAC-64
key is used for 2^40 messages; and that the attacker doesn't try many
forgery attempts---let's say just one. Please confirm that you agree
with the following calculations.

There are slightly over 2^39 AES invocations, assuming consecutive
nonces. Your security bound therefore says that the attacker's forgery
attempt succeeds with probability at most about 1/2^52. Furthermore, if
the forgery attempt _does_ succeed, and the attacker tries a few more
messages, then he can almost certainly compute the key, and selectively
forge messages until rekeying is forced---2^39 forgeries on average.

To summarize: What you've proven is that the attacker's one forgery
attempt---which, if successful, allows half a trillion extra forgeries
practically for free---has probability at most 1/2^52 of occurring,
under your recommended keying strategy, assuming that AES is secure. If
the attacker tries this against four billion different keys then he has
at most a one-in-a-million chance of forging half a trillion messages.

You summarize this as ``If an attacker could try out 2^60 MACs, then the
attacker would probably get one right.'' I don't think that's an honest
summary. The 2^60 isn't what you've actually proven, and ``one'' is a
wild underestimate of the number of successful forgeries.

I'm perfectly willing to discuss speed issues---for example, how long it
takes to load lengthy keys from DRAM---but security is job #1, and a job
that you don't seem to be taking seriously. I've been quite careful to
quantify the Poly1305-AES security guarantee in terms of the number of
authenticated messages, the number of forgery attempts, and the
attacker's chance of breaking AES; I suggest that you do the same for
UMAC, and then reconsider your assertion that UMAC-64 is ``safe.''

You say that moving to a much more reasonable security level costs only
0.5 cycles per byte. Why haven't you done it?

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