Subject: [Cfrg] UMAC

From: Russ Housley <[email-masked]>
Date: Fri, 09 Sep 2005 19:02:52 -0400

The RFC Editor has been requested to publish "UMAC: Message Authentication 
Code using Universal Hashing."  The document can be found at:

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

Please let me know if any cryptographic concerns with this specification in 
the next two weeks.

Russ  

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

---

From: Hal Finney <[email-masked]>
Date: Fri, 9 Sep 2005 17:42:16 -0700

> Please let me know if any cryptographic concerns with this specification 

There are two issues I am aware of with regard to UMAC. Dan Bernstein 
published a paper at Eurocrypt 05, http://cr.yp.to/papers.html#securitywcs , 
which pointed to some weaknesses in the proof of UMAC security. I think the 
problem was how the security results are stated and claimed, but it might be 
helpful if Dan could comment on the statements in the RFC about the proofs 
of security, to make sure they are accurate.

The second issue is that UMAC has the property that tags can be verified 
incrementally, 32 bits at a time. A 64 bit tag can have the first 32 bits 
verified, and then if they are OK the second 32 bits can be verified. The 
current draft doesn't seem to discuss this but some of the UMAC working 
papers have mentioned it as a possible advantage.

However, from discussion on Dan Bernstein's poly1305-aes mailing list I 
learned that implementing verification in this way opens up a potential 
timing attack. It may allow an attacker to randomly guess tags and, with 
about 2^32 guesses, find a tag which has the first 32 bits right, because 
those take slightly longer to be rejected. Then with the first 32 bits 
fixed, he can try another 2^32 messages and get lucky on the 2nd 32 bits. 
This reduces the security from the claimed 2^60 down to about 2^33.

Although the draft does not recommend implementing this mode, it is 
something that a reader might think of, so it would be good for the draft to 
caution against doing this in any situation where an attacker can 
distinguish whether the verifier accepted the tag.

Hal Finney

---

From: "D. J. Bernstein" <[email-masked]>
Date: 10 Sep 2005 06:35:26 -0000

http://www.ietf.org/internet-drafts/draft-krovetz-umac-04.txt makes
various false and deceptive statements regarding the security of UMAC.

