Subject: [Cfrg] UMAC draft version 06

From: David McGrew <[email-masked]>
Date: Tue, 11 Oct 2005 10:05:44 -0700

Hello,

the UMAC authors have submitted a revised version of their draft,  
which is now available at http://www.ietf.org/internet-drafts/draft- 
krovetz-umac-06.txt.  They have also posted a proof of security  
online at http://www.cs.ucdavis.edu/~rogaway/umac/ (please note that  
the Internet Draft referenced at that site is expired - you want to  
read version 06).  Thanks to Ted and the other authors for revising  
the draft and providing the additional material requested.

There has been contention on some technical points, so your review of  
the new version and comments on these topics will be appreciated.

David

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

---

From: "D. J. Bernstein" <[email-masked]>
Date: 11 Oct 2005 18:14:58 -0000

What's the schedule at this point?

Obviously this revision is a big improvement. The authors seem to have
swept through all their previous security claims, trying to bring the
new security claims in line with what we actually know.

What concerns me is that there's now quite a bit of new text to review.
The risk of error remains high. My first impression is that more of the
deltas need to be tripled, for example, and that the word ``rigorous''
needs to be removed. This review shouldn't be done in a rush.

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

---

From: canetti <[email-masked]>
Date: Sun, 16 Oct 2005 23:08:49 -0400 (EDT)

Folks,

We'd like to set a formal deadline for comments on this draft, that will
allow the authors to make it before the upcoming cutoff date even if some
additional small issues will come up. So let's set this Wednesday the 19th
as the deadline.

Thanks,

David and Ran

---

From: "D. J. Bernstein" <[email-masked]>
Date: 17 Oct 2005 05:29:31 -0000

canetti writes:
> So let's set this Wednesday the 19th as the deadline.

That strikes me as unreasonably fast. The new security claims in the
draft add up to quite a bit of new text. The underlying security proof
was posted just ten days ago and contains another two dense pages of
text. Aren't you concerned about the possibility of serious errors in
the proof and in the revised security claims?

---

From: canetti <[email-masked]>
Date: Mon, 17 Oct 2005 10:27:02 -0400 (EDT)

> the proof and in the revised security claims?

Not really...

Few reasons:
1. Then main changes in the I-D are clarifying text that was found unclear
in previous versions. Verifying that these clarifications are ok should not
take more than few minutes of reading.

2. The analysis document you refer to is not part of the I-D. While it
is an important document for having public assurance in the exact
numeric claims of the authors (as discussed on the list), I see little
possibility that the claims in this document will be found erroneous
to the extent that a change to the I-D will be needed.

3. The road from here to a published RFC is still long. In case that some
editorial/textual changes to the I-D will end up being necessary due to
unexpected holes in the security analysis, there
will still be several opportunities for the authors to make these
changes.

4. As far as the technical properties of the scheme itself, the
discussion so far was concentrated on the specific
values of some parameters which are, to the best of my
technical understanding, of secondary importance from a security
practitioner's point of view (see eg our prior discussions on the list
regarding the additive delta etc.)
There were no doubts regarding the basic security of the scheme.

Best,

Ran

---

From: "D. J. Bernstein" <[email-masked]>
Date: 19 Oct 2005 08:48:40 -0000

> There were no doubts regarding the basic security of the scheme.

The draft claims specific _quantitative_ security levels. Those claims
are new and have not been subjected to a reasonable level of review. I
have quite serious doubts regarding UMAC's ability to achieve the newly
claimed security levels. I think it was irresponsible of you on Sunday
night to set a Wednesday deadline for comments on these security claims.

> Then main changes in the I-D are clarifying text that was found
> unclear in previous versions.

No. The main changes in the I-D were replacing false security claims and
questionable security claims with new security claims. The underlying
security proof was posted just twelve days ago, makes security claims
clearly different from the previous claims, and is written far below
contemporary standards of rigor in security proofs. The risk of error
has been reduced but remains unacceptably large.

> I see little possibility that the claims in this document will be
> found erroneous to the extent that a change to the I-D will be needed.

I'm quite surprised at the notion that an erroneous security claim is
acceptable. Exactly what level of error do you consider acceptable? For
example, do you think it's okay to claim that forgery probabilities are
below 1/2^120, when in fact the forgery probabilities are many billions
of times larger?

---

From: Hugo Krawczyk <[email-masked]>
Date: Wed, 19 Oct 2005 18:38:33 +0200 (IST)

Paraphrasing the Great Daniel J. Bernstein: Cut the crap, Daniel!

