3DES Re-key requirements question

[Mark Bakke <mbakke@cisco.com>]

While talking with Paul Hoffman about the security draft,
it appeared that our requirements for 3DES re-keying are
likely much too strict.  It is also making me nervous seeing
comments on the list calling for mandating AES and not 3DES,
since we have to work with what is real.

Section 5.4 of the current ips-security draft contains some
information about key exhaustion.  The section suggests that
SAs using 3DES CBC mode (the most commonly implemented IPsec
encryption algorithm) will require re-keying very often; every
four minutes for a 1 Gbps connection, and every 20-30 seconds
for a 10 Gbps connection, and that it would be more prudent
to re-key 1 Gbps every 4 seconds, and 10 Gbps every 0.4
seconds.

While hardware is easily available to accelerate 3DES itself,
many implementations do the key exchange in software.  This
takes quite a bit of CPU time, often shared with many other
tasks.  This makes re-keying at these short intervals impractical.

This all seems to point at using AES-CBC instead of 3DES.

However, I have a requirements question.  The formulas shown
in the draft specifies the number of bytes that can be transmitted
on a connection before it becomes probable that SINGLE bit of
information is leaked.  It does not leak any bits of the key
itself at this point.  When doing disk or tape reads and writes,
a single bit of information is not all that valuable.  One would
have to leak many bits of information, probably some of them
sequential, in order for an observer to make actual use of the
data.  Furthermore, in order for the observer (Carol, right?)
to do the analysis to recover the leaked bits, the entire data
stream must be stored and available for processing; this cannot
be done on-the-fly (Storage Vendors - here's a possible new market :-).

In practice, this sort of cryptanalysis is required on many
stored terabytes of information in order to recover a handful
of bits of text.

Anyway, I think that we need to come up with what our real
requirements are for "data leakage", so that we can decide on
what the practical re-keying times ought to be for 3DES.  This
should help alleviate concerns about 3DES' effectiveness, which
are probably a bit on the paranoid side right now.

How about stating a requirement something like:

- The key for an IPsec SA shall be considered exhausted if:
  - More than x bits in y gigabits may be subject to leakage

This should relax the re-key requirements on 3DES enough that it
is practical to implement at 1Gbps, and perhaps 10Gbps, without
introducing realistic security risks.

Of course, AES will still be the right choice moving into the
future, but there's a lot of 3DES out there, and AES has not
yet been deployed.

--
Mark


-- 
Mark A. Bakke
Cisco Systems
mbakke@cisco.com
763.398.1054