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

From: David Wagner <[email-masked]>
Date: Fri, 21 Oct 2005 23:20:46 -0700 (PDT)

David McGrew writes:
>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.

But we do need to consider collisions between two different
nonces.  Can anyone explain to me what the PDF algorithm is
doing with its nonces?  The first few lines say:

      // Extract and zero low bit(s) of Nonce if needed
      if (taglen = 4 or taglen = 8)
        index = str2uint(Nonce) mod (BLOCKLEN/taglen)
        Nonce = Nonce xor uint2str(index, bytelength(Nonce))
      end if

What's that there for?  It seems that if I send two messages
with two nonces that differ only in their low bit, and if the
tag length is 4 or 8, then these two messages will use the same
nonce.  I'm having a hard time understanding how that can
be safe.  Can someone explain this to me?  What am I missing?

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

---

From: Hal Finney <[email-masked]>
Date: Sat, 22 Oct 2005 00:28:47 -0700

The idea is that for 4- or 8-byte tags, the 16-byte AES-encrypted
nonce value gets divided into respectively 4 or 2 parts, allowing one
AES encryption to serve for 4 or 2 tags (assuming sequential nonces).
It is a performance optimization. If you look down a little farther
you will see that it shifts which subset of the AES output is used,
depending on the low order 1 or 2 bits of the nonce.

Hal

On 10/21/05, David Wagner <[email-masked]> wrote:
> Can anyone explain to me what the PDF algorithm is

---

From: David McGrew <[email-masked]>
Date: Mon, 24 Oct 2005 06:35:36 -0700

David,

On Oct 21, 2005, at 11:20 PM, David Wagner wrote:

> nonces.

you're right, this case was omitted from the analysis, and should  
have been there.   But it's not a big deal since it doesn't affect  
the conclusions.   The uniqueness of the 'Nonce' inputs to PDF imply  
the uniqueness of the inputs to the ENCIPHER function, when taglen =  
16.  (Other taglen values don't have security problems, but the  
security is hard to state in terms of 'collisions' because of the way  
that single inputs to ENCIPHER are used for multiple outputs of PDF.)

David