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

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

Alex,

> -----Original Message-----
> From: Alex Alten [mailto:Alten@attbi.com]
> Sent: Monday, July 29, 2002 3:57 PM
> To: David A. Mcgrew
> Cc: ipsec@lists.tislabs.com
> Subject: RE: draft-ietf-ipsec-ciph-aes-ctr-00.txt
>
>
> Thanks David,
>
> My misunderstanding of the IV generation details.  I just read your
> other explanation of the secret starting offset for the IV sequence.
> In your/Fluher's design, is this offset generated separately from
> the key bits?

no, it would be generated along with the key.  In IKE, the counter mode key
would be taken from the KEYMAT, then split into the AES Key and Offset
fields.

>
> What if the key is used repeatedly, or in the worst case shared
> among many hosts?  What happens if a host reboots?  Does the secret
> offset start at the same initial value?  If not, how do you
> guarentee this?

The Offset is defined to be part of the key, so if a key is reused, then the
Offset is reused, and so forth.

I think that your concern is over how a device can ensure that the IVs are
unique.  This  is a point that deserves some attention (and of course is
independent of the use of an offset field).  A device can use checkpointing
to ensure that it doesn't use the same IV value twice.  Jesse Walker wrote a
short description of periodic checkpointing and how it can be used in
counter mode to address your concern, in a recent discussion on using that
mode.  It might be good to include something like that in a counter mode ESP
draft.

If the same counter mode key is used to encrypt traffic by two distinct
senders, then some other mechanism is needed in order to ensure that
keystream segments are disjoint.  This can be done by including a field in
the counter which has a distinct value for each distinct sender.  Using a
"sender id" field like this does allow the same counter mode key to be used
by multiple encryptors while preserving security.

In draft-ietf-ipsec-ciph-aes-ctr-00.txt, the lower 24 bits of the SPI are
included in the counter.  This field could be used as a sender-id, though
doing so would mean that the same key would be used in different SAs.  I'm
not sure if the draft intends for the truncated SPI field to be used in this
way.  It's clear that using a single key to protect both directions of a
duplex connection is intended, though I'm not sure what else is.

There are some caveats with using the same key in multiple senders.  The
mechanism by which the sender-id values are generated and distributed must
guarantee their uniqueness.  The limitation that no more than 2^64 blocks
can be encrypted must be coordinated across all senders, so that the limit
is enforced on the sum total number of blocks encrypted.  And of course the
mechanism by which the keys are distributed must be secure.

One advantage to using a single key for some number N of senders is that
storage for N keys is saved.  However, it's important to realize that the
other information normally associated with an SA (which at a bare minimum
includes the 64 bit sequence number and possibly some other 64 bits of
information used to generate the IV) must still be stored.  In some devices,
all N values of the other SA data must be stored.  So sharing keys across
multiple senders can be penny-wise but pound-foolish, except in some extreme
circumstances.

Another case in which sharing a key across multiple senders can have an
advantage is when its easier to distribute a single key, e.g. using a
multicast channel.

>
> I think these questions still are valid even if you combine the
> offset with the ESP sequence number and SPI (since these may
> repeat also).  WEP broke down with it's failure to answer these
> sorts of questions.

Agreed.

>
> BTW, I'm not completely clear on this aspect.  Does the sender
> completely control the IV sequence generation?  Can the receiver
> process incoming packets out-of-order or handle dropped packets?

Yes, out-of-order packets can be dealt with.  The counter mode definition in
Russ's draft generates a keystream segment for each packet, essentially
mapping an IV (and a secret key) to a particular segment of keystream.  The
order in which the segments are generated is unimportant.  Security follows
from the fact that the segments are disjoint and the IVs don't repeat.

Regards,

David

>
> (Russ, I guess I'm responding to my internal mental "gestalt" of
> the various emails flying around. :-)
>
> Regards,
>
> - Alex
>
>
> At 02:19 PM 7/29/2002 -0700, David A. Mcgrew wrote:
> >Alex,
> >
> >> -----Original Message-----
> >> From: owner-ipsec@lists.tislabs.com
> >> [mailto:owner-ipsec@lists.tislabs.com]On Behalf Of Alex Alten
> >> Sent: Monday, July 29, 2002 11:42 AM
> >> To: Housley, Russ; David A. Mcgrew
> >> Cc: ipsec@lists.tislabs.com
> >> Subject: RE: draft-ietf-ipsec-ciph-aes-ctr-00.txt
> >>
> >>
> >> At 09:59 AM 7/29/2002 -0400, Housley, Russ wrote:
> >> >[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.  If one is concerned about this type of dictionary
> >> attack, the
> >> >use of a longer AES key provides more protection without imposing
> >> >additional requirements on key management.
> >> >
> >> >Russ
> >> >
> >>
> >> I believe someone already has stated the problem will be to prevent the
> >> counter
> >> from repeating (or being predictable) with the same key. It's
> entropy in
> >> practice
> >> may be fairly low.  Also, there may be the fairly likely danger
> >> of shared keys
> >> across multiple hosts which is deadly if any IV values
> commonly repeat on
> >> different hosts (this helped to kill WEP).  I think this is the
> >> crux of the
> >> matter,
> >> and I don't think this can be solved with a software PRNG
> >> algorithm.  What I'd
> >> recommend is to try to pull it from hardware, like the Intel
> P4 supporting
> >> chipset.
> >> If this is not possible maybe a large random seed can be placed on each
> >> host, and
> >> the PRNG is then used to pseudo-randomly mix/fold the seed
> bits. One can
> >> get quite
> >> a few "unpredictable" random IV values that way. There will be an
> >> exponential
> >> decay in unpredictableness, but hopefull you can start high
> enough up on
> >> the curve
> >> for it to useful.  Eventually the seed would need to be
> refreshed, but if
> >> it is
> >> infrequent enough it could be done by hand.  The large seed
> should remain
> >> secret
> >> during its lifetime otherwise it will be subject to an inverse matrix
> >> precomputation
> >> attack.  It would be ideal if the PRNG had a large set of random small
> >> seeds available
> >> to it as well, so that the start of it's cycle per new session would be
> >> unpredictable
> >> (it too needs to be refreshed periodically).
> >
> >I think that the discussion is somewhat hard to follow, my
> apologies for the
> >terseness of the mail that started this thread.
> >
> >Russ' draft requires distinct IV values, which implies that a
> deterministic
> >mechanism must be used to produce them.  The use of a true random number
> >generator, as you'd suggest, would generate repeat values after 2^32
> >packets, with a high probability.  Given the fact that using the same IV
> >value twice in counter mode gives away the exor of the
> plaintexts, this is
> >something that we want to avoid.
> >
> >Russ and I are in agreement that counter mode should be implemented using
> >IVs generated by a deterministic algorithm.  What I was proposing is that
> >additional security against attacks which use precomputation (e.g.
> >key-collision and time-memory tradeoff attacks) by making part of the
> >counter secret, so that the adversary does not know all of the
> inputs to the
> >AES cipher that are used to generate a particular range of keystream.
> >
> >David
> >
> >
> --
>
> Alex Alten
> Alten@ATTBI.com
>