Subject: Re: [Cfrg] UMAC security proof posted

From: Ted Krovetz <[email-masked]>
Date: Thu, 6 Oct 2005 16:44:10 -0700

Hello,

> for UMAC-96, perhaps something like
> Pr[at least one forgery succeeds] <= 2^{-90} D + 2.01 delta, where  
> D is
> the number of forgery attempts. This is billions of times smaller than
> the (2^{-90} + 2.01 delta) D that you've proven so far

The results from Bellare, Goldreich and Mityagin show that if a UMAC  
attacker has a single-forgery success probability of \e when using  
random functions, then an attacker has probability d * \e of forging  
over d attempts. It is straightforward to apply this result to our  
proof to show Pr[at least one forgery succeeds] <= 2^{-90} d + 2.01  
delta.

The posted proof has been updated with a note to this regard.

-Ted

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

---

From: Ted Krovetz <[email-masked]>
Date: Fri, 7 Oct 2005 07:09:02 -0700

Some facts to try to refocus onto the UMAC draft:

- UMAC offers 2^30i forgery probability so long as AES is secure.  
This claim is stable and has not changed in years. We have modified  
the draft to include a 2^64 message limit and will soon include  
"delta" terms to make more explicit what we mean by "so long as AES  
is secure".

- UMAC offers choice in tag length. It is up to the security  
architect to choose a risk/performance tradeoff. We are clear in the  
draft both that forgery probability grows linearly with the number of  
attempts and that one forgery may mean subsequent forgeries are easy.  
We are changing the language in the draft from saying 64-bits is  
appropriate for "most applications" to saying 64-bits is appropriate  
for "many application". Since key discovery after a session has  
expired is of no value and many (maybe most) sessions are short  
lived, it is undoubtedly true that 2^-60 security is sufficient for  
many applications. That was the only place in the draft that we made  
an explicit recommendation of 64-bit tags.

-Ted Krovetz

PS -- An apology. In my apoplexy over a bogus claim that our proof  
showed only a D * (2^-30i + delta) forgery probability over D  
attempts rather than the intended (D * 2^-30i) + delta, I mistakenly  
referenced BGM04, which says nothing about this situation. It is well  
known and proved several times (including in Bernstein's work) that  
the uni-valued MACS have the better bound.