Re: [Cfrg] Re: universal MACs

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

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

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