Subject: Re: [Cfrg] New UMAC Draft

From: Ted Krovetz <[email-masked]>
Date: Wed, 28 Sep 2005 12:28:45 -0700

Dan,

> I don't believe you. Your paper claims ``no more than 1/2^60,'' but it
> isn't possible to obtain the exact 1/2^60 bound from feeding a 1/2^60
> function bound through a function-to-permutation switch, even if  
> (as you
> claim) the switch is applicable. Something close to 1/2^60 is  
> plausible,
> but that wouldn't justify the claim of ``no more than 1/2^60.''

The 1/2^60 bound collects a few terms, and we write 1/2^60 because  
that is nicer for most readers than to look at an uglier summation.  
The actual hash collision bound is closer to 1/2^61, which can  
withstand a small constant multiplier for the switch from function to  
permutation. The bound is correct.

> More importantly, you claim that your apparently-never-written proof
> relies on a March 2005 theorem of mine. But you were already  
> claiming in
> January 2005 to have ``rigorously proven'' a security bound of ``about
> 1/2^60.'' Do you admit that, at the time, you weren't capable of  
> proving
> this bound without severely limiting the number of messages to  
> something
> like 2^34?

What is relevant to the current discussion is whether the UMAC draft  
is correct. If you believe the draft has inaccuracies, please point  
them out.

UMAC is rigorously proven. We have good almost-SU bounds on UHASH  
collision probabilities, we know that almost-SU hash families along  
with random functions make good MACs, and your theorem shows that  
moving to a permutation has a small multiplicative effect up to $2^64 
$ uses.

As for the history, when we wrote that UMAC was rigorously proven, we  
were only considering the hash function's properties (as that is the  
most important component affecting real security). As you point out,  
we ignored the birthday bound for limiting permutation use. It is not  
that we "weren't capable" of including the birthday bound, it is  
simply that we didn't consider it. As your research shows, this is  
not an unreasonable thing to do. Nevertheless, it was an oversight  
that probably should not have happened, and I'm sorry that it did.

Sincerely,
Ted Krovetz

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

---

From: Hal Finney <[email-masked]>
Date: Wed, 28 Sep 2005 14:47:20 -0700

Let me throw another complication into the debate about security bounds.

As I understand it, the original Wegman-Carter construction looked
like UH(msg) + f(nonce) where UH is a universal hash, f is a random
function, and "+" is some field operator. For reasons which are not
completely clear to me, implementations of this idea like UMAC and Dan
Bernstein's Poly1305-AES substitute a random permutation p(nonce) for
the random function f(nonce). This is implemented as a block cipher,
usually AES.

The original WC security analysis based on a random function does not
go through when using a random permutation. Dan's Eurocrypt 2005 paper
explores this difference and develops improved security bounds when
using a random permutation. This work is referenced by Ted Krovetz to
support the UMAC security bounds.

My comment is that UMAC actually does not use either a random function
or a random permutation, except for the UMAC-128 variant. Shorter
versions like UMAC-64 (which is probably going to be the most
popular), use a truncated block cipher for f().

On the one hand, this is arguably at least as good as using a random
permutation. A 64-bit truncated AES should actually be pretty close to
a random function. On the other hand, we have analyses for random
functions and for random permutations, but technically a 64 bit
truncation of AES is neither. Perhaps this points to a gap in the
security proof.

Adding further complexity, UMAC does not just truncate the AES to 64
bits; rather, for two consecutive nonces, it uses alternating halves
of a single AES invocation for f(). It uses the left half of
AES(nonce) for even nonces, and the right half of AES(nonce-1) for
odd. This means that even if we considered a 64 bit truncation of AES
to be like a random function, if we look at two consecutive nonces,
there is correlation between the random functions used for those cases
due to the fact that they are the two halves of a permutation.

I don't think the security proofs take this complexity into
consideration. In practice, it's probably OK because truncating AES
should not be any worse than using it untruncated. But for provable
security it would be good to see some discussion of whether the
optimization of using one AES for two nonces is OK.

Hal Finney

---

From: Ted Krovetz <[email-masked]>
Date: Wed, 28 Sep 2005 17:29:51 -0700

Hal,

