The following paper was distributed at the Key Escrow Encryption Meeting held on September 6-7, 1995 at NIST.

Key Escrow Issues Meeting, September 6-7, 1995
Discussion Paper #4

Example Potential Solutions for the Draft Export Criteria for Software Key Escrow Encryption

1. The product shall use an unclassified encryption algorithm (e.g. DES, RC4) with a key length not to exceed 64 bits.

   It is important to understand that key in this context is related to the number of bits needed to decrypt a message which are not available over the communications channel. For some encryption algorithms the key is defined to be a number of bits which are kept secret and a number of bits which are transmitted in the clear (message key / initialization vector / salt). This criterion only specifies the number of secret bits.

2. The product shall be designed to prevent multiple encryption (e.g. triple-DES).

   One way to do this would be for the encryption program to store the ciphertext file name and the first n (e.g. 16) bytes of cipher for the last k (e.g. 8) encryptions. When the encryption routine is called, the program checks to see if the input file name is in the ciphertext file list or the first n bytes of the file match any of the k cipher text streams stored. Likewise, a plaintext header could be appended to each ciphertext file which says the file is encrypted. The encryption program would look for this header before encryption; if found, the program would not proceed with the encryption. These are just examples of what could be done. Each vendor's constraints will be different.

3. The key required to decrypt each message or file shall be accessible through a key escrow mechanism in the product, and such keys will be escrowed during manufacture in accordance with #10. If such keys are not escrowed during manufacture, the product shall be inoperable until the key is escrowed in accordance with #10.

   One way of doing this is for each user to have a Public and Private Escrow Key. The public escrow key is bound in a certificate signed by the Escrow Agent(s). This certificate would contain a key ID, the escrow agents's ID and the Public Escrow key. A header of the encrypted message could contain this certificate along with the message key, encrypted using the Public Escrow key. If the product is not escrowed during manufacture, the software will check to see if it has a valid escrow key prior to encrypting messages.

4. The key escrow mechanism shall be designed to include with each encrypted message or file, in a format accessible by authorized entities, the identity of the key escrow agent(s), and information sufficient for the escrow agent(s) to identify the key or key components required to decrypt that message.

   Following the example for criterion #3, the certificate that contained the user's escrow key would also contain the identity of the escrow agents holding the corresponding private escrow key.

5. The product shall be resistant to any alteration that would disable or circumvent the key escrow mechanism, to include being designed so that the key escrow mechanism cannot be disabled by a static patch (i.e. the replacement of a block of code by a modified block).

   Probably the most important aspect of this criterion is that source code for a product should not be available. Also it is important that the cryptography be integrated into the application in some nontrivial way. One way of achieving this criterion is for the application to store a hash or checksum of the cryptographic code in several places and check the cryptographic code several times during its use. One can prevent a static patch by making the hash or checksums dependent on a program ID code or something else that is unique about that copy of the software. Perhaps one of the best ways to defeat hackers from "patching around" the escrow would be a commitment from vendors to make each new release of the software be immune to existing static patches and patch programs.

6. The product shall not decrypt messages or files encrypted by non-escrowed products, including products whose key escrow mechanisms have been altered or disabled.

   If one follows the steps outlined under criterion #3, a receiving program could verify the escrow certificate contained in the message header, extract the escrow public key, and verify that the encrypted message decryption key is also found in the header. If it is not there, decryption does not proceed.

7. The key escrow mechanism allows access to a user's encrypted information regardless of whether that user is the sender or the intended recipient of the encrypted information.

   The message header could contain the decryption key encrypted under both the sender's public escrow key and the recipient's public escrow key. Then access to either the sender's or recipient's private escrow key would allow access to the decryption key.

8. The key escrow mechanism shall not require repeated involvement by the escrow agents for the recovery of multiple decryption keys during the period of authorized access.

   If the public and private escrow keys are unique to users, then the escrow agents could turn over the private escrow keys to the authorized parties. The private escrow key would allow access to keys encrypted with the corresponding public escrow key and not require repeated involvement with the escrow agents.

9. In the event any such product is or may be available in the United States, each production copy of the software shall either have a unique key required for decrypting messages or files that is escrowed in accordance with #10, or have the capability for its escrow mechanism to be re-keyed and any new key to be escrowed in accordance with #10.

   Following the example in criterion #3, the software could accept the load of a new escrow certificate. The software could store a "root" public key which is used to verify a certificate containing the escrow agent public key which in turn is used to sign the individual user's escrow certificate. Hence the header might contain both the escrow agent certificate signed by the root and the user certificate signed by the escrow agent(s). Once escrowed, the software could store the ID of the escrow agents and not accept loads of new escrow keys except from those agents.

10. The product shall accept escrow of its key(s) only with escrow agent(s) certified by the U.S. Government or by foreign governments with which the U.S. Government has formal agreements consistent with US law enforcement and national security requirements.

    Following the example in criterion #9, if the "root" authority only signed the certificates of escrow agents (foreign and domestic) approved by the U.S. Government then only keys escrowed by approved escrow agents will be accepted as valid by the software packages.