Subject: Re: [Cfrg] New UMAC Draft

From: Ted Krovetz <[email-masked]>
Date: Sat, 1 Oct 2005 11:26:29 -0700

> I'm going away for a few days. In my absence, please run the
> following algorithm
>
>

Funny thing... It turns out they have the Internet in the cafes of  
San Francisco!

> Please define ``secure'' and then show us the proof of this claimed
> forgery-probability bound.
>
>

Dan, I suggest to you that we have strayed far from the point of this  
discussion. On September 9, Russ Housley asked if there were any  
``cryptographic concerns'' with UMAC. You have stated your concerns  
and we have responded both online and with a revised Internet-Draft.  
Your concerns at this point no longer seem to me to be cryptographic  
in nature, but instead seem to be about history and process (ie, what  
bounds were claimed in the past and should RFCs be accompanied by  
formal proofs).

Clearly you believe that an \e-SU hash family wed with AES makes a  
good MAC (witness Poly1305-AES). So, your demands for "show me the  
proof, show me the proof", peppered with "your bounds were  
inaccurate, your bounds were inaccurate" ring as hollow haranguing to  
me. If you have any cryptographic concerns with our claim that UHASH  
is \e-SU or that it is wed appropriately with AES, please detail the  
worry (in any security model of your choosing).

I contend that a proof that UHASH is \e-SU along with the proofs of  
Wegman, Carter and Bernstein should be enough for any cryptographer  
worth his salt to be satisfied enough to accept UMAC passing into an  
RFC.

If you don't think people should use UMAC or if you can find a  
weakness in any security model of your choosing, you are welcome to  
publish your findings in whatever forum you choose. But, please, in  
the meantime, keep your comments focussed on cryptographic concerns  
affecting UMAC's passing into an RFC.

Ciao from North Beach,
Ted Krovetz

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

---

From: "D. J. Bernstein" <[email-masked]>
Date: 2 Oct 2005 00:22:01 -0000

Ted Krovetz writes:
> On September 9, Russ Housley asked if there were any  
> ``cryptographic concerns'' with UMAC.

I find myself extremely skeptical of your claimed bounds on the
attacker's single-forgery probability against UMAC: 2^(-30), 2^(-60),
2^(-90), and 2^(-120). Would you be surprised if I told you that I have
an attack achieving a larger forgery probability? How about much larger?

It is thoroughly irresponsible of you to claim ``rigorously proven''
bounds that you have not, in fact, proven. This is not merely a question
of dotting the i's and crossing the t's; there is a very important piece
of the proof that you obviously haven't even tried to do.

It is not _my_ responsibility to demonstrate that your bounds are wrong.
It is _your_ responsibility to avoid making unjustified claims. Suppose
that a user chooses UMAC-128 on the basis of your ``rigorously proven''
2^(-120) bound on the probability of a forgery succeeding, and then that
bound turns out to be incorrect; wouldn't you be ashamed for having
misled the user?

I am _not_ saying that UMAC is easily breakable. UMAC is close to
Gilbert-MacWilliams-Sloane, and I'm willing to believe that the changes
don't destroy security. However, I find myself extremely skeptical of
your specific quantitative claims of forgery-probability bounds.

> good MAC (witness Poly1305-AES).

The Poly1305-AES paper gives a precise statement and proof of the
Poly1305-AES security bound.

If you're going to claim a security bound then you need to show us a
proof. Your UMAC security claim is as follows, for each n in {1,2,3,4}:

   Claimed theorem. An attack against UMAC-32n using at most 2^64 chosen
   messages and one forgery attempt cannot have success probability
   larger than 2^{-30n}, if AES is secure.

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

---

From: "D. J. Bernstein" <[email-masked]>
Date: 3 Oct 2005 15:35:12 -0000

draft-krovetz-umac-05.txt claims that UMAC ``has been rigorously proven
to be secure.'' It makes the following specific security claim: ``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.''

I'm going to rip this ``rigorously proven'' security claim to shreds, by
showing you an easy attack on UMAC-128 whose forgery probability is
indisputably much larger than 1/2^120.

