# Presentation: 183767

## Key Establishment Schemes Workshop Document

- October 2001

## Outline

- Introduction
- Scope & Purpose
- Definitions
- Key Establishment Algorithm Classes
- Security Attributes
- Cryptographic Elements
- Key Agreement Schemes
- Key Transport
- Keys Derived from a “Master Key”
- Key Recovery

## Introduction

- Many cryptographic algorithms (e.g., AES, HMAC) require the establishment of *shared keying material* in advance.
- Manual distribution of keying material is inefficient and complex.
- Seek automated key establishment schemes.

## Scope & Purpose

- Development of a Federal key agreement schemes document based on
**ANSI X9.42** Agreement of Symmetric Keys using Discrete Logarithm Cryptography
**ANSI X9.44** Key Agreement and Key Transport using Factoring-Based Cryptography
- 	(To be provided)
**ANSI X9.63** Key Agreement and Key Transport using Elliptic Curve Cryptography

## Definitions

- Approved
- FIPS approved or NIST Recommended
- Keying Material
- The data (e.g., keys and IVs) necessary to establish and maintain cryptographic keying relationships.
- Shared Keying Material
- The keying material that is derived by applying a key derivation function to the shared secret.
- Shared Secret
- A secret value computed using a prescribed algorithm and combination of keys belonging to the participants in the key establishment scheme.

## General Symbols

| H | An approved hash function |
| --- | --- |
| [Text1], [Text2] | An optional bit string that may be used during key confirmation and that is sent between the parties establishing keying material |
| U | One entity of a key establishment process, or the bit string denoting the identity of that entity |
| V | The other entity of a key establishment process, or the bit string denoting the identity of that entity |
| X||Y | Concatenation of two strings X and Y |

## ANSI X9.42 Symbols 

| p, q, g | The domain parameters |
| --- | --- |
| mod p | The reduction modulo p on an integer value |
| rU, rV | Party U or Party V’s ephemeral private key |
| tU, tV | Party U or Party V’s ephemeral public key |
| xU, xV | Party U or Party V’s static private key |
| yU, yV | Party U or Party V’s static public key |
| Z | A shared secret that is used to derive keying material using a key derivation function |
| Ze | An ephemeral shared secret that is computed using the Diffie-Hellman primitive |
| Zs | A static shared secret that is computed using the Diffie-Hellman primitive |

## ANSI X9.63 Symbols

| [X] | Indicates that the inclusion of the bit string or octet string X is optional |
| --- | --- |
| a, b | Field elements that define the equation of an elliptic curve |
| avf(P) | The associate value of the elliptic curve point |
| de,U, de,V | Party U’s and Party V’s ephemeral private keys |
| ds,U, ds,V | Party U’s and Party V’s static private keys |
| FR | An indication of the basis used |
| G | A distinguished point on an elliptic curve |
| h | The cofactor of the elliptic curve  |

## ANSI X9.63 Symbols

| n | The order of the point G |
| --- | --- |
| q | The field size |
|   | A special point on an elliptic curve, called the point at infinity. The additive identity of the elliptic curve group. |
| Qe,U, Qe,V | Party U’s and Party V’s ephemeral public keys |
| Qs,U, Qs,V | Party U’s and Party V’s static public keys |
| SEED | An optional bit string that is present if the elliptic curve was randomly generated  |
| xP | The x-coordinate of a point P. |
| yP | The y-coordinate of a point P. |
| Z | A shared secret that is used to derive key using a key derivation function |
| Ze | An ephemeral shared secret that is computed using the Diffie-Hellman primitive |
| Zs | A static shared secret that is computed using the Diffie-Hellman primitive |

## Key Establishment Algorithm Classes

- Cryptographic keying material may be electronically established between parties using either key agreement or key transport schemes.
- During key agreement, the keying material to be established is not sent; information is exchanged between the parties that allow the calculation of the keying material. Key agreement schemes use asymmetric (public key) techniques.
- During key transport, encrypted keying material is sent from an initiator who generates the keying material to another party. Key transport schemes use either symmetric or public key techniques.

## Security Attributes

- To be determined...

## Cryptographic Elements

- Domain Parameters (Generation, Validation, and Management)
- Private/Public Keys (Generation, PK Validation, Management)
- Key Derivation Function
- Message Authentication Code
- Associate Value Function (Elliptic Curves Only)
- Cryptographic Hash Functions
- Random Number Generation
- Key Confirmation
- Calculation of Shared Secrets
- RSA Primitives (To be provided)
- Key Wrapping Primitive(s) (To be provided)

