In message <[EMAIL PROTECTED]>, Ron Rivest writes:
>
>Steve --
>
>Don't your statistics support the argument that key agility is
>*not* likely to be terribly important by itself?
>
>With a cache capable of storing only 5 key setups, you get at least a
>75% hit rate, by your statistics.
>
>This effectively reduces key setup time by a factor of *four*, making it
>really second-order compared to the bulk of the encryption work to be
>done.
>
>Depending on the algorithm, a cache for 5 key setups is pretty
>minimal. For example, a setup key for RC6 requires only 176 bytes; a
>kilobyte of RAM would easily do for a five-key cache.
>
>I like your miss-rate statistics, but feel they support better the
>argument that ``key agility is not terribly important by itself''
>rather than the statement ``key agility is terribly important.''
The short answer is "I don't know yet, and that's why I'm doing
experiments". But let me give a more detailed answer.
I assume that any hardware implementation of AES for something like
IPsec will have some cache for algorithms that would benefit from
one. (It's possible that some of the other candidates can do
key-scheduling in-line, and hence won't need a cache.) The question
is how big a cache is needed.
My experiment was couched in those terms because I regard that
question as more useful. Without a cache, the limiting case is
alternating short packets for two SAs, in which case you're doing
a setup operation for every packet. In that case, then, the
calculation is simple: the chip has to be able to run at a rate
so that the time for key setup plus cryptography is less than the
total transmission time for the packet. Otherwise, it would not
be able to keep up with a large burst. The smaller the packet,
the less time there is to amortize the cost of the key setup. If
key setup took as much time as encryption of 3-4 blocks, it would
require a chip to run about twice as fast if the data were exclusively
short blocks. My numbers certainly support the notion that in IP,
you'll see very few back-to-back packets for the same destination;
even in my small-scale experiment, I saw that 60-70% of the pairs
were to different destinations. That number is very likely to go up
for higher-speed nets with more endpoints.
As I said, though, that's a limiting case and not realisitic.
First, chips will most likely have caches. Second, not all blocks
are short in IP, thus providing some headroom. But we need traffic
data to quantify the effects of those figures. For example, the
mix of short and long packets determines how much input buffer
space the cryptographic engine would need to hold incoming packets
while doing key setup for a sequence of short ones. Similarly, we
don't yet know how large a cache is needed for more SAs -- does it
scale linearly? (I suspect not, but I don't know.) I was working
with about 150 SAs over a period of several hours, but their are
products on the market today that support 2000 simultaneous SAs,
at 70 Mbps. (See, for example, Timestep's Newbridge 237.) What
size gateways will be needed in 10 years?
There are also other sorts of VPNs than IPsec-based ones. In ATM,
cells are 53 bytes, stressing any key setup algorithm if fully
mixed. If the ATM net is used to carry IP traffic, you'll see
bursts more or less equivalent to IP's statistics, but if secure
voice is being carried, you really will see interleaved packets
from different conversations. I experimented on IPsec gateways because
I know them better, and have one available for experimentation.
What we need is more data. If someone has a larger IPsec gateway and
can monitor the traffic, I'll be happy to work with them to crunch the
data. What I did was just a start.
--Steve Bellovin
