[krbdev.mit.edu #9004] Fix quadratic performance for initiating to many services with same ccache

[Greg Hudson via RT]

Sun Apr 18 22:22:32 2021: Request 9004 was acted upon.
 Transaction: Ticket created by ghudson at mit.edu
       Queue: krb5
     Subject: Fix quadratic performance for initiating to many services with
 same ccache
       Owner: Nobody
  Requestors: ghudson at mit.edu
      Status: open
 Ticket <URL: https://krbdev.mit.edu/rt/Ticket/Display.html?id=9004 >


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