Next Page

Prev. page

Next Page Next Chapter

CHAPTER 22 ................................................ 512

Key-Exchange Algorithms ....................... 512

DIFFIE-HELLMAN .................................... 512

CHAPTER ..................................................... 513

Diffie-Hellman with Three or More Parties ..... 513

Extended Diffie-Hellman ............................... 514

Hughes .......................................................... 514

Key Exchange Without Exchanging Keys ..... 514

Patents .......................................................... 515

STATION-TO-STATION PROTOCOL ...... 515

SHAMIRâ€™S THREE-PASS PROTOCOL .... 515

COMSET .................................................. 516

The Basic EKE Protocol ................................ 517

Implementing EKE with RSA ........................ 518

Zmplementing EKE with ElGamal ................. 518

Implementing EKE with Diffie-Hellman ......... 518

Strengthening EKE ....................................... 519

Augmented EKE ........................................... 519

Applications EKE .......................................... 520

FORTIFIED KEY NEGOTIATION ............. 521

CONFERENCE KEY DISTRIBUTION ...... 522

Conference Key Distribution .......................... 523

Tatebayashi-Matsuzaki-Newman .................. 523

Page 512

Prev. Chapter Home Previous Page

Next Page

Prev. page

Next Page Next Chapter

22

CHAPTER

Key-Exchange

Algorithms

2 2.1 DIFFIE-HELLMAN

Diffie-Hellman was the first public-key algorithm ever invented, way back in 1976

[496]. It gets its security from the difficulty of calculating discrete logarithms in a

finite field, as compared with the ease of calculating exponentiation in the same

field. Diffie-Hellman can be used for key distribution-Alice and Bob can use this

algorithm to generate a secret key-but it cannot be used to encrypt and decrypt

messages.

The math is simple. First, Alice and Bob agree on a large prime, n and g, such that

g is primitive mod n. These two integers donâ€™t have to be secret; Alice and Bob can

agree to them over some insecure channel. They can even be common among a

group of users. It doesnâ€™t matter.

Then, the protocol goes as follows:

(1) Alice chooses a random large integer x and sends Bob

X=gXmodn

(2) Bob chooses a random large integer y and sends Alice

Y=gYmodn

(3) Alice computes

k=Yâ€ťmodn

(4) Bob computes

kâ€™=XYmodn

Both k and kâ€™ are equal to gâ€ť mod n. No one listening on the channel can compute

that value; they only known, g, X, and Y Unless they can compute the discrete log-

Page 513

Prev. Chapter Home Previous Page

Next Page

Prev. page

Next Page Next Chapter

CHAPTER 22 Key-Exchange Algorithms

arithm and recover x or y, they do not solve the problem. So, k is the secret key that

both Alice and Bob computed independently.

The choice of g and n can have a substantial impact on the security of this system.