> popular), use a truncated block cipher for f().

As you said, Wegman-Carter MACs are secure when used with a random  
function f (eg, UH(msg) + f(nonce)). This applies even in the case of  
UMAC's splitting of outputs for consecutive nonces because the halves  
are independent for a random function. What Bernstein's theorem says  
is that it does not matter HOW the function f is used, but instead  
HOW MANY times it is used. In moving from a random function to a  
random permutation, degradation of security is no worse than a small  
multiple for up to 2^64 applications of f. So even though you might  
imagine that f() output half-splitting might introduce a weakness  
when using a permutation, it simply is not true.

As for moving from a random permutation to AES, that had better not  
cause a significant degradation in security, or else AES is not  
behaving as we all expect it to.

-Ted

---

From: "D. J. Bernstein" <[email-masked]>
Date: 30 Sep 2005 04:36:34 -0000

Ted Krovetz writes:
> UMAC is rigorously proven.

I don't believe you. It seems possible, perhaps even likely, that such a
proof exists; but it's also clear that you haven't done the work yet.
The risk of error is still unacceptably high.

In October 2004 you claimed various ``rigorously proven'' bounds on the
UMAC forgery probability. It's crystal clear that this claim was false;
I'm sure that nobody knows how to prove those bounds; in fact, I think
that your alleged bounds were flat-out wrong. (I'm reminded of the OAEP
fiasco, where Bellare and your coauthor Rogaway claimed a security
theorem that they weren't actually able to prove and that's now widely
believed to be incorrect, although several applications of the claimed
theorem were subsequently rescued by more sophisticated techniques.)

The problem wasn't that you tried to write a proof and made a mistake.
The problem was that you didn't even bother writing a proof. You looked
at the collision-probability bounds in Black's thesis; you incorrectly
assumed that forgery probabilities can't exceed collision probabilities
(as you now admit); and then you falsely stated that your bounds had
been ``rigorously proven.''

The same problem exists now. You have new resources at your disposal,
specifically a theorem that helps transfer some forgery-probability
bounds from uniform random functions to uniform random permutations, but
all you've done with those resources is assert that they're applicable.
Saying ``Another result [2], when combined with [3, 6], shows that [blah
blah blah]'' is a far cry from giving a rigorous proof. You haven't even
given a careful _statement_ of your alleged security bounds; you've
neglected to add the AES distinguishing probability, for example.

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

---

From: "D. J. Bernstein" <[email-masked]>
Date: 30 Sep 2005 05:05:18 -0000

Hal Finney writes:
> For reasons which are not completely clear to me, implementations of
> this idea like UMAC and Dan Bernstein's Poly1305-AES substitute a
> random permutation p(nonce) for the random function f(nonce).

The reason is simple: We're taking advantage of the community's (perhaps
misplaced) trust in the security of a block cipher, namely AES.

I suspect that future cryptographers will regard the notion of a block
cipher as a historical accident, not something to actually be deployed
in any sort of cryptographic protocol. Using Poly1305 with a stream
cipher is easy: insert 128 blank bits at the beginning of the message
being encrypted, and steal those 128 bits of ciphertext for Poly1305.

Ted Krovetz writes:
> What Bernstein's theorem says  is that it does not matter HOW the
> function f is used, but instead  HOW MANY times it is used.

It's certainly true that the main parameters in the theorem are the
maximum number of f applications and the size of f's domain. However, to
apply the theorem, you also need a bound on Pr[A(f) = 1]; and producing
that bound requires knowing how f can be used by the algorithm A.

I agree that splitting isn't inherently a problem. The real question is
how UMAC chooses oracle inputs.

---

From: Hugo Krawczyk <[email-masked]>
Date: Fri, 30 Sep 2005 08:40:54 +0300 (IDT)

> The risk of error is still unacceptably high.

Indeed, I conjecture that the risk of error in our proofs after 2^64
annoying messages from Dan Bernstein to the cfrg list is still around
2^{-61} which as we all know is unacceptably high for the Gods but a great
accomplishment for erring mortals like myself.

Just in case you celebrate Rosh Ha-Shana (and also if you don't):
HAPPY NEW YEAR :)

Hugo