Subject: [Cfrg] Re: UMAC

From: "Shai Halevi" <[email-masked]>
Date: Wed, 05 Oct 2005 21:52:43 -0400

> Date: Wed, 5 Oct 2005 15:38:34 -0600
> From: "The Purple Streak, Hilarie Orman" <[email-masked]>
>
> I cannot see how the draft could be advanced with its current,
> confusing claims of security.  Perhaps "we" would understand what "we"
> had wrought, but how could we expect anyone else (say, the IESG) to
> understand?

I fully agree that there is confusion here, caused no doubt by a
way-too-long
discussion about things that are in fact very clear. What the UMAC proofs
provide is the following assertion:

  The vulnerability of UMAC (with tag of 32*i bits) is at most
  2^{-30*i} more than the vulnerability of AES in counter-mode.

It is by no mistake that I do not specify what I mean by "vulnerability".
You can plug any reasonable real-world meaning to this word and the
assertion will remain true.

I believe that such assertion is easily understandable by crypto
practitioners and there is no need for terms such Adv^prp(t, epsilon) or
bounds such as A^2/2^129. (Those may be needed if we were ever to write
a journal version of the UMAC paper, but in my eyes are worthless for a
standard process and an Engineering-oriented list such as CFRG.)

I would also point out that the level of rigor in the UMAC proofs (in
Black's PhD thesis in particular) exceeds what you can find for many other
common crypto schemes (be it AES in counter mode, CCM, GCM, HMAC, DSS,
RSA, and many many others).

I truly hope that none of the arguments above would be controversial.
What they mean for UMAC (or GCM, or CCM, or any of the others) is
of course a matter of personal interpretation..

Regards,

--  Shai

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

---

From: John Wilkinson <[email-masked]>
Date: Wed, 5 Oct 2005 23:02:26 -0400

>   2^{-30*i} more than the vulnerability of AES in counter-mode.

Shai, Ted, please don't take this personally, but I think it is the  
UMAC draft which is confused. The draft twice gives forgery  
probabilities without reference to the "delta" of the vulnerability  
of AES in counter-mode. If the draft had, in the first place, claimed  
exactly what you write above, I think this confusion could have been  
avoided. There is still the possibility to end this acrimonious  
debate on a positive note if a proof is completed and the draft is  
amended. Then I think we could all recommend UMAC for advancement  
without hesitation.

Respectfully yours,
John Wilkinson

---

From: "D. J. Bernstein" <[email-masked]>
Date: 6 Oct 2005 17:09:48 -0000

Shai Halevi writes:
> You can plug any reasonable real-world meaning to this word

Sure! Let's define ``vulnerability'' for a MAC as the average number of
successful forgeries after just 2^32 forgery attempts. This is a useful
concept for risk managers.

I'd now guess that the vulnerability of UMAC-32 is not just above the
obvious 1, but in fact above 2^31, as it would be for a comparable-size
Gilbert-MacWilliams-Sloane MAC. I'm sure that nobody knows how to prove
anything below 2^31. UMAC provides less than 1 bit of protection from
this perspective.

Your claim, however, is that this vulnerability is at most 2^(-30) more
than ``the vulnerability of AES in counter-mode.'' So you're claiming
that AES is shockingly vulnerable---above 2^31 - 2^(-30)---after just
2^32 invocations. Precisely what definition of ``vulnerability'' leads
you to make this nutty-sounding claim of AES vulnerability?

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