Key Establishment Schemes - Part 1

The rapid growth of information technology that has resulted in significant advances in cryptography to protect the integrity and confidentiality of data is astounding. New algorithms have been introduced such as the Advanced Encryption Standard (AES) as defined in the Federal Information Processing Standard (FIPS) 197 to offer three security strengths: 128 bits, 192 bits and 256 bits.

The use of AES requires the establishment of shared keying material in advance. Manual distribution methods such as trusted couriers are inefficient and complex. They simply do not scale as the system grows. Key establishment schemes are required to distribute keys in today’s communication systems. Protocols such as S/MIME, SSL and IPSec all use key establishment schemes.

Key establishment is so fundamental to security that the American National Standards Institute (ANSI) and the National Institute of Standards and Technology (NIST) are producing standards and recommendations for key establishment. For example, security products intended for government use will require FIPS 140-2 Validated modules with an approved key establishment method.

Before using key establishment schemes, there are a number of cryptographic elements that must be generated. Some of these elements must be kept private and some are made public. These elements include, among others, the generation, validation and authentication of static and ephemeral public-key key-pairs.

An entity’s static key-pair, as the name implies, is a long-term key-pair for the user and must be generated in a trusted manner. Static public-keys and user credentials may be digitally signed by a trusted third-party (i.e. a Certification Authority) to provide a strong level of assurance to recipients that the public-key can be trusted.

An entity’s ephemeral key pair is intended for exactly one use. The keys are created, used once in the calculation of a key establishment primitive and then destroyed immediately after the shared secret is computed. ANSI X9.42 and X9.63 describe the use of primitives for the calculation of the shared secret.

A primitive is a cryptographic building block that is used to facilitate the implementation of more complicated schemes. Each key establishment scheme, as outlined by NIST, requires the use of one primitive that is based on either the Diffie-Hellman (DH) or the Menezes-Qu-Vanstone (MQV) algorithm. These algorithms can be computed using Discrete-Log Cryptosystem (DLC) over finite-fields as in ANSI X9.42 or using Elliptic Curve Cryptography (ECC) as in ANSI X9.63.

As a result there are a number of possible primitive combinations to choose from for your key establishment scheme. For example, if you chose the MQV algorithm as the primitive to calculate the shared secret, you would also need to decide if MQV is calculated using DLC over a finite field or ECC. Similarly, you could chose DH as the primitive but again you would need to decide how it’s calculated.

Although all schemes are approved, there are a number of drawbacks of using DLC over finite-fields and of using DH. One drawback is that, with DLC over finite fields, the system needs to process very large keys for new symmetric ciphers such as AES. In a system using 256-bit AES, this would require a massive public-key pair on the order of 15,000 bits, which is not be feasible for most applications.

Key establishment schemes using the MQV primitives provide assurance to each entity that if a malicious entity compromises their static private key, the malicious entity cannot masquerade as a third party to the entity whose key was compromised. For example, if a malicious entity, E, compromises entity U’s static private key, then E cannot masquerade as any other party to U. Key establishment schemes using the DH primitive do not provide this assurance.