Subject: [Cfrg] UMAC security proof posted

From: Ted Krovetz <[email-masked]>
Date: Thu, 6 Oct 2005 12:17:46 -0700

Dear all,

UMAC is a Wegman-Carter-style MAC, which is based on the universal  
hash function UHASH. We proved that the "collision probability" of  
UHASH is at most 2^-30i for i \in {1,2,3,4}. As with all Wegman- 
Carter MACs using AES, this means that the maximum forging  
probability is 2^-30i, plus an error term that depends on an attack  
on AES.

At the following URL, you will find a sequence of straightforward  
lemmas, with some explanations, which prove our stated bounds.

   http://www.cs.ucdavis.edu/~rogaway/umac

The main reason for the need of this note is that our prior  
publications referred to an implementation of UMAC using a PRF while  
the current spec uses AES, a PRP. The note formalizes and quantifies  
what you get by basing security on a PRP instead of on a PRF.

Some on the list suggested that our proofs could be more formal. We  
wish to point out that the most important proofs were laid out very  
formally in Krovetz's PhD thesis, and that the level of details in  
the UMAC proofs far exceeds that of other common crypto schemes (be  
it HMAC, CCM, counter-mode, etc.)

The proofs on the above URL represent the "most formal" proofs that  
we have had time to produce. We believe that this level of detail is  
more than enough for anyone to be able to verify our claims. Short of  
a journal-version of the UMAC paper, we are unlikely to provide any  
more details.

Also, we are currently making minor revisions to the I-D to make more  
explicit that UMAC has a forgery probability of 2^30i + delta where  
delta indicates PRP distinguishing probability. We do not intend to  
make any other significant changes.

Thank you,
  John Black
  Shai Halevi
  Hugo Krawczyk
  Ted Krovetz
  Phillip Rogaway

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

---

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

> lemmas, with some explanations, which prove our stated bounds.

Much better! Unfortunately, what you've proven are _not_ the bounds you
previously claimed, but some revised bounds. Let's look at the details.

Your Theorem 1 states that a UMAC-32n attacker who inspects at most 2^64
valid messages, and then tries one forgery, has success probability at
most 2^{-30n} + 2.01 delta, where delta is his chance of breaking AES.
Here ``breaking AES'' has its standard meaning: distinguishing AES_k
from a uniform random permutation.

There are still some serious qualitative problems with this guarantee.
For example, any attacker with a reasonably large bank of computers can
push delta above 2^{-70}, so your Theorem 1 doesn't prove significantly
better security for UMAC-96 than it does for UMAC-64, despite your claim
that UMAC-96 provides ``more security.'' We already knew that UMAC-96
didn't achieve your previously claimed 2^{-90} bound on forgery
probabilities; your revised bound isn't even in the same ballpark!

As for UMAC-64, to rescue your claimed 2^{-60} forgery-probability bound
using the 0.545 2^(-60) + 2.01 delta from Lemma 9, you'd need to assume
a bound on delta somewhat below 2^{-62}---and, in particular, you'd need
to assume that the attacker is not capable of carrying out a 66-bit
brute-force search. I don't think that's a reasonable assumption.

Furthermore, even if you had a 2^{-60} bound on the success chance of
_one_ forgery attempt, you wouldn't have a 2^{-60} bound on the success
chance of _many_ forgery attempts. Each forgery attempt has its own
chance of success; even worse, a successful forgery will (presumably)
leak enough information to allow many more forgeries for free.

I'd guess---by analogy with traditional Wegman-Carter MACs---that it's
possible to prove much better bounds for UMAC-96, perhaps something like
Pr[at least one forgery succeeds] <= 2^{-90} D + 2.01 delta, where D is
the number of forgery attempts. This is billions of times smaller than
the (2^{-90} + 2.01 delta) D that you've proven so far, and I think that
it would justify referring to UMAC-96 as safe. But UMAC-64 will remain
fairly dangerous, clearly not something that implementors should select.

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

---

From: John Wilkinson <[email-masked]>
Date: Thu, 6 Oct 2005 21:14:09 -0400

Ted, et al,

Thank you for posting the proof, I read it with interest. Since you  
have agreed to include the "delta" term explicitly in the security  
claims, please consider including at least a simplified (one  
sentence) explanation in the introduction and wherever else you make  
quantitative claims, as well as a more detailed exposition in the  
security section. Unfortunately, many people never read past the  
introduction.

On a more qualitative note, is there a reason not to make UMAC-96 the  
"default" recommendation? While I can envision good applications for  
UMAC-64 (and even UMAC-32), I would think that most new applications  
should use UMAC-96 or -128. Does CFRG have any standard  
recommendations for MAC tag-length?

Thanks.

-John

---

From: Hal Finney <[email-masked]>
Date: Thu, 6 Oct 2005 22:13:16 -0700

On 6 Oct 2005 22:07:44 -0000, D. J. Bernstein <[email-masked]> wrote:
> But UMAC-64 will remain

