review of Projects/replay_cache_collision_avoidance, ending Jan. 12

[Tom Yu]

Sam Hartman <hartmans at MIT.EDU> writes:

>>>>>> "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> http://mailman.mit.edu/pipermail/krbdev/2005-May/003445.html
>
>     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:
>     >> 
>     >> http://mailman.mit.edu/pipermail/krbdev/2008-May/006601.html
>     >> 
>     >> 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 mit.edu
>     Tom> https://mailman.mit.edu/mailman/listinfo/krbdev
>
>
> 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.

Do we know of such an encryption scheme being used with Kerberos?

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

Actually the 2000 paper by Bellare and Namprempre describes some
formal notions that could help here.  We strongly imply in RFC 3961
that the property we desire is INT-CTXT.

    "We consider two notions of integrity (we use the terms
    authenticity and integrity interchangeably) for symmetric
    encryption schemes.  INT-PTXT (integrity of plaintexts) requires
    that it be computationally infeasible to produce a ciphertext
    decrypting to a message which the sender had never encrypted,
    while INT-CTXT (integrity of ciphertexts) requires that it be
    computationally infeasible to produce a ciphertext not previously
    produced by the sender, regardless of whether or not the
    underlying plaintext is 'new'.  (In both cases, the adversary is
    allowed a chosen-message attack.)  The first of these notions is
    the more natrual security requirement while the interest of the
    second, stronger notion is perhaps more in the impleications we
    discuss below." [1]

I don't know whether the terminology is original to those authors, but
I think it is useful.

[1] M. Bellare and C. Namprempre, "Authenticated Encryption: Relations
among notions and analysis of the generic composition paradigm",
extended version of a paper appearing in T. Okamoto ed., ASIACRYPT
2000, Lecture Notes in Computer Science 1976, pp. 531-545.
Springer-Verlag, 2000.