review of Projects/replay_cache_collision_avoidance, ending Jan. 12

Tom Yu tlyu at MIT.EDU
Sun Dec 28 22:32:29 EST 2008

Greg Hudson <ghudson at MIT.EDU> writes:

> I have two comments:
> 1. I don't see why it is necessary to store and compare the full
> authenticator text.  The consequences of a false hash collision are a
> false replay denial; but the odds of this happening by accident are
> vanishingly low, even if the hash function is insecure.  (And if it
> happens on purpose, we don't care.)

This is a good point.

> 2 If we are storing the full authenticator text, I'm not sure that it
> will save any time to also store a hash.  Comparing two different
> authenticators should be fast because we can stop as soon as we hit the
> first byte which differs.  Also, the time spent reading the record will
> be comparable to the time spent comparing it.

For a fixed client name, the first difference would likely be at the
application checksum, which could be farther into the encoded
authenticator cleartext than the length of an MD5 hash.  The point
about needing to spend time reading in the entire authenticator
cleartext is also a good one.  These points lead me to lean toward
abandoning the "store whole authenticator cleartext" scheme.

This does cause me to think that this scheme has a problem when faced
with the scenario of a replay cache shared between an old and a new

Consider two authenticators that would match under the old
implementation, but one authenticator is recorded by an old
implementation and one is recorded by a new implementation.  Now
imagine that a new implementation receives a replay of the
authenticator recorded by the old implementation.  Its hash won't
match the hash of the entry recorded by the new implementation, so
this authenticator should be accepted by the new implementation IF it
is known that no old implementation has written to the file.  How do
we make this determination usefully?

I think I might have somewhat of an idea of how to do this, but need
to think about it some more.  It has to do with ensuring that a new
implementation always writes pairs of entries (hash entry immediately
followed by old-style entry) and keeps track of which entries are not
paired with hash entries.

More information about the krbdev mailing list