<< . .

. 3
( : 6)

. . >>

the communicating parties must have copies of the was sometimes accomplished through the use of
same cryptographic key, and a method to securely couriers (sometimes humorously referred to as
convey these keys to the appropriate parties must “sneaker net”). The keying material was physi-
be available. Compromise of the secret key natu- cally destroyed when no longer needed.
rally leads to the compromise of any data that was However, modern symmetric cryptosystems are
encrypted using that key. more advanced and typically use some form of
Public key cryptography is characterized by the electronic key distribution. One possible model for
fact that the key used to perform a crypto- electronic distribution of symmetric keys is based
graphic operation (e.g., digital signature creation) on a trusted third party component known as a
is not the key used to perform the inverse cryp- Key Distribution Center (KDC) (e.g., see [5]). Be-
tographic operation (e.g., digital signature veri¬- fore an end-entity (e.g., an end user) can access
cation). Public key cryptography is based on the a target resource (e.g., a server), the end-entity
notion of key pairs. One key is referred to as makes a request to the KDC to establish a session
the public key and can be revealed to anyone. key that can be used to secure the communication
The other key is referred to as the private key and between the end-entity and the target resource.
is not revealed to anyone other than the end-entity This model is illustrated in Figure 1.
associated with that key (although there are ex- The outbound arrows between the KDC and the
ceptions such as private key backup with a trusted communicating parties are logical representations
third party when required). These keys are mathe- of the key distribution process. In practice, The
matically related; however, knowledge of the pub- KDC may distribute one copy of the symmetric key
lic key does not divulge enough information to directly to the end-entity and another copy to the
allow an attacker to determine the private key target resource, or both copies of the symmetric
Key management 329

Kerberos to illustrate the concepts associated with
symmetric key management.


In the Kerberos scheme, end-entities and target
resources are referred to as Principals. Kerberos
maintains a database of all Principals and their
associated symmetric keys. This allows the ses-
sion keys for each principal to be protected when
they are in transit. These symmetric keys are ini-
tialized separately and must be established before
an end-entity can send a request to the AS.


When an end-entity needs to communicate with a
Fig. 1. Key distribution center model
target resource for the ¬rst time, the end-entity
makes a request to the AS. The request contains
key may be distributed back to the end-entity and the end-entity™s identi¬er as well as the identi¬er
the end-entity would then pass the symmetric key of the target resource. Typically the initial target
to the target resource. In both cases two copies resource is the TGS and for the purposes of this
are needed since the symmetric key is encrypted example, we will assume that the request is for
for the intended recipients (i.e., one copy of the key a session with the TGS. However, this may not
is encrypted for the end-entity and another copy of always the case (see [4] for more information).
the key is encrypted for the target resource). This Assuming that the end-entity and target re-
is necessary to prevent someone in a position to source (i.e., TGS) are in the Kerberos database,
intercept the session key from being able to use the AS will generate a symmetric key (referred to
the key to eavesdrop on the subsequent commu- as a session key) and encrypt one copy of the ses-
nication. This implies that the KDC and the com- sion key using the symmetric key of the end-entity
municating parties must have been pre-initialized and another copy of the session key using the sym-
with keys that can be used to protect the distribu- metric key of the target resource (this is referred to
tion of the session keys. These are sometimes re- as a ticket). These encrypted copies of the session
ferred to as Key Encrypting Keys (KEKs).1 Note key are returned to the requesting end-entity.
The end-entity decrypts its copy of the session
that this pre-initialization step should not be con-
key and uses it to encrypt the end-entity™s iden-
sidered unusual since some form of initial boot-
tity information and a time stamp (this is referred
strap process is typically required in any crypto-
to as the authenticator). The time stamp is nec-
graphic system.
essary to prevent replay attacks. The session key
A classic example of an electronic secret key dis-
encrypted by the AS for the target resource (i.e.,
tribution based on this model is Kerberos V5 (see
the ticket for the TGS) and the encrypted au-
[4]). Kerberos enables electronic key distribution
thenticator are then sent to the target resource.
in a client/server network environment. Kerberos
The two communicating parties now have copies
is comprised primarily of two logical components:
of the session key and are able to communicate
(1) the Authentication Server (AS) and (2) the
Ticket Granting Server (TGS). The AS and TGS
From that point forward the end-entity can
may be physically separate, or they may reside on
make additional requests to either the AS or the
the same platform, or they may even be part of the
TGS (usually the TGS, but see [4] for more de-
same process. Collectively, these two logical com-
tails) in order to establish a session key between
ponents can be thought of as the KDC as described
the end-entity and any other target resource. The
above. Since Kerberos is a well known, publicly
difference between requesting this information
available symmetric cryptosystem, we will use
from the AS and from the TGS is that the end-
entity™s copy of the session key is encrypted with
1 It is possible to have all communicating parties pre-
initialized with the same KEK; however, this practice is gener- the end-entity™s symmetric key obtained from the
ally considered to be less secure since compromise of the single
Kerberos database when dealing with the AS,
KEK would impact the entire community rather than a single
but the end-entity™s copy of the session key is
330 Key management