The number (n - 1)/2 should also be a prime [ 12.531.And most important, n should

be large: The security of the system is based on the difficulty of factoring numbers

the same size as n. You can choose any g, such that g is primitive mod n; thereâ€™s no

reason not to choose the smallest g you can-generally a one-digit number. (And

actually, g does not have to be primitive; it just has to generate a large subgroup of

the multiplicitive group mod n.)

Parties

Diffie-Hellman with Three or More

The Diffie-Hellman key-exchange protocol can easily be extended to work with

three or more people. In this example, Alice, Bob, and Carol together generate a

secret key.

( 1) Alice chooses a random large integer x and sends Bob

X=gXmodn

(2) Bob chooses a random large integer y and sends Carol

Y=gYmodn

(3) Carol chooses a random large integer z and sends Alice

Z=gâ€™modn

(4) Alice sends Bob

Zâ€™=Zâ€ťmodn

(5) Bob sends Carol

Xâ€™=XYmodn

(6) Carol sends Alice

Yâ€™=Yâ€™modn

(7) Alice computes

k=Yâ€™â€śmodn

(8) Bob computes

k=Zâ€™Ymodn

(9) Carol computes

k=Xâ€ťmodn

The secret key, k, is equal to gxYzmod n, and no one else listening in on the com-

munications can compute that value. The protocol can be easily extended to four or

more people; just add more people and more rounds of computation.

Page 514

Prev. Chapter Home Previous Page

Next Page

Prev. page

Next Page Next Chapter

Extended Diffie-Hellman

Diffie-Hellman also works in commutitive rings [1253]. Z. Shmuley and Kevin

McCurley studied a variant of the algorithm where the modulus is a composite

number [ 1442,1038]. V. S. Miller and Neal Koblitz extended this algorithm to ellip-

tic curves [1095,867]. Taher ElGamal used the basic idea to develop an encryption

and digital signature algorithm (see Section 19.6).

This algorithm also works in the Galois field GF(2k) [1442,1038]. Some imple-

mentations take this approach [884,1631,1632], because the computation is much

quicker. Similarly, cryptanalytic computation is equally fast, so it is important to

carefully choose a field large enough to ensure security.

Hughes

This variant of Diffie-Hellman allows Alice to generate a key and send it to

Bob [745].

(1) Alice chooses a random large integer x and generates

k=gXmodn

(2) Bob chooses a random large integer y and sends Alice

Y=gYmodn

(3) Alice sends Bob

X= Ymodn

(4) Bob computes

z=y-l

kâ€™=Xâ€™modn

If everything goes correctly, k = kâ€™.

The advantage of this protocol over Diffie-Hellman is that k can be computed

before any interaction, and Alice can encrypt a message using k prior to contacting

Bob. She can send it to a variety of people and interact with them to exchange the

key individually later.

Key Exchange Without Exchanging Keys

If you have a community of users, each could publish a public key, X = gâ€ť mod n,

in a common database. If Alice wants to communicate with Bob, she just has to

retrieve Bobâ€™s public key and generate their shared secret key. She could then

encrypt a message with that key and send it to Bob. Bob would retrieve Aliceâ€™s pub-

lic key to generate the shared secret key.

Each pair of users would have a unique secret key, and no prior communication

between users is required. The public keys have to be certified to prevent spoofing

attacks and should be changed regularly, but otherwise this is a pretty clever idea.

Page 515

Prev. Chapter Home Previous Page

Next Page

Prev. page

Next Page Next Chapter

CHAPTER 22 Key-Exchange Algorithms

Patents

The Diffie-Hellman key-exchange algorithm is patented in the United States [7181

and Canada [719]. A group called Public Key Partners (PKP) licenses the patent,

along with other public-key cryptography patents (see Section 25.5). The U.S. patent

will expire on April 29, 1997.

22.2 STATION-TO-STATION PROTOCOL

Diffie-Hellman key exchange is vulnerable to a man-in-the-middle attack. One way to

prevent this problem is to have Alice and Bob sign their messages to each other [500].

This protocol assumes that Alice has a certificate with Bobâ€™s public key and that

Bob has a certificate with Aliceâ€™s public key. These certificates have been signed by

some trusted authority outside this protocol. Hereâ€™s how Alice and Bob generate a

secret key, k.

(1) Alice generates a random number, x, and sends it to Bob.

(2) Bob generates a random number, y. Using the Diffie-Hellman protocol he

computes their shared key based on x and y: k. He signs x and y, and

encrypts the signature using k. He then sends that, along with y, to Alice.

Yh&(X,Y))

(3) Alice also computes k. She decrypts the rest of Bobâ€™s message and verifies

his signature. Then she sends Bob a signed message consisting of x and y,

encrypted in their shared key.

Ek(S/thY))

(4) Bob decrypts the message and verifies Aliceâ€™s signature.

22.3 SHAMIR'S THREE-PASS PROTOCOL

This protocol, invented by Adi Shamir but never published, enables Alice and Bob

