RE: Counter Mode Security: Analysis and Recommendations

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

Paul,

> -----Original Message-----
> From: owner-ipsec@lists.tislabs.com
> [mailto:owner-ipsec@lists.tislabs.com]On Behalf Of Paul Koning
> Sent: Tuesday, November 19, 2002 2:01 PM
> To: mcgrew@cisco.com
> Cc: tytso@mit.edu; paul.hoffman@vpnc.org; ipsec@lists.tislabs.com
> Subject: RE: Counter Mode Security: Analysis and Recommendations
>
>
> >>>>> "David" == David A Mcgrew <mcgrew@cisco.com> writes:
>
>  David> Randomly setting the initial value of the 64-bit explicit IV
>  David> of draft-ietf-ipsec-ciph-aes-ctr-01 does *not* protect against
>  David> the precomputation attacks described in the writeup.  This is
>  David> because all values of that IV will be used during the lifetime
>  David> of a key.  So an attacker can pick any value of the IV during
>  David> its precomputation stage, then wait for the corresponding
>  David> packet to appear in the data stream protected by a particular
>  David> key before attacking that key. ...
>
> Given that counter mode is limited to 2^64 blocks, all values of the
> IV are used only if every packet contains at most 16 bytes.  But
> admittedly in many data streams the average packet size is not
> dramatically bigger than the block size.  (If the average packet size
> is <= 128 bytes, then you get the same gain in the TMTO attack if you
> increase the table size by a factor of 8.)

that's right.  If the whole keystream isn't used, then the strategy of
randomizing the explicit IV would provide additional security.  In my analysis,
I made the (unstated) assumption that the key would be used up all the way.

>
>  David> What I'm suggesting is that there be a distinct field in in
>  David> the counter which is unpredictable.  In principle, counter
>  David> mode *can* have a 64-bit randomizer because the limitation
>  David> that no more than 2^64 blocks can be generated implies that 64
>  David> bits suffice to index all of those blocks.  So the block
>  David> counter and IV fields together need not occupy more than 64
>  David> bits.
>
>  David> Here's a concrete proposal: reduce the block counter to 16
>  David> bits and the IV to 48 bits, and replace the 'truncated spi'
>  David> field with a 56-bit field that is set randomly at key setup
>  David> time.  This field should be considered part of the key, so
>  David> that key setup is easy.  This proposal has the following
>  David> advantages: better security than the current draft, and the
>  David> independence of the cipher from the SPI allocation.  It has
>  David> the following minor disadvantage: it cannot encrypt ipv6
>  David> jumbograms.
>
>  David> As an aside, the 8-bit 'flags' field prevents us from making
>  David> the randomizer field 64 bits long.  I'd prefer 64 bits but
>  David> would happy to get 56.
>
> Could we drop the flags byte?  I can't see much point in having a
> field that provides compatibility with a different transform, because
> by definition we're not using that transform when we're using the
> AES-CTR transform...

This is a good question.  I'm not sure to what extent the current draft lines up
with CCM.

David

>
>  David> An important point about the current draft is that, while it
>  David> aims to admit a variety of implementation strategies, it
>  David> excludes the cryptographically conservative one.  In my
>  David> opinion, that would be a mistake.
>
>  David> In the interest of moving the WG forward on the issue, I
>  David> suggest that we solicit WG input on the following questions:
>
>  David> 1) is a security level lower than that recommended for
>  David> commercial encryption (88 bits) considered acceptable?
>
> NO way.
>
>  David> 2) is a limitation to encrypting packets less than 64kb in
>  David> length considered acceptable?
>
> You mean "is it acceptable to limit packets to be 64k or less?"  If
> you make the block counter 16 bits, then the actual packet size limit
> is 1 megabyte because blocks are 16 bytes...  That's fine.
>
>  David> 3) if you could answer "yes" to only one of the above
>  David> questions, which would it be?
>
>  David> 4) is it acceptable to implement AES-192 or AES-256 and use
>  David> those ciphers for counter mode?  Or is it desirable to use
>  David> AES-128 for both CBC and counter mode?
>
> I would hate to depend on AES-192 or above, since it's not clear to me
> how widely those will initialy be implemented in high speed silicon.
>
> 	paul
>