review of Projects/replay_cache_collision_avoidance, ending Jan. 12

Sam Hartman hartmans at MIT.EDU
Mon Dec 29 12:28:14 EST 2008

>>>>> "Tom" == Tom Yu <tlyu at MIT.EDU> writes:

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

    Tom> This message


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

    Tom> What proportion of false positives is acceptable in a
    Tom> mixed-code deployment?

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

    Tom> Since we have two counted byte arrays in the record, we could
    Tom> make one of them the extension record that starts with a zero
    Tom> byte, and another that looks like a normal null-terminated
    Tom> 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.

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

As I explain in another message, I think that RFC 3961 allows us to
avoid this.  However, consider a stream cipher that integrity protects
the plaintext, *not* the ciphertext.  I think changes to the
confounder would be undetected.

It does not fall out of any of the standard definitions of security
for symmetric ciphers--not even non-malleability--guarantees that it
is hard given one ciphertext to construct another valid ciphertext
with the same plaintext.

More information about the krbdev mailing list