Could you clarify the problem with UMAC-64? Is it a generic problem
with 64 bit MACs, that they have a forgery probability of no better
then 2^-64? Is it a problem with Carter-Wegman MACs, that in addition
to this first-forgery probability, they are vulnerable (at least in
principle) to high-probability subsequent-forgery attacks? Or is it
something more specific to UMAC-64?

Hal Finney

---

From: Hugo Krawczyk <[email-masked]>
Date: Fri, 7 Oct 2005 09:08:08 +0200 (IST)

> recommendations for MAC tag-length?

This, as opposed to much of the confusion and dis-information
instilled into this list in many of the recent postings by
Bernstein, is a very valid (*) and important topic of discussion.

It seems to me that security of the order of 2^{-60} can be too
easily dismissed as inapropriate for the wrong reasons and hence we
try to explain in the draft why this assurance is better than it
may look. The usual reason why 2^{-60} seems inappropriate is that one
is misled to think that such level of security implies the existence
of an attack that after a 2^60 work factor can break the
construction (say, find the key or forge msgs at will). This however
is not the case of UMAC.

You can forge UMAC-64 with probability 2^{-60} but just working 2^60
time is of no help in improving this bound. Short of breaking AES,
your best bet is to try more and more forgeries. After a very large
number of forery attempts (say 2^30) you still have a very small
probability (2^{-30}) of a successful attempt. Is this trade-off
sufficient for security? I believe this to be appropriate for many
applications.  Indeed, I believe so in spite of the fact that, in
principle, after a first successful forgery subsequent forgeries may
be much easier to achieve.  In the past we used the following
analogy with DES.  The need to abandon DES was not based on the
possibility of an attacker getting lucky enough to guess a key but
because of the 2^56 (off-line) work factor needed to find a key with
probability ~1. As said, this work factor does not exist with UMAC
and the attack not only needs a lot of luck but also is inherently
on-line (i.e. fully involved with on-line communication).

Having said this I can see many applications where trading 50%
increase in running time for 2^30 times reduction in forgery
probability is the right thing to do (especially that UMAC-96 is
still very fast!). That's one of UMAC virtues: it let's you choose
your security/performance tradeoff level.  And I am not talking
about letting an end user choose the right level but for an
application/protool/standard to decide on this. For example, if the
discussion was about securing a specific application (say TLS) then
a more detailed discussion specific to the application would be
required. At this point I do not see the need to make these
decisions, but rather leave the possibilities open for a case by
case judgement.

Hugo

(*) Unfortuantely, some seem to believe that Bernstein's postings are
valid and even "reasonable". For the record (and I am not going to
discuss this further) let me say that asking for clarifications,
re-wording, accuracy etc are all valid (and necessary and welcome).
Basing these requests in pseudo-scientific claims, in completely
bogus accusations such as the lack of proofs validating the UMAC
scheme, in non-sense "attacks" that may sound "desvastating" to the
casual reader of the list, and in purely personal offenses is NOT
VALID. Such a conduct by a member of the list should be strongly
condemned.

(I will refer to the specific accusation that we lacked
proofs for UMAC in a separate message.)

---

From: Hugo Krawczyk <[email-masked]>
Date: Fri, 7 Oct 2005 09:11:30 +0200 (IST)

I promised a note on this issue:

Bernstein has repeatedly accused us of lacking the proofs to
validate the security analysis of UMAC and our claims.
This is FALSE (and I see no reason to believe that
Bernstein's accusation were made in good faith -- he is too
technically capable to "miss" the existing proofs)

The sad thing is that after repeating it enough times people start
believing him (that is why I am writing this note). It did not help us to
say that these proofs are available in public domain publications
(for 5+ years), that these works are referred in the I-D, and that
everyone is welcome to read the proofs. Therefore, we decided to fulfil
the request to provide a summary of this proof. We have done so in the
technical note that Ted posted in the UMAC web page.

However, let me make it very clear that all the claims used in that note,
except for one, are taken directly from [3,6] (and from the well-known
Carter-Wegman theory) "proving" (no pun intended) that the proofs were
there all along.

