Re: replay field size

[Steven Bellovin <[e-mail]>]

>   As you note, one can rekey more frequently than when the counter runs
> out.  However, the counter size does present an upper bound to the rekey
> interval.  In this way, they are related.  This relationship does need
> to be carefully considered by the working group, IMHO.
> 
>   For example, I am aware of commercial encrypting router products 
> (not cisco) that can handle a full IP stream at OC-3c rates (155 Mbps).  
> Based on the relatively small size of a large percentage of IP datagrams
> (as measured on a well-known OC-3 trans-Atlantic IP link), this is not
> a particularly long time interval between rekeys forced by a 32-bit
> replay counter.

If all packets were 40 bytes, 155Mbps is about 500K packets/second.
At 2^32 packets before rekey, the interval is over 2 hours if the link
were running flat-out.  That's not onerous.  Even at 1Gbps -- the
fastest I've heard anyone discuss -- it's still 20 minutes.  A router
that can switch packets at that rate will likely have a moderately serious
CPU for doing new key exchanges.

But not all packets are that small; in fact, the mean packet size is
about 250 bytes (see http://www.nlanr.net/NA/Learn/packetsizes.html) --
while tinygrams are a large percentage of the packet count, they don't
account for very much of the volume by byte; what fills up OC-3 lines
is the bulk tranfers.  At that rate, the rekey interval is over 15 hours
at OC-3 speeds.

But it's worse than that.  At 250 bytes/packet, there are about 2^5 DES
blocks/packet, which means there are 2^37 blocks per ``full'' 32-bit
security association.  That's getting unpleasantly close to the point
where linear cryptanalysis is feasbible.  (Matsui's CRYPTO '94 paper
says that with 2^38 known plaintexts, the success rate is 10% with
complexity 2^50.  The new ``Handbook of Applied Cryptography'' notes
that ``linear cryptanalysis is possible in a ciphertext-only
environment if some underlying plaintext redundancy is known (e.g.,
parity bits or high-order 0-bits in ASCII characters.))  I submit that
we really don't want to encrypt that much plaintext with any single key
-- ever.  And of course, we don't know that linear cryptanalysis is the
ultimate attack.

Furthermore, the 2^32 packet limit is the limit for a single association.
To my mind, that makes it highly improbable that it's a real limit
in any event -- and if we get near it, we should rekey.


>   By contrast, a 64-bit replay counter would not increase the size
> of the overall packet because it would just eliminate 32-bits of
> padding (that would be needed otherwise for IPv6 compliance).  However,
> a 64-bit replay counter would very significantly increase the upper
> bound and make premature forced rekeying a non-issue for the overwhelming
> majority of cases.

It would also mandate an 64-bit subtraction that's unpleasant on most
of today's hosts.

>   This argues that a 64-bit replay counter would best further the WG's
> goal of maintaining a set of specifications that work equally well with
> any cryptographic algorithm.
> 
> Ran
> [e-mail]