encrypted using the TGS session key when dealing the PKI-related services are referred to as end-
with the TGS. entities and may be end users, devices, processes,
or servers.
In terms of key cancellation, we need to consider
The generation of the public/private key pairs as-
that there are actually two types of keys being
sociated with the end-entities can occur within the
used. Each principal (i.e., end user or server) has a
CA, LRA, or the end-entity™s system. If necessary
shared secret key used to protect the distribution
(depending on where key generation occurred), the
of the session keys. The lifetime of these shared
private component of the public/private key pair
secret keys is typically very long. Cancellation of
must be securely distributed to the appropriate
a given key is usually facilitated through replace-
end-entity. Several protocols have been de¬ned to
ment (i.e., keys can be changed in accordance with
accomplish this (e.g., see [6] or [1]). The private
local policy) or deletion of an entry (e.g., when a
key is stored securely in standard formats such
principal no longer belongs within the Kerberos
as PKCS #5 and #8. The public key component is
realm). The second type of key is the session key.
populated in a signed data structure issued by a
The lifetime of the session keys is directly coupled
CA. This data structure is referred to as a pub-
with the lifetime of the session itself. Once the ses-
lic key certi¬cate. The latest version of the public
sion between the client and server is terminated,
key certi¬cate (version 3) is de¬ned in [7] and a
the session key is no longer used.
high-level representation of a version 3 public key
Summary and Observations certi¬cate is provided in Figure 2.
The digital signature appended to the public key
certi¬cate provides two things. First, the integrity
In summary, the Kerberos database is initialized
of the certi¬cate can be veri¬ed so any modi¬ca-
with entries for each principal. Each entry in-
tions to the data contained within the certi¬cate
cludes the shared secret key associated with that
after it was issued can be detected. Second, the
principal which is used to protect the session
identity of the issuing CA can be veri¬ed. This al-
keys. The session keys are generated by the KDC
lows the users of the certi¬cate to determine if the
in response to requests from clients and are se-
certi¬cate originated from a trustworthy source.
curely distributed to the appropriate principals.
Since both the content and source of the certi¬cate
The shared secret keys generally have long life-
can be veri¬ed, the certi¬cate can be distributed
times, but the session keys are ephemeral (i.e.,
via potentially nonsecure channels. For example,
the public key certi¬cate can be stored “in the
One of the criticisms associated with symmet-
clear” in a public repository (e.g., an X.500 direc-
ric only key management is that it does not scale
tory) which allows end-entities to retrieve these
well. It has also been criticized for having a single
certi¬cates easily when required.
point of failure (i.e., what happens when the KDC
When end-entities enroll with the PKI, they typ-
goes down?) as well as a single point of attack (all
ically use one or more shared secrets to demon-
of the pre-initialized symmetric keys are stored
strate they are the end-entity that they claim to be.
in the KDC database). However, alternative key
The shared secrets may have been established at
management schemes exist that help to alleviate
some point in the past, or they may be distributed
some of these problems. In particular, asymmetric
to the end-entity as part of a formal registration
cryptography can be used to exchange secret keys
process. This latter method is typically required
as discussed in the next section.
when the certi¬cate(s) are used in conjunction
ASYMMETRIC PUBLIC KEY CRYPTOG- with high assurance and/or sensitive transactions.
This often requires that the end-entity present
RAPHY: Asymmetric cryptography is often im-
himself or herself to an LRA along with accept-
plemented in association with a supporting
able forms of identi¬cation (e.g., a driver™s license
infrastructure referred to as Public Key Infra-
or employee ID). In any case, the shared secrets fa-
structure (PKI). PKI refers to the policies, pro-
cilitate the initial bootstrap process in which end-
cedures, personnel, and components necessary to
entities are ¬rst initialized with their keys.
support the key management process. The pri-
mary components of the PKI include the Certi-
¬cation Authority (CA) and Local Registration
Authority (LRA). (Other components may also
be present, but these are not relevant for the Once the end-entities are initialized with the
purposes of this discussion.) The consumers of PKI, they can engage in secure communication
Key management 331

Version 3 Public Key Certificate

Subject Public Digital
Issuer Optional
Serial Signature Issuer Subject
Validity Subject
Key Info Signature
Unique ID Unique ID Extensions
Number (Info)

Possible Extensions

Authority Key Subject Key
Identifier Identifier

Fig. 2. Version 3 public key certi¬cate

(e.g., secure e-mail) with their peers. Theoret- does not). Thus, we would like to take advantage of
ically, it would be possible for end-entities to the speed of symmetric cryptography, but we want
use public key cryptography to encrypt data for to avoid the key distribution problems mentioned
their peers by using the public key of each peer in the previous section. We also want to avoid en-
(assuming that the asymmetric algorithm sup- cryption of the data multiple times (once for each
ports encryption/decryption). However, there are recipient). This is why PKI supports both asym-
a few practical issues that make this an unattrac- metric and symmetric cryptography. Symmetric
tive approach. First, asymmetric cryptography is cryptography is used for data encryption (but the
notoriously slow when compared to symmetric data is only encrypted once regardless of the num-
cryptography. Asymmetric cryptography is there- ber of recipients), and asymmetric cryptography
fore suitable only for the encryption of small is used for the distribution of the secret key to the
amounts of data. Second, it would be extremely intended recipients.
wasteful to encrypt the data N times, once for We can illustrate how this works using the ex-
each intended recipient”especially when deal- ample illustrated in Figure 3. In this example, we
ing with large amounts of data (consider an e- are using a symmetric algorithm to encrypt data
mail with ¬le attachments). (Note that this is also (e.g., an e-mail message) and an asymmetric al-
true even when symmetric algorithms are used.) gorithm such as RSA (see RSA public key encryp-
Third, not all asymmetric algorithms support tion) to enable the secure distribution of the se-
encryption/decryption (e.g., RSA does, but DSA cret key that was used to encrypt the e-mail.

Fig. 3. Asymmetric key distribution
332 Key management

Essentially, the system generates a secret key that the private signing key can no longer be used
is then used to encrypt the message. Any number and the time that the associated public key cer-
of symmetric algorithms could be used for this pur- ti¬cate expires so that digital signatures created
pose (e.g., CAST-128 or Rijndael/AES). The secret before the corresponding private key expired can
key is then encrypted using the intended recipi- still be veri¬ed without exposing the end user to
ent™s public (encryption) key. If multiple recipients needless warning messages. These comprehensive
were involved, the original data would still be en- PKIs generally update the public/private key pairs
crypted once using the generated secret key, and (and public key certi¬cate) automatically.
the secret key would be encrypted N times, once for Finally, it is possible to revoke certi¬cates be-
each recipient. The public key certi¬cate for each fore they naturally expire. This might be done for
recipient can be retrieved from a repository, or per- a variety of reasons, including suspected private
haps the certi¬cate may have been conveyed to the key compromise. (See certi¬cate revocation for ad-
originator in a previous exchange. On receipt, each ditional information related to certi¬cate revoca-
recipient can use his/her corresponding private de- tion.)
cryption key to decrypt the symmetric key neces- The interested reader can ¬nd a more compre-
sary to decrypt the original data. This provides an hensive discussion of public key life cycle manage-
ef¬cient and secure key distribution mechanism ment in Chapter 7 of [2].
that does not suffer from the drawbacks discussed
in the previous section.
Summary and Observations
Asymmetric cryptography can also be used to
support a process known as key agreement. In
PKI provides comprehensive key management
this case, the communicating parties negotiate
through a combination of asymmetric and sym-
an ephemeral secret key. (See Dif¬e“Hellman key
metric cryptography. Symmetric cryptography is
exchange protocol for additional information.)
used for bulk data encryption/decryption and
asymmetric cryptography is used for key distri-
bution. The use of asymmetric cryptography to
facilitate key distribution is an extremely pow-
erful tool that serves to eliminate many of the
In terms of key cancellation, there are two things
problems associated with symmetric-only crypto-
to consider: (1) the secret key used to encrypt the
data and (2) the public/private key pair. In terms
of the secret key, this survives as long as the data Steve Lloyd
is encrypted, which could be inde¬nitely. How-
ever, the secret key is deleted/destroyed when
the associated ¬le is deleted or (permanently)
decrypted. There may also be cases when the pro-
[1] Adams, C. and S. Farrell (1999). “Internet X.509
tection is no longer considered adequate (e.g., the
public key infrastructure: Certi¬cate management
symmetric algorithm has been compromised or the
protocols.” Internet Request for Comments 2510.
key length used no longer provides adequate pro-
[2] Adams, C. and S. Lloyd (2003). Understanding PKI:
tection). In this event, the ¬le is decrypted and re-
Concepts, Standards, and Deployment Considera-
encrypted using a new algorithm and/or key. The
tions (2nd ed.). Addison-Wesley, Reading, MA. ISBN
original key would be deleted/destroyed. 0-672-32391-5.
In terms of the public/private key pairs, public [3] Dif¬e, W. and M. Hellman (1976). “New directions in
key certi¬cates are issued with a ¬xed lifetime, cryptography.” IEEE Transactions on Information
typically on the order of 2“5 years depending on Theory, 22, 644“654.
the purpose of the certi¬cate and the associated [4] Kohl, J. and C. Neuman (1993). “The Kerberos net-
work authentication service (V5).” Internet Request
local policy. In some PKIs, the certi¬cates (and as-
for Comments 1510.
sociated private key) are renewed automatically
[5] Needham, R. and M. Schroeder (1978). “Using en-
before the existing certi¬cate(s) expire. In other
cryption for authentication in large networks of
PKIs, end-entities must request new certi¬cate(s)
computers.” Communications of the ACM, 21 (12).
when their existing certi¬cate(s) expire.
It is possible to establish a different lifetime for
[6] Ramsdell, B. (1999). “S/MIME Version 3 certi¬cate
the private component of the public/private key handling.” Internet Request for Comments 2632.
pair when that key pair is used in conjunction with [7] ITU-T Recommendation X.509 (2000). “Information
digital signatures (see digital signature schemes). technology”open systems interconnection”the di-
This is done in comprehensive PKIs where it is de- rectory: Public key and attribute certi¬cate frame-
sirable to have a grace period between the time works.” (Equivalent to ISO/IEC 9594-8:2001).
Knapsack cryptographic schemes 333

The Encryption in Additive
Knapsack Schemes
SCHEMES In most additive knapsack systems the encryption
operation works as follows: Suppose Bob wants to
INTRODUCTION: The knapsack problem origi- send a binary x = (x1 , x2 , . . . , xn ) message to Alice,
and Alice™s public key is a = (a1 , a2 , . . . , an ). To en-
nates from operational research. Suppose one
wants to transport some goods which have a given crypt the message Bob computes the ciphertext
economical value and a given size (e.g., volume). (see cryptosystem):
The transportation medium, for example a truck, n
is however limited in size. The question then is S= xi · ai (2)
to maximize the total economical value to trans- i=1
port, given the size limitations of the transporta-
which he sends to Alice. So this de¬nes an encryp-
tion medium.
tion function Ea (·) that maps x into S.
The above mentioned knapsack problem is not
Since the encryption key is public and S can be
the one that was proposed for cryptographic pur-
eavesdropped, it must be “dif¬cult” to ¬nd x from
poses. The one used is only a special case namely,
S and a. This problem is the subset sum problem,
the one in which the economical value of each
which is an NP-complete problem. So, no ef¬cient
good is equal to its size. This special problem is
polynomial time algorithm exist to ¬nd x in the
known as the subset sum problem [24]. Merkle and
worst case (over all S and a). So it seemed that
Hellman initiated the use of the subset problem”
breaking the cryptographic knapsack was hard. It
which they called knapsack”for cryptographic
is important to notice the term “worst case.” In-
deed if a = (1, 2, 4, 8, . . . , 2n’1 ) it is trivial to ¬nd
for all S the corresponding x, by writing S in bi-
DEFINITION 1. In the subset sum problem n in-
nary form. Sequences a for which it is easy to
tegers ai are given (the size of n goods). Given a cer-
¬nd, for all S, its corresponding x, have been called
tain integer (the size of the transportation medium)
S, the problem is to decide whether a subset of the
To allow unique decryption, the encryption func-
n numbers exist such that by adding them together
tion Ea (·) has to be one-to-one. Shamir [47] called
one obtains S, formally to decide/¬nd (whether
a sequence a that leads to such a one-to-one en-
there are) bits xi such that:
cryption function a one-to-one system. It is co-NP-
S= xi · ai . (1) complete to decide whether a given sequence is a
one-to-one system [47].

The problem to decide whether such a subset ex-
The Decryption
ists is NP-complete [24].
For now on, when the “the knapsack problem”
If a is chosen randomly by Alice, there is no known
is mentioned, it is used as a synonym for “the sub-
method for her to decrypt S and ¬nd the plaintext
set sum problem”. Note that there is also a subset
(see cryptosystem). To allow this, Merkle and Hell-
product problem, which was used in the so-called
man [38] introduced some trapdoor (see trapdoor
multiplicative public key knapsack cryptographic
one-way function). The secret information used to
systems [38]. The multiplicative knapsack and its

<< . .

. 3
( : 6)

. . >>