Re: [Cfrg] Re: universal MACs

["D. J. Bernstein" <djb at cr.yp.to>]

The UMAC spec describes the security of UMAC-64 as follows: ``If an
attacker could try out 2^60 MACs, then the attacker would probably get
one right.''

But the normal situation for 60-bit Wegman-Carter MACs---including
UMAC-64, presumably---is that an attacker who tries out 2^60 MACs has a
good chance of seizing complete control and producing more than 2^59
selectively forged messages. Similarly, an attacker who tries out 2^40
MACs has roughly a one-in-a-million chance of producing billions of
forged messages.

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!

Furthermore, the UMAC security analysis ignores an issue raised by Shoup
in 1996. I'll assume (without having checked) that the UMAC proof is
correct, i.e., that the hash collision probability is under 2^60. What
this means for security is that the attacker's chance of success is at
most D/2^60 + delta, where D is the number of forgery attempts and delta
is the attacker's chance of distinguishing AES from a uniform random
_function_. 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!

For example, say the legitimate sender sends 2^50 messages and the
attacker tries _one_ forgery. The UMAC security analysis then says that,
if AES is secure, the chance that the forgery succeeds is at most about
1/2^39. This is better than no guarantee at all, of course, but it
doesn't justify the assertion that ``an adversary ... can do no better
than about 1/2^60.'' 

As one final security note, I'm bothered by the time variability of the
POLY(64) algorithm inside UMAC. The attacker will be able to detect,
from timings, whether L1-Hash has produced several consecutive 0xff
bytes; this won't occur often by chance, but figuring out whether the
attacker could trigger it deliberately would require a new analysis of
the details of the L1-Hash function.

Suggested fixes to UMAC: stop promoting MACs at a breakable security
level, notably UMAC-32 and UMAC-64; make whatever MAC changes are
necessary to prove a permutation-based security bound; and, internally,
switch from POLY to Poly1305. (The times for my fast Poly1305 software
are independent of the input.)

Once UMAC has caught up to the state of the art security-wise, we should
work together on comparative benchmarks of UMAC and Poly1305-AES for
various computers, various packet sizes, various data alignments,
various numbers of simultaneous keys, etc.

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

_______________________________________________
Cfrg mailing list
Cfrg at ietf.org
https://www1.ietf.org/mailman/listinfo/cfrg