Re: draft-ietf-ipsec-ciph-aes-ctr-00.txt

["Housley, Russ" <rhousley@rsasecurity.com>]

David:

Thank you for the careful reading of the draft.  See my responses below.

>I have several comments on draft-ietf-ipsec-ciph-aes-ctr-00.txt.  It's
>clearly written and I value the effort that you've made to get the
>job done and establish some sort of compromise.  However, there are
>two points on which the draft can be improved: packet expansion and
>strength against precomputation attacks.  In the following, I lay out
>some arguments in favor of an implicit (rather than an explicit) IV,
>discuss interoperability with other counter mode versions, and mention
>some other points.
>
>First, a correction to the Security Section.  In the last paragraph of
>Section 6, the draft is right to state that no more than 2^64 blocks
>should be encrypted with any fixed key.  But the draft implies that
>this limitation can be avoided if implementations "make use of the
>longer AES key sizes."  This is not right, the 2^64 limit applies to
>all key sizes.  It does not apply to larger block sizes; however, the
>AES spec doesn't include the larger RIJDNAEL block sizes.  In the same
>vein, the sentence "Additionally, AES with a 128-bit key is vulnerable
>to the birthday attack after 2^64 blocks" should read "Additionally,
>AES is vulnerable...".

You are correct.  I propose the following replacement paragraph:

    Additionally, since AES has a 128-bit block size, regardless of the
    mode employed, AES is vulnerable to a birthday attack after 2^64
    blocks are encrypted with a single key.  Since ESP with Enhanced
    Sequence Numbers allows for up to 2^64 packets in a single security
    association (SA), there is real potential for more than 2^64 blocks
    to be encrypted with one key.  Implementations SHOULD generate a
    fresh key before 2^64 blocks are encrypted with the same key.  Note
    that ESP with 32-bit Sequence Numbers will not exceed 2^64 blocks
    even if all of the packets are maximum-length Jumbograms.

>On the subject of packet expansion, the draft requires the use of an
>explicit IV that is eight bytes long and states that this overhead is
>acceptable.  I disagree.  Counter mode has the opportunity to provide
>zero expansion, and at Cisco we've regarded this property as
>important.  The consumption of eight bytes per packet can have a
>significant impact on bandwidth, especially for protocols with short
>packets like voice over IP (RFC 1889).  For example, RTP with the
>G.729 codec (as is commonly used) carries only twenty bytes of data
>per packet.  This protocol is often used with link-layer header
>compression over WAN links (e.g. RFC2508); these compression methods
>are quite efficient, making the bandwidth degradation due to
>uncompressible fields (like the explicit IV) pronounced.
>
>I think that the zero-expansion property is important enough that I
>want to comment on the points that the rationale presents in favor of
>an explicit IV:
>
>   Point 4.  "The assignment of the per-packet counter block value
>   needs to be inside the assurance boundary.  Some implementations
>   assign the sequence number inside the assurance boundary, but others
>   do not."  What implementations maintain the ESP sequence number
>   outside of the security perimeter?  Cisco does not do this, nor do
>   any of the several of crypto hardware suppliers that we use.
>
>   Counter mode ESP would be far simpler and more bandwidth efficient
>   if the ESP sequence number were used as the per-packet counter
>   value.  In addition, other cryptographic mechanisms that require a
>   nonce can use the sequence number for that purpose, if we are
>   allowed to assume that the sequence number is actually unique.
>   These mechanisms include ciphers like SEAL and Wegman-Carter based
>   MACs like MMH.  It's worth noting that we've implemented SEAL
>   encryption using ESP, as described in the Stream Cipher ESP; this
>   draft is now expired, but went through three revisions without this
>   point about the sequence number and assurance boundary being raised.
>   (The old draft is online at
>   www.mindspring.com/~dmcgrew/draft-mcgrew-ipsec-scesp-02.txt if
>   you're interested, and we'd be fine with re-issuing the draft were
>   there is interest from other implementers.)
>
>
>   Point 2.  "Adders are simple and straightforward to implement, but
>   due to carries, they do not execute in constant time.  LSFRs offer
>   an alternative that executes in constant time."  However, the
>   per-block increment operation is far more time critical than the
>   per-packet increment operation!  Since the block counter is a
>   monotonically increasing integer, and it's presumably fast enough,
>   it's hard to see how the fact cited in the draft supports the use of
>   LFSRs for the per-packet field.
>
>
>   Point 1.  "... there is no advantage to selecting a mechanism that
>   allows the decryptor to determine whether counter block values
>   collide.  Damage from the collision is done, whether the decryptor
>   detects it or not."  Yes, but the detection of a malfunctioning ESP
>   sender could enable an administrator to shut off the errant device.
>   Either the ESP CTR receiver or a passive security monitoring device
>   such as a network IDS system can detect ESP sequence number re-use.
>   When is the delayed detection of the failure of a security system
>   worse than no detection?
>
>I don't disagree with Point 3 and Points 5 and 6 follow from the
>others.
>
>I would be surprised if other implementers in the WG favored the use
>of an unspecified explicit IV over the use of the sequence number as
>an implicit IV.  At any rate, I think we've discussed the points well
>enough to allow others in the WG to chime in.

