(Following earlier posting by Steve Bellovin and myself on the same subject.)
Steve --
I don't quite understand your argument yet, although it is certainly
good to have some data to look at!
We can have a simple model for encryption time wherein
c + d n
to encrypt a packet of n bytes, for some nonnegative constants c and d.
Lower c implies better "key agility".
Suppose now that we have two algorithms A and B, with respective
encryption times
c_A + d_A n
and
c_B + d_B n
Suppose further (and without loss of generality) that
c_A > c_B
(That is, algorithm B has better "key agility".)
We now might as well assume that
d_A < d_B
otherwise it is "no contest" (B would always be better).
It can be argued that the only relevant criterion should be the
average time to encrypt a packet. This is
c_A + d_A E(n)
for algorithm A and
c_B + d_B E(n)
for algorithm B, where E(n) is the average packet length.
Latency is another relevant parameter, but it is closely related to
average time to encrypt a packet (I am drafting a note on this with
Mor Harchol-Balter, which we will post).
If we use a cache to save on key setups, and have a miss rate of
m, then this changes the formula from c + d n to
m c + d n
but otherwise everything else is the same.
Note that it is the *less* key-agile algorithms that benefit the
*most* from key setup caches! A cache may make such an algorithm the
"winner", when before it was a hopeless loser. Key caching can, as
you suggest, dramatically change the picture. But it has the effect
of eliminating key agility as a criterion, since with a sufficiently
large cache, key setup is close to negligible.
The existence of "packet trains" will have the effect of decreasing m
even further.
As time progresses, we will see larger and larger caches used
routinely, so that key agility may become less and less of an issue.
(There may be a countervailing trend that affects the miss rate, but
I suspect that this trend won't be as strong.)
In either case (with key setup cache or without) I believe we should
be focussing on the average time to encrypt a packet (including any
necessary key setup). By linearity, this is
c + d E(n)
where E(n) is the average packet length.
IP traffic has many short packets (e.g. 40 bytes) but the average
packet size is more like 300-400 bytes, and plausibly increasing over
time. (Your data is interesting in that it yields figures for both
upstream and downstream; the 106 bytes/packet upstream is intriguing).
This trend as well makes key agility less and less of an issue.
I agree that key agility is important, but only to the extent that it
is a component of average packet encryption time. Unless you are
building a key-search engine, you are doing key setups only in order
to do some real encryption/decryption work, and it is the overall work
factor that matters, not key setup by itself. Your considerations
help to clarify the complexity and variability of computing the
overall work factor from the key setup and encryption times, but don't
detract from this basic point...
But good estimates for average packet encryption time require good
estimates of packet size distributions and key miss rates (if you are
using key setup caches), so I welcome your data!
Cheers,
Ron Rivest
