[Cfrg] An attack violating the UMAC security claims

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.

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

_______________________________________________
Cfrg mailing list
Cfrg@ietf.org
https://www1.ietf.org/mailman/listinfo/cfrg