Proposed modifications to replay cache to prevent false positives

[Ken Raeburn]

On May 27, 2005, at 16:46, Jeffrey Altman wrote:
> The current cache format consists of:
>
>   unsigned int   - client length
>   variable       - client principal name
>   unsigned int   - server length
>   variable       - server principal name

Clarification: The lengths and data here include C-style trailing NUL 
bytes on the strings.  Also, strlen is used on the strings when writing 
them out, so the strings can't contain NUL internally.

> 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

... hex or base-64 encoded with NUL termination, for compatibility.  If 
the hash is stored in binary form, the strlen() calls in the current 
code base would break things.

>   unsigned int   - the value zero

This should be:
   unsigned int    - the value one
   one char        - nul

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

We could retain the checks against the old-style records too, when the 
hash value is not present.  It would be slower, and would continue to 
have false positives if the older implementation wrote out the value 
first, but it would be more secure.  And you're already going to be 
stuck with false positives until all of the applications are switched 
over.

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

Sounds good.  I think the timestamp may be a trickier issue.

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

I'd suggest SHA-1.  Yeah, we could have collision issues, but if 
someone's trying to generate authenticators that will produce false 
replay detections, let 'em.  And any work done to optimize either the 
replay cache code or the AES/SHA1 cryptosystem will benefit both.

Or, truncated SHA-1, to maybe 128 bits (quick to compare on a 64-bit 
machine).

Maybe make it configurable, by writing some identifying value into the 
record (the server field, maybe).  We wouldn't have to support any 
other value right now, but maybe having a marker there might help a 
transition?  Then again, in the long term, we probably want to change 
the format more drastically anyways, so never mind....

Ken