Subject: Re: [Cfrg] UMAC draft version 06

From: Ted Krovetz <[email-masked]>
Date: Thu, 20 Oct 2005 09:46:17 -0700

> [The introduction] omits the factor 2.01, and thus misstates the  
> conclusions of the security analysis.

We have striven to make the I-D readable to a broad audience and to  
make the introduction simpler than the security considerations. In  
past drafts, this translated to saying in the introduction that UMAC  
had forgery probabilities no more than 2^-30i and saying in the  
security section that so long as AES was secure that forgery  
probabilities were no more than 2^-30i. This gets the basic message  
across (longer tags give proportionally lower forgery probability),  
and the sophisticated reader of the security section would infer the  
AES-delta-term's existence.

This wasn't "honest" enough for many, so we have changed our  
presentation. Now the introduction says forgery probability is 2^-30i  
+ delta where value delta "measures the security of the pseudorandom  
function." Here delta is a general term that includes anything  
related to breaking AES. Making a more explicit claim of 2^-30i +  
3*delta would probably make things less clear for those who simply  
read introductions. The security section is now more explicit saying  
that forgery probabilities are no more than 2^-30i + 3*delta, and it  
gives a more explicit discussion of delta. [See footnote.]

This more simplistic use of a delta term in the introduction along  
with a more precise usage in the security section seems reasonable  
and appropriate.

Our core claim has not changed over any of these drafts: So long as  
AES is not broken, UMAC forgery probability is no more than 2^-30i.

-Ted

[Footnote.] The 3*delta term could be written 1.01*(delta(2^64)+delta 
(82)), where delta(q) is PRP distinguishing probability over q  
queries. This would make the 3*delta term much closer to 1*delta(q)  
than 3*delta(q), but we didn't want any ugly terms in the I-D so we  
wrote 3*delta. If delta is generally considered insignificant, so  
should 3*delta.

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

---

From: "D. J. Bernstein" <[email-masked]>
Date: 20 Oct 2005 21:17:20 -0000

Ted Krovetz writes:
> This gets the basic message  across (longer tags give proportionally
> lower forgery probability),

That message is horribly misleading. It makes users think, incorrectly,
that UMAC-128 is a billion times harder to break than UMAC-96. In fact,
for a small number of messages, current attacks on UMAC-128 have almost
exactly the _same_ success probability as current attacks on UMAC-96---
and it isn't possible for better attacks to increase the ratio, unless
there's a huge error in the UMAC security claims.

> AES is not broken, UMAC forgery probability is no more than 2^-30i.

That core claim is horribly misleading. It makes the reader think,
incorrectly, that the UMAC-128 (single-)forgery probability is no more
than 1/2^120. In fact, the UMAC-128 forgery probability is billions of
times larger than 1/2^120.

> The 3*delta term could be written 1.01*(delta(2^64)+delta 
> than 3*delta(q)

No! An attacker who does just _one_ query and searches through 2^50 keys
achieves delta(1) very close to 2^50/2^128. Obviously delta(2^64) and
delta(82) are at least delta(1), so if you're adding both delta(2^64)
and delta(82) then you have to add at least _two_ times this 2^50/2^128.

Even if your current security ``proof'' (which is far below contemporary
standards of rigor in security proofs) is correct, it doesn't justify
claiming an addition of just 1 times delta.

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

---

From: canetti <[email-masked]>
Date: Thu, 20 Oct 2005 23:15:51 -0400 (EDT)

Thanks Ted for the clarifying note. I agree that not mentioning the
precise 2.01 factor in the introduction is a reasonable move.

One thing regarding your note: I wouldnt treat the delta factor as
generically insignificant. It may be insignificant, or it may be very
significant... we dont know...

Ran