Skip Menu |
 

From: ghudson@mit.edu
To: rt@krbdev.mit.edu
Subject: Fix quadratic performance for initiating to many services with same ccache
Date: Sun, 18 Apr 2021 22:22:32 -0400
Initiating krb5 security contexts to N services using the same ccache currently costs O(N^2) time.  Operators can work around this problem by using different ccaches for each service, but they shouldn't have to.  We could provide a simpler workaround in the form of an environment variable to disable caching of service tickets, but that would still qualify as something operators shouldn't have to do.

This problem arises from two causes: krb5_cc_retrieve_cred() is O(N) with most ccaches, and there are explicit iteration operations in the GSS krb5 mech.

The ccache problem is solved for the KCM cache type by ticket 8997 if the KCM daemon implements OP_RETRIEVE.  For other existing types it may not be tractable.  Nico has a design for the FILE type involving a large config entry containing a hash-indexed table of cred slots for ephemeral creds; this would result in an unfortunate choice between creating large ccaches by default or requiring an operator choice to gain the performance benefits.  KEYRING probably cannot achieve O(1) performance because, although the keys are added with the server principal name as a description, there appears to be no efficient way to retrieve a key from a specific keyring by its description string.

On the GSS side of the problem, ticket 8998 eliminated one iteration by adjusting the semantics of krb5_cccol_have_content().  The harder problem is scan_ccache().  This function iterates once over all credentials in the cache to determine four pieces of information:

1. The expiration time of the ccache, as defined by the expiration time of the local TGT of the client principal realm if present or the first real credential if not.  (This code does not take into account start_realm.)

2. Whether a local TGT is present, for use by IAKERB.

3. The ccache config value of "proxy_impersonator" if present, to make stored S4U2Proxy creds work.

4. The ccache config value of "refresh_time" if present, to know when to next attempt a refresh a cache populated from a client keytab.

These could in theory be replaced with krb5_cc_get_config() and krb5_cc_retrieve() calls, falling back to a truncated iteration when no local ccache is present.  The downside is that when iteration is not efficient, this decomposition would increase the constant by a factor of 4.

More creative solutions might involve adding new ccache methods, or caching config values during iteration to avoid additioal iterations.  (Of the ccache config values defined so far, only refresh_time ever changes, and caching its value within a ccache handle isn't harmful.)