Subject: [Cfrg] New UMAC Draft

From: Ted Krovetz <[email-masked]>
Date: Tue, 27 Sep 2005 13:19:02 -0700

Hello,

In response to various comments in this list we have revised the
UMAC draft.

  http://www.ietf.org/internet-drafts/draft-krovetz-umac-05.txt

We have not changed anything algorithmically or in the
specification of UMAC, nor have we changed any of our claims.
But we added further clarifications where needed according to the
received comments.

The most substantive changes we made were

* Addressing explicitly the insignificance of the birthday bound in
   the context of UMAC. In particular, the Security Considerations  
section
   now states explicitly that our forgery bounds on UMAC hold for up  
to the
   generation of 2^64 MAC tags, citing Bernstein's work in this area.

* Added a paragraph in the Security section warning against the
   possibility of timing-attacks is POLY is not carefully implemented.

* Added a paragraph in the Security section warning against prefix-
   verification.

We also took this opportunity to make numerous editorial changes that
caught our eyes while we made these other changes.

We thank those providing well-intended comments.

Thank you,
Ted Krovetz

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

---

From: Hal Finney <[email-masked]>
Date: Tue, 27 Sep 2005 16:59:55 -0700

---------- Forwarded message ----------
From: Hal Finney <[email-masked]>
Date: Sep 27, 2005 4:58 PM
Subject: Re: [Cfrg] New UMAC Draft
To: Ted Krovetz <[email-masked]>

>   http://www.ietf.org/internet-drafts/draft-krovetz-umac-05.txt

I have been wondering about the problem of attackers reusing nonces.
At the end of section 6.2 you write:

   It should be pointed out that once an attempted forgery is
   successful, it is possible, in principle, that subsequent messages
   under this key may be forged, too.  This is important to understand
   in gauging the severity of a successful forgery, even though no such
   attack on UMAC is known to date.

I don't know if you have looked into this "in principle" possibility
very much, but I don't see a lot of resistance in UMAC against finding
subsequent forgeries with a given nonce, once you have valid tags for
two different (perhaps chosen) messages with that nonce. I haven't
worked it out in detail but it looks like it should be possible to use
the information from a valid forgery to speed up subsequent forgeries
(all with the same nonce). Do you have any estimations of how
resistant UMAC is likely to be to such an attack? Was such resistance
part of the UMAC design?

This affects the discussion of the replay attack in 6.4:

   A replay attack entails the attacker repeating a message, nonce, and
   authentication tag.  In many applications, replay attacks may be
   quite damaging and must be prevented.  In UMAC, this would normally
   be done at the receiver by having the receiver check that no nonce
   value is used twice.

There are really two kinds of replay attacks: message+nonce replays as
is described in the first sentence; and nonce replays (with different
messages). These latter attacks are how one would exploit the
theoretical vulnerability mentioned above. Now, the countermeasure
suggested here, watching for duplicate nonces, successfully defends
against both attacks. However the discussion does not make the threat
of the nonce replay attack very clear.

I am concerned that these theoretical nonce-replay attacks may become
possible. However the way the issue is presented, an implementor may
not realize that he has to worry about them. He might choose UMAC-32
in an environment where plain replay attacks are not a problem, but
still think he is not going to have more than 1/2^30 of the messages
come through as forgeries. In that case he would be vulnerable if it
does turn out to be possible to multiply forgeries.

