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

From: Ted Krovetz <[email-masked]>
Date: Sat, 22 Oct 2005 07:28:57 -0700

David,

Thank you for your analysis. It is true that there is a small chance  
of redundant inputs to AES during UHASH key-derivation. A simple  
birthday analysis shows the probability to be no more than 28/2^120.  
Although this value is of no practical significance -- it is an one- 
time additive term after all -- it is larger than the single-message  
forgery probability for 128-bit tags. (It is of no significance for  
shorter tags because 28/2^120 can easily be absorbed into their bounds.)

We can fix this inconsistency in a few ways, and would appreciate  
feedback from the CFRG community. We could

1) Ignore it as noise which is swamped by the delta term of prp- 
distinguishing probability, or

2) leave the current algorithm unchanged, but revise slightly the I- 
D's security discussion, or

3) make a small change to the algorithm, ensuring no redundant AES  
inputs. This would require no changes to the security analysis, but  
would require updates to UMAC code and test vectors.

Thank you,
Ted Krovetz

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

---

From: "D. J. Bernstein" <[email-masked]>
Date: 23 Oct 2005 05:28:55 -0000

Ted Krovetz writes:
> A simple  birthday analysis shows the probability to be no more than
> 28/2^120.  

Let me see if I understand the bottom line. Your ``rigorously proven''
security analysis states that

   * UMAC-128 with AES replaced by Func(128,128),Func(128,128) has
     forgery probability at most 0.562502^4/2^120 (``Lemma 3'');

   * UMAC-128 with AES replaced by Func(128,128) has forgery probability
     at most 1/2^120 (``Theorem 1'');

   * UMAC-128 with AES replaced by Perm(128) has forgery probability at
     most 1/2^120 (``Theorem 2'').

You're now withdrawing all of these statements?

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

---

From: canetti <[email-masked]>
Date: Mon, 24 Oct 2005 11:19:32 -0400 (EDT)

Ted,

What was your rationale in using this key derivation mode
instead of simply using counter mode?

I agree that the additional error term here is insignificant.
What bothers me more is the "cleanliness of design"
(namely, it is an "Occam's razor" style concern.)

Thanks,

Ran

---

From: Ted Krovetz <[email-masked]>
Date: Mon, 24 Oct 2005 08:48:45 -0700

> instead of simply using counter mode?

The use of feedback is a good design principle. It likely makes  
cryptanalysis harder because successive cipher inputs are  
unpredictable and there is a greater hamming distance between them.

Counter mode allows any scheme that ensures distinct inputs (ie, they  
don't have to be successive numerically), so combining a guaranteed  
non-repeating value with some feedback makes for a very good  
heuristic counter mode. The I-D has a mistake in this regard. Instead  
of AES inputs being constructed as <15 bytes feedback><1 byte  
counter>, it should be <14 bytes feedback><1 byte index constant><1  
byte counter>, creating several logical counter mode streams with  
feedback strengthening.

And, as I've said before, it is not really a problem. As is, with  
overwhelming probability the AES inputs are unique. We simply need to  
decide which is more important: algorithmic stability or a 28/2^120  
additive term.

---

From: Geir Myrdahl Køien <[email-masked]>
Date: Mon, 24 Oct 2005 18:06:26 +0200

På 24.10.2005 17:48, Ted Krovetz skrev:

We simply need to
 > decide which is more important: algorithmic stability or a 28/2^120

The RFCs are hard to update and minor flaws etc will stay there for years.

So my advice would be to use the design opportunity to fix these minor items 
while you still have the freedom to do so.
(ok, I don't particularly care about the 28/2^120 additive term)

/Geir
----
Geir M. Køien
Agder University College and Telenor R&D

Phone: +47 9075 2914

---

From: canetti <[email-masked]>
Date: Mon, 24 Oct 2005 16:06:46 -0400 (EDT)

Thanks for the clarification.

My personal tendency would be to at least include a discussion in the
security considerations section. In fact, in retrospect it would have been
a good idea to discuss the considerations behind the specific choice of
key expansion mode, as you sketch below, even regardless of this glitch.
Such a discussion can be of value for the IETF even independently of UMAC.

I don't have strong feelings regarding whether to actually change the
code. Its purely an aesthetic issue, but aesthetics do matter after all...

BTW, do we know of any existing/underway implementations of UMAC?

Ran

---

From: David McGrew <[email-masked]>
Date: Mon, 24 Oct 2005 13:14:39 -0700

Ted,

On Oct 22, 2005, at 7:28 AM, Ted Krovetz wrote:

> David,
>
> Thank you for your analysis. It is true that there is a small  
> chance of redundant inputs to AES during UHASH key-derivation. A  
> simple birthday analysis shows the probability to be no more than  
> 28/2^120. Although this value is of no practical significance -- it  
> is an one-time additive term after all -- it is larger than the  
> single-message forgery probability for 128-bit tags. (It is of no  
> significance for shorter tags because 28/2^120 can easily be  
> absorbed into their bounds.)
>

This option would be preferable if someone is interested in  
preserving compatibility with an existing implementation going  
forward.  The security concern is negligible, at least for most MAC  
users (even many professional paranoids follow the recommended 96-bit  
integrity check values in IPsec AH and ESP).  If there are any  
implementers with a compatibility concern, they should chime in now.

> would require updates to UMAC code and test vectors.

The change you'd suggested to move to <14 bytes feedback><1 byte  
index constant><1 byte counter> looks good to me.  I guess that I'd  
personally prefer 3) to 2), though I'd really like to hear from others.

Thanks for your ongoing willingness to tweak the specification.

David