Proposed modifications to replay cache to prevent false positives

[Jeffrey Altman]

The existing replay cache file format has been known to produce false
positives on fast multiprocessor machines when multiple processes or
threads are using the same client principal to contact one or more
services that share a common service principal.  When a false positive
occurs, the request from the client is denied and it becomes more
difficult to distinguish between normal behavior and an attack.

The false positives occur even though the authenticators used by the
various client processes differ, that fact is not reflected in the data
stored in the replay cache.

The current cache format consists of:

  unsigned int   - client length
  variable       - client principal name
  unsigned int   - server length
  variable       - server principal name
  krb5_int32     - micro seconds
  krb5_timestamp - timestamp

One proposal that has been discussed to avoid the false positives is to
store a hash of the authenticator in the replay cache instead of the
client and server principal names.

One of the concerns with changing the file format is the desire to
maintain compatibility with older Kerberos library implementations
that share the same replay cache.

I propose that we can avoid false positives in services linked to a new
replay cache implementation without breaking compatibility with older
applications.

I propose that we modify the replay cache library to store two records
for each entry.  The first will consist of the following:

  unsigned int   - length of hash
  variable       - hash of authenticator
  unsigned int   - the value zero
  krb5_int32     - micro seconds
  krb5_timestamp - timestamp

This would be followed during a transition period by a second record
consisting of the original client and server principal name data.
During the transition period there will be a small increase in the
attack footprint against new applications which do not look at the
old client and server principal name records if the ticket was first
used with an old application.  When all of the applications are known
to be using the new library, the practice of writing the old style
records can be discontinued.

I would also propose that the "unsigned int" types be replaced in the
code base with "krb5_int32" to ensure that 32-bit and 64-bit apps can
read/write from the same replay cache file.

One question that is outstanding is which hash algorithm should be used?

Comments?

Jeffrey Altman

[Ken Raeburn contributed to the ideas proposed in this e-mail.]