My opinion is that UMAC-32 is really not a very safe mode of operation
due to this problem. At a minimum, you need to emphasize the
importance of avoiding nonce replays. With UMAC-64 on up it is really
not an issue because finding the first forgery is so difficult that
you can pretty much ignore it. But with UMAC-32 it is very possible,
and if that first forgery leads cheaply to others (in an environment
which doesn't detect nonce replays) the security is lost.

Hal Finney

---

From: Ted Krovetz <[email-masked]>
Date: Tue, 27 Sep 2005 20:00:23 -0700

Hal,

> I have been wondering about the problem of attackers reusing nonces.

In the standard security model of MACs, the adversary is allowed to  
repeat nonces when attempting to forge. So our N/2^{30,60,90,120}  
bound for at least one successful forgery over N attempts holds even  
if the verifier is not checking for repeated nonces. So, in actuality  
<msg,nonce,tag> replays are the only ones we really care about, and  
we can defend against them by disallowing repeated nonces.

Now it is most likely true that an attacker wishing himself success  
would like to attack 32-bit nonces on a system that allows repeated  
nonces because that is likely the scenario that maximizes his  
probability of success, but that success is still bounded by N/2^30.

How much stronger would UMAC be if repeated nonces were not allowed  
for forgery attempts? The new nonce would cause a new, nearly random  
pad value, making the chance that the tag matches h(m) xor aes(nonce)  
about 1/2^32.

-Ted

---

From: "D. J. Bernstein" <[email-masked]>
Date: 28 Sep 2005 12:10:59 -0000

Ted Krovetz writes:
> for forgery attempts?

So, if you use the standard nonce sequence 0, 1, 2, 3, ..., the attacker
can destroy your connection by first sending forgeries with nonces 0, 1,
2, 3, ...? Brilliant.

Of course, this ludicrously fragile network protocol fails to solve the
problem under discussion, which is that your 2^30-packet attacker gains
so much information about the UMAC key (by seeing which forgeries work)
that he can then trivially replace all of your subsequent messages with
the messages of his choice. If he prevents the original messages from
getting through then there won't be any repeated nonces to detect.

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

---

From: "D. J. Bernstein" <[email-masked]>
Date: 28 Sep 2005 13:49:13 -0000

Ted Krovetz writes:
> In particular, the Security Considerations section
> to the generation of 2^64 MAC tags

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.''

Aren't you embarrassed to claim that something has been ``rigorously
proven'' when you haven't even written down the claimed _theorem_, never
mind the proof?

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?

When you claimed to have ``rigorously proven'' this bound, you were
claiming not just that it was true, but that you had _proven_ it. That
was a false claim. Perhaps someone now has a proof, but that doesn't
retroactively make your claim true. You owe the community an admission
that you did not, in fact, have the proof that you claimed to have.

Science moves forward because it has mechanisms to detect and correct
errors. Your refusal to admit your errors is despicable behavior.

---

From: David McGrew <[email-masked]>
Date: Wed, 28 Sep 2005 08:21:13 -0700

Dan,

> but that wouldn't justify the claim of ``no more than 1/2^60.''

this is an important technical comment.  If the forgery bounds aren't  
right, it would be good to correct them.

However, some of your comments below stray from technical issues on  
to personal ones.  Please keep the latter off this email list.

> errors. Your refusal to admit your errors is despicable behavior.

Despicable behavior?  Let him who is without sin cast the first stone.

It is important that we avoid having an atmosphere of hostility in  
the RG.  We rely on voluntary participation, and don't want to drive  
away potential contributors.

David

---

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

> we can defend against them by disallowing repeated nonces.

Okay, but then if you allow the attacker to repeat nonces at will, you
have the problem that if he manages even one forgery, then in
principle your security is gone, right? This is what you describe as:

My main concern is from the perspective of an implementor who might be
familiar with a CBC-MAC or HMAC construction, where a single "lucky"
successful forgery does not allow the attacker to arbitrarily forge
future messages with 100% success rate. This behavior of Wegman-Carter
MACs may come as a dangerous surprise to an implementor. I just want
to be sure that readers are adequately warned of the dangers of using
short authenticators while allowing nonce replays.

Perhaps you could reword the above paragraph to say something like:

"It should be pointed out that once an attempted forgery is
successful, this can in principle leak enough information about the
key to allow an attacker to forge subsequent message tags at will.
This is important to understand in gauging the severity of a
successful forgery, even though no such attack on UMAC is known to
date."

Hal Finney

---

From: Mark Baugher <[email-masked]>
Date: Wed, 28 Sep 2005 20:36:04 -0700

Dan,

> errors. Your refusal to admit your errors is despicable behavior.

I think this remark is not only counter-productive but in violation  
of list policy.  It really is not acceptable by our standards here.

Mark