This debate has been the focus of the discussion between you and Steve 
Kent.  A few others have offered opinions, but the vast majority of the WG 
has remained silent.  One notable exception is the posting from David 
Black, who offered support for the explicit IV.

So far, I do not see a consensus for overloading the semantics of the 
sequence number.  However, I am sure the debate is not over yet.

>On to other topics.  The draft says in Section 6 that AES CTR MUST NOT
>be used with statically configured keys.  I certainly agree that this
>is a good thing.  However, RFC2401 requires implementations to support
>such keys, saying "This document requires support for both manual and
>automatic distribution of keys."  Perhaps that RFC means that manual
>keying be provided only for some ciphers (the mandatory to implement
>ones?).  At any rate, it would be good for the WG to decide what is
>meant and to document it somewhere.  (The Stream Cipher ESP draft hit
>this same issue).

It is my understanding that RFC 2401bis is being made more flexible in this 
area.  Are you suggesting that the AES-CTR document should reference RFC 
2401bis instead of RFC 2401?

>On the subject of interoperability, the AES CTR draft could be
>implemented using draft-mcgrew-saag-icm-00.txt (the generic counter
>mode draft that I wrote last November, which also lines up with the
>AES CTR variant in draft-ietf-avt-srtp-05.txt), if the spec were bent
>hard enough.  This bending would consist of defining the 'initial
>offset' to be equal to (flags, truncated_spi), and of course throwing
>the explicit IV in front of the ciphertext.  All of the AES CTR specs
>that I've seen have managed to agree that the per-block counter be a
>big-endian integer in the least significant bits of the counter, which
>probably ensures that implementations can share keystream-generation
>components.
>
>OTOH, while the closeness of the various AES CTR specifications is a
>good thing, the fact that the initial offset is not random has a
>negative security impact.  The WG may decide that it prefers
>simplicity to strength against precomputation attacks.  If so, fine,
>but this subject needs to be discussed in the rationale.

The content of the Rationale section comes from the email discussion 
regarding my proposed compromise.  The major issue at that time was 
Explicit IVs, so it is not surprising that other aspects of the design 
rationale are slighted.

First, I propose the following additional paragraph in the Security 
Considerations section:

    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 randomly assign SPI values; however, since the only 24 bits of
    the SPI are included in the nonce, a random SPI value provides
    limited additional security.

I hope that this very brief description of precomputation attacks is 
sufficient.  Next, I propose the following additional paragraph for the 
rationale section:

    No explicit countermeasures against precomputation attacks are
    included in the counter block construction.  The use of long keys is
    the usual countermeasure to these attacks, and AES offers key sizes
    that thwart these attacks for many decades to come.

>In Section 6 the draft says:
>
>    "Thus, to avoid counter block collisions, ESP implementations that
>    permit use of the same key for encrypting and decrypting packets
>    with the same peer MUST ensure that the two peers assign different
>    SPI values to the security association (SA)."
>
>Is it actually kosher for two SAs to share the same keys?  SAs are
>simplex per RFC 2401, though they could in principle share a single
>key.  However, I'd expect that if the architecture allowed such
>key-sharing that it would require that the SAs be in the same SA
>bundle so that when one SA reaches it usage limit its twin gets
>deleted as well.  I'm not aware of any such language, which makes me
>suspicious about using the same keys twice.

I tried to point out that IKE would not generate such an SA.  However, 
there are serious security concerns if the same key streams are used for 
encryption and decryption.  I just wanted to make sure that no one did such 
a thing!

>Now for the real nit: at the bottom of page 7, a typo: "It is
>inappropriate to use this m AES-CTR"

This will be fixed in the -01 draft.

Russ