review of Projects/replay_cache_collision_avoidance, ending Jan. 12

Tom Yu tlyu at MIT.EDU
Mon Dec 29 08:02:22 EST 2008

Greg Hudson <ghudson at MIT.EDU> writes:

> On Mon, 2008-12-29 at 00:13 -0500, Tom Yu wrote:
>> I will try to dig up records of those discussions, but a pointer would
>> be helpful.
> I found:
> These posts from Sam are particularly relevant:


The above messages from Sam concern changes to the AP-REQ that are not
the actual ciphertext of the encrypted authenticator.  If an attacker
does not know the key, and manipulates the ciphertext, the result will
not be valid ciphertext except with probability on the order of a
successful exhaustive key search of the cipher.

Sam, if you know of a way that changing the actual ciphertext without
knowing the key will cause problems, please explain.

This message

does imply that storing binary strings in the replay cache could cause
problems for old implementations.  The worst case I can come up with,
given the current form of the proposal, is that an old implementation
would truncate the extension records at the leading zero byte when
doing an expunge.  A new implementation could detect this corruption
and compensate accordingly, possibly with an increased number of false

What proportion of false positives is acceptable in a mixed-code

One interesting possibility is to store a truncated copy of the hash
in the microseconds field, which an old implementation would likely
preserve when performing an expunge.

Since we have two counted byte arrays in the record, we could make one
of them the extension record that starts with a zero byte, and another
that looks like a normal null-terminated string and would be preserved
by an old implementation.

> The conversation picks up again in 2008:
> I'm not finding any piece of discussion specifically connecting the dots
> between "maybe an attacker can perturb the authenticator a little bit
> and change its hash without invalidating it" and "we should store the
> authenticator".  In fact, Sam seemed to be arguing simply for hashing
> the decrypted authenticator rather than its encrypted form.

I'd still like to know what benefit hashing the decrypted
authenticator has above hashing the ciphertext.  As Roland pointed out
elsewhere in that thread, the mandatory parts of the cleartext
authenticator contain nothing that is guaranteed to be different for
multiple rapidly consecutive legitimate requests.  Hashing the
ciphertext makes it less likely that false positives will occur.

More information about the krbdev mailing list