RE: Counter Mode Security: Analysis and Recommendations

["David A. Mcgrew" <mcgrew@cisco.com>]

Russ,

yes, Rivest's recommendation provides equivalent protection, but at a higher
implementation cost.  The larger AES key sizes require more computation, and are
not actually required of an AES implementation.  Perhaps this increased
implementation cost is an acceptable tradeoff to the WG.  I favor the lower
implementation cost solution since resources are a premium in embedded systems
and many network devices.

David

> -----Original Message-----
> From: Housley, Russ [mailto:rhousley@rsasecurity.com]
> Sent: Monday, November 18, 2002 5:23 PM
> To: David A. Mcgrew
> Cc: Theodore Ts'o; Paul Hoffman / VPNC; ipsec@lists.tislabs.com
> Subject: RE: Counter Mode Security: Analysis and Recommendations
>
>
> David:
>
> Thanks for documenting this issue so clearly.  The material presented here
> might be new for many participants on this list, but it was discussed at
> length by the design team.
>
> During the design team, I posted the following reply when you raised this
> issue.  At that time, you were calling the additional random value a
> salt.  This paper does not seem to use the same name.
>
> > > I have spoken to Ron Rivest about salt, and he is strongly opposed to
> > > it.  His reasons are pretty straightforward.  First, if the salt is needed
> > > to defeat a precomputation attack, then the key is too short.  A better
> > > countermeasure is a longer key.  With AES, longer keys are readily
> > > available.
>
> While I have not spoken to Ron Rivest about this topic since the design
> team, Ron was quite emphatic that the appropriate countermeasure to
> precomputation attacks is longer keys.  This is the reason that the counter
> mode draft includes support for all three AES key sizes.
>
> The use of the additional secret value that you propose leads to the
> generation of additional keying material.  If these attacks are an issue,
> then I propose that it is better to use it to make a longer AES key.
>
> There is already a discussion of precomputation attacks in the Security
> Considerations section of the current draft.  It says:
>
>     There are fairly generic precomputation attacks against all block
>     cipher modes that allow a meet-in-the-middle attack against the key.
>     These attacks require the creation and searching of huge tables of
>     ciphertext associated with known plaintext and known keys.  Assuming
>     that the memory and processor resources are available for a
>     precomputation attack, then the theoretical strength of AES-CTR (and
>     any other block cipher mode) is limited to 2^(n/2) bits, where n is
>     the number of bits in the key.  The use of long keys is the best
>     countermeasure to precomputation attacks.  Therefore, implementations
>     that employ 128-bit AES keys should take precautions to make the
>     precomputation attacks more difficult.  The concatenation of the
>     Flags, Truncated SPI, and IV fields within the counter block can be
>     thought of as a per-packet nonce.  Repeated use of the same nonce
>     value (even with different keys) ought to be avoided.  One approach
>     is to consecutively assign SPI values; however, since the only 24
>     bits of the SPI are included in the nonce, a SPI value provides
>     limited additional security.
>
> In my view, this document is ready for working group last call.
>
> Russ
>