Re: [Cfrg] New UMAC Draft

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