Ticket 5338: Race conditions in key rotation

[Jeffrey Hutzelman]

On Wed, 25 Jun 2008, Jeffrey Altman wrote:

> The worst part about this situation is that the client really has no
> idea why the ticket wasn't issued.  The client is not getting an error
> that explains the reason at all.  It is getting a KRB5_GENERIC error.

Yes, I agree that's a problem.

> > The issue here is that you are proposing that the answer to a set of KDC's
> > not presenting a consistent view of the realm is not to fix the KDC's, but
> > to require clients to query multiple KDC's and compare their responses,
> > which is not what the protocol specification says.
>
> The protocol specification doesn't say anything about the subject of
> master/slave, primary/secondary, or multi-master distributed KDC
> implementations.   It doesn't say that clients MUST, SHOULD, SHOULD NOT,
> or MUST NOT contact the Master/Primary KDC after a client request fails.

No, it doesn't.  The key point here is that the spec does not say that
clients respond to an error by trying another KDC, so a correct KDC
implementation should not depend on that behavior.  IMHO, a correct KDC
implementation provides a consistent view of the KDB and does not produce
spurious errors as a result of a change having been made on one server's
copy of the KDB and not another.

Note that I don't actually object to a client implementation trying other
KDC's.  I think it's a bit of a waste, because in 14 years of being a KDC
operator using multiple implementations, I cannot ever recall a situation
in which we've had a failure because a slave was "broken" and the master
was not.  We did once have occasional complaints about password changes
not propagating quickly enough; we resolved that problem by using
Heimdal's incremental propagation, but I can think of other ways to solve
the same issue with other KDC's.  Note that this is not perfect, and could
be done better, but it's never been a problem for us.

Still, as you and another poster point out, there is nothing prohibits
clients from trying another KDC.  There simply is also nothing that
requires them to do so, and so what I object to is changing client
behavior instead of improving the KDC.

> In fact, in section 3.1.6 discussion what a client should do in response
> to a KRB_ERROR message, it states that the client interprets it as an
> error and performs "whatever application-specific tasks are necessary
> for recovery."   Perhaps you are interpreting to mean that the krb5
> library must pass the error to the calling application and it is the
> application's responsibility to decide whether or not to retry.

Actually, my interpretation is that the KRB_ERROR means the Kerberos
operation has failed and the library should pass the error to the calling
application which then decides what to do next, such as trying another
method, or using different credentials, or giving up.  I personally don't
see "the Kerberos library always retries with another KDC" as an
applicaiton-specific task necessary for recovery.

However, I don't interpret that section as prohibiting the proposed
behavior; I just don't think it is relevant.



> The KDC deployment architecture selected by an implementation is an
> implementation specific detail that is independent of the protocol
> specification.

Correct.

> Inconsistencies in the deployment of the implementation
> specific database are addressed in an implementation specific manner.

Yes.  In the implementation of the database/KDC/etc, not in the clients,
which are not specific to the implementation-specific database.



> The MIT clients already do contact the Master/Primary KDC if one is
> defined for the realm when the client's AS request fails for any reason.
>   This is done explicitly because of the fact that Slave/Secondary KDCs
> might not have an up to date view of the world.

And that's fine, but it's not an excuse for not improving the KDC.


> Nico has commented to say that fail over for AS requests are ok and TGS
> requests are not because the volume of AS requests is lower than that
> for TGS requests.

I don't really buy the performance arguments for not doing this.  Unless
you are doing something bizarre, the number of failures due to legitimate
clients is small compared to the number of successful requests, and a
non-legitimate client (attacker) is going to do whatever benefits him
most, no mater what we decide.

> The problem here is that no matter what you say a KDC based solution
> should be, there is no transactional mechanism that you can put in place
> on an error prone network that will result in all copies of the database
> being consistent all of the time.

No, but it is possible to design a mechanism in which only servers with a
correct database provide service.  The original Ubik design does this;
only servers which are a member of a quorum may provide _any_ service.
Modern AFS relaxes this requirement and allows servers to provide
read-only service when not a member of a quorum, because the databases
were judged to change slowly enough and in ways that made it better to
servce out-of-date data than none at all.

It is also possible to use a different metric, such as requiring a quorum
of >75% of servers to change the database, and requiring presence of at
least 25% of servers to provide service.  This allows service without a
quorum of servers, and even in multiple zones of a partitioned network,
while insuring that no server provides service with out-of-date data.

It is also possible to achieve this goal by using an LDAP or RDBMS
backend, in which case all KDC's provide the same answers because they are
all using the same database (this punts the replication problem to the
LDAP or RDBMS subsystem, but both of those have examples of servers which
solve this problem).


Incidentally, I can easily imagine a scenario in which the proposed change
makes things worse, rather than better.  Over the next few months, we are
planning on transitioning to a model in which the advertised KDC addresses
are anycast addresses, with the routes managed by an automatic process
which insures they are always handled by KDC's which are functional.  This
will enable us to more evenly balance load, and also means that once a KDC
has failed (or if we want to remove it from service for maintenance), it
can be removed from the pool and client requests will always go to a KDC
that is up.

Now, this will still be a fixed-master system, so the kadmin service will
have to be advertised with the master's real name and address.  If the
master goes down, then kadmin, password-changing, and other services that
require modifying the database will be unavailable.  However, most clients
will not notice because their requests will be routed to another KDC.

Until you introduce this change, which causes clients to try the
advertised master for every KRB5KDC_ERR_S_PRINCIPAL_UNKNOWN they get
during aklog.  Now, instead of logins happening as quickly as if there
were no server down, they happen as slowly as if we didn't have the
anycast pool to begin with.

-- Jeff