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

[David McGrew <[e-mail]>]

Hi Dan,

your point is that the security claims in draft 05 don't take into  
account simple key-guessing attacks.  You're right, a such an attack  
can be used to distinguish AES from a random permutation, which the  
claims glossed over.  But it is easy enough to change the claims so  
that they are correct:

    In the case of UMAC the above guessing-attack strategy is close to
    optimal.  For example, in the case of UMAC-64 an adversary can
    correctly guess an 8-byte UMAC tag with probability 1/2^64 by simply
    guessing a random value.  The results of [3, 6] show that no  
feasible
    attack strategy can produce a correct tag with probability better
    than 1/2^60 if UMAC were to use a random function in its work rather
    than AES.  Likewise 32-, 96- and 128-bit tags cannot be forged with
    more than 1/2^30, 1/2^90 and 1/2^120 probability.  Another result  
[2],
    when combined with [3, 6], shows that UMAC is secure under  
reasonable
    assumptions about AES, whenever no more than about 2^64 messages are
    authenticated.

I also suggest to add something like the following:

    Therefore, we require that that each value of the key MUST NOT be  
used
    in more than 2^64 invocations of the tag generation
    algorithm, and MUST NOT be used in more than 2^64 invocations of
    the tag verification algorithm.

This concrete guidance is important because the vast majority of the  
implementers won't determine the appropriate usage limitations from  
whatever bounds are given or referenced.

Of course, what I've done with my edits above is merely gloss over  
the details in the claims (please let me know if you think the claims  
above are in error).  This would be completely unacceptable in a  
scientific publication, but we're discussing a draft spec.  Let me  
know what you think.

David

On Oct 3, 2005, at 8:35 AM, 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