[1367] in Kerberos_V5_Development
Re: kdc performance and rcache
daemon@ATHENA.MIT.EDU (Barry Jaspan)
Mon Jul 1 15:26:40 1996
Date: Mon, 1 Jul 1996 15:25:10 -0400
From: "Barry Jaspan" <bjaspan@MIT.EDU>
To: hartmans@MIT.EDU
Cc: raeburn@cygnus.com, hartmans@MIT.EDU, krbdev@MIT.EDU
In-Reply-To: <tslohlzvlts.fsf@tertius.mit.edu> (message from Sam Hartman on 01 Jul 1996 15:02:23 -0400)
This issue seems to be going in circles.
It seems pretty clear that the replay cache is a time sink and should
be removed if doing so is safe. The most likely possible problem
anyone has mentioned is the possibility of a known-plaintext attack if
the replay cache is removed. Is it really feasible for this to
present a threat even to single DES, given the krbtgt maximum lifetime
and the KDC's maximum throughput? Even if we increased the KDC's
throughput by a factor of ten (unlikely), an attacker could only
generate 1.8 million known-plaintext messages in 10 hours, and that
would require saturating the KDC the whole time (which surely would be
noticed). If this does present a credible threat to DES, there are
cheaper ways to prevent it than with a replay cache. For example, the
KDC could limit each user to 100 (or 1,000) requests per day, plenty
for a legit user but enough to eliminate the known-plaintext attack
risk; the counters could be stored in an in-memory hash table to make
the test-and-set fast. If that were still too slow, the KDC could
select perhaps a random 10% of all requests to count, again letting
legit users through but catching a massive request attack. Actually,
though, I doubt the known-plaintext attack is important, and we just
shouldn't use a replay cache for the TGS.
The lookaside buffer is a simpler issue. It is obvious (and Ken's
results show) that a linked list implementation is slow enough to
defeat its own purpose as a cache. If someone cares enough, it should
be reimplemented with a faster data structure, and some more testing
should be performed. If the lookaside buffer is a useful cache that
improves performance, great, keep it; otherwise, it serves no purpose
and should be disabled.
Note that the only time the lookaside buffer can possibly accomplish
anything in real life is when UDP retransmissions occur. Does this
happen often enough to warrant the extra complexity (bugs have been
found in this code before) and the programmer time requird to
implement the better datas structure? I suspect that the programmer
time needed to implement a new system will be more than the improved
cache will ever save an actual KDC; thus, if I were the development
manager, I'd never assign one of my engineering resources to spend
time on it.
Barry
