CS261Scribed by Pallavi JoshiNovember 18, 20081 Key DistributionSuppose there are n entities, and they all want to be able to communicate securelywith each other. A na¨ıve solution would be to have a shared secret for each pair ofentities. This would result in¡n2¢(which is O(n2)) shared secrets, or keys. Managingsuch a large number of keys becomes tedious. Moreover, whenever a new entity joinsa network, it has to contact all other entities in the network to establish shared secretswith them.Instead of having a shared key for each pair of entities, we can have a centralizedKey Distribution Center (KDC) that hands out keys to different entities. When twodifferent parties want to communicate with each other, then they can request theKDC to generate a shared key for them. The basic steps present in a protocol thatutilizes a KDC are as follows.1. Let us assume that Alice (A) wants to communicate with Bob (B). She contactsthe KDC providing it with her identity, Bob’s identity and requests for a keythat she can use to communicate with Bob. She also provides the KDC withan expiration time (texp), and requests that the shared key between herself andBob be valid till that time.2. The KDC replies back with a shared key kAB. It also includes Bob’s identity inthe message. The message is encrypted with the key that Alice shares with theKDC (KA,KDC). The message also has a timestamp ts.3. The KDC also sends a message to Bob that has the shared key kAB, and alsoAlice’s identity in it. The message is encrypted with the key that Bob shareswith the KDC ( KB,KDC). The message also has a timestamp ts.Now Alice and Bob have a shared key that they can use to communicate witheach other. If the expiration time is not included in the messages, then amalicious entity Eve can replay the message sent to Bob by the KDC, and trickBob into communicating with her if she somehow knew the shared key betweenAlice and Bob.A BKDCFigure 1: Key Distribution Center4. Alice now starts communicating with Bob. To make sure she is communicatingwith Bob, she sends a nonce NAto Bob that is encrypted with kAB.5. Bob sends back (NA+1) and another nonce NBto Alice. The message is en-crypted with kAB. Since Bob is the only entity that knows kAB, the fact thatAlice got back (NA+1) in the message means that the message came from Bob,since Bob is the only entity that could have decrypted Alice’s message and couldhave extracted NAout of it. Bob sends another nonce NBin his message toauthenticate Alice.6. Alice sends back (NB+1) to Bob. The message is encrypted with kAB. NowAlice and Bob know that they are communicating with the right entities (eachhas authenticated himself/herself to the other).The Needham-Schroeder protocol is based on the above idea of a KDC.2 KerberosAs shown in the figure, the following steps are involved in the Kerberos protocol.1. Alice sends a message to the KDC requesting for a session key to communicatewith Bob. The message has an expiration time texpand a nonce N .2. The KDC replies back with a ticket which consists of a session key kAB, theIP address of Alice, a timestamp ts, the expiration time texp, and the nonceN . The message is encrypted with the shared key between Alice and KDC,23:KDCA B1:2:4:5:6:[A,B,texp][B, ts, kAB, texp]KA,KDC{[NA]}kAB{[NA+ 1, NB]}kAB{[NB+ 1]}kAB[A, ts, kAB, texp]KB,KDCFigure 2: Needham-Schroeder ProtocolKA,KDC. The KDC also encrypts the ticket with the key that Bob shares withit (KB,KDC), and sends it to Alice.3. Alice decrypts the message that is encrypted with KA,KDC, and extracts thesession key kABout of it. She then sends a message to Bob that has heridentity, Bob’s identity, and a timestamp ts, and is encrypted with kAB. Shealso sends the ticket that she received from the KDC, and which was encryptedwith KB,KDC.4. Bob decrypts the ticket, and extracts the session key kABout of it. It then sendsa message back to Alice that has his and Alice’s identities, and the timestamptswith 1 added to it. The message is encrypted with kAB.Below are some attacks that are possible if we leave out some of the componentsin the messages above.1. If we leave out Bob’s identity in the messages from Alice, then a man-in-the-middle attack is possible. The man-in-the-middle intercepts the first messagefrom Alice, and replaces Bob with Bob’. The KDC replies back with a ticketthat is encryped with the shared key between itself and Bob’. The man-in-the-middle then intercepts the message from Alice to Bob, and forwards it to Bob’,and forwards the response from Bob’ to Alice.2. A man-in-the-middle might also flip bits in message 1 (as shown in Figure 3)to make B as B’, or flip bits in message 3 ((as shown in Figure 3)) in the ticketencrypted with KB,KDCto make A as A’.We now discuss the design or system issues with Kerberos below.3A BKDC1:3:4:2:{[T ]}KB,KDCA,B,texp, N{[kAB, A, B, ipaddr, ts, texp, N ]}KA,KDC{[A, B, ts]}kAB,{[T ]}KB,KDC{[A, B, ts+ 1]}kABFigure 3: Kerberos1. The TCB in this system consists of the KDC, and the time service. If thesecurity of the KBC is compromised, then the whole system is compromised.2. The KDC uses passwords to authenticate users, which is not good.3. Revocation of a key is easy; to remove a user from the system, just remove theinformation of its key from the KDC.Implementation issues of Kerberos are discussed below.1. No MAC or checksum is included with the messages.2. No IV (or Initialization Vector) is used for encryption.3. srand(time(NULL)) and rand() are used in implementations. One can guessthe time on a system, and hence guess the series of random numbers that wereused in an instantiation of the protocol.4. In older days, since encryption was very CPU-intensive, Kerberos had onlyauthentication by default, and encryption was kept