to communicate securely without any advance exchange of either secret keys or

public keys [ 10081.

This assumes the existence of a symmetric cipher that is commutative, that is:

C&(P)) = k&%(P))

Aliceâ€™s secret key is A; Bobâ€™s secret key is B. Alice wants to send a message, M, to

Bob. Hereâ€™s the protocol.

(1) Alice encrypts M with her key and sends Bob

Cl = EA(MI

(2) Bob encrypts C1 with his key and sends Alice

Cz = -&b%(M))

Page 516

Prev. Chapter Home Previous Page

Next Page

Prev. page

Next Page Next Chapter

22.4 COMSET

(3) Alice decrypts Cz with her key and sends Bob

= DAL%(EA(M)))= ˜ALWB(MM = &Ml

C3

(4) Bob decrypts C3 with his key to recover M.

One-time pads are commutative and have perfect secrecy, but they will not work

with this protocol. With a one-time pad, the three ciphertext messages would be:

C,=POA

CP=POAOB

C,=P@B

Eve, who can record the three messages as they pass between Alice and Bob, sim-

ply XORs them together to retrieve the message:

Cl @ Cz CD = (P @A) 0 (P @A @ B) 63(P cDB) = P

C3

This clearly wonâ€™t work.

Shamir (and independently, Jim Omura) described an encryption algorithm that

will work with this protocol, one similar to RSA. Let p be a large prime for which p

- 1 has a large prime factor. Choose an encryption key, e, such that e is relatively

prime to p - 1. Calculate d such that de = 1 (mod p - 1).

To encrypt a message, calculate

C=Memodp

To decrypt a message, calculate

M= Cdmodp

There seems to be no way for Eve to recover M without solving the discrete loga-

rithm problem, but this has never been proved.

Like Diffie-Hellman, this protocol allows Alice to initiate secure communica-

tion with Bob without knowing any of his keys. For Alice to use a public-key algo-

rithm, she has to know his public key. With Shamirâ€™s three-pass protocol, she just

sends him a ciphertext message. The same thing with a public-key algorithm

looks like:

(1) Alice asks Bob (or a KDC) for his public key.

(2) Bob (or the KDC) sends Alice his public key.

(3) Alice encrypts M with Bobâ€™s public key and sends it to Bob.

Shamirâ€™s three-pass protocol will fall to a man-in-the-middle attack.

22.4 COMSET

COMSET (COMmunications SETup) is a mutual identification and key exchange

protocol developed for the RIPE project [ 13051 (see Section 25.7). Using public-key

Page 517

Prev. Chapter Home Previous Page

Next Page

Prev. page

Next Page Next Chapter

CHAPTER 22 Key-Exchange Algorithms

cryptography, it allows Alice and Bob to identify themselves to each other and also

to exchange a secret key.

The mathematical principle behind COMSET is Rabinâ€™s scheme [ 12831 (see Sec-

tion 19.5). The scheme itself was originally proposed in [224]. See [1305] for details.

22.5 ENCRYPTED KEY EXCHANGE

The Encrypted Key Exchange (EKE) protocol was designed by Steve Bellovin and

Michael Merritt [109]. It provides security and authentication on computer net-

works, using both symmetric and public-key cryptography in a novel way: A shared

secret key is used to encrypt a randomly generated public key.

The Basic EKE Protocol

Alice and Bob (two users, a user and the host, or whoever) share a common pass-

word, P Using this protocol, they can authenticate each other and generate a com-

mon session key, K.

(1) Alice generates a random public-key/private-key key pair. She encrypts the

public key, Kâ€™, using a symmetric algorithm and P as the key: E,(Kâ€™). She

sends Bob

A, E,(Kâ€™)

(2) Bob knows P He decrypts the message to obtain Kâ€™. Then, he generates a

random session key, K, and encrypts it with the public key he received

from Alice and P as the key. He sends Alice

W&W))

(3J Alice decrypts the message to obtain K. She generates a random string, RA,

encrypts it with K, and sends Bob

J?&)

(4) Bob decrypts the message to obtain RA. He generates another random

string, RB, encrypts both strings with K, and sends Alice the result.

&d&> &I

(5) Alice decrypts the message to obtain RA and RB. Assuming the RA she

received from Bob is the same as the one she sent to Bob in step (3), she

encrypts RB with K and sends it to Bob.

-C&j

(6) Bob decrypts the message to obtain R,. Assuming the R, he received from

Alice is the same one he sent to Alice in step (41,the protocol is complete.

Both parties now communicate using K as the session key.

At step (3), both Alice and Bob know R and K. K is the session key and can be used

to encrypt all other messages between Alice and Bob. Eve, sitting between Alice and

Page 518

Prev. Chapter Home Previous Page

Next Page

Prev. page

Next Page Next Chapter

22.5 Encrypted Key Exchange

and some messages encrypted with K. In other pro-

Bob, only knows E,( Kâ€™), EP(ER(K)),

tocols, Eve could make guesses at P (people choose bad passwords all the time, and if

Eve is clever she can make some good guesses) and then test her guesses. In this pro-

tocol, Eve cannot test her guess without cracking the public-key algorithm as well.

And if both Kâ€™ and K are chosen randomly, this can be an insurmountable problem.

The challenge-response portion of the protocol, steps (3) through (6), provides val-

idation. Steps (3) through (5) prove to Alice that Bob knows K; steps (4) through (6)

prove to Bob that Alice knows K. The Kerberos protocol timestamp exchange

accomplishes the same thing.

EKE can be implemented with a variety of public-key algorithms: RSA, ElGamal,

Diffie-Hellman. There are security problems with implementing EKE with a knap-

sack algorithm (aside from the inherent insecurity of knapsack algorithms): The

normal distribution of the ciphertext messages negates the benefits of EKE.

Implementing EKE with RSA

The RSA algorithm seems perfect for this application, but there are some subtle

problems. The authors recommend encrypting only the encryption exponent in step

(1) and sending the modulus in the clear. An explanation of the reasoning behind

this recommendation, as well as other subtleties involved in using RSA, is in [ 1091.

Zmplementing EKE with ElGamal

Implementing EKE with the ElGamal algorithm is straightforward, and there is

even a simplification of the basic protocol. Using the notation from Section 19.6, g

and p are parts of the public key and are common to all users. The private key is a

random number r. The public key is gâ€™ mod p. The message Alice sends to Bob in

step (1) becomes

Alice, gâ€™ mod p

Note that this public key does not have to be encrypted with l? This is not true in

general, but it is true for the ElGamal algorithm. Details are in [ 1091.

Bob chooses a random number, R (for the ElGamal algorithm and independent of

any random numbers chosen for EKE), and the message he sends to Alice in step (2)

becomes

Ep(gRmod p, KgRâ€™ mod p)

Refer back to Section 19.6 for restrictions on choosing the variables for ElGamal.

Implementing EKE with Diffie-Hellman

With the Diffie-Hellman protocol, K is generated automatically. The final proto-

col is even simpler. A value for g and n is set for all users on the network.

(1) Alice picks a random number, rA, and sends Bob

A, 9â€™â€ť mod n

With Diffie-Hellman, Alice does not have to encrypt her first message

with I?

Page 519

Prev. Chapter Home Previous Page

Next Page

Prev. page

Next Page Next Chapter

CHAPTER 22 Key-Exchange Algorithms

(2) Bob picks a random number, rB, and calculates

K=gâ€™A *â€˜Bmodn

He generates a random string RB, then calculates and sends Alice:

G4P mod 4, EKNB)

(3) Alice decrypts the first half of Bobâ€™s message to obtain gâ€™˜ mod n. Then she

calculates K and uses K to decrypt Rg. She generates another random

string, RA, encrypts both strings with K, and sends Bob the result.

&@A> RB)

(4) Bob decrypts the message to obtain RA and Rg. Assuming the Rg he received

from Alice is the same as the one he sent to Alice in step (2), he encrypts RA

with K and sends it to Alice.

&@A)

(5) Alice decrypts the message to maintain RA. Assuming the RA she received

from Bob is the same as the one she sent to Bob in step (3), the protocol is

complete. Both parties now communicate using K as the session key.

Strengthening EKE

Bellovin and Merritt suggest an enhancement of the challenge-and-response por-

tion of the protocol-to prevent a possible attack if a cryptanalyst recovers an old

K value.

Look at the basic EKE protocol. In step (3) Alice generates another random num-

ber, SA,and sends Bob

&@A, SA)

