Subject: [Cfrg] Critical gap in the UMAC security ``proof''

From: "D. J. Bernstein" <[email-masked]>
Date: 20 Oct 2005 23:13:16 -0000

A conventional Wegman-Carter(-Brassard) MAC has two independent keys.
One key is used for a family of hash functions with low differential
probabilities. The second key is used to encrypt the hash output.

For example, in Poly1305-AES, there's one key for the Poly1305 hash, and
one key for AES. The AES key is used in counter mode to encrypt the
Poly1305 hash output, producing the Poly1305-AES authenticator.

UMAC, although described as ``a Carter-Wegman MAC,'' deviates from the
conventional model. It has just one key, an AES key. AES inputs are fed
to this key for two different purposes; the AES outputs are used both
for creating a hash key and for encrypting the hash output.

A system designed in this way can be disastrously insecure if it has any
overlap between the AES inputs used for creating a hash key and the AES
inputs used for encrypting the hash output. This isn't merely a concern
regarding what we're able to prove; I can build systems that look just
like UMAC, that have overlaps in the AES inputs, and that allow very
easy attacks.

Does UMAC have this type of disastrous overlap in its AES inputs? I look
at the UMAC security ``proof'' (version 2005.10.07) and I see no
analysis of the AES inputs. If UMAC has the disastrous overlaps but is
otherwise constructed safely then Lemma 7 is correct but Lemma 8 is
wildly inaccurate. The ``rigorous proof'' of Lemma 8 is ludicrously
brief (``Lemma 8 is obtained from Lemma 7 in the standard way that one
passes from information-theoretic to complexity theoretic results in
provable-security cryptography'') and simply ignores the overlap issue.

Hopefully the UMAC designers didn't make a huge mistake. Hopefully it's
not difficult to prove that UMAC doesn't repeat its AES inputs. But this
proof needs to be written down; it's critical for the proof of Lemma 8.

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

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

---

From: canetti <[email-masked]>
Date: Thu, 20 Oct 2005 23:32:06 -0400 (EDT)

Dan, I think you're fighting windmills here. The preliminary use of AES
that you refer to is standard key derivation, and AES in ctr mode is one
of the best ways we know to do it.

BTW, I'm not familiar with Poly1305-AES, but from your description it
seems that the application that uses it would probably derive the two keys
that Poly1305-AES requires from a single seed using some cryptographic key
derivation. So in the end we'd get the same thing in both cases.
In fact, I feel a bit more comfortable with a scheme that does its own key
derivation - this way I know for sure that the keys are derived securely.

I think it's time to let it go...

Ran

---

From: "D. J. Bernstein" <[email-masked]>
Date: 21 Oct 2005 08:07:25 -0000

canetti writes:
> The preliminary use of AES that you refer to is standard key
> derivation, and AES in ctr mode is one of the best ways we know to do it.

Fascinating. Are you aware that UMAC doesn't use standard counter mode?
It derives keys with some sort of wacky ad-hoc feedback mode.

Anyway, no matter what the mode is, there's no excuse for the mode to be
ignored in the security proof. Some modes are disastrously insecure.

P.S. Regarding your comment about deriving a Poly1305-AES key: A typical
application will produce the 32-byte Poly1305-AES key by hashing a
Diffie-Hellman shared secret. Doing an intermediate 16-byte hash, and
then expanding the hash to 32 bytes, would be poor cryptographic design.

---

From: canetti <[email-masked]>
Date: Fri, 21 Oct 2005 09:39:56 -0400 (EDT)

Dan,

> ignored in the security proof. Some modes are disastrously insecure.

I stand corrected, thanks. They use a (quite standard) feeback mode,
that is, as far as we know, just as secure as ctr, and probably even more.
I see no reason to believe that this mode is less secure than modes
used in existing IETF standards.  There are a hundred ways to skin this
cat, all enjoy roughly the same security analysis. They picked one.
(That's the beauty of key derivation using the PRF abstraction...)
Also, their analysis does account for the key generation.

> then expanding the hash to 32 bytes, would be poor cryptographic design.

I see no reason to believe that this is a general truth. In fact, I'm sure
it's possible to come up with hash functions where direct hashing to 32 bytes
will have weakenesses, but if you first hash to 16 bytes and then expand
securely to 32 bytes then the weaknesses will go away.

Also, that's not the end of the story, is it. The same DH secret will
probably be used to derive also encryption keys and probably other stuff.
So you can't get away from computational dependencies and imperfection of
keys.

Ran

---

From: David McGrew <[email-masked]>
Date: Fri, 21 Oct 2005 08:04:12 -0700

Okay, my curiosity was raised, and I had a look at UMAC to consider  
the issue.  I wrote up my thoughts and copied them below.  Comments  
welcome.

David

--

Define a 'collision' as the case in which two distinct invocations of
the ENCIPHER operation, for the same key, have the same input.  The
function KDF is invoked five distinct times for each UMAC key, once in
Section 3.3.1 (with index = 0) and four times in Section 5.1 (with
index values of 1, 2, 3, and 4).

The function KDF is used to derive a secondary key that is used in the
PDF algorithm (Section 3.3.1).  The nonce is processed only by the
secondary key, so we need not consider collisions between the nonce
and the inputs to the ENCIPHER operation provided during the
evaluation of the function KDF.  We need only consider collisions that
occur during two different invocations of KDF.

We consider two different invocations of KDF, and let X_1 denote the
initial block for the first invocation, and Y_1 denote the initial
block for the second invocation.  The KDF feedback function is

   X_i = ENCIPHER(K, X_{i-1}[1...15] || uint2str(i mod 256, 1))
   Y_j = ENCIPHER(K, X_{j-1}[1...15] || uint2str(j mod 256, 1))

for i,j between 2 and ceil(numbytes/16).

When a collision occurs, then X_i = Y_j; note that this is only
possible when i = j.  (Here we assume that the value of 'numbytes' is
less than 16*256 = 2^12, which is holds for all uses of KDF.)  If the
first fifteen bytes of X_i match the corresponding bytes of Y_i, then
there will be a collision between blocks X_{i+1} and Y_{i+1}, and
collisions between the following blocks, if any.  Additionally,
if there is a collision between X_i and Y_i, then there must be
a match between the first fifteen bytes of X_{i-1} and Y_{i-1}.

If the values of the 'index' input provided to each invocation of KDF
are distinct, then the initial blocks X_1 and Y_1 are distinct.  The
remaining ceil(numbytes/16)-1 blocks are distinct with very high
probability if ENCIPHER is a random permutation, but are not
guaranteed to be distinct.

The largest value of numbytes is 1072 (during the computation of L1Key
in Section 5.1, with taglen at its maximum value of 16).  Thus there
are fewer than 66 blocks generated during all of the invocations of
KDF.  A collision occurs only if two of these blocks happens to match
in their first 15 bytes.

An attacker can use an attack that takes advantage of a collision to
break UMAC.  Thus any proof of security that relates the UMAC forgery
probability to the advantage of distinguishing AES from a random
permutaiton will need to account for this fact.  However, the
probability of collision is so small that we conjecture that it will
not be the dominant term, except perhaps when UMAC is invoked very few
times (since each invocation calls ENCIPHER through PDF), and
that it will not have a significant impact on security.

---

From: David McGrew <[email-masked]>
Date: Fri, 21 Oct 2005 08:34:25 -0700

> KDF.  A collision occurs only if two of these blocks happens to match

a nit: there are 66 blocks per invocation of KDF, and there are 5  
such invocations, for a total of 335 blocks.

David