Network Working Group Kaduk
Internet-Draft MIT
Intended status: Informational March 12, 2014
Expires: September 13, 2014

krb5 based key derivation for rxkad
draft-kaduk-afs3-rxkad-k5-kdf-00

Abstract

This document describes two extensions to the rxkad security class for the RX RPC protocol, rxkad-k5 and rxkad-kdf. rxkad currently relies on the Kerberos Key Distribution Center to support single-DES encryption types, which are increasingly disabled by default in Kerberos implementations. This document provides a framework for rxkad to support long-term service keys with strong enctypes (rxkad-k5), and a key derivation procedure to allow Kerberos session keys with strong enctypes to be used with rxkad (rxkad-kdf).

Status of This Memo

This Internet-Draft is submitted in full conformance with the provisions of BCP 78 and BCP 79.

Internet-Drafts are working documents of the Internet Engineering Task Force (IETF). Note that other groups may also distribute working documents as Internet-Drafts. The list of current Internet-Drafts is at http://datatracker.ietf.org/drafts/current/.

Internet-Drafts are draft documents valid for a maximum of six months and may be updated, replaced, or obsoleted by other documents at any time. It is inappropriate to use Internet-Drafts as reference material or to cite them other than as "work in progress."

This Internet-Draft will expire on September 13, 2014.

Copyright Notice

Copyright (c) 2014 IETF Trust and the persons identified as the document authors. All rights reserved.

This document is subject to BCP 78 and the IETF Trust's Legal Provisions Relating to IETF Documents (http://trustee.ietf.org/license-info) in effect on the date of publication of this document. Please review these documents carefully, as they describe your rights and restrictions with respect to this document.


Table of Contents

1. Introduction

rxkad-k5 and rxkad-kdf are extensions to the rxkad Kerberos [RFC4120] based security class for the rx [RX] protocol. rxkad provides authentication, confidentiality and integrity protection for rx RPC calls but is limited to single-DES encryption types. The original incarnation of rxkad used version 4 of the Kerberos protocol, but limited support was later added for using version 5 of the Kerberos protocol, but only with single-DES enctypes, which remain deeply ingrained in the rxkad protocol.

Kerberos version 4 is obsolete and the use of single-DES enctypes is deprecated [RFC6649]. Accordingly, the administrators of Kerberos realms are eager to fully disable the use of single DES for Kerberos service and session tickets. However, rxkad's dependence on single DES is a major obstacle to such changes for many sites. Providing a way to use stronger encryption types for the Kerberos tickets used by rxkad will enable modernization of Kerberos Key Distribution Centers (KDCs).

rxkad-k5 allows the service long-term key to use a strong enctype, and requires changes only to AFS servers. rxkad-kdf allows the short-term Kerberos session key to use a strong RFC 3961 enctype [RFC3961], and requires changes to both clients and servers.

1.1. Requirements Language

The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this document are to be interpreted as described in RFC 2119 [RFC2119].

2. Indicating Protocol Support

rxkad does not provide a facility for negotiating support for an extended feature set. Within a given interaction, a new revision of the protocol for that interaction may be indicated by changing the size of a data structure, but this does not generalize well and is ill-suited for indicating a global protocol change.

Therefore, an out-of-band mechanism is used to indicate support for the rxkad-k5 and rxkad-kdf extensions. The KDC is entrusted to signal this information: the KDC has access to the list of supported encryption types for both the client and the service, as well as the encryption type(s) used for the service principal's long-term key(s). The presence of a non-DES long-term key for the service principal indicates service support for strong service keys (rxkad-k5), and the ability to use non-DES session keys for either client or service indicates that the client or service, respectively, is able to support key derivation (rxkad-kdf).

The use of key derivation to obtain a shared DES key between client and service is preferred to requesting a DES key directly from the KDC. This mechanism is chosen because Kerberos best practices indicate that weak cryptography (including single-DES) should not be enabled, both on the KDC and on user machines. AFS with rxkad does require DES keys, owing to the wire protocol format, but it is desired to contain the use of weak cryptography entirely within AFS, so that Kerberos deployments may comply with current best practices (which are increasingly being mandated by organizational compliance departments).