In step (4) Bob generates another random number, Sg, and sends Alice

&@A, RB, SB)

Alice and Bob now can both calculate the true session key, SA 8 Sg. This key is

used for all future messages between Alice and Bob; K is just used as a key-

exchange key.

Look at the levels of protection EKE provides. A recovered value of S gives Eve no

information about P, because P is never used to encrypt anything that leads directly

to S. A cryptanalytic attack on K is also not feasible; K is used only to encrypt ran-

dom data, and S is never encrypted alone.

Augmented EKE

The EKE protocol suffers from one serious disadvantage: It requires that both par-

ties possess the P Most password-based authentication systems store a one-way

hash of the userâ€™s password, not the password itself (see Section 3.2). The Aug-

mented EKE (A-EKE) protocol uses a one-way hash of the userâ€™s password as the

Page 520

Prev. Chapter Home Previous Page

Next Page

Prev. page

Next Page Next Chapter

superencryption key in the Diffie-Hellman variant of EKE. The user then sends an

extra message based on the original password; this message authenticates the newly

chosen session key.

Hereâ€™s how it works. As usual, Alice and Bob want to authenticate each other and

generate a common key. They agree on some digital signature scheme where any

number can serve as the private key, and where the public key is derived from the

private key, rather than being generated along with it. The ElGamal and DSA algo-

