Projects/Larger key versions

This is an early stage project for MIT Kerberos. It is being fleshed out by its proponents. Feel free to help flesh out the details of this project. After the project is ready, it will be presented for review and approval.

This project is targeted at 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 pivot logic to work around 8-bit kvno limitations when retrieving keytab entries. The pivot logic is:

• When searching for the highest kvno, if any kvno values greater than 240 are seen, compare key versions using (kvno + 128) % 256 so that values 0-127 compare greater than values 128-255.
• When searching for a specific kvno, consider the entry kvno equal to the desired kvno if the least significant 8 bits of the version match.

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 pruned, the pivot logic may not function correctly and ktrem could select an incorrect key version to preserve.

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 is the most difficult facet of the problem. 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 order of keytab entries rather than (or in addition to) the key versions themselves. That is, if we see a small key version following a large key version, we could treat the small key version as highest, perhaps with some conditions such as if the large key version being near an 8-bit or 16-bit boundary.