Key Derivation Functions with Assignment
draft-stjohns-kdf-with-assignment-00

Abstract

This document describes a key derivation function (KDF) wrap-around or a meta-KDF that's designed to mix in key assignment parameters to the key stream generation phase. This allows a security module to rely upon and enforce the key assignment parameters during the assigment of key material from the generated key stream to the cryptographic objects.

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 January 22, 2016.

Copyright Notice

Copyright (c) 2015 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. Code Components extracted from this document must include Simplified BSD License text as described in Section 4.e of the Trust Legal Provisions and are provided without warranty as described in the Simplified BSD License.

Table of Contents

• 1. Introduction
• 1.1. Discussion of Document Structure
• 2. Existing Key Derivation Functions
• 3. Key Derivation with Assignment
• 3.1. KDFA Processing Steps
• 3.1.1. KDFA Instantiation
• 3.1.2. Extraction
• 3.1.3. Expansion
• 3.1.4. Assignment
• 3.2. ObjectTemplate Considerations
• 4. Security Considerations
• 4.1. General
• 4.2. Security of Public/Private Data Production
• 5. IANA Considerations
• 6. Normative References
• Appendix A. KDFA with Integer Parameters
• A.1. Object Template Definition and Encoding
• A.2. Parameter Assignments
• Appendix B. An Example KDFA Instantiation Statement
• Author's Address

1. Introduction

This document came about as a result of some analysis by the author of the existing PKCS11 TLS key derivation functions (KDFs). It became apparent that not only were the existing PKCS11 TLS KDF functions severely flawed in that it was possible to extract sensitive key material, but that the actual definition of the TLS key derivation model made it impossible to implement a secure (with regard to key extraction) version of those PKCS11 functions with all current models of KDFs.

Existing KDFs (see for example [SP800-108], [SP800-56C], [RFC5869] and [X9.63]), do an excellent job of producing pseudo-random key streams from a master key and some user supplied mix-in data. Where they fall down is in the assignment of the key stream to cryptographic objects (e.g. keys or public random data such as IVs).

The issue with the above is that the production targets of the KDF call - the specific objects to be produced rather than just the length of the key stream - are not involved in the production of the key stream. That means the keystream does not change with a change in production targets.

In other words, it is possible to run the KDF multiple times with different production targets, the same supplied parameters, and the same master key with the result that different cryptographic objects are constructed from an identical key stream. This is obviously a problem if part of the key stream is assigned in one case to a public object such as an IV, and in another case the same part of the key stream is assigned to an AES key. Note that this is the case for all KDFs used with TLS1.2 ([RFC5246]) and previous versions.

It's also possible to run the KDF multiple times, get the same exact key, but use the key with different modes in ways that can compromise security. In the case of authenticating cryptographic modes such as CCM and GCM vs non-authenticating modes such as Counter, the rules for the authenticating modes require that the plaintext not be released until the message is authenticated. However, it's trivial to use the same key in Counter mode and discard the authentication tag and glean the exact same plain text without every verifying the authentication.

Other issues exist with the use of the same symmetric key both with CMAC and with a key derivation function based on CMAC. The output of CMAC, when not used with a KDF, is a public - an integrity tag. But the direct CMAC mode could be used to replicate the result of using the key with a KDF based on CMAC.

In general, cryptographic guidance is to not use the same key for different purposes. In practice, when such a key is derived from a master secret, or via a key agreement scheme, it's difficult to enforce this guidance. This document describes a scheme which allows for the enforcement of that guidance by the simple expedient of ensuring the key stream changes with any change of mode, key length or key type.

This document uses the term "cryptographic object" to refer to both key material and to other items that various protocols might want to produce from a keyed function. The other various items include at least generic random data and random data that's to be used as an Initialization Vector (IV) or Nonce.

1.1. Discussion of Document Structure

The document is broken up into two different normative parts. The first part is the body of the document which describes the general format for a KDF with assignment, but does not define the on-the-wire, crypto API input values. The second part is Appendix A which defines a concrete set of input values.