Per standard Kerberos operation, the administrator MUST NOT configure the AFS service principal with non-DES enctypes in the KDC database until the AFS server supports strong enctypes for the long-term service key. The KDC MUST NOT issue a non-DES session key for the AFS service principal in a service ticket unless the server supports session key derivation. The client MUST NOT include non-DES enctypes in its TGS-REQ for the AFS service ticket if the client does not support key derivation. This is a new requirement not present in the existing (implicit) rxkad specification, but all known implementations of the aklog and afslog utilities are in compliance with it (see Appendix A. Some klog.krb5 implementations are not in compliance, and will break when the rxkad-kdf extension is enabled for the AFS service.

It is common for KDC implementations to indicate service support for (session-key) enctypes by the enctypes available in the key list of the service principal, which in practice requires servers to implement support for rxkad-k5 and rxkad-kdf simultaneously.

3. Strong Service Keys

Modifying rxkad to add support for strong service keys (rxkad-k5) requires only minimal protocol change. The Kerberos service ticket is handled as an opaque blob by the client and passed to the server as an authentication token. This behavior is independent of the ticket enctype. As long as the service ticket fits in the buffer allocated by rxkad, client support for strong service keys is already present for clients using krb5 natively. Legacy deployments using krb4 or a krb524 service will not be able to use the rxkad-k5 extension.

The server operation for rxkad-k5 is also straightforward: the server receives the client's token and decrypts it using the service long-term key. The session key contained within the ticket is then used as in normal operation.

4. Key Derivation

When both client and server have indicated to the KDC their support for rxkad-kdf key derivation (that is, non-DES session key enctypes), the KDC will return a service ticket to the client containing a session key with a non-DES enctype. The rxkad security class requires a DES key for operation, so a key derivation function is employed to generate a DES key from the session key contained in the service ticket.

The key-derivation process follows the algorithm of NIST SP800-108 [NIST-SP-800-108] using HMAC-MD5 in counter mode as the pseudo-random function. However, this KDF procedure requires that the input key to the derivation function be a random or pseudo-random string of bits. This property does not hold for all RFC3961 enctypes, in particular, the single- and triple-DES families of enctypes have keys which include parity bits. Other enctypes, including enctypes 4, 6, 8, 9, 10, 11, 12, 13, 14, and 15, do not have a random key per se, and are completely unsuitable for use as session keys for rxkad-kdf.

4.1. DES enctypes

When the service ticket returned by the KDC contains a session key whose enctype is from the single-DES family (des-cbc-crc, des-cbc-md4, des-cbc-md5), the session key can be used as-is by rxkad and no key derivation is necessary.

4.2. Preparing a Random Seed

When the service ticket returned by the KDC contains a session key whose enctype is from the triple-DES family (des3-cbc-md5, des3-cbc-sha1, des3-cbc-sha1-kd), the session key is not a cryptographic key in the definition of NIST SP 800-108. In order to produce a random seed from the session key, it is necessary to reverse the RFC3961 random-to-key operation. For triple-DES enctypes, the random-to-key operation is just the addition of parity bits (expanding a 56-bit random keystring to a 64-bit DES key). Reversing the operation thus requires the removal of the parity bits. The random-to-key operation (and thus its inverse) are defined to interchange between 56-bit random strings and 64-bit DES keys; to convert a triple-DES key to a 168-bit random string the key-to-random operation must be performed individually on the three components, and then the resulting 56-bit random strings concatenated.

key-to-random:
      1  2  3  4  5  6  7 63
      9 10 11 12 13 14 15 62
     17 18 19 20 21 22 23 61
     25 26 27 28 29 30 31 60
     33 34 35 36 37 38 39 59
     41 42 43 44 45 46 47 58
     49 50 51 52 53 54 55 57
          

The output bit order of the 56 random bits extractable from a 64-bit DES key. The eight parity bits are discarded.

The (concatenated) output random bitstreams are used as input for the key derivation step.

4.3. Key Derivation Function

Once a random bitstring has been obtained for use as an input key (whether directly as the key of a suitable RFC 3961 enctype or as the output of a key-to-random operation), key derivation of a DES key can proceed.

The output of HMAC-MD5 is the output length of MD5, that is, 128 bits. Since a DES keys occupies only 64 bits, standard application of NIST SP800-108 would use a value of 1 for the n (number of iterations) parameter, as only one application of the PRF would be necessary to produce the output key. However, single-DES has the complication that a certain handful of keys are weak and should not be used. Therefore, we use a larger value of n (255) and discard PRF outputs which produce weak DES keys, until a non-weak key is produced.

In normal operation, the KDF output in counter mode is the concatenation of the output of the PRF with incremented counter values. rxkad-kdf does not strictly speaking use the concatenation of the output with incremented counter values, but still provides for computation of the PRF output with incremented counter values. The input to each PRF application is a random seed to key the hash (the same key for each iteration), and an input string to the PRF. This input string is defined as the concatenation of the counter variable, an application-specific "label" (with NUL byte terminator), a "context" specific to this particular key derivation, and the length of output key material needed. In the October 2009 revision of NIST SP 800-108, it is permitted to omit one or more of these fields from PRF input string if that field is not needed. For rxkad-kdf usage, the "context" field is omitted, as the input key comes from the session key of a Kerberos service ticket for an AFS service principal, and no other key derivations are expected to be performed using this session key. The label for this KDF is the constant string "rxkad". The KDF specification is then:

K(i) = PRF(Ks, [i]_2 || Label || 0x00 || [L]_2)
          

|| is the concatenation operation.
Ks is the random key used to seed the hash (that is, the output of the key-to-random operation for triple-DES keys, and the key itself for other enctypes).
[i]_2 is the value of the counter variable encoded as a binary string of 8 bits.
Label is the literal string "rxkad".
0x00 is a NUL byte (eight zero bits).
[L]_2 is the integer value 64, encoded as a binary string of 32-bits (in network byte order).

The key derivation procedure for rxkad-kdf is to first compute K(1) and take the first 64 bits of output. This 64-bit value is then converted to a DES key by replacing the eighth bit of each octet with the parity of the other seven bits in the octet. If this DES key is not a weak key, the key derivation is finished. If it is a weak key, then the algorithm proceeds iteratively, repeating the extraction-and-parity-fixup procedure with K(2), K(3), ..., K(255), until a non-weak key is produced. If all 255 possible K(i) produce weak keys, then key derivation fails and the rxkad-kdf extension is unusable with that Kerberos service ticket.

5. AFS-3 Registry Considerations

This document makes no request of the AFS-3 Registrar.

6. IANA Considerations

This document includes no request to IANA.

7. Security Considerations

7.1. DES weakness

The rxkad-kdf procedure defined in this document allows AFS to operate in a Kerberos realm with single-DES enctypes disabled on the KDC. However, single-DES (or rather, its weakened variant fcrypt, which uses DES keys) is still used to protect all encrypted or checksummed rxkad traffic. Therefore, that traffic is only protected by weak cryptography. The main security gain from the extensions specified in this document comes from rxkad-k5, in particular the provisioning of strong enctypes for the long-term AFS service key, as the compromise of that key is tantamount to complete compromise of the cell. Although administrative access to the cell still uses single-DES for encryption of network traffic, that single-DES key is time limited and may be resistant to brute-force key recovery prior to its expiration.

7.2. MD5 weakness

MD5 is a rather old hash function and is weak with respect to collision resistance [RFC6151]. Since this document uses the output of MD5 as a secret key, this weakness does not affect the security of the algorithm. Per RFC 6151, HMAC-MD5 is still acceptable, though the scope of some attacks are not well understood. Given that single-DES is known to be critically weak and the output of HMAC-MD5 is used to produce a single-DES key in this document, it appears that the strength of single-DES remains the limiting factor in the security of the rxkad-kdf system.

7.3. Enctype portability

The rxkad-kdf procedure requires an RFC 3961 enctype that has a random key. Some enctypes do not have this property and are unsuitable for use with rxkad-kdf; it is possible that in the future, new enctypes will be created that will share this property. Implementors should be aware of this possibility. In order to obtain a random bitstring from an RFC 3961 enctype's random key, it is necessary to invert the random-to-key operation of enctypes for which this operation is not the identity function. At present, the only enctypes with a non-trivial random-to-key operation are the single-DES and triple-DES families. It is not expected that future enctypes will be created with non-trivial random-to-key functions, but implementors should be aware of this possibility.

8. References

8.1. Informational References

[RX] Zeldovich, N., "RX protocol specification", October 2002.

8.2. Normative References

[RFC2119] Bradner, S., "Key words for use in RFCs to Indicate Requirement Levels", BCP 14, RFC 2119, March 1997.
[RFC3961] Raeburn, K., "Encryption and Checksum Specifications for Kerberos 5", RFC 3961, February 2005.
[RFC4120] Neuman, C., Yu, T., Hartman, S. and K. Raeburn, "The Kerberos Network Authentication Service (V5)", RFC 4120, July 2005.
[RFC6151] Turner, S. and L. Chen, "Updated Security Considerations for the MD5 Message-Digest and the HMAC-MD5 Algorithms", RFC 6151, March 2011.
[RFC6649] Hornquist Astrand, L. and T. Yu, "Deprecate DES, RC4-HMAC-EXP, and Other Weak Cryptographic Algorithms in Kerberos", BCP 179, RFC 6649, July 2012.
[NIST-SP-800-108] National Institute of Standards and Technology, , "Recommendation for Key Derivation Using Pseudorandom Functions, NIST SP800-108", SP 800-108, October 2009.

Appendix A. Historical Version Compatibility

Converting a user's Kerberos credentials into an AFS token is traditionally performed using a klog or aklog utility, with klog corresponding roughly to krb4 and aklog to krb5. Known implementations of aklog explicitly request a single-DES encryption type for the session key, with the following caveats.

Many deployments of IBM AFS (which used its own kaserver as a Kerberos 4 KDC) were converted to use krb5 for authentication via an unofficial "AFS-krb5 migration kit", distributed informally from site to site. It is difficult to obtain all versions of this migration kit which were distributed, but the aklog utility included in versions 1.2, 1.3, and 2.0 of the migration kit explicitly request a single-DES encryption type for the session key. Specific information about other versions is not readily available, but it seems likely that this behavior was introduced at an early stage.

OpenAFS imported an aklog utility from the migration kit into its tree on 19 November 2004, with the code to explicitly request ETYPE_DES_CBC_CRC commented out. That code was uncommented on 19 June 2005. No releases were made on a stable release branch during this period, though the development releases 1.3.75 through 1.3.84 did contain this buggy code. The next release after 1.3.84 was 1.4.0; the 1.4.0 release contains an aklog utility that correctly requests a single-DES session key.

The Arla AFS client appears to depend on the Heimdal Kerberos distribution for obtaining AFS credentials. The core Heimdal routine supplying AFS authentication from krb5 credentials, get_cred() in the source file afskrb5.c, has explicitly requested a DES session key since 19 October 1999; the first Heimdal release containing this code was Heimdal 0.2b. Heimdal's AFS through krb5 support was introduced on 15 August 1997, and first appeared in release 0.0e. At that time, single-DES was the primary enctype available, and support for triple-DES was still under development.

The "kAFS" incomplete AFS client included with the linux kernel does not include a utility to obtain credentials -- a primitive utility is separately available. This utility only supports krb4 authentication.

OpenAFS supplies a klog.krb5 utility with the semantics of the traditional (krb4) klog utility that uses krb5 for authentication. This utility was first imported into the source tree on 27 October 2006, but was not installed as part of the distribution until 28 June 2008. The first release version containing klog.krb5 was OpenAFS 1.4.8; it was also present as of the 1.6.0 release. Code to explicitly request ENCTYPE_DES_CBC_CRC was added on 14 October 2011, and was first present in the 1.6.1 release. This code was never added to the 1.4.x branch, so klog.krb5 is incompatible with the rxkad-kdf extension on all 1.4.x releases which contain a klog.krb5 utility.

Arla does not appear to provide a utility with klog semantics that uses krb5 for authentication.

No other AFS implementations are known to the author.

Appendix B. Test Vectors

Some test vectors for the key-to-random operation and KDF application are presented.

in :=   0 1 1 1 0 1 0 1  75
        1 0 1 0 1 0 1 1  ab
        0 1 0 1 0 0 0 1  51
        0 0 1 1 0 1 1 1  37
        1 1 1 0 0 1 0 1  e5
        0 0 1 0 0 1 0 1  25
        1 1 1 1 0 0 1 0  f2
        1 1 1 0 0 0 0 0  e0
key-to-random(in) :=
        0 1 1 1 0 1 0 0  74
        1 0 1 0 1 0 1 0  aa
        0 1 0 1 0 0 0 0  50
        0 0 1 1 0 1 1 0  36
        1 1 1 0 0 1 0 1  e5
        0 0 1 0 0 1 0 1  25
        1 1 1 1 0 0 1 1  f3
        

The key-to-random operation on a single DES keyblock. The hex representation of each byte is presented for convenience.

in :=   1 0 1 1 0 1 1 0   b6
        0 1 0 0 0 0 0 0   40 
        0 1 1 1 0 0 0 0   70
        0 0 0 0 0 1 0 0   04
        0 1 1 1 0 0 0 0   70
        1 0 0 0 0 1 1 0   86
        0 0 0 0 1 0 0 0   08
        1 0 1 0 1 1 1 0   ae
        1 0 1 1 0 1 1 0   b6
        1 0 1 1 1 1 1 1   bf
        1 1 0 0 0 1 1 1   c7
        1 1 0 1 0 0 0 0   d0
        1 1 1 0 0 1 0 1   e5
        1 1 1 1 1 1 0 1   fd
        0 0 1 0 0 0 1 1   23
        1 1 1 0 0 1 1 0   e6
        0 1 1 1 1 0 1 0   7a
        0 1 1 0 0 1 1 1   67
        0 0 0 1 1 1 1 1   1f
        1 0 1 1 0 1 0 1   b5
        0 1 0 0 1 0 0 1   49
        1 0 0 1 0 0 0 1   91
        1 0 0 1 1 0 1 1   9b
        1 1 1 1 1 1 0 1   fd
key-to-random(in) :=
        1 0 1 1 1 1 1 1   b7
        0 1 0 0 0 0 0 1   41
        0 1 1 1 0 0 0 1   71
        0 0 0 0 0 1 0 0   04
        0 1 1 1 0 0 0 1   71
        1 0 0 0 0 1 1 0   86
        0 0 0 0 1 0 0 1   09
        1 0 1 1 0 1 1 1   b7
        1 0 1 1 1 1 1 1   bf
        1 1 0 0 0 1 1 0   c6
        1 1 0 1 0 0 0 0   d0
        1 1 1 0 0 1 0 1   e5
        1 1 1 1 1 1 0 1   fd
        0 0 1 0 0 0 1 1   23
        0 1 1 1 1 0 1 0   7a
        0 1 1 0 0 1 1 1   67
        0 0 0 1 1 1 1 1   1f
        1 0 1 1 0 1 0 1   b5
        0 1 0 0 1 0 0 1   49
        1 0 0 1 0 0 0 1   91
        1 0 0 1 1 0 1 1   9b
        

The key-to-random operation performed on a triple-DES keyblock. Though equivalent resistance to brute-force attacks is provided by having the first and third keyblock be identical, the Heimdal Kerberos implementation produces three independent random DES keys for a triple-DES key. The hex representation of each byte is presented for convenience.

Random input seed:
        11010100  d4
        10101100  ac
        01000011  43
        10000110  86
        11001000  c8
        11011101  dd
        10101110  ae
        10100011  a3
        01010001  51
        10110101  b5
        00110101  35
        11111110  fe
        01111000  78
        11110010  f2
        10110011  c3
        00111000  38

Derived DES key:
        00011010  1a
        11001110  ce
        00010101  15
        00111011  3b
        10110011  b3
        10111001  b9
        10010001  91
        00001110  0e
        

A key-derivation function test vector, using a 128-bit random string as input. The hex representation of each byte is presented for convenience.

Appendix C. Acknowledgments

rxkad-k5 and rxkad-kdf are the brainchild of Chaskiel Grundman and Alexander Chernyakhovsky; this document is a description of the protocol that they have implemented.

Author's Address

Benjamin Kaduk MIT Kerberos Consortium EMail: kaduk@mit.edu