Subject: Re: [IPsec] updating ESP and AH requirements

From: "David McGrew (mcgrew)" <[email-masked]>
Date: Mon, 5 Nov 2012 15:34:38 +0000

Thanks Yaron, Paul, David, Yoav, and Scott for your input on the draft and
the issues it addresses.

The main concern so far has been the TDES-CBC encryption guidance.  I was
unable to find a reference that gives a good treatment of attacks on
64-bit block ciphers used at and beyond the birthday bound, so I wrote one
up; it is online at <http://eprint.iacr.org/2012/623>.  What is most
relevant to TDES-CBC are Sections 2 and 4.   Table 1 shows  the expected
number of bits leaked by TDES-CBC (the w=64 row) with that of AES-CBC (the
w=128 row) for comparison.  The security benefits of AES, and the risks of
over-used TDES, clearly warrant some deprecation of TDES.

Several folks have made the valid points that interoperability with
pre-2003 implementations requires TDES-CBC encryption, and that TDES-CBC
can  provide security if it protects low-volume traffic.  I propose
putting TDES-CBC as a MAY- implement, and adding the following text to the
Usage Guidance section: "IPsec implementations from before 2003 will not
support AES-CBC encryption.  New implementations that aim to interoperate
with these earlier implementations will need Triple-DES CBC encryption.
However, AES-GCM and AES-CBC provide significantly stronger
confidentiality, and SHOULD be used instead of TDES-CBC whenever possible.
 AES-CCM and AES-CTR also provide stronger confidentiality than TDES.
When TDES is used, it SHOULD NOT encrypt more than 50 Megabytes of data
with a single key; otherwise, it may start to leak information about
plaintexts to attackers [citation]."  In my opinion "MAY-" is better than
"MAY" because TDES is and should be on a clear path to retirement, and if
history is any guide, the ESP requirements won't be updated again until
2019.  But as this is intended to be a standards track document, I will
defer to the opinion of the group.

It may be useful to also add specific guidance that IKE proposals should
put AES before TDES, since that policy achieves the goals of using AES
when possible and TDES when it is the only option.  This touches on the
general issue of the evolution of crypto requirements, and it would make
sense to define a category of "use only for backwards compatibility"
algorithms and key sizes.  What do you think, would this make things more
or less clear to implementers and users of IPsec?

Some people have commented that TDES-CBC is worth keeping around in order
to provide algorithm diversity.  I respectfully disagree, for several
technical reasons.  First, it is hard to conceive of a set of realistic
circumstances in which TDES would provide better security than AES.  The
security degradation due to TDES being 64 bits wide, versus the 128 bit
width of AES, is far more significant than the effects of block cipher
cryptanalysis techniques such as differential, linear, integral,
algebraic, and biclique cryptanalysis. For example: the biclique attack on
AES-128 requires 2^88 chosen plaintexts/ciphertexts and takes O(2^126)
operations, which is a million times as much plaintext than that needed
for collision attack on AES-CBC, and 2^62 times as much computation.
Also, the structure of TDES makes it open to attacks such as that of
Stefan Lucks [1].  Second, supposing that in some bizarre alternate
universe AES was believed to be less secure than TDES, the performance
differences between TDES-CBC and AES are such that the former is not a
viable replacement for the latter; this is especially true for AES-GCM,
AES-CCM, and AES-CTR.  Thus it does not make sense to consider retaining
TDES for the sake of algorithm diversity.  I do think that algorithm
diversity is a valid goal, but one that deserves more deliberate
consideration.  Important goals for an alternative cipher would be AES
compatibility, in the sense of draft-irtf-cfrg-cipher-catalog-01 Section
3.1, security, performance, no IPR issues, and ideally, diversity from the
AES design methodology.

I would also be interested in hearing input on the other algorithm
changes.  

Thanks again, and regards,

David

[1] S. Lucks, "Attacking Triple Encryption", Proceedings of the 5th
International Workshop on Fast Software Encryption workshop,
Springer-Verlag, 1998.

On 10/26/12 5:56 PM, "Yaron Sheffer" <[email-masked]> wrote:

>The need to interoperate with older implementations, as well as Yoav's
>justification of having a widely implemented algorithm as a backup for
>AES, both seem to argue for keeping 3DES as a MAY or MAY-.
>
>I suggest to include a concrete recommendation on rekeying. We could
>argue the numbers forever, but I think a 1/1,000,000 probability for a
>single collision is good enough. So we could RECOMMEND a rekey once
>every 50 MB sent.
>
>Thanks,
>     Yaron
>
>--
>
>It is not a question of implementing new: *all* new systems coming into
>the VPNC lab have AES-CBC, and have for a few years. However, if those
>implementations want to interoperate with older implementations, they
>need to also have 3DES. Thus, a "MAY" for 3DES with a clear explanation
>why it is inappropriate in high-volume implementations would be
>valuable. --Paul Hoffman
>_______________________________________________
>IPsec mailing list
>[email-masked]
>https://www.ietf.org/mailman/listinfo/ipsec

---

From: Yoav Nir <[email-masked]>
Date: Mon, 5 Nov 2012 20:30:16 +0200

By the formula in that paper, if we rekey every 10 seconds, 3DES is good enough up to about 10 Gbps, which is pretty high end for most VPNs. The IKE implementation that goes with a 10 Gbps IPsec implementation should have no problem rekeying every 10 seconds.

I don't think it matters much whether 3DES is SHOULD- or MAY, but I do think we need to have algorithm diversity. IPsecME is not the venue for a competition like those that NIST held, but perhaps we should go over the ciphers specified in section 4 of the cipher catalog, and choose a backup cipher to become a SHOULD in the requirements draft.

Yoav

---

From: "David McGrew (mcgrew)" <[email-masked]>
Date: Mon, 5 Nov 2012 20:03:41 +0000

Hi Yoav,

On 11/5/12 1:30 PM, "Yoav Nir" <[email-masked]> wrote:

>By the formula in that paper, if we rekey every 10 seconds, 3DES is good
>enough up to about 10 Gbps, which is pretty high end for most VPNs. The
>IKE implementation that goes with a 10 Gbps IPsec implementation should
>have no problem rekeying every 10 seconds.

At the data rate and key lifetime that you mention, the expected number of
bits that an attacker can glean is about two bits every ten seconds, or 2
kilobytes per day, 15 kilobytes per week, 60 kilobytes per month, 788
kilobytes per year.   This is not a set of parameter choices that we
should be recommending.  Another consideration is: what happens if the
attacker interferes with the rekeying?

I agree with the idea that there are some data rates low enough that TDES
is a perfectly good algorithm, but not north of one gigabit :-)

>
>I don't think it matters much whether 3DES is SHOULD- or MAY, but I do
>think we need to have algorithm diversity. IPsecME is not the venue for a
>competition like those that NIST held, but perhaps we should go over the
>ciphers specified in section 4 of the cipher catalog, and choose a backup
>cipher to become a SHOULD in the requirements draft.

I think it makes sense to look for cipher diversity, but I don't think
this is a selection that should be made hastily.  Also, it would be good
to have the selection of an alternate cipher be something done at the IETF
level, and not at the WG level.   I hope that IPsec ME can move forward
with updated algorithm guidance without waiting for the selection of an
alternate, which could be a protracted process.  Also I notice that for
ESP we will need to recommend a mode of operation as well.

Thanks,

David