VALENTINE: Why then, I would resort to her by night.DUKE: Ay, but the doors be lock'd and keys kept safe,That no man hath recourse to her by night. VALENTINE: What lets but one may enter at her window? | ||
| --The Two Gentlemen of Verona, III, i, 110–113. | ||
Key management refers to the distribution of cryptographic keys; the mechanisms used to bind an identity to a key; and the generation, maintenance, and revoking of such keys. We assume that identities correctly define principals—that is, a key bound to the identity “Bob” is really Bob's key. Alice did not impersonate Bob's identity to obtain it. Chapter 14, “Representing Identity,” discusses the problem of identifiers naming principals; Chapter 12, “Authentication,” discusses a principal authenticating herself to a single system. This chapter assumes that authentication has been completed and that identity is assigned. The problem is to propagate that authentication to other principals and systems.
We first discuss authentication and key distribution. Next comes key generation and the binding of an identity to a key using certificates. Next, we discuss key storage and revocation. We conclude with digital signatures.
A word about notation. The statement
X → Y : { Z } k
means that entity X sends entity Y a message Z enciphered with key k. Subscripts to keys indicate to whom the keys belong, and are written where multiple keys are in use. For example, kAlice and kBob refer to keys belonging to Alice and Bob, respectively. If Alice and Bob share a key, that key will be written as kAlice,Bob when the sharers are not immediately clear from the context. In general, k represents a secret key (for a classical cryptosystem), e a public key, and d a private key (for a public key cryptosystem). If multiple messages are listed sequentially, they are concatenated and sent. The operator a || b means that the bit sequences a and b are concatenated.
We distinguish between a session key and an interchange key [1024].
Definition 10–1. An interchange key is a cryptographic key associated with a principal to a communication. A session key is a cryptographic key associated with the communication itself.
This distinction reflects the difference between a communication and a user involved in that communication. Alice has a cryptographic key used specifically to exchange information with Bob. This key does not change over interactions with Bob. However, if Alice communicates twice with Bob (and “communication” can be with, for example, an e-mail or a Web browser), she does not want to use the same key to encipher the messages. This limits the amount of data enciphered by a single key and reduces the likelihood of an eavesdropper being able to break the cipher. It also hinders the effectiveness of replay attacks. Instead, she will generate a key for that single session. That key enciphers the data only; it does not authenticate either principal, and it is discarded when the session ends. Hence, the name “session key.”
Session keys also prevent forward searches [923]. A forward search attack occurs when the set of plaintext messages is small. The adversary enciphers all plaintexts using the target's public key. When ciphertext is intercepted, it is compared with the precomputed texts. This quickly gives the corresponding plaintext. A randomly generated session key, used once, would prevent this attack. (See Exercise 2 for another approach.)
An interchange key is associated with a principal. Alice can use the key she shares with Bob to convince Bob that the sender is Alice. She uses this key for all sessions. It changes independently of session initiation and termination.
The goal of key exchange is to enable Alice to communicate secretly to Bob, and vice versa, using a shared cryptographic key. Solutions to this problem must meet the following criteria.
The key that Alice and Bob are to share cannot be transmitted in the clear. Either it must be enciphered when sent, or Alice and Bob must derive it without an exhange of data from which the key can be derived. (Alice and Bob can exchange data, but a third party cannot derive the key from the data exchanged.)
Alice and Bob may decide to trust a third party (called “Cathy” here).
The cryptosystems and protocols are publicly known. The only secret data is to be the cryptographic keys involved.
Classical cryptosystems and public key cryptosystems use different protocols.
Suppose Alice and Bob wish to communicate. If they share a common key, they can use a classical cryptosystem. But how do they agree on a common key? If Alice sends one to Bob, Eve the eavesdropper will see it and be able to read the traffic between them.
To avoid this bootstrapping problem, classical protocols rely on a trusted third party, Cathy. Alice and Cathy share a secret key, and Bob and Cathy share a (different) secret key. The goal is to provide a secret key that Alice and Bob share. The following simple protocol provides a starting point [888].
Alice → Cathy: { request for session key to Bob }kAlice
Cathy → Alice: { ksession }kAlice { ksession }kBob
Alice → Bob: { ksession }kBob
Bob now deciphers the message and uses ksession to communicate with Alice.
This particular protocol is the basis for many more sophisticated protocols. However, Bob does not know to whom he is talking. Assume that Alice sends Bob a message (such as “Deposit $500 in Dan's bank account today”) enciphered under ksession. If Eve records the second message in the exchange above, and the message enciphered under ksession, she can send Bob the message { ksession }kBob followed by the message enciphered under ksession. Bob will not know who is sending it.
Avoiding problems such as this replay attack adds considerable complexity. Key exchange protocols typically add, at a minimum, some sort of authentication and defense against replay attack. One of the best-known such protocols is the Needham-Schroeder protocol [764].
Alice → Cathy : { Alice || Bob || rand1 }
Cathy → Alice : { Alice || Bob || rand1 || ksession, {Alice || ksession} kBob } kAlice
Alice → Bob : { Alice || ksession } kBob
Bob → Alice : { rand2 } ksession
Alice → Bob : { rand2 – 1 }ksession
In this protocol, rand1 and rand2 are two numbers generated at random, except that they cannot repeat between different protocol exchanges. These numbers are called nonces. (If Alice begins the protocol anew, her rand1 in the first exchange will not have been used there before.) The basis for the security of this protocol is that both Alice and Bob trust Cathy.
When Bob receives the third message and deciphers it, he sees that the message names Alice. Since he could decipher the message, the message was enciphered using a key he shares only with Cathy. Because he trusts Cathy not to have shared the key kBob with anyone else, the message must have been enciphered by Cathy. This means that Cathy is vouching that she generated ksession so Bob could communicate with Alice. So Bob trusts that Cathy sent the message to Alice, and that Alice forwarded it to him.
However, if Eve recorded the message, she could have replayed it to Bob. In that case, Eve would not have known the session key, so Bob sets out to verify that his unknown recipient does know it. He sends a random message enciphered by ksession to Alice. If Eve intercepts the message, she will not know what to return; should she send anything, the odds of her randomly selecting a message that is correct is very low and Bob will detect the attempted replay. But if Alice is indeed initiating the communication, when she gets the message she can decipher it (because she knows ksession), apply some fixed function to the random data (here, decrement it by 1), and encipher the result and return it to Bob. Then Bob will be sure he is talking to Alice.
Alice needs to convince herself that she is talking to Bob, also. When she receives the second message from Cathy, she deciphers it and checks that Alice, Bob, and rand1 are present. This tells her that Cathy sent the second message (because it was enciphered with kAlice, which only she and Cathy know) and that it was a response to the first message (because rand1 is in both the first and second messages). She obtains the session key and forwards the rest to Bob. She knows that only Bob has ksession, because only she and Bob can read the messages containing that key. So when she receives messages enciphered with that key, she will be sure that she is talking to Bob.
The Needham-Schroeder protocol assumes that all cryptographic keys are secure. In practice, session keys will be generated pseudorandomly. Depending on the algorithm used, it may be possible to predict such keys. Denning and Sacco [277] assumed that Eve could obtain a session key and subverted the protocol. Assume that the protocol above took place. Then:
Eve → Bob : { Alice || ksession } kBob
Bob → Alice : { rand3 } ksession [intercepted by Eve]
Eve → Bob : { rand3 – 1 }ksession
Now Bob thinks he is talking to Alice. He is really talking to Eve.
Denning and Sacco suggest using timestamps to enable Bob to detect this replay. Applying their method to the Needham-Schroeder protocol yields
Alice → Cathy : { Alice || Bob || rand1 }
Cathy → Alice : { Alice || Bob || rand1 || ksession || {Alice || T || ksession} kBob } kAlice
Alice → Bob : { Alice || T || ksession } kBob
Bob → Alice : { rand2 } ksession
Alice → Bob : { rand2 – 1 }ksession
where T is a timestamp. When Bob gets the message in step 3, he rejects it if the timestamp is too old (too old being determined from the system in use). This modification requires synchronized clocks. Denning and Sacco note that a principal with a slow clock is vulnerable to a replay attack. Gong [406] adds that a party with a fast clock is also vulnerable, and simply resetting the clock does not eliminate the vulnerability.
The Otway-Rees protocol [791] corrects these problems[1] by avoiding the use of timestamps.
Alice → Bob : num, Alice, Bob, { rand1, num, Alice, Bob }kAlice
Bob → Cathy : num || Alice || Bob, || { rand1 || num || Alice || Bob }kAlice || {rand2 || num || Alice || Bob }kBob
Cathy → Bob : num, { rand1 || ksession }kAlice { rand2 || ksession } kBob
Bob → Alice : num, { rand1 || ksession }kAlice
The purpose of the integer num is to associate all messages with a particular exchange. Again, consider the elements of the protocol.
When Alice receives the fourth message from Bob, she checks that the num agrees with the num in the first message that she sent to Bob. If so, she knows that this is part of the exchange. She also trusts that Cathy generated the session key because only Cathy and Alice know kAlice, and the random number rand1 agrees with what Alice put in the enciphered portion of the message. Combining these factors, Alice is now convinced that she is talking to Bob.
When Bob receives the message from Cathy, he determines that the num corresponds to the one he received from Alice and sent to Cathy. He deciphers that portion of the message enciphered with his key, and checks that rand2 is what he sent. He then knows that Cathy sent the reply, and that it applies to the exchange with Alice.
Because no timestamps are used, the synchronization of the system clocks is irrelevant. Now suppose that Eve acquired an old session key and the message in 3.
She forwards that message to Alice. Alice immediately rejects it if she has no ongoing key exchanges with Bob. If she does, and num does not match, she rejects Eve's message. The only way Eve could impersonate Bob is if she acquired ksession for an ongoing exchange, recorded the third message, and resent the relevant portion to Alice before Bob could do so. In that case, however, Eve could simply listen to the traffic, and no replay would be involved.
Kerberos [589, 967] uses the Needham-Schroeder protocol as modified by Denning and Sacco. A client, Alice, wants to use a server S. Kerberos requires her to use two servers to obtain a credential that will authenticate her to S. First Alice must authenticate herself to the Kerberos system; then she must obtain a ticket to use S (see next paragraph). (This separates authentication of the user to the issuer of tickets and the vouching of identity to S.)
The basis of Kerberos is a credential known as the ticket. It contains[2]
TAlice,Barnum = Barnum || {Alice || Alice address || valid time || kAlice,Barnum}kBarnum
In this ticket, kBarnum is the key that Barnum shares with the authentication server, and kAlice,Barnum is the session key that Alice and Barnum will share. The valid time is the time interval during which the ticket is valid, which is typically several hours. The ticket is the issuer's voucher for the identity of the requester of the service.
The authenticator contains the identity of the sender of a ticket and is used when Alice wants to show Barnum that the party sending the ticket is the same as the party to whom the ticket was issued. It contains[3]
AAlice,Barnum = {Alice || generation time || kt}kAlice,Barnum
where kAlice,Barnum is the session key that Alice and Barnum share, kt is an alternative session key, and the authenticator was created at generation time. Alice generates an authenticator whenever she sends a ticket. She sends both the ticket and the authenticator in the same message.
Alice's goal is to print a file using the service Guttenberg. The authentication server is Cerberus and the ticket-granting server is Barnum. The Kerberos (Version 5) protocol proceeds as follows.
Alice → Cerberus: Alice || Barnum
Cerberus → Alice : { kAlice,Barnum} kAlice || TAlice,Barnum
At this point, Alice deciphers the first part of the message to obtain the key she will use to communicate with Barnum. Kerberos uses the user's password as the key, so if Alice enters her password incorrectly, the decipherment of the session key will fail. These steps occur only at login; once Alice has the ticket for the ticket-granting server Barnum, she caches it and uses it:
Alice → Barnum : Guttenberg || AAlice,Barnum || TAlice,Barnum
Barnum → Alice : Alice || {kAlice,Guttenberg} kAlice,Barnum || TAlice,Guttenberg
Alice → Guttenberg : AAlice,Guttenberg || TAlice,Guttenberg
Guttenberg → Alice : { t + 1} kAlice,Guttenberg
In these steps, Alice first constructs an authenticator and sends it, with the ticket and the name of the server, to Barnum. Barnum validates the request by comparing the data in the authenticator with the data in the ticket. Because the ticket is enciphered using the key Barnum shares with Cerberus, he knows that it came from a trusted source. He then generates an appropriate session key and sends Alice a ticket to pass on to Guttenberg. Step 5 repeats step 3, except that the name of the service is not given (because Guttenberg is the desired service). Step 6 is optional; Alice may ask that Guttenberg send it to confirm the request. If it is sent, t is the timestamp.
Bellovin and Merritt [76] discuss several potential problems with the Kerberos protocol. In particular, Kerberos relies on clocks being synchronized to prevent replay attacks. If the clocks are not synchronized, and if old tickets and authenticators are not cached, replay is possible. In Kerberos 5, authenticators are valid for 5 minutes, so tickets and authenticators can be replayed within that interval. Also, because the tickets have some fixed fields, a dictionary attack can be used to determine keys shared by services or users and the ticket-granting service or the authentication service, much as the WordPerfect cipher was broken (see the end of Section 9.2.2.1). Researchers at Purdue University used this technique to show that the session keys generated by Kerberos 4 were weak; they reported deciphering tickets, and finding session keys, within minutes [306].
Conceptually, public key cryptography makes exchanging keys very easy.
Alice → Bob : { ksession } eBob
where eBob is Bob's public key. Bob deciphers the message and obtains the session key ksession. Now he and Alice can communicate securely, using a classical cryptosystem.
As attractive as this protocol is, it has a similar flaw to our original classical key exchange protocol. Eve can forge such a message. Bob does not know who the message comes from.
One obvious fix is to sign the session key.
Alice → Bob : Alice, { { ksession } dAlice } eBob
where dAlice is Alice's private key. When Bob gets the message, uses his private key to decipher the message. He sees the key is from Alice. Alice uses her public key to obtain the session key. Schneier [888] points out that Alice could also include a message enciphered with ksession.
These protocols assume that Alice has Bob's public key eBob. If not, she must get it from a public server, Peter. With a bit of ingenuity, Eve can arrange to read Bob's messages to Alice, and vice versa.
Alice → Peter : { send me Bob's public key } [ intercepted by Eve ]
Eve → Peter : { send me Bob's public key }
Peter → Eve : eBob
Eve → Alice : eEve
Alice → Bob : { ksession } eEve [ intercepted by Eve ]
Eve → Bob : { ksession } eBob
Eve now has the session key and can read any traffic between Alice and Bob. This is called a man-in-the-middle attack and illustrates the importance of identification and authentication in key exchange protocols. The man-in-the-middle attack works because there is no binding of identity to a public key. When presented with a public key purportedly belonging to Bob, Alice has no way to verify that the public key in fact belongs to Bob. This issue extends beyond key exchange and authentication. To resolve it, we need to look at the management of cryptographic keys.
The secrecy that cryptosystems provide resides in the selection of the cryptographic key. If an attacker can determine someone else's key, the attacker can read all traffic enciphered using that key or can use that key to impersonate its owner. Hence, generating keys that are difficult to guess or to determine from available information is critical.
This raises the issue of randomness. Given a set K of potential keys, the probability of a key being guessed is at a minimum when the key is selected at random from the elements of K. The problem of selecting such a key is equivalent to generating a random number between 0 and |K| – 1, inclusive (see Exercise 1). Typically, many keys are required, so a sequence of random numbers is needed.
Definition 10–2. A sequence of cryptographically random numbers is a sequence of numbers n1, n2, ... such that for any positive integer k, an observer cannot predict nk even if n1, ..., nk–1 are known.
A random number generator requires a physical source of randomness, such as background radiation or some other quantifiable physical phenomenon. For example, in 1955 the RAND Corporation published a table of one million random digits obtained from measuring random pulses [828]. Other mechanisms use electromagnetic phenomena [12, 338] or characteristics of the physical computing environment such as disk latency [261, 319, 602]. Because mechanisms for doing this are often not available, computers use algorithms to generate sequences of numbers that act as though they were random.
Definition 10–3. A sequence of cryptographically pseudorandom numbers is a sequence of numbers intended to simulate a sequence of cryptographically random numbers but generated by an algorithm.
When we say “random numbers” and “pseudorandom numbers” without any further qualification, we mean cryptographically random and pseudorandom numbers.
Creating such generators is difficult [797]. A common method of generating pseudorandom numbers is by a linear congruential generator
nk = (ank–1 + b) mod n
where a and b are parameters, n is the period of the sequence, and a, b, and n are relatively prime. Reeds [834] and Boyer [139, 140] show how to determine a and b given some numbers from the sequence. The obvious generalization, a polynomial congruential generator:
nk = (aj xk–1j + ... + a1xk–1 + a0) mod n
has also been broken [595].
The best software pseudorandom number generators are mixing functions.
Definition 10–4. [319] A strong mixing function is a function of two or more inputs that produces an output each bit of which depends on some nonlinear function of all the bits of the input.
The Data Encryption Standard (DES) is an example of a strong mixing function. It takes 120 bits of input (64 message bits and 56 input bits) and produces 64 output bits. The dependence of the output bits on the input bits is complex and nonlinear. The hash functions MD4 and MD5 are other good examples, taking any number of input bits and producing 128 output bits. SHA-1 is another, producing 160 output bits from an arbitrary set of input bits.
The initial input to the mixing function must be unpredictable and irreproducible. Random numbers are best, but if they cannot be obtained, lots of data obtained from highly variable sources often suffices.
Because classical cryptosystems use shared keys, it is not possible to bind an identity to a key. Instead, two parties need to agree on a shared key. Section 10.2, “Key Exchange,” presents protocols that do this.
Public key cryptosystems use two keys, one of which is to be available to all. The association between the cryptographic key and the principal is critical, because it determines the public key used to encipher messages for secrecy. If the binding is erroneous, someone other than the intended recipient could read the message.
For purposes of this discussion, we assume that the principal is identified by a name of some acceptable sort (Chapter 14, “Representing Identity,” discusses this issue in more detail) and has been authenticated to the entity that generates the cryptographic keys. The question is how some (possibly different) principal can bind the public key to the representation of identity.
An obvious idea is for the originator to sign the public key with her private key, but this merely pushes the problem to another level, because the recipient would only know that whoever generated the public key also signed it. No identity is present.
Kohnfelder [579] suggests creating a message containing a representation of identity, the corresponding public key, and a timestamp, and having a trusted authority sign it.
CAlice = { eAlice || Alice || T } dCathy
This type of structure is called a certificate.
Definition 10–5. A certificate is a token that binds an identity to a cryptographic key.
When Bob wants to communicate with Alice, he obtain's Alice's certificate CAlice. Assuming that he knows Cathy's public key, he can decipher the certificate. He first checks the timestamp T to see when the certificate was issued. (From this, he can determine if the certificate is too old to be trusted; see below.) He looks at the subject entity (Alice, to whom the certificate was issued). The public key in the certificate belongs to that subject, so Bob now has Alice's public key. He knows that Cathy signed the certificate and therefore that Cathy is vouching to some degree that the public key belongs to Alice. If he trusts Cathy to make such a determination, he accepts the public key as valid and belonging to Alice.
One immediate problem is that Bob must know Cathy's public key to validate the certificate. Two approaches deal with this problem. The first, by Merkle, eliminates Cathy's signature; the second structures certificates into signature chains.
Merkle [697] notes that certificates can be kept as data in a file. Changing any certificate changes the file. This reduces the problem of substituting faked certificates to a data integrity problem. Cryptographic hash functions create checksums that reveal changes to files. Merkle uses the same approach.
Let Yi be an identifier and its associated public key, and let Y1, ..., Yn be stored in a file. Define a function f: D × D → D, where D is a set of bit strings. Let h: N × N → D be a cryptographic hash function.
The hash of the entire file (called the root) is h(1, n). Drawn as a diagram, the recursion creates a tree structure of the hashes (see Figure 10-1).
Figure 10-1. A representation of the recursion involved in Merkle's scheme for a file with four identity and public key pairs. The hash of the file is h(1, 4), and this is known to all parties.
Under Merkle's scheme, the ancillary hashes needed to validate a certificate are called the authentication path. In the example above, the authentication path of Y3 is Y3, h(4, 4), and h(1, 2). The authentication path forms the certificate C3.
Merkle's scheme requires only that the root value be known and that the file be publicly available. If any identity and public key pair is compromised, then the root value will be incorrect and this will be detected during validation. However, if anyone changes their public key, the root value must be recomputed and redistributed.
Merkle's scheme is important because it examines certification hierarchies and suggests a mechanism that does not use public key signatures to create certificates. However, the need to have the file available so the root value can be recomputed at will makes this scheme impractical for networks involving large numbers of certificates on widely separated systems.
The usual form of certification is for the issuer to encipher a hash of the identity of the subject (to whom the certificate is issued), the public key, and information such as time of issue or expiration using the issuer's private key. To validate the certificate, a user uses the issuer's public key to decipher the hash and check the data in the certificate. The user trying to validate the certificate must obtain the issuer's public key. If the issuer has a certificate, the user can get that key from the issuer's certificate. This pushes the problem to another level: how can the issuer's certificate be validated?
Two approaches to this problem are to construct a tree-like hierarchy, with the public key of the root known out of band, or to allow an arbitrary arrangement of certifiers and rely on each individual's knowledge of the certifiers. First, we examine X.509, which describes certificates and certification in general. We then look at the PGP certification structure.
X.509—the Directory Authentication Framework [512] is the basis for many other protocols. It defines certificate formats and certification validation in a generic context. Soon after its original issue in 1988, I'Anson and Mitchell [506] found problems with both the protocols and the certificate structure. These problems were corrected in the 1993 version, referred to as X.509v3.
The X.509v3 certificate has the following components [960].
Version. Each successive version of the X.509 certificate has new fields added. If fields 8, 9, and 10 (see below) are present, this field must be 3; if fields 8 and 9 are present, this field is either 2 or 3; and if none of fields 8, 9, and 10 are present, the version number can be 1, 2, or 3.
Serial number. This must be unique among the certificates issued by this issuer. In other words, the pair (issuer's Distinguished Name, serial number) must be unique.
Signature algorithm identifier. This identifies the algorithm, and any parameters, used to sign the certificate.
Issuer's Distinguished Name. This is a name that uniquely identifies the issuer. See Chapter 14, “Representing Identity,” for a discussion.
Validity interval. This gives the times at which the certificate becomes valid and expires.
Subject's Distinguished Name. This is a name that uniquely identifies the subject to whom the certificate is issued. See Chapter 14, “Representing Identity,” for a discussion.
Subject's public key information. This identifies the algorithm, its parameters, and the subject's public key.
Issuer's unique identifier (Version 2 and 3 certificates only). Under some circumstances, issuer Distinguished Names may be recycled (for example, when the Distinguished Name refers to a role, or when a company closes and a second company with the same Distinguished Name opens). This field allows the issuer to disambiguate among entities with the same issuer name.
Subject's unique identifier (Version 2 and 3 certificates only). This field is like field 8, but for the subject.
Extensions (Version 3 certificates only). X.509v3 defines certain extensions in the areas of key and policy information, certification path constraints, and issuer and subject information. For example, if an issuer has multiple certification keys, the “authority key identifier” allows the certificate to indicate which key should be used. The “basic constraints” extension indicates if the certificate holder can issue certificates.
Signature. This field identifies the algorithm and parameters used to sign the certificate, followed by the signature (an enciphered hash of fields 1 to 10) itself.
To validate the certificate, the user obtains the issuer's public key for the particular signature algorithm (field 3) and deciphers the signature (field 11). She then uses the information in the signature field (field 11) to recompute the hash value from the other fields. If it matches the deciphered signature, the signature is valid if the issuer's public key is correct. The user then checks the period of validity (field 5) to ensure that the certificate is current.
Definition 10–6. A certification authority (CA) is an entity that issues certificates.
If all certificates have a common issuer, then the issuer's public key can be distributed out of band. However, this is infeasible. For example, it is highly unlikely that France and the United States could agree on a single issuer for their organizations' and citizens' certificates. This suggests multiple issuers, which complicates the process of validation.
Suppose Alice has a certificate from her local CA, Cathy. She wants to communicate with Bob, whose local CA is Dan. The problem is for Alice and Bob to validate each other's certificates.
Assume that X<<Y>> represents the certificate that X generated for the subject Y (X is the CA that issued the certificate). Bob's certificate is Dan<<Bob>>. If Cathy has issued a certificate to Dan, Dan has a certificate Cathy<<Dan>>; similarly, if Dan has issued a certificate to Cathy, Cathy has a certificate Dan<<Cathy>>. In this case, Dan and Cathy are said to be cross-certified.
Definition 10–7. Two CAs are cross-certified if each has issued a certificate for the other.
Because Alice has Cathy's (trusted) public key, she can obtain Cathy<<Dan>> and form the signature chain
Cathy<<Dan>> Dan<<Bob>>
Because Alice can validate Dan's certificate, she can use the public key in that certificate to validate Bob's certificate. Similarly, Bob can acquire Dan<<Cathy>> and validate Alice's certificate.
Dan<<Cathy>> Cathy<<Alice>>
Signature chains can be of arbitrary length. The only requirement is that each certificate can be validated by the one before it in the chain. (X.509 suggests organizing CAs into a hierarchy to minimize the lengths of certificate signature chains, but this is not a requirement.)
Certificates can be revoked, or canceled. A list of such certificates enables a user to detect, and reject, invalidated certificates. Section 10.5.2 discusses this.
PGP is an encipherment program widely used to provide privacy for electronic mail throughout the Internet, and to sign files digitally. It uses a certificate-based key management infrastructure for users' public keys. Its certificates and key management structure differ from X.509's in several ways. Here, we describe OpenPGP's structure [167]; but much of this discussion also applies to other versions of PGP.
An OpenPGP certificate is composed of packets. A packet is a record with a tag describing its purpose. A certificate contains a public key packet followed by zero or more signature packets. An OpenPGP public key packet has the following structure.
Version. This is either 3 or 4. Version 3 is compatible with all versions of PGP; Version 4 is not compatible with old (Version 2.6) versions of PGP.
Time of creation. This specifies when the certificate was created.
Validity period. (Version 3 only). This gives the number of days that the certificate is valid. If it is 0, the certificate does not expire.
Public key algorithm and parameters. This identifies the algorithm used and gives the parameters for the cryptosystem used. Version 3 packets contain the modulus for RSA (see Section 9.3.2). Version 4 packets contain the parameters appropriate for the cryptosystem used.
Public key. This gives the public key. Version 3 packets contain the exponent for RSA. Version 4 packets contain the public key for the cryptosystem identified in field 4.
The information in an OpenPGP signature packet is different for the two versions. Version 3 contains the following.
Version. This is 3.
Signature type. This describes the specific purpose of the signature and encodes a level of trust (see Section 14.5.3, “Trust”). For example, signature type 0x11 says that the signer has not verified that the public key belongs to the named subject.
Creation time. This specifies the time at which the fields following were hashed.
Key identifier of the signer. This specifies the key used to generate the signature.
Public key algorithm. This identifies the algorithm used to generate the signature.
Hash algorithm. This identifies the algorithm used to hash the signature before signing.
Part of signed hash value. After the data is hashed, field 2 is given the time at which the hash was computed, and that field is hashed and appended to the previous hash. The first two bytes are placed into this field. The idea is that the signature can be rejected immediately if the first two bytes hashed during the validation do not match this field.
Signature. This contains the encipherment of the hash using the signer's private key.
A Version 4 signature packet is considerably more complex, but as a Version 3 signature packet does, it binds a signature to an identifier and data. The interested reader is referred to the OpenPGP specifications [167].
PGP certificates differ from X.509 certificates in several important ways. Unlike X.509, a single key may have multiple signatures. (All Version 4 PGP keys are signed by the owner; this is called self-signing.) Also unlike X.509, a notion of “trust” is embedded in each signature, and the signatures for a single key may have different levels of trust. The users of the certificates can determine the level of trust for each signature and act accordingly.
In the example above, Alice followed two signature chains:
Henry<<Henry>> Henry<<Giselle>> Giselle<<Bob>>
and
Jack<<Ellen>> Ellen<<Bob>>
(where the unchecked signatures have been dropped). The trust levels affected how Alice checked the certificate.
A subtle distinction arises here between X.509 and PGP certificates. X.509 certificates include an element of trust, but the trust is not indicated in the certificate. PGP certificates indicate the level of trust, but the same level of trust may have different meanings to different signers. Chapter 14, “Representing Identity,” will examine this issue in considerable detail.
The deployment and management of public keys is complex because of the different requirements of various protocols. Most protocols use some form of the X.509v3 certificates, although the extensions vary. The infrastructure that manages public keys and certification authorities is called a public key infrastructure. Several such infrastructures are in place, such as the PGP Certificate Servers and the commercial certificate issuers for World Wide Web browsers.
Key storage arises when a user needs to protect a cryptographic key in a way other than by remembering it. If the key is public, of course, any certificate-based mechanism will suffice, because the goal is to protect the key's integrity. But secret keys (for classical cryptosystems) and private keys (for public key cryptosystems) must have their confidentiality protected as well.
Protecting cryptographic keys sounds simple: just put the key into a file, and use operating system access control mechanisms to protect it. Unfortunately, as we will discuss in Chapter 23, operating system access control mechanisms can often be evaded or defeated, or may not apply to some users. On a single-user system, this consideration is irrelevant, because no one else will have access to the system while the key is on the system. On a multiuser system, other users have access to the system. On a networked system, an attacker could trick the owner into downloading a program that would send keystrokes and files to the attacker, thereby revealing the confidential cryptographic key. We consider these systems.
On such systems, enciphering the file containing the keys will not work, either. When the user enters the key to decipher the file, the key and the contents of the file will reside in memory at some point; this is potentially visible to other users on a multiuser system. The keystrokes used to decipher the file could be recorded and replayed at a later date. Either will compromise the key.
A feasible solution is to put the key onto one or more physical devices, such as a special terminal, ROM, or smart card [268, 321, 665]. The key never enters the computer's memory. Instead, to encipher a message, the user inserts the smart card into a special device that can read from, and write to, the computer. The computer sends it the message to be protected, and the device uses the key on the smart card to encipher the message and send it back to the computer. At no point is the cryptographic key exposed.
A variant relies on the observation that if the smart card is stolen, the thief has the cryptographic key. Instead of having it on one card, the key is split over multiple devices (two cards, a card and the physical card reader, and so on.) Now, if a thief steals one of the cards, the stolen card is useless because it does not contain the entire key.
As the previous discussion implies, keys can belong to roles.
A reasonable concern is how one recovers the key if it is lost, or if the people who know it are unable or unwilling to reveal it. Three alternatives arise: either the key or the cryptosystem can be weak, or a copy of the key can be placed somewhere.
Definition 10–8. A key escrow system is a system in which a third party can recover a cryptographic key.
The contexts in which key escrow arises are business (recovery of backup keys, for example) and law enforcement (recovery of keys used to encipher communications to which an authority requires access, such as enciphered letters or telephone messages). Beth et al. [91] identify five desirable properties or goals.
The escrow system should not depend on the encipherment algorithm. The escrow techniques should work regardless of how the messages are enciphered.
Privacy protection mechanisms must work from one end to the other and be part of the user interface. This protects the user's privacy unless the escrowed keys are used, and then only those who have the escrowed keys can access the messages.
Requirements (legal or business) must map to the key exchange protocol. This prevents a user from enciphering a message and then entering it directly into the communications channel, bypassing the escrow system.
A system supporting key escrow must require that all parties authenticate themselves. In particular, if a principal uses the escrowed keys, the system must ensure that the principal is authenticated not only by name but also by the time and place of the principal and by any equipment used in the interception and the decipherment. This protects against unauthorized parties using escrowed keys.
If the message is to be observable for a limited time, the key escrow system must ensure that the keys are valid for that interval exactly (no more and no less).
Key escrow systems consist of a user security component, a key escrow component, and a data recovery component [273]. The user security component does the encryption and decryption as well as supports the key escrow component. The key escrow component manages the storage and use of the data recovery keys. The data recovery component does the data recovery.
The most famous key escrow system is the one that the U.S. government's Clipper chip supports.
Although the Clipper chip is the best-known component of the U.S. government's Escrowed Encryption Standard (EES) [746], the system itself is a set of interlocking components designed to balance the need for law enforcement access to enciphered traffic against citizens' right to privacy. How well the system achieves this balance is left for the reader to decide in light of his or her philosophies. This section focuses on the technical components only [278].
The key escrow hardware components consist of a chip called “Clipper,” which is used to prepare the per-message escrow information, and a device called the Key Escrow Decrypt Processor (KEDP). The chip is placed into the user security component of each device and is numbered uniquely (this number is called a UID, for “Unique Identifier for Device”). The KEDP is available to agencies authorized to read messages. In addition, a special facility creates the escrow devices and programs the chips, and the key used to access messages is split and the parts given to two different escrow agencies.
Each user security component contains a unique device key kunique and a nonunique family key kfamily in addition to the UID. The user security component uses a classical cipher called Skipjack [749]. Skipjack accepts 64-bit blocks as input and enciphers them into 64-bit output blocks using an 80-bit key. (The details of Skipjack were classified until 1998 [760].) In addition to the enciphered message, the user security component generates a Law Enforcement Access Field (LEAF) of 128 bits, containing
{ UID || {ksession } kunique || hash } kfamily
where hash is a 16-bit authenticator generated from the session key and an initialization vector [123]. This is transmitted with the message.
The user component chip is programmed in a secure facility. Two escrow agents, one from each of the two key escrow agencies, are present. In addition, a set of family key components has been generated.
Each escrow agent independently supplies a random seed and key number. The family key components are combined to form kfamily , and the key numbers are combined to make a key component enciphering key kcomp. The random seeds are mixed with additional random data to generate a sequence of keys kunique for the chips being created. Each chip is imprinted with the UID, the kunique for that chip, and a copy of kfamily.
When kunique is created, the key generator creates two additional key components ku1 and ku2, where ku1 ⊕ ku2 = kunique. These components are enciphered under the key component key kcomp. The first escrow agent is given { ku1 } kcomp, and the second is given { ku2 } kcomp. The escrow agents take these encrypted key components to their respective agencies.
When Alice obtains legal authorization to read a message, she first runs the LEAF through the KEDP. The KEDP knows kfamily , so it can validate the contents of the LEAF and obtain the UID for the sending device. Alice takes the authorization and the UID to each of the two escrow agencies. They verify that the authorization is valid (using whatever procedures are appropriate), and each brings its encrypted key component and the corresponding key numbers. The components, LEAF, and key numbers are loaded onto the KEDP. The KEDP uses the key numbers to generate kcomp, uses kcomp to obtain ku1 and ku2, and exclusive-or's ku1 and ku2 to obtain kunique. The KEDP then extracts the appropriate 80 bits of the LEAF and deciphers them to obtain the session key ksession. Because that key enciphers the message, the message can now be read.
Blaze has pointed out an interesting way to defeat the key escrowing [123]. He noticed that the hash component of the LEAF was only 16 bits long. This means that out of the 2128 possible LEAFs, 2112 will have a valid checksum. Of these, only one has the actual session key and UID. An attacker could generate a LEAF with a valid checksum but an incorrect session key and UID, thereby defeating the decipherment efforts of the party authorized to obtain the session key. Blaze ran some experiments, and found that the expected time to generate such a LEAF was 42 minutes. Although too slow for telephonic applications, it is very feasible for an application such as electronic mail. Denning and Smid [278] also have pointed out that deployed devices would have countermeasures, such as a counter of the number of times an invalid LEAF was presented, that would defeat Blaze's trial-and-error method.
The Encrypted Key Escrow system meets the first four goals of a key escrow system (see Section 10.5.1.1). Unfortunately, it fails on the fifth. The problem is that kunique is fixed for each unit, so if an authority obtains that key, he can read any message enciphered by the device, with or without authorization.
Ganesan [381] developed a key escrow system meeting the five requirements. This system, Yaksha, is based on the RSA cryptosystem and a central server. The central server will generate session keys, which it can provide on demand to appropriate authorities (or which it can destroy).
In this system, each user has two private keys derived from the original RSA key. Let nAlice be Alice's modulus. The first private key, dAliceA, is known only to Alice; the second, dAliceY , is known only to the Yaksha server. The keys are related by dAliceAdAliceY = dAlice mod nAlice. Alice's public key is eAlice and is available to all. Bob has similar keys dBobB, dBobY , and eBob.
When Alice wishes to communicate with Bob, she sends a message to Yaksha asking for a session key. The Yaksha server generates a random session key ksession. The server then sends Alice 
. Alice can determine the session key as 
. Similarly, Bob, who receives an analogous message, can recover the session key. The Yaksha server can archive the session key, or delete it, as needed.
This scheme eliminates the problem of an authority acquiring an escrow key and being able to read multiple sessions. Because the session key is random and not reused (a nonce), only the message that it enciphered can be read. This satisfies goal 5. Goal 1 is met if the focus is on the message enciphering algorithms, because the Yaksha system is tied to an RSA interchange with the server. The other requirements can be implemented, if a supporting infrastructure is available; certainly, interaction with the Yaksha server requires authentication.
The fifth goal relies on “time.” Both the EES and Yaksha interpret “time” as “sessions.” Others have explored basing escrow systems on the length of time needed to solve some difficult problem. For example, Beth et al. [91] present an escrow system in which the secret key used to generate the session key is not given to the escrow authority, but a related key is. To find the actual key from the related key, the authority must solve an instance of the discrete log problem. Techniques such as this assume that the difficulty of solving a particular problem is relatively constant. With advances in technology, such assumptions must be examined carefully.
Bellare and Rivest [71] have proposed a technique called “translucent cryptography,” in which some fraction f of the messages Alice sends to Bob can be read. Their proposal relies on a cryptographic technique called “oblivious transfer,” in which a message is received with a given probability [70]. This is not a key escrow system, because the keys are not available, but it does serve the ends of such a system in that the messages can be read with a specified probability. The puzzle is the value to which f must be set.
Certificate formats contain a key expiration date. If a key becomes invalid before that date, it must be revoked. Typically, this means that the key is compromised, or that the binding between the subject and the key has changed.
We distinguish this from an expired certificate. An expired certificate has reached a predesignated period after which it is no longer valid. That the lifetime has been exceeded is the only reason. A revoked certificate has been canceled at the request of the owner or issuer for some reason other than expiration.
There are two problems with revoking a public key. The first is to ensure that the revocation is correct—in other words, to ensure that the entity revoking the key is authorized to do so. The second is to ensure timeliness of the revocation throughout the infrastructure. This second problem depends on reliable and highly connected servers and is a function of the infrastructure as well as of the locations of the certificates and the principals who have copies of those certificates. Ideally, notice of the revocation will be sent to all parties when received, but invariably there will be a time lag.
The X.509 and Internet public key infrastructures (PKIs) use lists of certificates.
Definition 10–9. A certificate revocation list is a list of certificates that are no longer valid.
A certificate revocation list contains the serial numbers of the revoked certificates and the dates on which they were revoked. It also contains the name of the issuer, the date on which the list was issued, and when the next list is expected to be issued. The issuer also signs the list [960]. Under X.509, only the issuer of a certificate can revoke it.
PGP allows signers of certificates to revoke their signatures as well as allowing owners of certificates, and their designees, to revoke the entire certificates. The certificate revocation is placed into a PGP packet and is signed just like a regular PGP certificate. A special flag marks it as a revocation message.
As electronic commerce grows, so does the need for a provably high degree of authentication. Think of Alice's signature on a contract with Bob. Bob not only has to know that Alice is the other signer and is signing it; he also must be able to prove to a disinterested third party (called a judge) that Alice signed it and that the contract he presents has not been altered since Alice signed it. Such a construct is called a digital signature.
Definition 10–10. A digital signature is a construct that authenticates both the origin and contents of a message in a manner that is provable to a disinterested third party.
The “proof ” requirement introduces a subtlety. Let m be a message. Suppose Alice and Bob share a secret key k. Alice sends Bob m { m }k (that is, the message and its encipherment under k). Is this a digital signature?
First, Alice has authenticated the contents of the message, because Bob deciphers { m }k and can check that the message matches the deciphered one. Because only Bob and Alice know k, and Bob knows that he did not send the message, he concludes that it has come from Alice. He has authenticated the message origin and integrity. However, based on the mathematics alone, Bob cannot prove that he did not create the message, because he knows the key used to create it. Hence, this is not a digital signature.
Public key cryptography solves this problem. Let dAlice and eAlice be Alice's private and public keys, respectively. Alice sends Bob the message m { m }dAlice. As before, Bob can authenticate the origin and contents of m, but in this situation a judge must determine that Alice signed the message, because only Alice knows the private key with which the message was signed. The judge merely obtains eAlice and computes { { m }dAlice } eAlice. If the result is m, Alice signed it. This is in fact a digital signature.
A digital signature provides the service of nonrepudiation. If Alice claims she never sent the message, the judge points out that the originator signed the message with her private key, which only she knew. Alice at that point may claim that her private key was stolen, or that her identity was incorrectly bound in the certificate (see Chapter 14, “Representing Identity”). The notion of “nonrepudiation” provided here is strictly abstract. In fact, Alice's key might have been stolen, and she might not have realized this before seeing the digital signature. Such a claim would require ancillary evidence, and a court or other legal agency would need to handle it. For the purposes of this section, we consider the service of nonrepudiation to be the inability to deny that one's cryptographic key was used to produce the digital signature.
All classical digital signature schemes rely on a trusted third party. The judge must trust the third party. Merkle's scheme is typical [697].
Let Cathy be the trusted third party. Alice shares a cryptographic key kAlice with Cathy. Likewise, Bob shares kBob with Cathy. When Alice wants to send Bob a contract m, she computes { m }kAlice and sends it to Bob. Bob sends it to Cathy, who deciphers m, enciphers it with kBob, and returns { m }kBob to Bob. He can now decipher it. To verify that Alice sent the message, the judge takes the disputed messages { m }kAlice and { m }kBob and has Cathy decipher them using Alice's and Bob's keys. If they match, the sending is verified; if not, one of them is a forgery.
In our earlier example, we had Alice encipher the message with her private key to produce a digital signature. We now examine two specific systems.
Section 9.3.2 discussed the RSA system. We observe that using it to authenticate a message produces a digital signature. However, we also observe that the strength of the system relies on the protocol describing how RSA is used as well as on the RSA cryptosystem itself.
First, suppose that Alice wants to trick Bob into signing a message m. She computes two other messages m1 and m2 such that m1m2 mod nBob = m. She has Bob sign m1 and m2. Alice then multiplies the two signatures together and reduces mod nBob, and she has Bob's signature on m. (See Exercise 8.) The defense is not to sign random documents and, when signing, never sign the document itself; sign a cryptographic hash of the document [888].
A second problem [32] demonstrates that messages that are both enciphered and signed should be signed first, then enciphered. Suppose Alice is sending Bob her signature on a confidential contract m. She enciphers it first, then signs it:
and sends the result to Bob. However, Bob wants to claim that Alice sent him the contract M. Bob computes a number r such that Mr mod nBob = m. He then republishes his public key as (reBob, nBob). Note that the modulus does not change. Now, he claims that Alice sent him M. The judge verifies this using his current public key. The simplest way to fix this is to require all users to use the same exponent but vary the moduli.
This attack will not work if one signs first and then enciphers. The reason is that Bob cannot access the information needed to construct a new public key, because he would need to alter Alice's public key. (See Exercise 9.)
This scheme is similar to the Diffie-Hellman scheme presented in Section 9.3.1. It relies on the difficulty of solving the discrete logarithm problem. Choose a prime p and two random numbers g and d both less than p. Compute y = gd mod p. The public key is the triplet (y, g, p); the private key is d [324].
Suppose Alice wants to send Bob a signed contract m. She chooses a number k that is relatively prime to p – 1 and has not been used before. She computes a = mk mod p and then uses the Extended Euclidean Algorithm (see Chapter 31) to find b such that
m = (da + kb) mod p – 1
The pair (a, b) is the signature.
To verify the signature, check that
yaab mod p = gm mod p
If someone learns k, the corresponding message m, and the signature (a, b), then she can use the Extended Euclidean Algorithm to recover x, Alice's public key.
Cryptographic infrastructure provides the mechanisms needed to use cryptography. The infrastructure sees to the distribution of keys and the security of the procedures and mechanisms implementing cryptographic algorithms and protocols.
Key exchange and authentication protocols, although distinct in principle, are often combined because the first step in most communications is to prove identity. Exchanging a session key in the process saves another exchange. Both public key and classical cryptosystems can provide authentication and key exchange, provided that the appropriate infrastructure is present.
A key element of such an infrastructure is a mechanism for binding cryptographic keys to identity. This mechanism leads to the distinction between session keys (generated once per session, and associated with that session) and interchange keys (generated once per principal, and associated with that principal). It also leads to certification, in which a representation of identity, along with other information such as expiration time, is cryptographically signed and distributed as a unit. The name of the signer (issuer) is included so that the certificate can be verified.
The mechanism used to sign certificates and other documents is a digital signature. A disinterested third party, called a judge, must be able to confirm or disprove that the (alleged) sender computed the digital signature of the (alleged) signed message.
Session keys require pseudorandom number generation. Of the many algorithms in use, the best are mixing algorithms in which every bit of the output depends on every bit of the input, and no bit can be predicted even if all previous bits are known.
The management of keys involves storing them and revoking them, both of which involve system issues as well as cryptographic ones. Another aspect is the idea of key recovery. Under some circumstances (such as the key holder dying, or a legal order), a principal may need to obtain a key to read enciphered information. Key escrow systems provide this capability, but must meet strict requirements to ensure that they do not permit unauthorized and unlimited access to messages.
All issues discussed in this chapter are under active study. In particular, the design and deployment of public key infrastructures are critical as electronic commerce becomes more common. Unless technical mechanisms are sufficiently robust to support legal enforcement, electronic commerce will not be accepted. Key management mechanisms, in particular, must mimic the noncomputer world's procedures and processes, because they could be used to replace those processes.
Authentication protocols are critical to network use, and it is seductively easy to believe they are correct when they are not. Researchers are creating and testing various logics of authentication to prove protocols correct, or to prove them incorrect and fix them. The results of applying such logics must be interpreted in light of the environment in which the authentication protocol is used. For example, a proof that protocol X authenticates a user is misleading if that user keeps his private key in a file that anyone can read. The integration of system information, and of assumptions, into logics, as well as the development of new logics, are prime topics for research.
Key escrow defeats the confidentiality aspect of cryptographic protocols. Development of escrow, and recovery, systems that minimize the threat of unauthorized users accessing information to which they are not entitled is actively under way. Both classical and public key cryptographic methods, as well as more esoteric methods relying on techniques such as oblivious transfer, are under study. Researchers are also proposing systems that allow decipherment to some degree of probability rather than within some period of time.
Digital signatures provide the assurance needed to accept documents as legally binding: a judge can determine whether specific parties signed them (to the limits of the protocols). If an attacker could forge a digital signature, the judge could reach incorrect conclusions. Research in both compromising of digital signature schemes and development of more secure schemes is examining how to minimize this threat.
Ellison explores methods of binding an identity to a public key without using certificates [327].
The Internet Security Association and Key Management Protocol [666] deals with key exchange and authentication on the Internet. Several key exchange protocols are based on classical cryptosystems [163, 768]. Protocols based on public key methods abound (see, for example, [764, 790, 991, 1056]).
Several papers discuss issues in public key infrastructure, including interoperation [501, 502, 852], organization [623, 644], requirements [40, 853], and models [232, 800]. Park and Sandhu [796] have proposed extensions for X.509v3 certificates. Adams and Lloyd [7] discuss many aspects of public key infrastructures.
Several key escrow schemes explore different ways to control access. Burmester et al. [162] present a protocol with a limited time span. Several authors discuss the nontechnical aspects of the proposed U.S. key escrow system (for example, see [704, 886, 961]). Clark [197] and Walker et al. [1032] discuss the relationship between key recovery and key escrow. Others have proposed enhancements and extensions of various Internet protocols for key recovery [57, 660, 890].
Digital signature protocols abound. One standard, the DSS [747], uses a variant of El Gamal; Rivest and others have criticized some of its features [843]. Others, especially those associated with the ITU's X.500 series of recommendations, recommend (but do not require) RSA. Grant's book [416] discusses digital signatures in general and presents many case studies.
The electronic commerce protocol SET [904, 905, 906] uses dual digital signatures to tie components of messages together in such a way that neither the messages nor their association can be repudiated. Ford and Baum [365] discuss SET and the supporting infrastructure. Ghosh [389] provides a balanced view of the dangers of Internet commerce using the Web.
1: | The problem of selecting a cryptographic key is equivalent to generating a random number from 0 to |K| – 1, inclusive. However, certain issues may complicate this process. This exercise asks you to examine them.
|
2: | Reconsider the case of Alice and her stockbroker, Bob. Suppose they decide not to use a session key. Instead, Alice pads the message (BUY or SELL) with random data. Explain under what conditions this approach would be effective. Discuss how the length of the block affects your answer. |
3: | Modify Kohnfelder's scheme (see page 254) to allow a principal to issue its own certificate. Identify one or more problems other principals might have in relying on such a certificate. In particular, under what conditions would this solve the problem of an imposter spoofing the sender? |
4: | Show that, under the Yaksha security scheme, Alice can obtain the session key by computing  |
5: | An X.509 certificate revocation list contains a field specifying when the next such list is expected to be issued. Why is that field present? |
6: | Consider the following authentication protocol, which uses a classical cryptosystem. Alice generates a random message r, enciphers it with the key k she shares with Bob, and sends the enciphered message {r}k to Bob. Bob deciphers it, adds 1 to r, and sends {r + 1}k back to Alice. Alice deciphers the message and compares it with r. If the difference is 1, she knows that her correspondent shares the same key k and is therefore Bob. If not, she assumes that her correspondent does not share the key k and so is not Bob. Does this protocol authenticate Bob to Alice? Why or why not? |
7: | Needham and Schroeder suggest the following variant of their protocol:
Show that this protocol solves the problem of replay as a result of stolen session keys. |
8: | Consider an RSA digital signature scheme (see Section 10.6.2.1). Alice tricks Bob into signing messages m1 and m2 such that m = m1m2 mod nBob. Prove that Alice can forge Bob's signature on m. |
9: | Return to the example on page 269. Bob and Alice agree to sign the contract G (06). This time, Alice signs the message first and then enciphers the result. Show that the attack Bob used when Alice enciphered the message and then signed it will now fail. |
[2] See Kohl and Neuman [589], Section 5.3.1, for a complete description of a ticket. We include only the parts that are relevant to our discussion.
[3] See Kohl and Neuman [589], Section 5.3.2, for a complete description of an authenticator. We include only the parts that are relevant to our discussion.
[4] See Chapter 12.
[5] In practice, P is tested for primality by applying a series of probabilistic tests on the chosen number until the probability of that number being composite is sufficiently low. See, for example, Rabin [825] and Adleman, Pomerance, and Rumley [10].