## Domain Parameter Generation

- ANSI X9.42 Requirements
- (p,q,g) where p and q are prime, and g is the generator of the q-order cyclic subgroup of GF(p)
- ANSI X9.63 Requirements
- (q, FR, a, b, [SEED], G, n, h) where q (field size), FR (basis used), a and b (field elements), SEED (optional bit string), G (point), n (order of the point G), and h (cofactor).

## Domain Parameter Validation

- One of three methods _must_ be employed before use
- The party generates (and checks) the parameters
- The party validates parameters as specified in appropriate ANSI standards
- The party receives assurance from a trusted party (e.g., a CA) that the parameters are valid by one of the above methods

## Domain Parameter Management

- Only authorized (trusted) parties should generate domain parameters
- Key pairs must be associated with their domain parameters
- Modification or substitution of domain parameters may cause security risks

## Private/Public Keys

- Key Pair Generation
- Static and ephemeral key pairs are generated using the same primitives
- Private keys must be created using an approved RNG
- Public Key Validation
- Static public keys **must** be validated by the recipient, or by an entity that is trusted by the recipient
- Each ephemeral public key **must **be validated by the recipient before being used to derive a shared secret
- Key Pair Management
- Public/private key pairs **must** be correctly associated with their corresponding domain parameters
- Static public keys **must **be obtained in a trusted manner
- Ephemeral keys **must** be destroyed immediately after the shared secret is computed

## Cryptographic Elements

- Key Derivation Function (KDF)
- Used to derive keying material from a shared secret
- Uses identities of communicating parties
- Message Authentication Code (MAC)
- A function of both a symmetric key and data
- MAC function used to provide key confirmation
- Associate Value Function (EC Only)
- Used by the MQV family of key agreement schemes to compute an integer associated with an elliptic curve point

## Cryptographic Elements

- Cryptographic Hash Functions
- Use approved hash functions whenever required.
- Random Number Generation
- Use approved random number generators whenever required
- Key Confirmation
- Used to provide assurance that the parties have derived the same keys

## Calculation of Shared Secrets

- Use DH of ANSI X9.42 for dhHybrid1, dhEphem, dhHybridOneFlow, dhOneFlow, and dhStatic schemes
- Use Modified DH of ANSI X9.63 for Full Unified Model, Ephemeral Unified Model, 1-Pass Unified Model, 1-Pass Diffie-Hellman, and Static Unified Model Schemes (Differs from ANSI X9.63)

## Calculation of Shared Secrets

- Use MQV2 primitive of ANSI X9.42 for the MQV2 scheme
- Use MQV1 primitive of ANSI X9.42 for MQV1 scheme
- Use MQV primitive of Section 5.5 of ANSI X9.63 for Full MQV and 1-Pass MQV schemes
- Shared Secrets
-  **must not** be used directly as shared keying material.
**must** be calculated by applying a key derivation function to the shared secret.

## Other Primitives

- RSA Primitives
- To be addressed later...
- Key Wrapping Primitive(s)
- To be addressed later...

## Key Agreement Schemes Categories

**C(2): Two Party Participation**
*Interactive, 2-way*
- Each party generates an ephemeral key pair.
**C(1): One Party Participation**
*Store-and-Forward, 1-way*
- Only the initiator generates an ephemeral key pair.
**C(0): Static Keys Only**
*Static (passive)*
- No ephemeral keys are used.

## Key Agreement Schemes Subcategories

- C(2,2): Each party generates an ephemeral key pair and has a static key pair.
- C(2,0): Each party generates an ephemeral key pair; no static keys are used.
- C(1,2): The initiator generates an ephemeral key pair and has a static key pair; the responder has a static key pair.
- C(1,1): The initiator generates an ephemeral key pair, but has no static key pair; the responder has only a static key pair.
- C(0,2): Each party has only static keys.

## Key Agreement Schemes Subcategories

- Primitive: Either a DH or an MQV primitive
- Arithmetic: Either FF as in ANSI X9.42 or EC as in ANSI X9.63
- Example: dhHybrid1 can be classified as C(2, 2, DH, FF)

## Key Agreement Schemes

## Key Agreement Schemes Overview