This was done somewhat in the same vein as the NIST definition of CBC-MAC Counter Mode (CCM) ([SP800-38C]) where the main body of the document describes the general form of how to use CCM, and where Appendix A of that document defines one specific Nonce formation primitive.

2. Existing Key Derivation Functions

Existing KDFs refer to one or two steps or stages in key derivation: Extraction (which may or may not be present) and expansion. The former is use to extract and concentrate entropy from a master key (and sometime also to provide a length match between the master key and the function used for expansion) and the latter is used to provide a key stream of arbitrary length.

In some KDFs, the extraction phase is subsumed in the key length matching function of the KDF's underlying pseudo-random function. E.g., the description of HMAC provides a means to adapt a key of any length for use with the HMAC function and that adaptation function is computationally similar to that described for discrete expansion functions.

There is a third step - assignment - which is implied, but the process of doing the actual assignment is left as an exercise to the user or protocol designer. This is problematic, as the protocol designer may not realize the implications of this step to the security of keys within a security module. In addition, a security module implementer may have to implement many different assignment functions to satisfy each of the protocol needs.

Existing KDFs have a general model. Specifics will differ, but the calling sequence is similar to:

• Step 1: Extraction (optional or missing for some KDFs)
  • master_secret = KDF-Extract(master_secret,[seed]);
  • Where:

    master_secret

    is the master key or shared secret input to the KDF

    seed

    is an optional, not necessarily secret, value used to provide additional entropy to the extraction phase

• Step 2: Expansion
  • key_stream = KDF-Expand (master_secret, info, L);
  • Where:

    key stream

    is the raw octet stream produced by the expansion function.

    KDF-Expand

    is the expansion function, usually driven by one of a CMAC, HMAC or HASH function

    master_secret

    is the key for the KDF, either the original master secret, or the extracted master secret from step 1.

    info

    is the information supplied by the caller of the KDF mix-in data. For TLS1.2 and before this is the concatenation of the "label" and "context", for HKDF this is the "info". The actual formation varies according to the specific construct and the needs of the KDF caller or protocol using the KDF.

    L

    is the length of the key stream to be produced - usually in bits. Depending on the KDF, the L term may or may not be part of the data the KDF mixes in as mandatory dependent data in key derivation, and may only tell where to truncate the output stream.

Note that alternate calling sequences for the above are possible, notably:

• key_stream = KDF (master_secret, label, context, L);

But that most KDFs concatenate label and context before input to the underlying pseudo-random function.

This document proposes to wrap the two steps described above into a key derivation construct that adds a mandatory third step: key assignment.

3. Key Derivation with Assignment

The general form for a KDF with assignment (KDFA) call is:

• ObjectHandle[] = KDFA (master_secret, label, user_context, object_count, ObjectTemplate[]);
• ObjectTemplate = { ObjectType, ObjectLength, ObjectMode, ObjectFlags }

Where:

ObjectHandle[]

is an array of handles pointing to the created objects. Object handles are public data, but may reference either public (e.g., IVs), or secret (e.g., AES key, EC private key) data.

master_secret

is the input master secret or the handle thereof

label

is a string of octets which describe the general purpose of the call

user_context

is a set of data (a string of octets) which is particular to this call of the KDFA.

object_count

is the number of objects to assign from the key stream

ObjectType

is an enum listing the various types of objects that can be created. See below, but this includes at least AES keys, HMAC keys, IV/Nonce (public), and generic public random data.

ObjectLength

is the length in bytes of the key stream data needed to produce the object (not necessarily the same as the key length of the produced object, but usually. See the discussion below in Appendix A of how to produce derivable EC Private Keys for example.)

ObjectMode

depends on object type, but is an enum which constrains the created object into a specific use. E.g. AES keys can be use to encrypt/decrypt, encrypt/decrypt in AEAD modes, CMAC and be a master secret for use with a KDF. The mode specifies which of these are correct.

ObjectFlags

permits the specification of how a security module might handle the object. E.g. some produced objects might as a general rule be exportable.

3.1. KDFA Processing Steps

Inputs:

KSG

The key stream generator, which is an underlying KDF of specific type and characteristics - see step 0.

seed_value

