Negotiating a Session Key

To use DES or any other single-key cryptosystem to encrypt communications, the two communicating parties must first agree on a secret session key, that is, a key for encrypting all communications transmitted in either direction. The process of establishing a session key is called key exchange, negotiation, or distribution.

A public-key distribution system allows the security devices operating on behalf of two parties to negotiate a secret session key without exchanging any secret values (see Exhibit 3). Each device generates a private key, which is random, secret value. Next, it computes a one-way function of that value, which results in a public key. The one-way function is computationally irreversible, so that the private key cannot be computed from the public key. The two devices then exchange their public keys. Finally, each device computes a function of its private key and the public key received from the other device. The result is a common session key that is a function of both private keys. An eavesdropper observing the exchange cannot determine the private keys and, thus, the session key.

Exhibit 3.  Key Negotiation Using Public-Key Distribution System

The first public-key distribution method was invented by W. Diffie and M. Hellman. Exhibit 4 shows the mathematics of their scheme. In this example, user A generates a random, private key x_A, and user B generates a random, private key x_B. Then A computes a public key y_A from x_A, and B computes a public key y_B from

Exhibit 4.  The Diffie-Hellman Key Exchange

A: y_A = g^X_A mod p

B: y_B = g^X_B mod p

where p is a global prime and g is a second global number. Arithmetic is done modulo p. The users then exchange their public y values and use them to generate a common key

A:K = y_A^X_A mod p = g^X_AX_B mod p

B:K = y_A^X_B mod p = g^X_AX_B mod p

An eavesdropper intercepting the y values cannot compute the key K because he or she lacks the appropriate x value. Although in theory x can be computed from its related y value by taking the discrete log (i.e., the log mod

A public-key cryptosystem can also be used to establish a session key. In this case, the key is picked by one user and transmitted to the other using the public-key system.

Escrowed Encryption

The U.S. key escrow encryption technology emerged from an effort to make strong, affordable encryption widely available in a way that would not harm national security and public safety. The technology is based on a tamper-resistant hardware chip (originally called Clipper) that implements an NSA-designed single-key encryption algorithm called SKIPJACK, together with a method that allows all communications encrypted with the chip, regardless of what session key is used or how it is selected, to be decrypted through a special chip unique key and a special law enforcement access field (LEAF) transmitted with the encrypted communications.

The chip unique key is formed as the XOR of two components, each of which is encrypted and stored in escrow with a separate escrow agent. The key components of both escrow agents are needed to construct the chip unique key and decrypt intercepted communications. These components are released to an authorized government official only with authorized electronic surveillance and only in accordance with procedures issued and approved by the Attorney General. The key components are transmitted to a government-controlled tamper-resistant decrypt device, where they are decrypted and combined to form the chip unique key. On termination of the electronic surveillance, the keys are destroyed within the decrypt device.

The escrowed encryption technology is intended to become a government standard for sensitive but unclassified telecommunications, including voice, fax, and data transmitted on circuit-switched systems at rates as high as 14.4 Kb/s or using basic-rate ISDN or similar grade wireless service. Use of the standard outside the government is voluntary. The first product to incorporate the new chip will be the AT&T 3600 Telephone Security Device.

The SKIPJACK Algorithm

SKIPJACK is a single-key encryption algorithm that, like DES, transforms a 64-bit input block into a 64-bit output block. However, its key length is 80 bits, as compared with DES’s 56 bits. The algorithm can be used in one or more of the four operating modes defined for use with the DES. (The AT&T device uses the output feedback model.) The algorithm is classified to prevent someone from implementing it in software or hardware without providing the law enforcement access feature, thereby taking advantage of the government’s strong algorithm while rendering encrypted communications immune from lawful government surveillance.

Because the internals of the algorithm are not available for public scrutiny, the government invited outside experts in cryptography to independently evaluate the algorithm and publicly report their findings. The author was one of the reviewers, all of whom issued a joint report in July 1993 concluding that SKIPJACK appeared to be a strong encryption algorithm and that there was no significant risk that the algorithm had trapdoors or could be broken by any short-cut method of attack. (Brickell, E. F., Denning, D. E., Kent, S. T., Maher, D. P., and Tuchman, W., “The SKIPJACK Review, Interim Report: The SKIPJACK Algorithm,” July 29, 1993; available from Georgetown University, Office of Public Affairs, Washington, D.C. or by E-mail from denning@cs.georgetown.edu.) The authors also concluded that though classification is essential to protect law enforcement and national security objectives, classification does not cover up weaknesses and is not necessary to protect against a cryptanalytic attack.

With respect to an attack by exhaustive search, the reviewers used DES as a benchmark and considered the advantages of SKIPJACK’s 80-bit keys over DES’s 56 bits. Because SKIPJACK keys are 24 bits longer than DES keys, there are 2²⁴ times more possibilities to try. Therefore, under an assumption that the cost of processing power is halved every year and a half, it will be 1.5(24) = 36 years before the cost of breaking SKIPJACK by exhaustive search is comparable to the cost of breaking DES today.

SKIPJACK, however, is but one component of a large, complex system in which the security of the entire system depends on all the components. The reviewers are therefore evaluating the entire system as it is defined and will issue a report when the evaluation is complete.