rithms work well for this. Aliceâ€™s password P (or perhaps some simple hash of it) will

serve as the private key and as Pâ€™.

Alice picks her random exponent R, and transmits

(1)

E&$ mod n)

(2) Bob, who knows only Pâ€™ and cannot derive P from it, chooses Rb and sends

Ep(gRAmod n)

(3) Both Alice and Bob calculate the shared session key K = gâ€™˜ * â€˜B mod n.

Finally, Alice proves that she knows P itself, and not just Pâ€™, by sending

EK(SP(K))

Bob, who knows both K and Pâ€™, can decrypt and validate the signature. Only Alice

could have sent this message, since only she knows P; an intruder who obtains a

copy of Bobâ€™s password file can try guessing at P, but cannot otherwise sign the ses-

sion key.

The A-EKE scheme does not work with the public-key variant of EKE, since in it

one party chooses the session key and imposes it on the other. This permits a man-

in-the-middle attack by an attacker who has captured Pâ€™.

of EKE

Applications

Bellovin and Merritt suggest using this protocol for secure public telephones [ 1091:

Let us assumethat encrypting public telephones are deployed. If someone wishes

to use one of these phones, some sort of keying information must be provided.

Conventional solutions . . . require that the caller possess a physical key. This is

undesirable in many situations. EKE permits use of a short, keypad-entered pass-

word, but uses a much longer session key for the call.

EKE would also be useful with cellular phones. Fraud has been a problem in the

cellular industry; EKE can defend against it (and ensure the privacy of the call) by

rendering a phone useless if a PIN has not been entered. Since the PIN is not

stored within the phone, it is not possible to retrieve one from a stolen unit.

EKEâ€™s primary strength is that both symmetric and public-key cryptography work

together in a manner that strengthens them both:

amplifier. That is, it can

From a general perspective, EKE functions as a privacy

be used to strengthen comparatively weak symmetric and asymmetric systems

Page 521

Prev. Chapter Home Previous Page

Next Page

Prev. page

Next Page Next Chapter

CHAPTER 22 Key-Exchange Algorithms

when used together. Consider, for example, the key size needed to maintain secu-

rity when using exponential key exchange. As LaMacchia and Odlyzko have

shown [934], even modulus sizes once believed to be safe (to wit, 192 bits) are vul-

nerable to an attack requiring only a few minutes of computer time. But their

attack is not feasible if one must first guess a password before applying it.

Conversely, the difficulty of cracking exponential key exchange can be used to

frustrate attempts at password-guessing. Password-guessing attacks are feasible

because of how rapidly each guess may be verified. If performing such verification

requires solving an exponential key exchange, the total time, if not the concep-

tual difficulty, increases dramatically.

EKE is patented [ 1111.

FORTIFIED KEY NEGOTIATION

2 2.6

This scheme also protects key-negotiation schemes from poorly chosen passwords

and man-in-the-middle attacks [47,983]. It uses a hash function of two variables that

has a very special property: It has many collisions on the first variable while having

effectively no collisions on the second variable.

Hâ€™( x, y) = H( H( k, x) mod 2â€ť, x),

where H(k, x) is an ordinary hash function on k and x

Alice and Bob share a secret password, P, and have just

Hereâ€™s the protocol.

exchanged a secret key, K, using Diffie-Hellman key exchange. They use P to check

that their two session keys are the same (and that Eve is not attempting a man-in-

the-middle attack), without giving P away to Eve.

Alice sends Bob

(1)

Hâ€™ O? K)

(2) Bob computes Hâ€™ (P, K) and compares his result with what he received from

Alice. If they match he sends Alice

Hâ€™ W(P, Kl)

(3) Alice computes Hâ€™ (H(P, K)) and compares her result with what she

received from Bob.

If Eve is trying a man-in-the-middle attack, she shares one key, K,, with Alice, and

another key, Kz, with Bob. To fool Bob in step (2), she has to figure out the shared

password and then send Bob Hâ€™ * (e K2). With a normal hash function she can try

common passwords until she guesses the correct one, and then successfully infil-

trate the protocol. But with this hash function, many passwords are likely to pro-

duce the same value when hashed with K1. So when she finds a match, she will

probably have the wrong password, and hence Bob will not be fooled.

Page 522

Prev. Chapter Home Previous Page

Next Page

Prev. page

Next Page Next Chapter

CONFERENCE KEY DISTRIBUTION AND SECRET

22.7

BROADCASTING

Alice wants to broadcast a message, M, from a single transmitter. However, she

doesnâ€™t want it to be intelligible by every listener. In fact, she only wants a select

subset of listeners to be able to recover M. Everyone else should get nonsense.

Alice can share a different key (secret or public) with each listener. She encrypts

the message in some random key, K. Then she encrypts a copy of K with each of the

keys of her intended recipients. Finally, she broadcasts the encrypted message and

then all of the encrypted KS. Bob, who is listening, either tries to decrypt all the KS

with his secret key, looking for one that is correct, or, if Alice doesnâ€™t mind every-

one knowing who her message is for, he looks for his name followed by an encrypted

key. Multiple-key cryptography, previously discussed, also works.

Another method is suggested in [352]. First, each listener shares a secret key with

Alice, one that is larger than any possible encrypted message. All of those keys

should be pairwise prime. She encrypts the message in a random key, K. Then, she

computes a single integer, R, such that R modulo a secret key is congruent to K

when that secret key is supposed to decrypt the message, and R modulo a secret key

is otherwise congruent to zero.

For example, if Alice wants the secret to be received by Bob, Carol, and Ellen,

but not by Dave and Frank, she encrypts the message with K and then computes R

such that

R = K (mod KB)

R = K (mod Kc)

R = 0 (mod K,)

R = K (mod KE)

R = 0 (mod K,)

This is a straightforward algebra problem, one that Alice can solve easily. When

listeners receive the broadcast, they compute the received key modulo their secret

key. If they were intended to receive the message, they recover the key. Otherwise,

they recover nothing.

Yet a third way, using a threshold scheme (see Section 3.7), is suggested in [141].

Like the others, every potential receiver gets a secret key. This key is a shadow in a

yet-untreated threshold scheme. Alice saves some secret keys for herself, adding

some randomness to the system. Letâ€™s say there are k people out there.

Then, to broadcast M, Alice encrypts M with key K and does the following.

(1) Alice chooses a random number, j. This number serves to hide the number

of recipients of the message. It doesnâ€™t have to be very large; it can be as

small as 0.

Page 523

Prev. Chapter Home Previous Page

Next Page

Prev. page

Next Page Next Chapter

CHAPTER 22 Key-Exchange Algorithms

(2) Alice creates a (k + j + 1, 2k + j + 1) threshold scheme, with:

K as the secret.

The secret keys of the intended recipients as shadows.

The secret keys of nonrecipients not as shadows.

j randomly chosen shadows, not the same as any of the secret

keys.

(3) Alice broadcasts k + j randomly chosen shadows, none of which is any of

the shadows listed in step (2).

(4) All listeners who receive the broadcast add their shadow to the k + j shad-

ows they received. If adding their shadow allows them to calculate the

secret, then they have recovered the key. If it does not, then they havenâ€™t.

Another approach can be found in [885,886,1194]. For yet another approach,

see [ lOOO].

Key Distribution

Conference

This protocol allows a group of n users to agree on a secret key using only insecure

channels. The group shares two large primes, p and 4, and a generator g the same

size as q.

(1) User i, where i goes from 1 to n, chooses a random ri less than 4, and

broadcasts

z,=@modp

(2) Every user verifies that zI4 = 1 (mod p), for all i from 1 to n.

(3) User i broadcasts

X, = (z, + l/zi - I)â€˜1mod p

(4) User i computes

All index computations in the above protocol-i - 1, i - 2, and i + l-should be

computed mod n. At the end of the protocol, all honest users have the same K. No

one else gets anything. However, this protocol falls to a man-in-the-middle attack.

Another protocol, not quite as pretty, is in [757].

Tatebayashi-Matsuzaki-Newman

This key distribution protocol is suitable for networks [ 15211.Alice wants to gen-

erate a session key with Bob using Trent, the KDC. All parties know Trentâ€™s public

key, n. Trent knows the two large primes that n factors to, and hence can easily take

Page 524

Prev. Chapter Home Previous Page

Next Page

Prev. page

Next Page Next Chapter

22.7 Conferenc

cube roots modulo n. A lot of the details are left out of the following protocol, but

you get the idea.

(1) Alice chooses a random number, r,, and sends Trent

rA3mod n

(2) Trent tells Bob that someone wants to exchange a key with him.

(3) Bob chooses a random number, rB, and sends Trent

rB3mod n

(4) Trent uses his private key to recover rA and rg. He sends Alice

rA @rB

(5) Alice calculates

(rA@rB)@rA=rB

She uses this rB to communicate securely with Bob.

This protocol looks good, but it has a horrible flaw. Carol can listen in on step (3)

and use that information, with the help of an unsuspecting Trent and another mali-

cious user (Dave), to recover rB [ 14721.

(1) Carol chooses a random number, rc, and sends Trent

rB3rc3mod n

(2) Trent tells Dave that someone wants to exchange a key with him.

(3) Dave chooses a random number, r,, and sends Trent

rD3mod n

(4) Trent uses his private key to recover rc and rD. He sends Carol

(rBrc) mod n 0 rD

(5) Dave sends rD to Carol.

(6) Carol uses rc and rD to recover rg. She uses rB to eavesdrop on Alice and Bob.

This is not good.