Subject: [Cfrg] More FUD (Re: D. J. Bernstein's non-attack on UMAC)

From: "Shai Halevi" <[email-masked]>
Date: Tue, 04 Oct 2005 07:31:06 -0400

Executive summary of Bernstein's "attack": The attacker guesses 2^40
random AES keys and test them against UMAC. The attacker is successful
if it guessed the right AES key (which happens with probability 2^{-88}).

Why is Bernstein calling this an attack on UMAC? Your guess is as good
as mine. Trying to pass this as a weakness of UMAC is nothing short of
a deliberate disinformation. (And describing this "attack" over a two-page
email, complete with multi-line formulas, smells like an attempt at using
math to scare people.)

At this point, it should be clear for all that there are no real
security concerns with the use of UMAC for message authentication
(Bernstein's personal insults notwithstanding).

At the end of this letter I am attaching a short high-level discussion
of the security of Carter-Wegman MACs and UMAC in particular, trying
to put in perspective all these "mysterious bounds" that this list was
dragged through over the last few weeks.

> I'm quite disappointed at the ruthlessly anti-mathematical attitude [...]

To be sure, the disappointment is mutual. I used to read Bernstein's
posts, but this last line of increasingly off-the-mark posts (and this
last one in particular) are an abuse of my time and attention. I thus
regrettably added Bernstein to my killfile. Maybe it is time for the
moderators to apply their judgment as to whether posts such as these
have a place on this list.

-- Shai

Basics of Carter-Wegman MACs:
=============================
In an idealized version of this style of MACs, the communicating peers
share a secret one-time-pad as well as a secret key to a keyed hash
function H. Roughly, the hash function should have the property that
for any two fixed distinct messages X, X', the odds of a collision
H(K; X)=H(K; X') when the key K is chosen at random are very small.(*)

Then, the authentication tag on the i'th message X_i sent between these
peers is computed by hashing X_i with H and adding the i'th segment of
the one-time-pad

  tag_i = H(K; X_i) xor i'th-segment-of-the-pad

It can be shown (by a very simple argument) that when the key K and the
one-time-pad are chosen at random, any attacking algorithm (that works
with no a-priory knowledge of these shared secrets) cannot forge a tag
any better than the "collision probability" of the hash function H.

The case of UMAC
=================
A concrete instance of Carter-Wegman MACs therefore consists of:

(a) A particular hash function for which one can prove low "collision
probability", and

(b) Some cryptographic realization of the one-time-pad

In the case of UMAC, the hash function is the function UHASH that is
described in the Internet Draft, and the one-time-pad is realized using
AES in counter mode.

No one on the list disputed the proof of the "low collision probability"
of UHASH. The entire argument was about whether or not AES in counter
mode is a sufficiently secure pseudorandom generator.

Indeed, there are some slight imperfections in using AES in counter-mode
as a pseudorandom generator. For example, AES is just a block cipher and
thus one can guess its key with some small probability. Another imperfection
is  that AES is a permutation (because it is invertible), so in the "pad"
that is generated by AES no two blocks can be the same.  (There are other
imperfection, e.g. the probability that a random hardware bit-flip causes
the sender to re-use a nonce. In reality, however, the biggest imperfection
is implementation errors that lead either to re-use of nonces or to leakage
of the key.)

In most all crypto proofs (UMAC proof included), these imperfections
are lumped together into an insignificant "error term". Just to remove
doubt, there is nothing in the MAC application (or specifically in UMAC)
that makes it more sensitive to these imperfections than any other
application of AES in counter-mode. On the contrary, Bernstein's own
recent lemma proves that the error term due to AES being a permutation
is indeed second order. (And terms such as the probability of guessing
the key at random are clearly unrelated to the design of UMAC.)

Bernstein's entire argument is that the error term due to the use of AES
in counter-mode as pseudorandom generator may be larger in some settings
than the first-order term that comes from the collision probability of
the hash function. But note that if your biggest problem is second-order
terms such as the attacker guessing the key to AES-128, then UMAC delivered
on its security promise.

At the end of the day, you should trust the security of UMAC if (and only
if) you trust the security of AES in counter mode for any other purpose.

---------
(*) The exact property that is needed of the functions H is slightly
stronger than "rare collisions". This property usually goes by the name
of "epsilon-xor-universality".

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

---

From: "D. J. Bernstein" <[email-masked]>
Date: 4 Oct 2005 16:23:04 -0000

> if) you trust the security of AES in counter mode for any other purpose.

I've never said anything to the contrary. I'm not saying that UMAC is
easily breakable. I'm attacking the specific QUANTITATIVE security
bounds claimed in the UMAC documentation.

There are more problems here than the UMAC authors' omission of the AES
distinguishing probability. For example, if I wanted to guess what the
UMAC authors might obtain if they ever actually did the proof that
they've been falsely claiming to have done, I'd start from the bound
3*2^(-32) + 2^(-33) in Black's Theorem 6.4.7, take the third power for
UMAC-96, and divide by (1 - 2^(64-128))^(2^63) for the switch from
functions to permutations with at most 2^64 messages (meaning 2^64 AES
invocations for UMAC-96), producing something slightly _larger_ than the
claimed 2^(-90) per forgery attempt, even before I add the AES
distinguishing probability. Note that the UMAC authors currently claim
the 2^(-90) etc. to be exact upper bounds, not approximations.

Of course, I could be missing a better proof approach, but in any case
it isn't _my_ responsibility to write down a rigorous proof of bounds on
the UMAC forgery probability. The UMAC authors have been fraudulently
claiming ``rigorously proven'' bounds on the UMAC forgery probability;
the reality is that their bounds fail to take account of several issues
that would be obvious to them if they had ever actually done a proof.

The level of weaseling by the UMAC authors here is really astonishing.
You'd think they'd be more apologetic for claiming ``rigorously proven''
forgery-probability bounds that turned out to be false.

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