Subject: [Cfrg] Re: UMAC

From: Shai Halevi <[email-masked]>
Date: Thu, 06 Oct 2005 13:30:12 -0400

I wrote:
> I would also point out that the level of rigor in the UMAC proofs
> (in Black's PhD thesis in particular) [...]

but meant "... Krovetz'es PhD thesis in particular". Sorry, Ted.

John Wilkinson wrote:
> 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.

I believe that the I-D does talk about these "deltas" in the security
considerations section. And I personally have no problems with adding
these terms elsewhere as well. (Especially if this means ending this
silly argument that has already taken more of my time than I can afford
to spend.)

The discussion on the list so far seemed to suggest that there were
problem with either the security of UMAC or its published proofs (to
which I strongly disagree). If the issue is only needing to change some
wordings in the draft, then I'm sure this should cause no problems.
(After all, the process for moving from I-D to RFC is meant to give
people an opportunity to insert changes in the wording of things.)

-- Shai

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

---

From: "D. J. Bernstein" <[email-masked]>
Date: 6 Oct 2005 18:19:20 -0000

Shai Halevi writes:
> If the issue is only needing to change some wordings in the draft

No, that's not the only issue.

UMAC-32 is insanely dangerous. UMAC-64 is fairly dangerous, certainly
not what I would call safe. Have we learned nothing from 56-bit DES,
512-bit RSA, and 80-round SHA-1?

My comments have focused mostly on your quantitative exaggerations of
the proven UMAC security level, but the main reason to care about the
numbers is that they lead to _qualitative_ conclusions regarding UMAC.

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

---

From: canetti <[email-masked]>
Date: Thu, 6 Oct 2005 15:34:00 -0400 (EDT)

It appears to me that the recent discussion on the UMAC analysis has
been bloated way out of proportion and seems to have generated much
confusion. Let me try to explain things as I see them. Hopefully this
will help clarify and focus.

The security analysis of UMAC has essentially two parts:

1.  An analysis of the probability of generating a forgery, assuming that
in each application of the function the Pad value is a fresh random value.

This part is purely combinatorial, and is based on the
Carter-Wegman paradigm and the almost-xor-univerality of UHASH.
This bound is rigorously proven in the UMAC paper, and
I dont think that anyone has doubted this bound.

(BTW, this is the main part of the analysis,
and it is here where the ingenuitiy and novelty of UMAC lies.)

2. An analysis of the closeness of the pad-generating schedule in UMAC
(i.e, AES in counter mode) to a random pad.

As far as I understand, all the complaints of "inaccuracies" and "lack of
rigor" in the UMAC analysis are on this part.

A first thing to note is that this part is not specific to UMAC: rather,
it is a standard element that appears in many other schemes, e.g.
CCM, GCM, and any other scheme that uses AES in counter mode
to generate pseudorandom pads.

More to the point, the only thing we can do with this term is to assume
that it is small enough. No rigorous proof are possible with today's state
of scientific knowledge.

So the only thing we can expect from the UMAC I-D is that it will
explicitly mention this term when giving explicit bounds, and explain its
meaning.  I dont see that any new proofs are necessary.

Ran

BTW, what's a reasonable assumption on the size of this error term? I.e,
assuming the adversary runs in time T (where T is measured in units of
AES-computation time), what is a resonable bound on the probability that it
sitinguishes between a random pad of length 128N bits, and the output of AES
in counter-mode applied N times?
We know that, since AES has key size of 128, the adversary can exhustively
search for the key and get distinguishing probability of T/2^{128}.
Also, since AES is a permutation, it can run a birthday attack that succeeds
with probability N^2/2^129.  I'm not aware of any other attack here.
Specifically, I'm not aware of attacks that utilize specific computational
properties of AES (as opposed to a "perfect block cipher").
So, as far as we know, it could be the case that a bound of (N^2+T)/2^{128}
is good enough. If we want to be conservative, and like round numbers, we
can assume, say, that this distinguishing probability is no more than
(N^2+T)/2^{100}. Does this bound sound reasonable to people?

Ran

---

From: "D. J. Bernstein" <[email-masked]>
Date: 6 Oct 2005 22:32:21 -0000

canetti writes:
  [ on the chance of distinguishing AES outputs from a one-time pad ]
> More to the point, the only thing we can do with this term is to
> assume that it is small enough.

If that were the only thing we could do then we'd have deeply
unsatisfactory results, certainly not justifying the claims that
single-forgery probabilities for UMAC are below 2^{-30}, 2^{-60}, etc.

For example, the attacker has more than one chance in a billion of
distinguishing 2^50 AES outputs from a one-time pad, and more than one
chance in a thousand of distinguishing 2^60 AES outputs from a one-time
pad. If we had to incorporate these ``PRF'' distinguishing probabilities
into our forgery-probability bounds (which is the best we had for UMAC
back in January, triggering some of my complaints at that point) then
long-term keys would never achieve a respectable security level.

Fortunately, as Shoup pointed out in 1996, your statement isn't true.
The property that AES was actually designed to achieve---namely,
indistinguishability from a uniform random _permutation_---isn't limited
by the number of outputs. We can prove MAC forgery-probability bounds
far below the one-time-pad distinguishing probabilities by working
directly with these ``PRP'' distinguishing probabilities. The UMAC
authors are (finally!) taking this approach.

> we can assume, say, that this distinguishing probability is no more than

It's a plausible, and nearly useless, conjecture.

---

From: canetti <[email-masked]>
Date: Fri, 7 Oct 2005 12:34:52 -0400 (EDT)

I beg to differ.

It is true that using the Shoup analysis and the Bernstein improvment it is
possible to shave off most of the additive N^2/2^129 factor in the error
term (which translates directly to the adversary's probability of forging).
This are indeed very nice and important scientific results, and I am glad
that they were incorporated into the UMAC analysis.

But in the end of the day we have to add to all these meticulously calculated
bounds the error term corresponding to the quality of AES as a block cipher.
We have no idea how large this term might be, or might be shown to be next
week. Here the only thing we can (and should) do is take safety margins.

So, we should keep reminding ourselves not to get too engrossed and in love
with these exact numbers. They might give a false sense of security.

What we know for sure is that if we had an ideal pad then the forgery
probabilities of UMAC are as stated. What are the probabilities when we use
AES in counter mode is no more than a guess. (An informed guess, but still a
guess.)

Ran