Re: [Cfrg] An attack violating the UMAC security claims

[canetti <[e-mail]>]

[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



On Mon, 3 Oct 2005, D. J. Bernstein wrote:

> 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
> [e-mail]
> https://www1.ietf.org/mailman/listinfo/cfrg
>

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