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

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

Russ,

> -----Original Message-----
> From: Housley, Russ [mailto:rhousley@rsasecurity.com]
> Sent: Tuesday, July 30, 2002 7:23 AM
> To: David A. Mcgrew
> Cc: ipsec@lists.tislabs.com
> Subject: Re: draft-ietf-ipsec-ciph-aes-ctr-00.txt
>
>
> 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.

the text looks fine.  I would prefer that the SHOULD be a MUST, because
violating that limitation voids the security warranty, so to speak.  Though
current IPsec drafts do leave this sort of limitation to 'security policy',
which is consistent with your approach.

>
> >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?

Well, we don't want to add a normative dependency that might delay counter
mode from progressing to RFC!  Do you really think that it is necessary to
reference the ID rather than the RFC in order to avoid manual key use with
counter mode?  If that's the case, we should perhaps change the text in the
counter mode draft.  It might be acceptable to say that "AES-CTR MUST NOT be
used with manual keying, except for the purposes of testing", or something
along that line.

>
> >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.

Actually, the 24-bit truncated SPI values need not be random in order to
protect against a precomputation attack.  It is sufficient for those values
to be used uniformly.  An implementation which generates SPI values
sequentially would reap the same benefit, if it generated all possible
values (and didn't favor the initial portion of the sequence).
But we can't rely on a SPI selection strategy for security anyway, since
RFC2401 allows any SPI selection method, so it doesn't make much difference.

>
> 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.

It written clearly, though I personally don't understand why an implementer
would not include such protection.  What other benefit is gained by not
including that protection?  It would be good to include that explanation, so
that the WG can evaluate the tradeoffs that you've made.

>
> >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!

Using the same counter mode key across multiple SAs is potentially
dangerous, and the draft needs to be explicit on this.  It's my impression
that using the same key across multiple SAs is a false economy; I know many
that agree with this statement, and a few that disagree with it.  I don't
care much either way, but we certainly need to make it clear to future
implementers what they cannot do.

The draft asks that IKE detect and correct collisions in truncated SPI
values.  To comply with this request, IKE implementations would need to
change their behavior.  I strongly suspect that it would be best to avoid
any need to change IKE!

thanks,

David


>
> >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