an optional (depending on protocol, KSG or use) value used with the KDF-Extract phase.

master_secret

a secret key appropriate for the KDF type selected in step 0.

ObjectTemplate[]

a set of templates for objects to be produced. At least 1 and as many as are required to the limits of the permitted length of the underlying KDF.

user_context

the data provided by the caller. Generally a concatenation of the user "label" and "context" of some form. This is opaque to the KDF and not interpreted by the security module.

3.1.1. KDFA Instantiation

Step 0: Select and instantiate an underlying KDF as the key stream generator (KSG).

• Most KDFs are actually described as a family of KDFs and require specification of one or more characteristics to form a specific KDF.
• For example, HKDF [RFC5869] requires the selection of an underlying hash function such as SHA-256; [SP800-56C] requires the selection of a KDF function from [SP800-108] and that KDF requires, in turn, the selection of the specific mode (iterative or feedback), specific pseudo-random function (PRF) (e.g. HMAC-SHA256 or AES-CMAC or others), ordering of fields, and the length of the L and i values when expressed for input to the PRF.
• If an extraction phase is used by the KSG, it will use the same underlying function as the expansion phase unless otherwise specified.
• The KDFA also needs to specify the size of the ObjectTemplate fields.

3.1.2. Extraction

Step 1:

if required by the KSG then
              
    master_secret = KSG-Extract(master_secret[,seed]);
              

3.1.3. Expansion

Step 2:

a) Calculate the length of the key stream to be generated:

L = 0

for (i = 0; i < object_count; i++) {
    L += ObjectTemplate[i].length;
}
            

b) Set up the info field:

// the || operator represents concatenation of the encoded 
// bytes of the value
// object_count is the length of the ObjectTemplate[] array and 
// represents the number of key templates
// Separator is an optional value - its inclusion is specified by 
// the protocol or KDF definition. If present, generally a single
// octet of 0x00. 
    

// Marshall the base mixin data
info = label || [separator ||] user_context;

// Add the count of objects
info = info || object_count;

// append each of the object templates to the info data
for (i = 0; i < object_count; i++) {
    info = info || encodeTemplate(ObjectTemplate[i]);
}
            

c) Calculate the key stream

// key_stream is an array of octets

key_stream = KSG-Expand (master_secret, info, L);
            

The "encodeTemplate()" function takes an object template and turns it into an array of octets. Each KDFA instantiation specifies the meaning and ordering of octets within the encoding, and specifies the meaning of the values specified for each field within an ObjectTemplate. See Appendix A for a concrete definition of a KDFA for use within IETF specified protocols.

The ordering of subfields within the "info" field are subject to modification by a specific KDFA instantiation. If not otherwise specified, the info field has the ordering specified above and with the inclusion of a single octet of zero as a separator.

3.1.4. Assignment

Step 3: Assign

// "handles" is an array of cryptographic object handles of
// the same length as ObjectTemplate
     
ObjectHandles[] handles = 
    new ObjectHandles[object_count];
           
offset = 0;
     
for (i = 0; i < object_count; i++) {

   handles[i] = 
       createObject (key_stream, offset, ObjectTemplate[i]);
   offset += ObjectTemplate[i].ObjectLength;
}
              

The "createObject()" function is expected to create a cryptographic object with attributes as specified or derived from those in the provided ObjectTemplate. In the case of a hardware security module (HSM), the HSM is expected to create an object with enforceable policy based on those attributes. In the case of a software security module, where secret and non-secret data usually share the same memory domain, the attributes tend to be advisory.

3.2. ObjectTemplate Considerations

Although the ObjectTemplate is specified above as four distinct fields, specific KDFAs may choose to combine one or more of the fields as long as the information about the object type, use mode and length are readily discernable.

For example, a notional KDFA might specify the combination of those three fields into a single field specified by an ASN1 OBJECT IDENTIFIER (OID) which in turn defines the key type, length and use mode: "id-aes-128-ccm: 2.16.840.1.101.3.4.1.7". This notional KDFA might use the ASN1 DER encoding of that OID as the ObjectTemplate mixin data and use a table lookup of the OID to derive object length.

