Projects/Larger key versions

This project was completed in release 1.14.

Background

In some deployments it is desirable to periodically rotate keys using an automated process. Current implementation limits can cause surprising behavior when key versions exceed 255 or 31767. This project will relax some of the implementation limits to produce more predictable behavior in common scenarios.

The current implementation limits on key versions are:

8-bit limitations:

• The FILE keytab format stores the key version as an unsigned 8-bit field.
• The kadmin protocol marshals the kvno and mkvno fields of kadm5_principal_ent_rec as an unsigned 8-bit field. The kvno field is used by kadmin ktadd as the version of the newly added key, because there is no key version in the chrand reply.
• The KADM_DATA tl-data value uses 8 bits to marshal the history key version.

16-bit limitations:

• The krb5_key_data structure in kdb.h represents the key version as a signed 16-bit field.
• The db2 KDB module marshals the key version as a signed 16-bit field.
• The LDAP KDB module marshals the key version as an ASN.1 INTEGER, internally restricting the value to signed 16-bit values. The documented ASN.1 schema for key data uses the type "UInt16" without formally defining it.
• The kadmin protocol marshals the key version of key_data structures as a signed 16-bit field.

32-bit limitations:

• The krb5_kvno type is unsigned int, which is usually 32 bits.
• The iprop protocol represents the version of key data as a signed 32-bit field.
• krb5_dbe_def_search_enctype(), used to retrieve keys from DB entries, accepts a signed 32-bit kvno parameter, with special meanings for negative and 0 values.

The FILE keytab code contains some workarounds for 8-bit key version limitations in krb5_ktfile_get_entry() which retrieves keytab entries. The workarounds are:

• Pivot: when searching for the highest key version, if any versions greater than 240 are seen, begin applying (kvno + 128) % 256 to each version before comparing them, so that values 0-127 compare greater than values 128-255.
• Fuzzy match: when searching for a specific key version, match against only the low 8 bits of the desired version.

The current best practice for key rotation with kadmin is to use ktadd princname to retrieve new random keys, and then ktrem princname old to remove old entries after the maximum ticket length has elapsed. As long as only a few versions of the key are present in the keytab at a time, and ktrem will correctly pick the most recent key version to preserve even after a wraparound from 255 to 0. If old versions are not regularly pruned, the pivot logic may not function correctly and ktrem could select an incorrect key version to preserve. The pivot logic can have different outcomes based on entry order; for example, if a keytab contains key versions 80, 160, and 242 in that order, version 242 will be selected, whereas if the entries are ordered 160 242 80, version 80 will be selected. Entry order in keytab files is unpredictable because new entries can replace deleted entries.

When the key version reaches 32767, a subsequent ktadd operation will report kvno 0 to the client and store kvno 0 in the FILE keytab, as one would expect from an 8-bit wraparound. However, the key data in the database stores the new key version as -32768. Because of the special meaning for negative kvno values in krb5_dbe_def_search_enctype(), the server principal will not work (TGS requests will receive "KDC has no support for encryption type"). The next ktadd operation will use kvno value 1 and service resumes.

Possible improvements

The kadmin 8-bit key version limitations can be relaxed in an interoperable fashion simply by using xdr_u_int() instead of xdr_u_char() in the implementation of xdr_krb5_kvno(). XDR uses four bytes to marshal an 8-bit value and does no bounds-checking when decoding 8-bit values; a peer running an old version will simply truncate the result to the lower eight bits. The kadmin 16-bit kvno limitations could also be relaxed, because xdr_krb5_int16() uses xdr_int() and truncates the result without bounds-checking.

The FILE keytab limitation can be removed by implementing an extension implemented in Heimdal and Shishi. In this extension, a 32-bit kvno is marshalled at the end of a keytab entry. When a key entry is read, if there are at least four bytes left in the record and they are not all zero, the value of those bytes override the 8-bit kvno value from the key entry.

The DB2 16-bit kvno limitation cannot be easily relaxed while retaining binary database compatibility, because the field is fixed-width and buried inside an array of key_data representations which have no versioning or framing. It would be relatively easy to expand the range to 65535, since negative kvno values are not meaningful in key_data entries.

The LDAP 16-bit kvno limitation could be relaxed by changing the in-memory representations of LDAP key sequences. We would be ignoring (or changing) the documented ASN.1 type of the field, but the implementation already does not match that type.

The in-memory 16-bit kvno limitation for key_data structures can be relaxed by bumping the KDB ABI number.

The pivot logic in the FILE keytab presents a number of design considerations. Although it is apparently designed only to work around the 8-bit kvno limitation of the file format, it also works around the 8-bit kvno limitation of the kadmin protocol. Most of the options have some negative edge cases after 8-bit kvno limitations are relaxed:

• Eliminating the pivot logic entirely would result in incorrect key rotation behavior when a new server interacts with an old kadmind which still transmits 8-bit kvnos during ktadd operations. After key version 255, the old kadmind would tell the server that the next key version is 0, and ktrem would preserve key version 255 instead of the most recent key.

• Leaving the pivot logic alone would result in incorrect key rotation behavior after key version 383; ktadd ktrem would preserve key version 383 in preference to key version 384, because (383 + 128) % 256 is greater than (384 + 128) % 256.

• We could disable the pivot logic upon seeing key versions greater than 255. Key rotation would work properly up until the key version needs to wrap due a 16-bit limitation on the KDC. At this point ktrem would preserve key version 32767 (or 65535) instead of the new key version 0 (or perhaps 1). Also, some of the exotic edge cases of the pivot logic would remain even in an environment with no 8-bit kvno limitations to justify them.

• We could disable the pivot logic upon seeing key versions greater than 255 but add new pivot logic around 16-bit boundaries. This would be working around KDC limitations in the FILE keytab code, which is inelegant, and would also be complicated.

• We could replace the old pivot logic with new logic based on the timestamps of keytab entries rather than (or in addition to) the key versions themselves.

There are also some considerations for the fuzzy match logic. Since we know that the entry might have been written with a truncated key version, either due to a pre-1.14 kadmind or because the keytab was written by a pre-1.14 library, we should continue to allow fuzzy matches. However, we can continue reading to see if there is an exact match in a later entry.

Chosen improvements

• Change the key_data_kvno field from signed 16-bit to unsigned 16-bit. When adding new keys, wrap from 65535 to 1 to avoid using the special value 0.
• In the kadmin protocol, marshal the kvno and mkvno fields as unsigned 32-bit values instead of unsigned 8-bit values.
• Implement the 32-bit kvno extension for the FILE keytab format.
• Change the pivot workaround to consider any small version (less than 128) to be more recent than any large version (more than 240) if the timestamp of the smaller-versioned entry is the same or greater than the larger-versioned entry. This pivot logic is still order-dependent, but should work for kvno wraparounds at any boundary as long as only a small number of older keys are present.
• Change the fuzzy match workaround to remember the first match against the low 8 bits of the desired version, but to keep searching for an exact match.

Tests

t_keytab.py contains some existing tests for key rotation around kvno 255. These will be expanded to verify that key versions do not wrap at 255 or 32767 and do wrap from 65535 to 1. The tests will verify that ktrem preserves the more recent key after each rotation including after a wraparound.

Tests will be added to verify edge cases of the FILE format 32-bit kvno extension, using hand-crafted entries.

Documentation

We do not currently document key version limitations, and this project makes it less necessary to do so.

References

[krbdev.mit.edu #7532]

Release notes

XXX TBD