Subject: RE: [Cfrg] UMAC security proof posted

From: "Blumenthal, Uri" <[email-masked]>
Date: Fri, 7 Oct 2005 06:24:30 -0400

>The usual reason why 2^{-60} seems inappropriate is that one
>is misled to think that such level of security implies the existence
>of an attack that after a 2^60 work factor can break the
>construction (say, find the key or forge msgs at will).

Usually yes, certainly.

> This however is not the case of UMAC.
>
>You can forge UMAC-64 with probability 2^{-60} but just working 2^60
>time is of no help in improving this bound. Short of breaking AES,
>your best bet is to try more and more forgeries. After a very large
>number of forery attempts (say 2^30) you still have a very small
>probability (2^{-30}) of a successful attempt.

And the probability of a successful attempt increases with increase of
the number of forgery attempts? And after the first successful attempt
again the probability of success increases? If so - why is this
assurance any better than it looks?

>Is this trade-off sufficient for security? 

Not a question I would like to answer - it certainly depends on the
specific security requirements. But probably answering "no" here is
easier.

>I believe this to be appropriate for many applications.  

"Many" does sound like an exaggeration - but there probably are some
applications that don't mind.

>Indeed, I believe so in spite of the fact that, in principle, 
>after a first successful forgery subsequent forgeries may
>be much easier to achieve.  

Our beliefs seem to differ.

>As said, this work factor does not exist with UMAC and the attack 
>not only needs a lot of luck but also is inherently
>on-line (i.e. fully involved with on-line communication).

Regarding on-line communication requirements - a very good point. Still,
I'd not mix "luck" and "probability". :-)
As probability increases - so does the "luck". 

>Having said this I can see many applications where trading 50%
>increase in running time for 2^30 times reduction in forgery
>probability is the right thing to do (especially that UMAC-96 is
>still very fast!). That's one of UMAC virtues: it let's you choose
>your security/performance tradeoff level.  

Agreed.

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