- Each party in a key agreement process **must **use the same domain parameters.
- These parameters **must** be established prior to the initiation of the key agreement process.
- Static public keys may be obtained from other entity or trusted third party (e.g., a CA)

## Two Party Participation C(2)

- Each party generates an ephemeral key pair and has a static key pair
*Four *C(2,2) schemes
- dhHybrid1
- Full Unified Model
- MQV2
- Full MQV

## Figure 1: General Protocol when each party has both static and ephemeral key pairs

## Table 4: dhHybrid1 Key Agreement Scheme C(2,2,DH,FF)

## Table 5: Full Unified Model Key Agreement Scheme C(2,2,DH,EC)

## Table 6: MQV2 Key Agreement Scheme C(2,2,MQV,FF)

## Table 7: Full MQV Key Agreement Scheme C(2,2,MQV,EC)

## Two Party Participation

- Each party generates an ephemeral key pair; no static keys are used.
*Two *C(2,0) schemes
- dhEphem
- Ephemeral Unified Model

## Figure 2: General protocol when each party generates ephemeral key pairs; no static keys are used

## Table 8: dhEphem Key Agreement Scheme C(2,0,DH,FF)

## Table 9: Ephemeral Unified Model Key Agreement Scheme C(2,0,DH,EC)

## One Party Participation

- Initiator has a static key pair and generates an ephemeral key pair; Responder has a static key pair.
*Four *C(1,2) schemes
- dhHybridOneFlow
- 1-Pass Unified Model
- MQV1
- 1-Pass MVQ

## Figure 3: General protocol when the Initiator has both static and ephemeral key pairs, and the Responder has only a static key pair 

## Table 10: dhHybridOneFlow Key Agreement Scheme C(1,2,DH,FF)

## Table 11: 1-Pass Unified Model Key Agreement Scheme C(1,2,DH,EC)

##   Table 12: MQV1 Key     Agreement Scheme C(1,2,MQV,FF)

## Table 13:1-Pass MQV Model Key Agreement Scheme C(1,2,MQV,EC)

## One Party Participation

- Initiator generates only an ephemeral key pair; Responder has only a static key pair.
*Two *C(1,1) schemes
- dhOneFlow
- 1-Pass Diffie-Hellman

## Figure 4: General protocol when the Initiator has only an ephemeral key pair, and the Responder has only a static key pair

## Table 14: dhOneFlow Key Agreement Scheme C(1,1,DH,FF)

## Table 15: 1-Pass Diffie-Hellman Model Key Agreement Scheme C(1,1,DH,EC)

## Static Keys Only

- Each party has only a static key pair
- Two C(0,2) schemes
- dhStatic
- Static Unified Model

## Figure 5: Each party has only a static key pair

## Table 16: dhStatic Key Agreement Scheme C(0,2,DH,FF)

## Table 17: Static Unified Model Key Agreement Scheme C(0,2,DH,EC)

## Topics to be Addressed

- Key Transport
- To be addressed
- Keys Derived from a “Master Key”
- Suggestions welcome

## Key Recovery

- Some applications may desire to recover protected data by first recovering the associated key
- Static key pairs may be saved (See Key Management Guideline document)
- Static public keys may be saved (e.g., public key certificates)
- Ephemeral public keys may be saved
- Ephemeral private keys **must not** be recoverable or saved

## Implementation Validation

- Implementations of schemes in the final schemes document must be tested in order to claim compliance
- For information on NIST’s testing program see http://csrc.nist.gov/cryptval

## Questions?

## Give me a break!

## Discussion Topics

- Are there any situations which are not addressed by at least one of the schemes in the document?
- Which schemes should use key confirmation?
- Should key confirmation ever be mandatory?
- Does it unnecessarily hinder any application  to require a distinction between initiator and responder in a scheme?
- Should the identities of the initiator and responder be used in the calculation of shared secrets? (related to previous question)

## Discussion Topics	

- Should this document address broader forms of key derivation (e.g., key derivation for multi-user applications)?
- What are the most important key establishment scheme attributes, and how should they be presented? (Please bring your ideas)
- Are there any additional topics that should be covered?
- Are there any additional appendices that should be included?

## Questions or Discussion?

## Closing	

- Thanks for coming and  helping
- See _[http://www.nist.gov/kms](http://www.nist.gov/kms)__ _
- We will  let you know when report is posted
- Send comments to _[kmscomments@nist.gov](mailto:kmscomments@nist.gov)_
- Have a safe trip home