Subject: Re: [Cfrg] New UMAC Draft

From: Ted Krovetz <[email-masked]>
Date: Fri, 30 Sep 2005 08:14:11 -0700

Lest anyone think we "haven't done the work yet", I am willing to  
continue to engage Bernstein further in this discussion.

> > UMAC is rigorously proven.
>
> I don't believe you. It seems possible, perhaps even likely, that  
> such a
> proof exists; but it's also clear that you haven't done the work yet.

Please tell me which of the following is not true:

- Suppose H is a \e-SU hash family with each h \in H returning n  
bits, further suppose that h is randomly chosen from H and f is a  
randomly chosen function returning n bits. Then, the probability an  
attacker could forge against h(msg) xor f(nonce) is at most \e.

- Since UHASH is \e-SU, this bound holds for UMAC when UMAC is used  
with a random function.

- Let A be an algorithm that is given random function \rho with 128- 
bit outputs and inputs. Let A run an attacker on UMAC-64 and let A  
simulate UMAC-64 for the attacker using \rho instead of AES. Let A  
output 1 if the attacker forges. We know that the probability of  
success here is no more than 2^{-61} (for the sake of argument) in  
the attacker's forgery attempt. This means A outputs 1 with  
probability no more than 2^{-61}. Let's say the attacker sees 2^i  
MACs along the way (meaning no more than 2^i \rho invocations). Then,  
Bernstein's theorem says that if we substitute random permutation \pi  
for \rho, then A will output 1 (indicating forgery success) with  
probability no more than (1 - 2^{i-128})^{2^{i-1}} 2^{-61} < 2^{-60}  
for i <= 64.

Thank you,
Ted Krovetz

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

---

From: "D. J. Bernstein" <[email-masked]>
Date: 30 Sep 2005 20:50:48 -0000

> Please tell me which of the following is not true:
  [ series of lemmas that might be useful in a UMAC security proof ]

As I see it, the main risk of error is not in any of your lemmas, but
in how you're putting the lemmas together to obtain an overall bound on
the UMAC forgery probability. Certainly this is the part that led to
your incorrect UMAC security claims last year, and the part where you're
continuing to be incredibly sloppy.

Your latest UMAC security claim (which, like your incorrect claims, is
alleged to be ``rigorously proven'') appears to be the following:

   Claimed theorem. An attack against UMAC-32n using at most 2^64 chosen
   messages and one forgery attempt cannot have success probability
   larger than 2^{-30n}, if AES is secure.

There isn't much wiggle room here: you haven't defined ``secure'' yet,
but you've clearly stated that you're bounding the forgery probability,
you've clearly stated that your bounds are exactly 2^{-30}, 2^{-60},
2^{-90}, 2^{-120} for UMAC-32, UMAC-64, UMAC-96, and UMAC-128, and
you've clearly stated that you're allowing 2^64 chosen messages.

Please define ``secure'' and then show us the proof of this claimed
forgery-probability bound.

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