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

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

Russ,

sorry for the delayed response, I've been traveling.  More inline:

> -----Original Message-----
> From: Housley, Russ [mailto:rhousley@rsasecurity.com]
> Sent: Tuesday, July 30, 2002 6:16 AM
> To: David A. Mcgrew
> Cc: ipsec@lists.tislabs.com; sfluhrer@cisco.com
> Subject: RE: draft-ietf-ipsec-ciph-aes-ctr-00.txt
>
>
> David:
>
> > > [Klaus]
> > > > > yes, I agree with you, I can not see any reason to use an
> external
> > IV for
> > > > > AES CTR if algorithms easy can be defined for internal
> building of
> > IV's with
> > > > > ESP sequence number and SPI. The only cryptographic
> requirement for the
> > > > > sequence of IV's is, that all the counter values, derived
> from all
> > the IV's
> > > > > over all the ESP packets, transformed by AES, are
> different as long
> > as one
> > > > > fixed key is used.
> > >
> > > [David]
> > > >that's right.  Additionally, some additional strength
> against attacks
> > which
> > > >rely on precomputation of a database to use during the
> attack stage can be
> > > >gained by having the part of the counter be secret.
> > >
> > > We have discussed the inclusion of a secret component in the
> counter.  It
> > > complicates the key management by requiring an additional
> secret value to
> > > be managed.
> >
> >I disagree with the supposition that including a secret component in the
> >counter complicates key management.  I'll explain what I'm
> thinking; please
> >let me know if or where your assumptions are different.
> >
> >One simple way in which counter mode can include a secret component is to
> >define that value to be part of the key.  This method allows
> counter mode to
> >use a secret component in the counter, while hiding that fact from a key
> >management protocol.
> >
> >For example, define the format of the counter key to look like:
> >
> >    +---------------+------------+
> >    |    AES Key    |   Offset   |
> >    +---------------+------------+
> >
> >where "Offset" is the secret counter component.  The AES Key field would
> >have a fixed length (as the draft has a distinct IANA transform
> number for
> >each AES key length).  The Offset could be fixed length (which
> is certainly
> >simpler), or could have a variable length if that proves
> desirable.  In any
> >case, a variable-length Offset field would not introduce any ambiguity.
> >
> >The counter mode ESP transform gets to define what its key looks
> like; the
> >above definition is perfectly valid.  IKE is quite capable of
> dealing with
> >the format above, since it can work with any key length cipher in ESP.  I
> >defer to Scott Fluhrer for more details, as he's implemented what I've
> >described here (which he and I worked out in the summer of y2k, to give
> >credit where it is due).
> >
> >I certainly agree that it would be overly complicated to expect a key
> >management system to manage the 'secret counter component' as a distinct
> >data type.  But there's no reason to do that, since the simple key format
> >described above works just as well.  I fear that perhaps this
> point has been
> >a source of miscommunication between us in the past.
>
> I agree that managing one secret value that is divided into two
> components
> within the encryption transform does not add any complication to the key
> management protocol.  To the key management protocol, it appears
> to be one
> large key.
>
> > > If one is concerned about this type of dictionary attack, the
> > > use of a longer AES key provides more protection
> >
> >Yes, this is completely true.  Using a bigger AES key also provides
> >protection against precomputation attacks.  However, this
> approach has some
> >disadvantages.  The computational cost of AES is greater for the
> 192-bit key
> >and 256-bit key versions, by 20% and 40% respectively, making
> this approach
> >less efficient than that of using a random offset.  Also, a number of
> >current AES implementations do not include the larger key sizes, and thus
> >could not use this approach.
>
> If I understood Scott Fluhrer's follow-up message correctly, the use of
> 128-bit AES key coupled with an offset still only provides 128 bits of
> strength.  Thus, the larger AES key sizes (and the additional rounds
> associated with them that account for the bulk of the added computational
> cost) are providing significantly more protection than the offset.

To be precise, using a 192-bit AES key rather than a 64-bit 'secret counter
component'
does not provide more security.  This is because precomputation attacks are
foiled equally well by either method, and the security level of a
cryptosystem is determined by the minimum effective attack.  A 192-bit AES
key does potentially provide protection against more types of attacks, of
course.

I have a hard time seeing why we wouldn't want to include a portion in the
counter that's unpredictable to an adversary.  It has near-zero
implementation cost and provides a non-trivial improvement in security.

I can cite two other common ciphers which use the
make-it-as-secure-as-practical design philosophy: triple-DES and RSA
Security's DESX (http://www.rsasecurity.com/rsalabs/faq/3-2-7.html).  In
fact, the motivation for the secret counter component is directly analogous
to that for DESX.  From the URL above, "the main motivation for DESX was in
providing a computationally simple way to dramatically improve on the
resistance of DES to exhaustive key search attacks."

Triple-DES uses a 168-bit key and provides no more than 112 bits of security
(less in some circumstances, e.g. where the work of Stefan Lucks can be
brought to bear).  However, the fact that the number of bits in the key is
larger than the effective security level is not a problem.  That fact does
not detract from the real security of the system, it's no harder for a key
management protocol to generate the larger key than the smaller, and the
security level of the algorithm is understood.

>
> >In summary, my reasons for preferring the inclusion of a 'secret counter
> >component' are that 1) it adds a significant amount of security against
> >precomputation attacks, 2) it adds little or no computational
> cost, and 3)
> >it fits easily into the current architecture.
>
> I understood these points from our discussions before I published
> the draft.
>
> As you know, I have spoken to Ron Rivest about this concept.  He feels
> strongly that the use of a longer key is the correct countermeasure to
> precomputation attacks.  This is the reason that I included all three AES
> key sizes in the draft.
>
> Russ

Using larger keys provides more security.  If all costs were equal, no doubt
implementers would adopt larger AES key sizes.  However, costs aren't equal,
since the cost (in sw clock cycles or hw gates) of the larger key sizes is
greater than that of AES with 128-bit keys.  Also, many implementations only
include 128-bit AES (it's the default key size, and the only
mandatory-to-implement key size), and many other specifications only mandate
the implementation of that key size.  The counter mode draft includes 128
bit keys as well.  (Question: is this the mandatory-to-implement key size?
Or will AES-192 be required?)

I have a hard time understanding why we would not want to improve the
security of AES-128 when simple and cheap methods that work well with IKE
are known.

thanks,

David