All but the simplest encryption systems incorporate a key, which is a special data item known only to the sender and receiver. Even if an eavesdropper knows the cipher system in use, cipher text messages cannot be decrypted without knowledge of the key.

This is called Symmetric Key or Private Key encryption, because the same, closely held key is used both for encryption and decryption.

If, in the figure above, Bob receives a message that sensibly decrypts, he can be sure that Alice was the sender, that is, Alice cannot deny having sent the message. This is because only Alice and Bob know the encryption key, and Bob (because he is not schizophrenic) knows that HE did not encrypt it, so Alice is the only person who could have.

This non-repudiation property does not extend to a third party. If Bob discloses to Charlie the message “kill all the deans at noon Friday”, Charlie cannot determine if Alice really originated the message, or if instead Bob has forged it.

The repudiation problem is exacerbated when more than two parties share the same key. If Charlie receives a message “blow up the central administration building at midnight”, he cannot determine if Alice really originated the message, or if it was forged by Bob (or any other party with access to the key). While this problem may be addressed by using a different key for each pairing of sender and receiver, if this is done a total of n(n-1) / 2 keys will be needed.

Finally, in symmetric systems some key distribution scheme must exist. If Alice creates the key, she must somehow get the key to Bob, and the communications link itself is not a good candidate for this channel. If Vladimir happens to be eavesdropping when the key is transmitted, he can subsequently read and forge messages whenever he desires.

Asymmetric-Key Systems

If, conversely, the decryption key is granted, then a signature system is generated. Since the encryption key (in this case the “private key”) is closely held, any message that sensibly decrypts can only have been generated by the holder, even though any grantee of the decryption key can verify such a signature. In the extreme case, the decryption key can be granted to the public at large, so anybody can verify the signature of the private key holder.

By using two pairs of keys, one pair for privacy and another pair for signature, a system for sending private, non-repudiable messages can be erected. In such systems the key distribution problem takes a slightly different form. Because the private keys need never be distributed beyond the participating principal, only the public keys need be distributed at all, and eavesdropping does not threaten such a system. The vulnerability is in forgery of the public keys. Natasha can easily create new key pairs, and if she can fool Alice into believing that a forged key belongs to Bob, she will be able to read any message Alice sends to Bob using that forged key. So, even though public keys can be universally known, some way must be found to prevent their forgery.

Certificates

In this way the key distribution problem is not eliminated, but it is greatly simplified. Instead of needing all the public keys of all the other principals, a principal need only know the public key of the one authority. That authority can sign certificates for all the principals, and these certificates can be distributed without fear of forgery.

The public key of the authority can be manually distributed, or can itself be vouched for by being present in a certificate signed by a second, higher level authority. Multiple such heirarchical relationships form a certificate authority tree, at the root of which is a root certificate authority which ultimately vouches for all the certificate authorities in its tree.

In the general case, there may be multiple, disjoint authority trees, each vouched for by a different root certificate, and the scheme used for distribution of these root certificates must preclude forgery. If a principal can be induced to accept a forged root certificate, the forgery of subsidiary certificates cannot be prevented.

The totality of certificate authorities, certificate trees, public and private keys, etc, is referred to as a Public Key Infrastructure or PKI.

Performance Issues

For example, the bulk text of a secure email can be symmetrically encrypted with a session key which is a random number generated by the sender. This session key is also independently asymmetrically encrypted with the public key of the recipient, and both encrypted items are combined to produce the secure email message. The recipient can use her private asymmetric key to decrypt the encrypted session key, and then use that session key to symmetrically decrypt the bulk text.

With this scheme only the session key itself is asymmetrically encrypted, the bulk of the data is encrypted with the more efficient symmetric system. An additional benefit is that multiple addressees can be accomodated by sending multiple copies of the encrypted session key, each one encrypted with the public key of its associated addressee.

The tradeoff is that the symmetric system may be weaker than the asymmetric one, and if an adversary (such as a national security agency) can break the symmetric cipher, it has no need to attack the asymmetric one. For this reason these systems should be carefully designed so the protections afforded by the various pieces are well balanced.

Another area for weakness is the generation of the random session key itself. As it turns out, it is difficult to design a good random number generator, and attacks based on predicting the next session key to be generated have been frighteningly successful. Modern operating systems include randomness sources (such as the /dev/random device driver in Linux) that incorporate keystroke timing, arrival times of network packets, and disk access times to attempt to glean randomness from the environment. Use of such randomness sources is good engineering practice.

For signature a secure hash algorithm, such as MD5 (RivestB) is used to generate a fixed-size message residue which is then asymmetrically encrypted with the private key of the sender and sent along with the message text. The recipient can use the sender's public key to decrypt the message residue, then independantly generate the residue for the text actually received, and finally ensure that the two residues are identical.

In this way, only the fixed-length message hash need be asymetrically encrypted. The added vulnerability is that if a message can be forged with the same residue value as a previously observed message, the signature from that message can be added to the forged message to make it seem genuine.

Storage of Private Keys

To avoid the inconvenience of being tied to a security token or to a specific workstation, various network-based keyserver schemes have been developed. The usual method is for the server to send the client workstation a copy of the requested principal's private key, but to send it symmetrically encrypted with a key derived from the password of that principal. The intuition is that the information is useless without the password. However, the keyserver should not store the principal's password explicitly, nor should it store the derived symmetric key, since this makes the keyserver a tempting target for exploit. Even if the keyserver stores only the symmetrically encrypted private keys, if an adversary can eavesdrop on an authentication request, she can carry the message away and employ a dictionary attack or a brute force attack on the password at her leisure. For this reason a keyserver must be seen as a weakening of security.

Various schemes attempt to avoid this problem by partitioning the private key data, representing part of it in the principal's password and part of it in the response from a keyserver. Such systems represent the cutting edge at the time of this writing (July 2001).

For information on use of PKI to implement secure email see: http://www.oit.umd.edu/middleware/email.html

For information on use of PKI for remote user authentication see: http://www.oit.umd.edu/middleware/authn.html

References

Diffie

Diffie, W., and Hellman, M.E., New directions in cryptography. IEEE Transactions on Information Theory 22 (1976), 644-654.

Kahn

Kahn, David, The Codebreakers (New York: Scribner, 1996).

RivestA

Rivest, R.L., Shamir, A., and Adelman, L.M., A method for obtaining digital signatures and public key cryptosystems. Communications of the ACM (2) 21 (1978), 120-126. For further information on the RSA Public (Asymmetric) Key encryption system:
http://www.rsalabs.com/faq/3-1-1.html

RivestB

Rivest, R.L., RFC 1321: The MD5 Message-Digest Algorithm (Internet Activities Board, 1992). For further information on MD5:
http://www.rsalabs.com/faq/3-6-6.html

Singh

Singh, Simon, The Code Book, The Evolution of Secrecy from Mary, Queen of Scots to Quantum Cryptography (New York: Doubleday, 1999).