[Cfrg] Re: universal MACs

[Ted Krovetz <tdk at csus.edu>]

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
Cfrg at ietf.org
https://www1.ietf.org/mailman/listinfo/cfrg