[krbdev.mit.edu #1201] kdc returns replay when replayed request not apparent

[Tom Yu via RT]

Hi, it seems very likely that you have encountered a bug in replay
detection.  There are many places to which we might assign blame for
this one.  These include the MIT krb5 implementation of the replay
cache, the protocol specification itself, and the Windows krb5 client
implementation.

Basically, the replay cache in MIT krb5 only stores the tuple of {client
principal, server principal, time, microseconds}.  If two authenticators
have identical such tuples, the second is considered to be a replay,
even if it is different from the first.  This behavior, while not
explicitly required by RFC 1510 (the specification of the Kerberos v5
protocol), is strongly suggested by some wording in the RFC.

A complicating factor is the historical behavior of the gettimeofday()
system call on Unix.  This system call returns monotonically increasing
microsecond values for multiple calls within the same second, regardless
of whether the callers are different processes.  Additionally, I believe
that the PC hardware clock only has a resolution of 55ms.  If Windows is
using this hardware clock to retrieve microsecond values for
constructing authenticators, it is quite possible for two authenticators
for distinct requests to have identical {client principal, servver
principal, time, microseconds} tuples.

In your packet trace, I see four distinct TGS-REQ messages.  Of
particular interest are the third and fourth TGS-REQ messages.  The
third, issued at 14:51:20.868353, asking for a
cifs/adcsm2.test.uncc.edu at UNCC.EDU ticket, receives a KRB-ERROR due to a
request for a non-existent service.  The fourth, issued at
14:51:20.877389, asking for a ticket for krbtgt/TEST.UNCC.EDU at UNCC.EDU,
receives a replay error.  Note that fewer than 55ms have elapsed between
these requests.

I cannot verify my hypothesis directly, since I do not have access to
the session key used to encrypt the authenticators in question.  I can
observe from the packet trace that they are not identical.  At the very
least, the checksums inside the authenticators would have to be
different, as they intend to authenticate requests asking for different
tickets.

I will attempt to correspond with some contacts at Microsoft to discover
whether my hypothesis regarding the Windows generation of microseconds
values for authenticators is likely to be correct.  Meanwhile, I will
investigate correcting this bug in the MIT implementation, though it
does seem potentially difficult because of assumptions made in the API
design.  Also, I have begun discussion in the IETF Kerberos working
group to discover if there are any security vulnerabilities that might
be introduced by making the replay detection procedure only compare the
encrypted authenticators.

---Tom