Perhaps I should start by summarizing what _has_ been proven regarding
the security of UMAC:

   (1) There's a hash function inside UMAC. This hash function has been
       proven to have differential probability at most 1/2^60.

       (At least, allegedly proven; I haven't checked the details of the
       proof. But it's certainly not a shocking statement. The hash
       function is a Pentium-4-optimized-and-other-machines-be-damned
       complication of the standard Gilbert-MacWilliams-Sloane hash
       function, which has easy differential-probability bounds.)

   (2) Assume that we use a one-time pad instead of the AES outputs in
       UMAC. Assume that an attacker tries many forgeries against this
       one-time-pad-UMAC, say D forgeries. Then

          Pr[at least one forgery is successful] <= D/2^60.

   (3) What if we really use UMAC as specified, with AES, rather than
       one-time-pad-UMAC? What has been proven is that

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

       where delta is the maximum distinguishing probability (for the
       attacker's level of computing power) between AES and a uniform
       random permutation, and A is the total number of AES inputs used
       in legitimate messages and in forgery attempts.

The UMAC authors misrepresent several important features of the bound
Pr[at least one forgery is successful] <= delta + A^2/2^129 + D/2^60:

   * They often omit the delta term. For example, they start by saying
     that UMAC ``has been rigorously proven to be secure''---ignoring
     the possibility of an attacker forging messages by breaking AES.

   * They always omit the A^2/2^129 term---apparently because they've
     confused uniform random functions with uniform random permutations.

     They claim, for example, that ``an adversary ... can do no better
     than about 1/2^60'' per forgery attempt. They claim that this has
     been ``rigorously proven.'' But if A = 2^50 and D = 1 then what has
     actually been proven is around 1/2^29, not 1/2^60.

     I have recent theorems (http://cr.yp.to/papers.html#securitywcs
     and http://cr.yp.to/papers.html#permutations) that _often_ allow
     this type of A^2/2^129 term to be considerably reduced. Perhaps
     these theorems can be applied to UMAC, but one can't check this
     without delving into the details of how UMAC uses AES. The best
     UMAC security theorem so far includes the A^2/2^129 term.

   * They misrepresent Pr[at least one forgery is successful] as a limit
     on the _number_ of successful forgeries: ``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.''

     In fact, all we can say about the average number of successful
     forgeries is that it's Pr[at least one forgery is successful] times
     at most D. There's a big difference between Pr and D Pr.

     For example, an attacker who tries out 2^60 MACs would probably
     seize complete control and produce more than 2^59 selectively
     forged messages. (It's easy to write down attacks of this type
     against typical Wegman-Carter MACs, and presumably UMAC isn't an
     exception; anyway, the _proven_ bound is 2^60, not 1.) There's a
     big difference between ``probably get one right'' and ``produce
     more than 2^59 selectively forged messages.''

     Similarly, an attacker who tries out 2^40 MACs has roughly a
     one-in-a-million chance of producing billions of forged messages.

     The reason that cryptographers normally don't bother counting
     forgeries after the first one is that cryptographers normally
     choose parameter sizes to prevent the first forgery. There's a big
     difference in security between 60 bits and 100 bits; I think it's
     highly irresponsible of the UMAC authors to recommend 64-bit tags.

Beyond these issues, I see three timing-attack issues:

   * AES timings leak secret information, often allowing the attacker to 
     deduce the AES key. This isn't a UMAC-specific problem; there are
     several papers that the UMAC document can cite.

   * As Hal Finney mentioned, accelerated rejection of forgeries leaks
     secret information, often dramatically speeding up UMAC attacks.
     The UMAC authors need to explain this danger to people. Actually,
     I'm not sure whether the UMAC authors understand the danger:
     memcmp(), which leaks similar information, is the only tag-checking
     mechanism provided in the UMAC source code.

   * Timings of the POLY(64) algorithm inside UMAC will leak secret
     information: namely, whether L1-Hash has produced several 0xff
     bytes in a row. This won't occur often by chance, but figuring out
     whether the attacker could trigger it deliberately would require a
     new analysis of the details of the L1-Hash function.

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

---

From: Hal Finney <[email-masked]>
Date: Mon, 12 Sep 2005 23:17:00 -0700

Another question with UMAC relates to its definition of four tag lengths: 
32, 64, 96 and 128 bits. The issue is that the function is defined so that 
at least in some circumstances the shorter tags are exact prefixes of the 
longer ones. This could cause a problem if an attacker could query a 
verification oracle and control the length of the tags being used. The 
attacker could find a valid 32 bit tag and use it as a prefix to extend it 
another 32 bits and find a valid 64 bit tag. This could similarly be 
extended to 96 and 128 bit tags. He could find a valid 128 bit tag with only 
about 2^34 queries. Of course this does require a perhaps implausibly 
helpful kind of implementation.

This could be avoided if the tag length were incorporated in some simple way 
into the algorithm, for example by stealing two bits of input into the block 
cipher from the nonce and using them to encode tag size. Then each different 
tag length would produce unique tags.

UMAC does something along these lines already, in that for 32 or 64 bit tags 
it zeros respectively the bottom two or one bits of the nonce (and uses the 
erased bits to decide which 4 or 8 bytes from the 16 byte AES output to 
use). This is described in section 3.3.1 of 
http://www.ietf.org/internet-drafts/draft-krovetz-umac-04.txt .

This means that nonces which happen to have their low two bits set will in 
fact have the 32 and 64 bit tags not be prefixes of each other or of the 
longer tags (however the 96 bit tag will still be a prefix of the 128). For 
nonces which have their low two bits clear, the different sizes of tags are 
all prefixes of each other as described above.

No doubt there are simple ways to incorporate two bits of information 
regarding tag size as inputs to the algorithm. That would avoid the arguably 
undesirable property of short tags revealing information about long ones.

In looking at section 3.3.1 I just noticed another problem. It is important 
with these kinds of MACs that the nonce never be re-used for a given key. 
However the pad definition function takes a nonce of variable length, 1 to 
16 bytes, and then pads it up to 16 bytes by appending zeros. This means 
that a nonce of 1 and one of 1,0 will both be treated mathematically as the 
same value. This would cause the nonce to effectively be re-used even though 
the inputs to the PDF are different, harming the security of the MAC. Either 
the padding needs to include some indicator of how many padding bytes are 
being added, or else the padding function should be defined just to take 
nonces of length BLOCKLEN, all of which must be unique.

Hal Finney

---

From: [email-masked] (David Wagner)
Date: Wed, 14 Sep 2005 05:45:37 +0000 (UTC)

>helpful kind of implementation.

Yes.  Good point.  Phil Rogaway and I pointed out a similar observation
about CCM.  http://eprint.iacr.org/2003/070/

To fix this, it suffices to ensure that the tag length is a parameter that
is immutably bound to the key and never changed.  In other words, never use
the same key with different parameter sizes.  I don't think the algorithm
needs to be changed, as long as this rule is followed.