Key Distribution Protocols on Symmetric Ciphers

This text will be one of the rewritten chapters for a textbook on the protection of information of the Department of Radio Engineering and Control Systems MIPT (MG). The full tutorial is available on github (see also draft releases ). On Habré, I also plan to post new “big” pieces, first, to collect useful comments and observations, and second, to give the community more overview material on useful and interesting topics.

The key distribution task is one of the many tasks of building a reliable communication network for many subscribers. The task is to obtain at the right time by two legal subscribers of the network a secret session encryption key (and message authentication). A good solution to this problem is a key distribution protocol that satisfies the following conditions.

• As a result of the protocol operation, a secret session key must be formed between two subscribers.
• Successful completion of the protocol key distribution should mean successful mutual authentication of subscribers. There should not be such that the protocol was successfully completed from the point of view of one of the parties, while the other party is represented by the attacker.
• Only legal users of the network should be allowed to participate in the work of the protocol. An external user should not be able to get a common session key with any of the subscribers.
• Adding a new subscriber to the network (or exclusion from it) should not require notification of all network members.

The last requirement immediately excludes such variants of protocols in which each of the subscribers would know some master key of communication with any other participant. These options are bad because with the growth of the system the number of pairs of master keys "subscriber-subscriber" grows as a square of the number of participants. Therefore, a large part of the solutions under consideration consists in the fact that one or several T trusted centers ( Trent , from English trust ) are allocated in the network, which exactly have information about all legal participants of the network and their keys. They will explicitly or implicitly be one of the participants in the session key generation protocols.
')

Variants of networks without a dedicated trusted center and with a dedicated trusted center T

An important point in the analysis of solutions to this problem is that the session keys generated at a particular point in time are less reliable than the master keys used to generate session keys. In particular, it must be assumed that although an attacker cannot obtain a session key during the communication of subscribers, he can do it after some time (days, weeks, months). And although the knowledge of this session key will help the attacker to decrypt old messages, he should not be able to organize a new session using the session key already known to him.

Symmetric protocols

Symmetric will include protocols that use primitives only classical cryptography on secret keys. These include already known block ciphers, cryptographically secure pseudo-random number generators (CRCGN) and hash functions.

When considering the protocols will use the following notation.

• Alice , Bob are legal network subscribers for whom a common session key is generated. Alice is the initiator.
• Trent is a trusted network hub.
• $$$A$, $$$B$- Some identifiers of legal subscribers of Alice and Bob, respectively.
• $$$E_A$, $$$E_B$- the result of encrypting some data block using the secret keys of legal subscribers of the network of Alice and Bob, respectively. This encryption can be done either by the legal subscribers themselves or by a trusted center who knows all the secret keys.
• $$$R_a$, $$$R_b$, $$$R_t$- random numbers generated by Alice, Bob, and Trent, respectively.
• $$$T_A$, $$$T_b$, $$$T_T$- time stamps generated by Alice, Bob and Trent respectively.
• $$$K$- a secret session key, the receipt of which is one of the goals of the protocols.

Wide-Mouth Frog Protocol

The Wide-Mouth Frog protocol is perhaps the simplest center-trusted protocol. Its author is Michael Burrows (1989, Eng. Michael Burrows ). The protocol consists of the following steps.

1. Alice generates a new session key. $$$K$and sends it along with a timestamp, a bob id and his unencrypted id to a trusted center:
   

   $$

   $$Alice \ rightarrow \ {A, E_A \ left (T_A, B, K \ right) \} \ rightarrow Trent$$
2. Trusted center using received unencrypted identifier $$$A$, finds Alice’s secret key in Alice’s database of legal subscribers and decrypts the data packet for them. Checks the timestamp (that the packet is not very old). Next, it sends a similar data packet to Bob, encrypted with his private key:
   

   $$

   $$Trent \ rightarrow \ {E_B \ left (T_T, A, K \ right) \} \ rightarrow Bob$$
   
   Bob, in addition to decrypting the package, also checks the time stamp of the trusted center.

The scheme of interaction between subscribers and trusted center in the protocol Wide-Mouth Frog

At the end of the protocol, Alice and Bob have a common session key. $$$K$.

This protocol has many flaws.

• The key generator is the initiator. If we assume that Bob is a server providing some service, and Alice is a thin client requesting this service, it turns out that the task of generating a reliable session key falls on the shoulders of the subscriber with the lowest capacity.
• In the protocol, communication with the called subscriber occurs through a trusted center. As a result, the second subscriber can become a target for a DDOS attack with a reflection (eng. Distributed denial-of-service attack ), when an attacker sends packets to a trusted center, and then creates new packets and sends them to the subscriber. If the subscriber is connected to several networks (with several trusted centers), this will allow the attacker to disable the subscriber. Although it is quite simple to defend against such an attack by adjusting the trusted center accordingly.

However, the most serious problem of the protocol is the possibility of using the following attacks.