The exception to which I refer is the use of Bernstein's recent result
about the distance between prp's and prf's.  Is this result essential for
our results?  NO! Our previous claims (prior to Bernestein's result) when
applied to the current UMAC specification were the same except that we
needed the following assumption (this is an informal English formulation
that can be replaced with well established mathematical language)

Assumption1: under a feasible number of messages (or queries),
AES in counter mode cannot be distinguished from a random function with a
probability better than d1 (where d1 is a function of the attack
capabilities and is assumed to be insignificant as long as AES in counter
mode is not broken)

In contrast by using new Bernstein's result we could replace Assumption1
with:

Assumption2: under a feasible number of messages (or queries),
AES cannot be distinguished from a random permutation with a
probability better than d2 (where d2 is a function of the attack
capabilities and is assumed to be insignificant as long as AES is
not broken)

Is Assumption2 better than Assumption1? YES. It is somewhat weaker and
much more elegant.

Is assuming Assumption2 legitimate and assuming Assumption1 is not?
NOT AT ALL.
Both are UNPROVEN assumptions and both are resonable assumptions given our
current knowledge.
They have some quantifiable relations but not absolute ones, and the
basis for both is the same: the BELIEF on the security of AES.
Certainly the belief on the security of AES in counter mode is common and
implicit in each one of the many applications using AES in counter mode.

Now, Mr Bernstein is going to "rip these informal explanations to shreds"
hopefully throwing into its response some intimidating numbers and
formulas, and as many as pesonal offenses as possible.
As for me I will stop here before the last hope for sanity is ripped to shreds
forever...

---

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

Hugo Krawczyk writes:
> This is FALSE

Cut the crap, Hugo. Everyone can see that some of your ``rigorously
proven'' UMAC claims (such as ``the probability that an attacker can
produce a correct tag for any message ... is no more than ... 1/2^120'')
were simply wrong. Everyone can see that you've been slowly modifying
other ``rigorously proven'' claims over time, inserting a message limit
here and a factor of 2.01 there.

---

From: "D. J. Bernstein" <[email-masked]>
Date: 7 Oct 2005 11:06:31 -0000

> something more specific to UMAC-64?

UMAC-64 has a combination of problems: it is limited to 64 bits; it
actually seems to be below 60 bits; and any forgery allows a huge number
of extra forgeries. The overall UMAC-64 security level is inadequate.

---

From: Greg Rose <[email-masked]>
Date: Fri, 07 Oct 2005 10:26:09 -0700

At 09:08 2005-10-07 +0200, Hugo Krawczyk wrote:
>probability (2^{-30}) of a successful attempt.

I completely agree, and would even go further. Whether this is good 
enough or not depends to some extent on the system, risk model and 
countermeasures deployed. For example, a system with severely 
constrained bandwidth (say, very low frequency communications to 
submarines) might make it physically impossible to launch many 
forgery attempts. Another possibility is that the system under attack 
might recognise many forgery attempts and take preventative action 
(such as silently blocking the target account). The fact that the 
target must be involved in checking the forgeries places very 
different constraints on the attacker.

Greg.

---

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

Greg Rose writes:
> For example, a system with severely constrained bandwidth (say, very
> low frequency communications to submarines) might make it physically
> impossible to launch many forgery attempts.

This is an internet-draft, not a submarine-net-draft. Normal Internet
applications would be crazy to drop from UMAC-96 down to UMAC-64. We're
talking about saving 1 claimed cycle per byte, and 4 bytes per packet,
at the expense of a huge quantitative and qualitative sacrifice in the
conjectured security level.

> Another possibility is that the system under attack might recognise
> many forgery attempts and take preventative action (such as silently
> blocking the target account).

So now we have a trivial denial-of-service attack.

Automatically switch to another key, you say? Suddenly you're giving the
attacker new forgery chances. You haven't gained any actual security.

---

From: Greg Rose <[email-masked]>
Date: Fri, 07 Oct 2005 14:39:42 -0700

At 20:46 2005-10-07 +0000, D. J. Bernstein wrote:
>This is an internet-draft, not a submarine-net-draft.

Hey, I was on the Australian end of the first IP connection to 
Antarctica, at 50 Baud. Don't give me this "infinite bandwidth" bull.

>  Normal Internet

Sure, "normal" internet applications, I agree; or I would if I knew 
what one was.

>So now we have a trivial denial-of-service attack.

In a CDMA system, denial of service by transmitting white noise is 
trivial. Sending coherent packets with bad MACs is actually pretty damned hard.

All I said was "look at the risk model". I stand by that statement. 
There *are* applications for short MACs.

regards,
Greg.

---

From: "D. J. Bernstein" <[email-masked]>
Date: 8 Oct 2005 02:34:13 -0000

Greg Rose writes:
> trivial.

Assuming a continuous broadcast, right? For comparison, an ``n bad MACs
and you're disabled'' system allows the attacker to pop in, obliterate
your account, and disappear.

(As I said before, if the account has not actually been obliterated---if
the system merely switches keys---then the attacker simply attacks the
new key, so there's no improvement in security.)

> All I said was "look at the risk model". I stand by that statement. 

This sort of risk analysis is almost never done correctly. For example,
people say things like ``a 1 / 2^60 forging probability means that if an
attacker could try out 2^60 MACs, then the attacker would probably get
one right,'' when the reality is that the attacker has a good chance of
getting 2^59 forgeries right.

It's possible to do a correct risk analysis for this sort of dangerous
system. But the bigger picture is that we have better options that, at
low cost, make the risks negligible. You can't justify the existence of
UMAC-64 by merely finding an application that can tolerate high risk;
you have to find an application that can tolerate high risk _and_ that
has a cryptographic cost limit so close to the cost of UMAC-64 (without
being below it) that we can't afford to use anything better.

Can you name an application that meets the second condition? Something
where there's a hard limit on costs, and where UMAC-64 just barely
squeaks in below the cost limit, while better MACs are unusable?