The "ObjectFlags" field may be omitted by any given KDFA. However, as that field provides some information about extractability and sensitivity, such KDFAs might be specified in a manner that does not permit the extraction of produced material from an HSM. This should be discussed by any KDFA definition.

Appendix A provides one concrete definition of the format and meaning of the ObjectTemplate fields for use with IETF protocols.

4. Security Considerations

4.1. General

This document provides a definition of a family of KDFs that allow for the enforcement of policy during the assignment of key material to cryptographic objects. The KDFAs have the property that all of the parameters that describe the derived cryptographic objects are involved in the production of the key stream. That means that any change in the parameters for the cryptographic objects (e.g. length, type, mode, handling restrictions) will result in a change of the complete key stream.

KDFs without this property generally can't prevent the assignment the same key stream material to different cryptographic objects. This can result in weaker protection of the key material.

For example, consider a key stream of 16 octets which is, in one instance. assigned to a single 128 bit AES key and is, in another instance, assigned to two single DES keys. This reduces the brute force attack work factor from a single attack on one 128 bit key into two attacks on 56 bit keys. Once you've recovered the DES keys, you can easily reconstitute the AES key.

If the KDF allows the assigment of some part of the key stream to public data (such as Initialization Vectors) as does the TLS1.2 and earlier KDFs, it's trivial to arrange for part of a putatively secret key to be assigned to the public data.

KDFs with assignment provides a convention for describing a set of values that are involved in both the production of the derived key stream and with the assignment of the keys stream to cryptographic objects. The document does not change any of the underlying cryptographic primitives, but provides a way of ensuring that security modules, especially HSMs can derive objects from key material with enforceable security properties. However, protocols must adopt and define KDFAs in place of their existing KDFs to gain the benefits of this convention.

4.2. Security of Public/Private Data Production

NIST, in various documents related to key derivation, has prohibited the KDF production of public data (E.g. IVs) from secret key material. That appears to be a necessary restriction since the KDFs specified by NIST do not have an assignment step where the target object parameters and types are mixed into the key stream generation process.

One question for discussion is whether or not the addition of the assignment process described in this document can be used as an argument to remove that restriction. A number of protocols, TLS in particular, have needs for various types of cryptographic material that can be exported from a security module. The author believes the KDFA scheme provides the security guarantees necessary to obviate this restriction.

5. IANA Considerations

To be provided. IANA management will be required for the Appendix A values. There are no values in the main body of the document that require IANA management.

6. Normative References

Appendix A. KDFA with Integer Parameters

This section describes a concrete realization of an KDFA by providing both the encoding process for an ObjectTemplate and providing specific values for the four notional fields of an object template.

A.1. Object Template Definition and Encoding

An object template consists of the four fields described above and in the order described above, specifically: object type, object mode, object length and object flags.

All four fields are represented as 16 bit unsigned network byte order integers. Object length is specified in octets.

To encode an object template for inclusion in the KSG mixin data, express each field as a two octet network-byte-order integer and concatenate them in order. E.g. to encode a template representing an AES 256 bit CMAC key that is not exportable (AES/CMAC/32/0), you would get (hex): [00 01 00 06 00 20 00 00].

To complete the encoding of the info field of the KDF, concatenate in order the "user_context" data, the number of object template expressed as an unsigned 16 bit network byte order integer, and the encoded object templates in order provided.

The requested key lengths must be compatible with both the key type and mode.

With HMAC and MASTER-HMAC keys, any output length key is acceptable, but shorter keys may be prohibited by security module policy. Note that the extraction step (if any) takes place before (and generally replaces) the normal HMAC key size adjustment step.

With AES-MASTER-CMAC keys, any output key length is acceptable. But note that any length other than 128, 192 and 256 will require an underlying KSG/KDF that has an extraction step. Note this also means the effective security of the KDF is limited to the 128 bit output size of the extraction step.

Master secrets of any type produced by a KDFA compliant with this appendix may only be used with KDFAs of identical formulation (i.e., same underlying KDF and PRF and parameter choices and ordering unless they are produced with the LEGACY usage flag set in the object template.

A.2. Parameter Assignments