3.3 Digging into the Cryptanalysis of IPsec

(See the previous installment or the top level of this series of posts.)

What is the recommended lifetime of an IPsec Security Association today?  This is the question that has proven to be so hard to answer, and that has led me wandering all across the web.  Probably the most relevant source is, naturally, the mailing list where most of the design work is documented.

One early, relevant message from 08 March 1995 carries the quote:

"I think 2^32 is a better bound than 2^43, at least for certain modes
of DES. For instance, after 2^32 blocks in CBC mode, you expect to see
two identical ciphertext blocks, say c[i] and c[j]; the difference
between their predecessors will match the difference between the
corresponding plaintext blocks, i.e.,
p[i] xor p[j] = c[i-1] xor c[j-1]
Information thus starts to leak after 2^32 blocks (square root of the
message space). I would recommend 2^32 blocks as the limit for the
lifetime of a key, and that takes care of the 2^43/2^47 attacks as
well."

referring, although not by name, to both the birthday paradox and the differential cryptanalysis limits discussed above.  Keep in mind that at $2^{32}$ blocks, we are at a 39% probability of there being at least one ciphertext collision revealing some information.

Searching the archives for "birthday" also turned up some relevant messages, e.g. the relatively recent (21 April 2015) message  quoting the earlier message:

"> I think the main problem with 3DES is not that it is significantly slower
> than AES, but that it has blocksize of 64 bits, that is considered
> loo small for high-speed networks, when the possibility of birthday attack
> leads to necessity to frequently rekey.
It’s hard to make that case. The blocksize is 64 bits. So it’s prudent
to not use more than, say, a billion blocks. A billion blocks is 64
Gb. There are very few real tunnels that run that kind of throughput
in under a minute. OTOH it’s no problem at all to run a CreateChildSA
every minute, or even every five seconds. So I think there are very
few cases that *can’t* use 3DES."

This is interesting, particularly given its newness.  The author (Yoav Nir, one of the long-time leaders of the IPsec community) considers 3DES plus very frequent rekeying to be sufficient, at least for some use cases, and it's important for backwards compatibility.  However, in a slightly earlier (2012) exchange on the mailing list, David McGrew (another key IPsec person) and Nir covered the same issue, with McGrew arguing that no more than 50 megabytes should be encrypted with the same key even using 3DES, due to the birthday paradox.  McGrew went so far as to write up a 16-page analysis posted on the Cryptology preprint server (see references for more).