In 1995, Ros Anderson and Roger Needham (Eng. Ross Anderson, Roger Needham ) proposed an attack on the protocol, in which an attacker (Eve) can indefinitely extend the validity of a specific session key. The idea of ​​the attack is that after the end of the protocol, the attacker will send his packets back to the trusted center, complementing them with identifiers of the allegedly initiating subscriber.

1. $$$Alice \ rightarrow \ {A, E_A \ left (T_A, B, K \ right) \} \ rightarrow Trent$
2. $$$Trent \ rightarrow \ {E_B \ left (T_T, A, K \ right) \} \ rightarrow Bob$
3. $$$Eva \ rightarrow \ {B, E_B \ left (T_A, A, K \ right) \} \ rightarrow Trent$
4. $$$Trent \ rightarrow \ {E_A \ left (T'_T, B, K \ right) \} \ rightarrow Alice$
5. $$$Eva \ rightarrow \ {A, E_A \ left (T'_T, B, K \ right) \} \ rightarrow Trent$
6. $$$Trent \ rightarrow \ {E_B \ left (T '_ T, A, K \ right) \} \ rightarrow Bob$
7. Repeat steps 3 and 5 until the time required to decrypt $$$K$.

From the point of view of the trusted center, steps 1, 3, and 5 are valid packets, initiating the communication between subscribers. The time stamps in them are correct (if Eve keeps up with the time to send these packets). From the point of view of legal subscribers, each of the packages is an invitation to the other subscriber to begin communication. As a result, two things will happen:

• Each subscriber will be sure that the protocol for creating a new session key has ended, that the second subscriber has successfully authenticated himself to the trusted center. And that to establish the next communication session, the new (in fact, the old) key will be used $$$K$.
• After the time elapsed for the attacker Eve to break the session key $$$K$Eva will be able to read all the correspondence between the subscribers and successfully impersonate both of the subscribers.

The second attack in 1997, Gavin Lowe (born Gavin Lowe ) is easier to implement. As a result of this attack, Bob is sure that Alice has authenticated herself in front of the trusted center and wants to start a second communication session. Which, of course, is not true, since the second session was initiated by the attacker.

1. $$$Alice \ rightarrow \ {A, E_A \ left (T_A, B, K \ right) \} \ rightarrow Trent$
2. $$$Trent \ rightarrow \ {E_B \ left (T_T, A, K \ right) \} \ rightarrow Bob$
3. $$$Eva \ rightarrow \ {E_B \ left (T_T, A, K \ right) \} \ rightarrow Bob$

In the same paper, Low proposed a protocol modification introducing explicit mutual authentication of subscribers using a random tag. $$$R_b$and checking that Alice can decrypt a packet with a label encrypted with the shared session key of subscribers $$$K$. However, this modification leads to the fact that the protocol loses its most important advantage over other protocols - simplicity.

1. $$$Alice \ rightarrow \ {A, E_A \ left (T_A, B, K \ right) \} \ rightarrow Trent$
2. $$$Trent \ rightarrow \ {E_B \ left (T_T, A, K \ right) \} \ rightarrow Bob$
3. $$$Bob \ rightarrow \ {E_K \ left (R_B \ right) \} \ rightarrow Alice$
4. $$$Alice \ rightarrow \ {E_K \ left (R_B + 1 \ right) \} \ rightarrow Bob$

Protocol Needham — Schroeder

The Nidham – Schroder protocol (born Roger Needham, Michael Shroeder , 1979) is similar to the modified Wide-Mouth Frog protocol, but differs in that the trusted center (Trent) does not communicate with the second subscriber while the main part of the protocol is running. The first subscriber receives from the trusted center a special package, which he sends to the second subscriber without any modification.

1. $$$Alice \ rightarrow \ {A, B, R_A \} \ rightarrow Trent$
2. $$$Trent \ rightarrow \ {E_A \ left (R_A, B, K, E_B \ left (K, A \ right) \ right) \} \ rightarrow Alice$
3. $$$Alice \ rightarrow \ {E_B \ left (K, A \ right) \} \ rightarrow Bob$
4. $$$Bob \ rightarrow \ {E_K \ left (R_B \ right) \} \ rightarrow Alice$
5. $$$Alice \ rightarrow \ {E_K \ left (R_B - 1 \ right) \} \ rightarrow Bob$

The scheme of interaction between subscribers and the trusted center in the Needham-Schröder protocol


The protocol provides two-way authentication of the parties, and, it would seem, protection against replay attacks (English replay attack ). The latter is done by introducing random labels already known from the Wide-Mouth From protocol. $$$R_a$and $$$R_b$. Indeed, without knowing the key, the attacker will not be able to impersonate Alice in front of Bob (since he will not be able to decrypt the packet with the encrypted tag $$$R_b$). However, as we agreed earlier in the introduction to this chapter, the session key itself cannot be considered reliable for a long time. If an attacker succeeds at some point in time to obtain a previously used session key $$$K$, he will be able to convince Bob that he is Alice, and that this is a new session key. To do this, he will need a packet transmitted earlier via an open channel from point 3 of the protocol.

1. $$$Eva \ rightarrow \ {A, B, R_A \} \ rightarrow Trent$
2. $$$Trent \ rightarrow \ {E_A \ left (R_A, B, K, E_B \ left (K, A \ right) \ right) \} \ rightarrow Alice$
3. $$$Alice \ rightarrow \ {E_B \ left (K, A \ right) \} \ rightarrow Bob$
4. $$$Bob \ rightarrow \ {E_K \ left (R_B \ right) \} \ rightarrow Alice$
5. $$$Alice \ rightarrow \ {E_K \ left (R_B - 1 \ right) \} \ rightarrow Bob$
   
   ... after some time ...
6. $$$Eva ~ (Alice) \ rightarrow \ {E_B \ left (K, A \ right) \} \ rightarrow Bob$
7. $$$Bob \ rightarrow \ {E_K \ left (R_B \ right) \} \ rightarrow Eva ~ (Alice)$
8. $$$Eva (Alice) \ rightarrow \ {E_K \ left (R_B - 1 \ right) \} \ rightarrow Bob$

A relatively minor flaw in the protocol is that in the second packet, the trusted center in encrypted form transmits that in the third step it is sent over an open channel ( $$$E_B \ left (K, A \ right)$).

If you add time stamps to the protocol, thereby limiting the time that a session key can be used, as well as fix a minor flaw with double encryption, you can get the protocol that underlies the widely used Kerberos authentication method for local networks.

Kerberos protocol

This section will describe the authentication protocol of the parties with a single trusted center. The network protocol "Kerberos" uses these ideas when combining several trusted centers into a single network to ensure reliability and resiliency. For more information about the Kerberos network protocol, see section 12.1. "Kerberos system for LAN".

As in the Needham-Schröder protocol, the initiating subscriber (Alice) only communicates with a dedicated trusted center, receiving from it two packets with an encrypted session key — one for itself and the other for the called subscriber (Bob). However, unlike Needham-Schröder, in the protocol under consideration, encrypted packets also contain a timestamp. $$$T_T$and session key expiration date $$$L$(from the English. lifetime - the term of life). That allows, firstly, to protect against the replay of the attack described in the previous section. And, secondly, it allows the trusted center to manage subscribers in a certain sense, forcing them to receive new session keys after a predetermined time has elapsed. $$$L$.

1. $$$Alice \ rightarrow \ {A, B \} \ rightarrow Trent$
2. $$$Trent \ rightarrow \ {E_A \ left (T_T, L, K, B \ right), E_B \ left (T_T, L, K, A \ right) \} \ rightarrow Alice$
3. $$$Alice \ rightarrow \ {E_B \ left (T_T, L, K, A \ right), E_K \ left (A, T_A \ right) \} \ rightarrow Bob$
4. $$$Bob \ rightarrow \ {E_K \ left (T_T + 1 \ right) \} \ rightarrow Alice$

The scheme of interaction between subscribers and trusted center in the protocol "Kerberos"


Please note that the third step, by using the timestamp from the trusted center $$$T_T$instead of a random tag from bob $$$R_b$allows you to reduce the protocol by one step compared with the Needham-Schroeder protocol. Also, the presence of a timestamp makes it unnecessary to pre-generate a random label by Alice and transfer it in the first step.

It is interesting to note that the packages $$$E_A \ left (T_T, L, K, B \ right)$and $$$E_B \ left (T_T, L, K, A \ right)$identical in format. In a sense, they can be called session key certificates for Alice and Bob. Moreover, all such pairs of packages can be generated in advance (for example, at the beginning of the day), put on a shared resource, provided for free use and turned off the trusted center (he has already done his job by generating these packages). And up to the point in time $$$T_t + l$these "certificates" can be used. But only if you are one of the allowed pairs of subscribers. Of course, this idea is impractical - because the number of such pairs grows as a square of the number of subscribers. However, it is interesting that such packages can be generated in advance. This idea will come in handy when we consider the public key infrastructure (PKI ).

(the following is a discussion of protocols using asymmetric encryption)

Afterword for those who read Schneier and Wikipedia. This section is mainly based on the third chapter of the book “Applied Cryptography” (2002 edition), the information from which was framed in the form of a lecture that was read to students, who prepared the articles in the Russian section following the presentation (and the book, and other sources). Wikipedia. Information from articles (for example, about attacks) was further used in lectures and in the manual. Interestingly, Schneier did not trace the connection between the individual protocols, although from a methodological point of view it is always interesting to trace the evolution from a simple solution (Wide-Mouth Frog) to a complex one (Kerberos). For the same purpose, punctured Yaholom was excluded from consideration. He is good - just does not fit into the "evolutionary" chain. And to give it to students just for the sake of “one more protocol,” it seems to me, is wrong.