Before I present the attack, let me emphasize some basic epistemology.
It perhaps wasn't known earlier that the UMAC security claims are wrong.
However, the characterization of the security claims as ``rigorously
proven'' has always been wrong, and has always been known by the UMAC
authors to be wrong. Stating that the forgery probability ``is no more
than ...'' has always been a misrepresentation of the available
knowledge. The UMAC authors were obliged to say ``is conjectured to be
no more than ...'' unless and until they proved the conjecture (which we
now know isn't possible, since the conjecture is wrong).

I'm quite disappointed at the ruthlessly anti-mathematical attitude that
has been displayed by the UMAC authors throughout this discussion, and I
hope that their shame at claiming bogus ``rigorously proven'' security
bounds leads them to understand the importance of proofs in the future.

Anyway, here's the attack. Observe first that the complete UMAC-128 key
is 128 bits:

   If AES is used with 16-byte keys ... KEYLEN would equal 16. ...
   Unless specified otherwise, AES with 128-bit keys shall be assumed to
   be the chosen block cipher for UMAC. ...

   UMAC algorithm Input: K, string of length KEYLEN bytes. M, string of
   length less than 2^67 bits. Nonce, string of length 1 to BLOCKLEN
   bytes. taglen, the integer 4, 8, 12 or 16. ...
   
   UMAC-128(K, M, Nonce) = UMAC(K, M, Nonce, 16)

The attacker collects an authenticator UMAC-128(K,M,N) on a known
message M with a known nonce N by watching the sender. The attacker then
generates 2^40 uniform random 16-byte strings G, and for each G computes
UMAC-128(G,M,N). (I haven't found thorough UMAC-128 benchmarks, but I
think each UMAC-128 evaluation takes fewer than 2^15 Pentium-4 cycles,
for a total of a day on a bank of 2^7 Pentium-4s.) If there's a match
between UMAC-128(K,M,N) and some UMAC-128(G,M,N), the attacker picks one
G and generates a forgery attempt UMAC-128(G,M',N') on the attacker's
selected message (M',N').

The probability that UMAC-128(K,M,N) = UMAC(G,M,N), for uniform random
(G,K) such that G != K, is indisputably below 2^(-60). (Any larger
number would---unless UMAC seriously screws up its uses of nonces---be a
shocking revelation about AES; any larger number would imply that 2^35
different keys have an overwhelming chance of UMAC-128 output
collisions, which would easily be detected by a small computer
experiment; and, more to the point, any larger number would imply an
even simpler attack on UMAC-128 with forgery probability above 2^(-60).)

Consequently, the probability that the first guess G_1 is different from
K, that UMAC-128(K,M,N) = UMAC-128(G_1,M,N), and that one of the other
guesses matches K, is at most

   (1 - 2^(-128)) 2^(-60) (1 - (1 - 2^(-128))^(2^40 - 1))

since each guess is independent. The same comment applies to the second
guess, the third guess, etc., so the overall probability that some guess
G != K has UMAC-128(K,M,N) = UMAC-128(G,M,N), with another guess
matching K, is at most

   2^40 (1 - 2^(-128)) 2^(-60) (1 - (1 - 2^(-128))^(2^40 - 1)).

The probability that some guess matches K is exactly

   1 - (1 - 2^(-128))^(2^40)

so the probability that some guess matches K, without any other guess G
having UMAC-128(K,M,N) = UMAC-128(G,M,N), is at least

   1 - (1 - 2^(-128))^(2^40)
   - 2^40 (1 - 2^(-128)) 2^(-60) (1 - (1 - 2^(-128))^(2^40 - 1))
   
which is larger than 2^(-88.001). In this situation, the attacker's
selected G is exactly K, and the attacker's forgery attempt works.

To summarize: This attack inspects one valid UMAC-128 tag, performs a
reasonable amount of computation, and generates one tag on a message of
its choosing; this tag is correct with probability above 1/2^(88.001).
For comparison, here is the ``rigorously proven'' UMAC security bound:

   When UMAC produces ... 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^120.

The attack directly contradicts this ``rigorously proven'' bound:
1/2^(88.001) is larger, in fact a whopping 2^32 times larger, than
1/2^120.

I should note that there are other security claims in the UMAC document,
such as a claim in Section 6.2 that forgery probabilities are small if
``AES is secure.'' The UMAC authors have ignored my repeated requests
for a definition of ``secure,'' so they might now claim that AES is not
actually secure, retroactively making their Section 6.2 claim vacuously
true and completely useless. However, this sort of weaseling doesn't let
them escape the fact that their Section 1 security claim is wrong.

---

From: David McGrew <[email-masked]>
Date: Wed, 5 Oct 2005 05:19:21 -0700

Hi Dan,

your point is that the security claims in draft 05 don't take into  
account simple key-guessing attacks.  You're right, a such an attack  
can be used to distinguish AES from a random permutation, which the  
claims glossed over.  But it is easy enough to change the claims so  
that they are correct:

    In the case of UMAC the above guessing-attack strategy is close to
    optimal.  For example, in the case of UMAC-64 an adversary can
    correctly guess an 8-byte UMAC tag with probability 1/2^64 by simply
    guessing a random value.  The results of [3, 6] show that no  
feasible
    attack strategy can produce a correct tag with probability better
    than 1/2^60 if UMAC were to use a random function in its work rather
    than AES.  Likewise 32-, 96- and 128-bit tags cannot be forged with
    more than 1/2^30, 1/2^90 and 1/2^120 probability.  Another result  
[2],
    when combined with [3, 6], shows that UMAC is secure under  
reasonable
    assumptions about AES, whenever no more than about 2^64 messages are
    authenticated.

I also suggest to add something like the following:

    Therefore, we require that that each value of the key MUST NOT be  
used
    in more than 2^64 invocations of the tag generation
    algorithm, and MUST NOT be used in more than 2^64 invocations of
    the tag verification algorithm.

This concrete guidance is important because the vast majority of the  
implementers won't determine the appropriate usage limitations from  
whatever bounds are given or referenced.

Of course, what I've done with my edits above is merely gloss over  
the details in the claims (please let me know if you think the claims  
above are in error).  This would be completely unacceptable in a  
scientific publication, but we're discussing a draft spec.  Let me  
know what you think.

David

---

From: "D. J. Bernstein" <[email-masked]>
Date: 5 Oct 2005 17:04:14 -0000

There are several different cryptanalytic threats against UMAC, and none
of them should be hidden from the users.

My 10 September 2005 message spent several paragraphs explaining the
best UMAC-64 forgery-probability bound that had been proven, namely

   Pr[at least one forgery is successful] <= D/2^60 + A^2/2^129 + delta

where D is the number of forgery attempts, A is the number of AES inputs
used in legitimate messages and in forgery attempts, and delta is the
attacker's AES-breaking probability. Each term here is important:

   * The D/2^60 term allows the attacker to forge blindly, or perhaps
     2^4 times better than blindly by modifying known authenticators.

   * ``At least one forgery is successful'' allows the attacker to
     succeed in as many as D forgeries.

   * The A^2/2^129 term allows the attacker to take advantage of the
     guaranteed lack of collisions in AES outputs.

   * The delta term allows the attacker to guess the AES key---note that
     this is qualitatively a quite different type of guessing from blind
     forgeries---or conceivably to cryptanalyze AES.

For example, the claim ``UMAC has been rigorously proven to be secure''
is an exaggeration of the truth, because it ignores the possibility of
AES being cryptanalyzed. Once again: None of these threats should be
hidden from the users!

My message then identified three separate ways that this bound was being
misrepresented in the UMAC specification: the delta term was often
omitted; the A^2/2^129 term was always omitted; and Pr[at least one
forgery is successful] was viewed as a limit on the number of successful
forgeries. My message also pointed out three timing-attack issues.

I indicated a way that the A^2/2^129 term could perhaps be improved by a
careful function-to-permutation switch---although I don't know enough
about UMAC's AES inputs to verify that the switch is possible. What one
hopes for, as a proven result, would reduce A to 1 plus the number of
AES inputs used in legitimate messages, and would replace D/2^60 +
A^2/2^129 + delta with (1 - A/2^128)^(A/2) D/2^60 + delta.

>    used in more than 2^64 invocations of the tag generation algorithm,

As far as we know, a restriction of that type is critical for security.
One hopes for a bound that looks like D/2^59 + delta, maybe better,
under this restriction on the reduced A.

>    and MUST NOT be used in more than 2^64 invocations of

As far as we know, that's superstitious nonsense having nothing to do
with security. It's much too large to save the original A^2/2^129, and
it has zero effect on the reduced-A bounds.

---

From: John Wilkinson <[email-masked]>
Date: Wed, 5 Oct 2005 16:58:42 -0400

On 10/5/05, David McGrew <[email-masked]> wrote:
> account simple key-guessing attacks.

[snip]

> whatever bounds are given or referenced.

[snip]

David, I don't think your suggestion is relevant to Bernstein's attack
(though I agree that it is desirable to include such strict guidance
anyway). As far as I can tell, Bernstein's attack works if AES is used
with a 128-bit key, by the legitimate parties to the communication, to
generate and verify only *one* tag. Limiting repeated use of the key
does nothing to change the fact that the following claim is incorrect:

   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

It is true that other MACs, such as HMAC and CMAC, have the same
susceptibility to key-guessing attacks, but, IIRC, the HMAC and CMAC
specifications do not make quantitative claims on "the probability
that an attacker can produce a correct tag for any message of its
choosing".

IMHO, if an author wishes to make a claim of security in a standards
document, that claim should be stated as precisely as possible.

If the author wishes to state the claim as proven (rather than as
conjectured), a complete proof should be referenced, and not left
incomplete as an exercise to the reader.

I would suggest that after the UMAC authors have completed their proof
and made it available, that their security claims could be slightly
modified to state something like the following:

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 + Delta, 1/2^60 + Delta, 1/2^90 + Delta or
1/2^120 + Delta, respectively, where Delta is the probability that an
attacker can break the block cipher utilized by UMAC.

-John

---

From: David McGrew <[email-masked]>
Date: Thu, 6 Oct 2005 14:44:43 -0700

> it has zero effect on the reduced-A bounds.

On the contrary, it significantly affects the expected number of  
successful forgeries, since an attacker who succeeds in forging one  
message will be able to forge messages at will afterwards.

Also, the usage bounds should clearly be smaller for the shorter tags.

David

---

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

David McGrew writes:
  [ on limiting the number of tag verifications to 2^64 for one key ]
> message will be able to forge messages at will afterwards.

I understand what you're saying, and I agree with the calculations, but
I think that this situation is an unmitigated disaster long before the
18446744073709551617th successful forgery.

We don't have to engage in this sort of calculation with MACs that are
properly designed to guarantee that, with overwhelming probability,
there are _zero_ forgeries. The problem with UMAC-64 is that, for the
sake of a 33% speed improvement, it treats an occasional forgery as
something acceptable---forcing us to ask exactly how much damage is
actually done on those occasions.

---

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

[co-chair hat on]

Dan,

In the note below, as well as in many others, you keep using abusive
and offensive language that is not appropriate for human discourse in
general, and especially not for collegial technical discussion lists such
as CFRG. This goes on in spite of repeated requests to stop.

It is hard for me to speculate what brings you to this jouvenile
behavior. In any case, I doubt that it helps you gain respect from the
readers of your postings.

Once more, please try to change your tone. I assure you that this will
only help in getting your technical points heard.

Ran

---

From: "D. J. Bernstein" <[email-masked]>
Date: 7 Oct 2005 20:34:10 -0000

The UMAC authors continued making false ``rigorously proven'' security
claims for many months, despite my polite explanations of exactly what
was wrong with their claims. Labelling them as liars---which is exactly
what they are---has finally succeeded in making them back off from some
of their false claims. It's vastly more important for the users to have
accurate security information than for the UMAC authors' fragile egos to
be coddled.

---

From: canetti <[email-masked]>
Date: Sat, 8 Oct 2005 18:02:57 -0400 (EDT)

Dan,

I maintain that your abusive and intentionally insulting language is
highly inappropriate as well as counter-productive. I dont think that the
list should suffer such language under any circumstances.

Also, I find painting this language as a necessary means to
get the cooperation of the UMAC authors to be quite ridiculous.
In fact, going over the discussion starting from your Sept 10 note,
I get the strong impression that the author's willingness to respond
to your comments decreased significantly as your insults grew louder.
They were also very responsive to comments by others.

Ran

To the rest of the list: I feel quite ridicuous myself playing the
"policeman" here, and I'm sure that David feels the same way. I'd love to
get a feeling of what the list members feel regarding this issue: should
there be limits on abusive language? what steps should be taken to
enforce them?

---

From: "D. J. Bernstein" <[email-masked]>
Date: 9 Oct 2005 01:47:52 -0000

> In fact, going over the discussion starting from your Sept 10 note,

Try starting from my 18 January 2005 note. Almost all of the issues that
we're discussing now were highlighted in that note, my 20 January 2005
note, and my Eurocrypt paper. The UMAC authors saw all of this---and
then continued making false security claims for many months, disproving
my initial presumption that the exaggerations were accidents.

> the author's willingness to respond to your comments

I get the feeling that you've lost sight of the ball here. As I said
before, it is vastly more important for the users to have accurate
security information than for the UMAC authors' fragile egos to be
coddled. What the authors are ``willing'' to do is not relevant; the
authors are _required_ to withdraw their false security claims.