There were NO no new security claims nor new proofs since Ted's thesis
which has been in the public domain since 2000 (and the main underlying
results are already in the full 1999 CRYPTO paper). The only adjustment we
did recently is to move our PRF-based quantification to PRP-based using
your recent results. As I already said, the latter quantification is more
elegant and desirable than a PRF-based, yet in both cases the significance
is inherently heuristic as it entitles a non-quantifiable ACTUAL security
of AES.

You can dislike our English interpretation of the results and bounds in
the I-D (and we did our best in the recent revision to re-phrase them in a
way that improves their accuracy and understandability by non-experts) but
they were always clearly stated as the things an attacker can do short of
attacking AES, and we always referred the interested reader to the
accurate results in the technical references.  If you find mistakes there
(you had five years to do so), please let us know. As long as this is not
the case then please stop misleading (just to use a polite term that you
do not deserve) this community.

Hugo

---

From: canetti <[email-masked]>
Date: Wed, 19 Oct 2005 17:00:07 -0400 (EDT)

Dan,

I think you've misunderstood my point, so let me try to clarify:

> do you think it's okay to claim that forgery probabilities are

I dont think the draft claims that forgery probabilities are below 1/2^120.
They can't possibly claim that since we dont know it's true. In fact, it's
most probably false.

The claim is that the forgery probability is below 1/2^120, *plus delta*,
where delta is the probability of distinguishing AES from an ideal cipher.
This delta is an unknown quantity, and it may well be billions of times
larger than 1/2^120. So, from a security practitioner's point of view
it doesnt really matter much if the probability of forgery assuming an
ideal cipher is 1/2^120, 1/2^100, or even 1/2^80. It all disappears in the
noise. This is why I believe that the exact bounds in the new proof are
unlikely to matter for the I-D.

That said, I'd like to second David's proposal to write a document on the
effect of short tags on the forgery probability, including the issue of
multiple forgeries versus first forgery. These are important
issues that are not specific to UMAC and are of general interest.

Best,

Ran

---

From: "D. J. Bernstein" <[email-masked]>
Date: 20 Oct 2005 07:41:37 -0000

> where delta is the probability of distinguishing AES from an ideal cipher.

Actually, what Section 6.2 says is that you have to add 3 times delta:
``Over N forgery attempts, forgery occurs with probability no more than
N/2^30, N/^60, N/2^90 or N/2^120, plus 3*delta.'' The separate security
document claims that 2.01*delta is enough.

What Section 1 says is different: ``one has to add to the above forgery
probabilities [N/2^120 etc.] a value delta which measures the security
of the pseudorandom function.'' This omits the factor 2.01, and thus
misstates the conclusions of the security analysis.

This is one of many new security claims that were written this month and
that obviously have not undergone adequate cryptographic review.

> They can't possibly claim that since we dont know it's true. In fact, it's

It's _definitely_ false, and it was clearly claimed in previous drafts
of the document. These facts are relevant to a thorough risk analysis.

I'm not saying that the same claim appears now. I'm not saying that the
new draft is anywhere near the disastrous state of the previous drafts.
I'm simply trying to understand the limits of your rather strange view
that erroneous security claims are acceptable.

---

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

Hugo Krawczyk writes:
> which has been in the public domain since 2000

False. Consider, for example, the following security claim appearing in
draft-krovetz-umac-05.txt, shortly after the claim that UMAC ``has been
rigorously proven to be secure'':

   When UMAC produces 32-, 64-, 96- or 128-bit tags, the probability
   that an attacker can produce a correct tag for any message of its
   choosing is no more than 1/2^30, 1/2^60, 1/2^90 or 1/2^120,
   respectively.

This is just one of many UMAC security claims that did not appear in the
2000 Krovetz thesis. In fact, if you look at the Krovetz thesis, you
won't find _any_ proofs of bounds on UMAC forgery probabilities! As
David Wagner put it: ``There are some claims and proofs about the UMAC
2-universal hash, but that's just a component in the UMAC authentication
scheme.''

Let me also emphasize that the above security claim is false. I've
already given a detailed explanation of a fast attack that indisputably
has much larger success probability against UMAC-128. This is an
illustration of the importance of reviewing security claims.

> The only adjustment we did recently is to move our PRF-based
> quantification to PRP-based using your recent results.

No, that's not the only ``adjustment'' you did recently. You've removed
quite a few false and questionable security claims---while failing to
state for the record that you are no longer making those claims---and
replaced them with different security claims. The new claims need
review, just as the old ones did.