Computer Science 431
Notes on key management
The thing that encryption fundamentally accomplishes is to replace
the confidentiality of one piece of information (the plaintext) with
the confidentiality of another piece of information (the decryption key).
This allows us to do things like concentrate the confidentiality of
information in a single key, but does not eliminate the need for keeping
things confidential. Moreover, it raises new problems in the area of
what is called key management.
Key management involves several different things, each of which is
discussed below.
Who chooses keys?
One of the early security bugs discovered in Netscape concerns the manner in
which they were selecting session keys for use in encryption. The problem of
generating random unpredictable keys is one that people often overlook, but
is serious. Computers are designed in such a way that they are predictable,
and sampling predictable quantities is antithetic to producing cryptographic
keys. Various strategies
have been devised to get around this, including
the use of "secure tokens" that emit cryptographically secure streams,
noisy diodes that oscillate with unpredicatable patterns, and Netscape's
approach of sampling the operating environment.
Another approach altogether is to relieve the client machine of the need
to produce cryptographic keys, and to devise a system in which the ability
to produce session keys is concentrated in a trusted authority. This
is the approach used by the Kerberos system, and will be discussed in some
detail in a future lecture.
In the use of public key encryption, the problem of keeping an encryption key
secret is replaced by the problem of knowing which encryption key is the
legitimate one to use. This can be accoomplished with the use of a
Certification Authority, in which all parties place trust to identify
entities, and provide certificates (digital signatures with their own public
key) to link the identity of entites to their public keys. In this case, the
person verifying the identity of a key need only know the public key of the
certification authority, after which they can verify the certificate of the
key they intend to use.
How long do we use keys?
This topic was already
discussed in some detail in chapter 2, where the notion of spurious keys was
introduced. Unfortunately, the concepts of that chapter were extremely
pessimistic, and would have us replacing keys extremely rapidly. For example,
according to the notion of unicity distance, we would replace a DES key after
having used it for encrypting only a few blocks of information. By contrast,
the best known attack against DES uses either exhaustive key search (against
which the only known attack is to change DES), or Linear Cryptanalysis. The
latter requires the cryptanalyst to have on the order of 241 known
plaintext/ciphertext pairs. As long as we change our keys before we reach
this threshold, we will effectively avoid the attack. Such principles are
more realistic in practice than the theory of unicity distance in which the
cryptanalyst is assumed to have unlimited computation power.
How do we revoke a key
Keys may be compromised
by a variety of techniques, including influencing how they are chosen (as in
the Netscape attack), predicting them from too small a set (as in DES
exhaustive key search), direct cryptanalysis (as in a direct factoring attack
on RSA), or disclosure through improper storage and handling. In any event,
the need to revoke keys is sometimes required, and there are two major
techniques that can be employed for this. The first is to place a time limit
on how long a key can be used. This can be done in certificates, in which a
time limit can be made part of the message that is signed in the certificate.
That way if a key is compromised, it will only be a vulnerability for a short
period of time. The Kerberos system uses a similar approach, in which
"tickets" that are issued by the key server have a limited lifetime. This way
if a Kerberos password is compromised, the tickets that can potentially
compromise the system will only be useful for a limited time (typically 8
hours).
Even if a key has a limited lifespace, there may still be a period of time
when the key is exposed to abuse. For example, if a public key used for
signing documents is compromised, the certificate for the key will still be in
existence for the lifetime of the key. If a system is unwilling to suffer
from this exposure, then it becomes required to have "revocation lists" of
public keys, in much the same way that MasterCard and Visa used to issue books
of bad credit card numbers. This worked for a while in the early days of
credit card usage, but eventually became untenable. In the end they went to
an "online" system in which each transaction is checked in real time to verify
that the card had not been revoked. If a system requires this kind of
assurance, then the benefits of public key are greatly reduced.
We have already seen that the Diffie-Hellman protocol
provides a means to construct a shared key between two parties, using only a
public communication channel. Unfortunately, the lack of authentication in
the basic Diffie-Hellman protocol allows "mad in the middle" attacks to be
mounted against the protocol. This can be fixed by a variety of techniques,
several of which are mentioned in the textbook in sections 8.1, 8.2, and 8.4.
Of particular interest is the "station to station protocol". Other
alternatives can be devised using RSA as a building block.
How many keys are required for a group of n
people?
One of the major advantages of public key cryptography is
that in a group of n people, there is no need for having n(n-1)/2 keys for n
people to have all possible combinations of pairwise secure communciations.
If each user is issued a certified RSA or Diffie-Hellman public key, then only
n keys are required for a group of n people to be able to communicate securely
(one for each potential receiver). If different session keys are required for
each communication, the agreement on these keys can be bootstrapped from
only the existence of one public key for each user.
How do we use keys to broadcast to a group
This topic is beyond the scope of the course, but is a major concern for a
wide range of applications, including sattelite pay-TV systems and military
command situations. Recall that one of the homework problems alluded to one
potential solution to this problem, where a bulk encryption key is encrypted
with the public key of each legitimate receiver, and is appended to the
message. In this way, the actual message need not be repeated in encrypted
form for each user, but only the encryption key is reproduced. Other
techniques exist.
Key escrow
Why would we want to escrow keys
for later recovery?
This topic became an emotional one when the topic
of key escrow was raised by the government in the form of the "clipper"
program. The basic purpose is that whenever an encryption key is used, there
may be reasons why this key is escrowed with a "trusted" third party. For
example, the FBI currently has the technical ability to wiretap on phone
conversations in the US (presumably only under a court order). If encryption
is widespread in telephone equipment, this could effectively remove this
capability from the toolbox that law enforcement has at their disposal. In
order to address this point, the US government launched a program known as
"clipper" in which equipment makers would incorporate a back door into the
equipment, so that the encryption keys would be split in two pieces and
escrowed with trusted entities within the government. For fairly obvious
reasons, many people in US society reacted to this with horror in reaction to
the "big brother" overtones that it conveys. Note also that companies may
wish to preserve the same ability when it comes to their company equipment
being used by their employees.
There is another application of key escrow that should not be overlooked.
This was originally referred to as "key recovery" rather than "key escrow",
but lately the terms have become synomous in the interests of political
correctness. For example, when a file containing sensitive company
information is encrypted by an employee, the encrypted information is in
danger of being lost forever if the employee loses the key or is hit by a
truck in the street when leaving work. For this reason, companies are often
anxious to be able to have an escrowed copy of the key located in a safe
facility within the company. After all, the encrypted information is
presumably important to the company, and remains the property of the
company. It is imagined that this will grow to a viable business in the
future,
with companies lining up to provide a "key recovery" service for businesses.
Note however that there is a fundamental difference between these two
applications of key escrow, depending on whose information is being protected
and whether the information is stored data or real-time communciation. Most
of the controversy surrounding key escrow surrounds the use for eavesdropping
by authorities on real-time communication rather than key recovery for
encrypted stored data.. In the latter case, there is a presumption that the
owner of the data has a right to keep control over that data. In the case of
wiretapping, there are fundamental constitutional issues about freedom of
association, as well as societal privacy issues.
Politics aside, there
are some real challenges in the implementation of key escrow. Early attempts
by the government to design such a system contained several failures,
including a bad decision on the size of the Clipper LEAF (Law Enforcement
Access Field), as well as protocol failures involving the ability of parties
to implicate others in criminal activity. The government has still not
addressed these issues to the satisfaction of the cryptographic research
community, and of course they will never convince some elements of society who
object to key escrow for wiretapping on purely philosophical and political
grounds. After the original clipper initiative, the government adopted a
program where individuals were allowed to choose their own trusted entities
with which to escrow their keys. Several companies including Trusted Information
Systems and IBM have started
commercial ventures to serve this need, and the debate goes on.
In general there are two approaches to key escrow - send a copy of the session
key to a third party escrow service encrypted with a key used for this
purpose, or store it locally (or include it in the transmission) in the
original encrypted data. In addition, the key that was to be escrowed in the
original clipper system was to be split in two pieces and distributed to
"independent" entities, both of whose cooperation was required to produce the
actual encryption key. This can be accomplised in a simple fashion, by
choosing a random number r, and giving one party r and the other party (r XOR
k). When the two are combined and XORed together, the original key is
recovered, but each piece in itself reveals nothing about the actual key.
This is an example of a technique in cryptography called "secret sharing",
and is discussed in chapter 11 of the textbook. More on this later.
Key management techniques
Some key management techniques to be discussed in class in more detail:
- Certificates and their management
- Station-to-station authenticated Diffie-Hellman protocol
- Needham-Schroeder model of key management with a trusted third party
- Kerberos versions 4 and 5, and it's use for identification of entities,
as well as establishment of session keys for authentication and encryption.
- Secret sharing, in which keys (and trust) are distributed among
several parties.
Return to the CS431 home page.