Subject: Re: [Cfrg] Critical gap in the UMAC security ``proof''

From: Ted Krovetz <[email-masked]>
Date: Sun, 23 Oct 2005 10:25:08 -0700

> Let me see if I understand the bottom line.
> You're now withdrawing all of these statements?

No. An insignificant problem has been found in our implementation of  
UMAC as an I-D (if you can call an event that occurs with no more  
than 28/2^120 probability a problem). The proof of UMAC is valid  
based on the assumption that there are no redundant AES inputs. We  
can proceed by adjusting the current claims to accommodate the fact  
that there is a 28/2^120 probability that this assumption is false  
(requiring no change to code or test-vectors), or make a trivial  
change to the algorithm (making the assumption true but requiring  
changes to code and test-vectors).

A third choice is to ignore Bernstein's Quixotic attempts to find a  
significant security problem with UMAC, of which there have been none  
after weeks of looking, and get on with ratifying the I-D. The value  
28/2^120 is after all smaller than 3*delta (where delta is AES-prp  
distinguishing probability), and therefore irrelevant vis-a-vis the I- 
D's security claims.

After we see if anybody has an opinion, we will decide how to proceed.

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

---

From: "D. J. Bernstein" <[email-masked]>
Date: 24 Oct 2005 14:26:25 -0000

Ted Krovetz writes:
> The proof of UMAC is valid  
> based on the assumption that there are no redundant AES inputs.

Yes or no: Are you continuing to claim that UMAC-128, with AES replaced
by Func(128,128), has forgery probability at most 1/2^120? That's what
your ``Theorem 1'' says. That's also what your I-D says:

   The theory of Wegman-Carter MACs and the analysis of UMAC show that
   if one "instantiates" UMAC with truly random keys and pads then the
   probability that an attacker ... produces a correct tag for any
   message of its choosing is no more than ... 1/2^120 if the tags
   output by UMAC are of length ... 128 bits.

If you're unable to prove this ``rigorously proven theorem'' then you
need to clearly state for the record that the ``theorem'' is withdrawn.
It's really not acceptable for you to issue revised security claims
without clarifying the status of the previous claims.

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