RE: Counter Mode Security: Analysis and Recommendations

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

Ted,

here is a long-winded reply and a suggested direction for the ipsec counter mode
draft.    First, thanks for your feedback, I realize that I need to be more
clear on the point that you brought up.

Randomly setting the initial value of the 64-bit explicit IV of
draft-ietf-ipsec-ciph-aes-ctr-01 does *not* protect against the precomputation
attacks described in the writeup.  This is because all values of that IV will be
used during the lifetime of a key.  So an attacker can pick any value of the IV
during its precomputation stage, then wait for the corresponding packet to
appear in the data stream protected by a particular key before attacking that
key.  If the attacker does not store the ciphertext contained by the packets
that were sent previous to the IV value used in the precomputation, she will not
be able to decipher those packets.  However, this does not seriously impair the
effectiveness of the attack, since on average 1/2 of the plaintext will be
decipherable by the attacker.

What I'm suggesting is that there be a distinct field in in the counter which is
unpredictable.  In principle, counter mode *can* have a 64-bit randomizer
because the limitation that no more than 2^64 blocks can be generated implies
that 64 bits suffice to index all of those blocks.  So the block counter and IV
fields together need not occupy more than 64 bits.

Here's a concrete proposal: reduce the block counter to 16 bits and the IV to 48
bits, and replace the 'truncated spi' field with a 56-bit field that is set
randomly at key setup time.  This field should be considered part of the key, so
that key setup is easy.   This proposal has the following advantages: better
security than the current draft, and the independence of the cipher from the SPI
allocation.  It has the following minor disadvantage: it cannot encrypt ipv6
jumbograms.

As an aside, the 8-bit 'flags' field prevents us from making the randomizer
field 64 bits long.  I'd prefer 64 bits but would happy to get 56.

An important point about the current draft is that, while it aims to admit a
variety of implementation strategies, it excludes the cryptographically
conservative one.  In my opinion, that would be a mistake.

In the interest of moving the WG forward on the issue, I suggest that we solicit
WG input on the following questions:

  1) is a security level lower than that recommended for commercial encryption
(88 bits) considered acceptable?

  2) is a limitation to encrypting packets less than 64kb in length considered
acceptable?

  3) if you could answer "yes" to only one of the above questions, which would
it be?

  4) is it acceptable to implement AES-192 or AES-256 and use those ciphers for
counter mode?  Or is it desirable to use AES-128 for both CBC and counter mode?

Knowing the WG sentiment on these topics will enable us to make a dispassionate
evaluation.  It is late and I'm tired, and I may have missed decision point, so
I invite others to propose questions as well.

For the record, I am still of the opinion that omitting the explicit IV in order
to cut down on the size of the packet is worthwhile.  However, I'm neglecting
that issue in order to focus the discussion on the security issue, which is
certainly more important.

David

> -----Original Message-----
> From: Theodore Ts'o [mailto:tytso@mit.edu]
> Sent: Saturday, November 16, 2002 6:32 PM
> To: David A. Mcgrew
> Cc: Paul Hoffman / VPNC; ipsec@lists.tislabs.com
> Subject: Re: Counter Mode Security: Analysis and Recommendations
>
>
> Hi David,
>
> 	Barbara and I held off issuing a last call on
> draft-ietf-ipsec-ciph-aes-ctr-01 on Friday because Barbara indicated
> to me that she had talked to you, and she had told you that you were
> about to publish a five-page writeup documenting a security
> shortcoming in the current I-D that was about to be published.  I assume
> that this writeup is the one that you were referring to:
>
> > http://www.mindspring.com/~dmcgrew/ctr-security.pdf
>
> Having read your writeup, I'm confused how this applies to
> draft-ietf-ipsec-ciph-aes-ctr-01.  The basic summary of your writeup
> seems to be (1) the IV needs to be 64 bit, (2) it needs to be
> unpredictable, and a good way to do this is to generate the IV using a
> counter starting at an unpredictable random value.
>
> The current ID specifies the use of a 64-bit explicit IV, which can be
> set by the sender in any fashion which is convenient for the sender,
> as long as the requirement that an IV is never reused for a particular
> key.  There is even text in the security requirements section which
> covers the topic of precomputation attacks.
>
> Perhaps it could be made more explicit in the light of your comments
> by adding a recommendation that if the sender is using an incrementing
> counter or an LFSR to generate the IV, an unpredictable starting value
> for the counter or LFSR would be a good idea.  Not starting the IV at
> zero would seem to me to be self-evident, but sometimes stating such
> things explicitly for the benefit of the college intern implementing
> from the RFC is a good thing.
>
> Did I miss anything from your counter-mode security writeup?
>
> 							- Ted