review of Projects/replay_cache_collision_avoidance, ending Jan. 12

Jeffrey Altman jaltman at
Mon Dec 29 00:06:06 EST 2008

Tom Yu wrote:
> 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.

The reason the full authenticator is being stored is not so that it can
be compared today but so that it is available for alternate comparisons
in the future.

If you go back through the history of the replay cache discussions
there were concerns that it might be possible to alter the binary
authenticator by adjusting the asn.1 representation of the components.

>> 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
> implementation.
> 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.

There are absolutely weaknesses while both formats are supported.
Supporting both formats provides a viable transition path.

Jeffrey Altman

-------------- next part --------------
A non-text attachment was scrubbed...
Name: smime.p7s
Type: application/x-pkcs7-signature
Size: 3355 bytes
Desc: S/MIME Cryptographic Signature
Url :

More information about the krbdev mailing list