💹 👆🏿 ☝🏿 Cryptographic protocols: definitions, records, properties, classification, attacks 😹 🧑🏿‍🤝‍🧑🏿 🤷🏻

This text will be one of the rewritten chapters for the training manual on information protection of the Department of Radio Engineering and Control Systems, as well as, from this training code, the Department of Information Protection of the MIPT (GU). The full tutorial is available on github (see also draft releases ). I plan to upload new “big” pieces on the hub, firstly, to collect useful comments and comments, and secondly, to give the community more overview material on useful and interesting topics.

Basic concepts

For the successful fulfillment of any information protection goals, it is necessary to participate in the process of protecting several entities that, according to certain rules, will perform technical or organizational actions, cryptographic operations, interact with each other, for example, transmitting messages or verifying each other's personalities.

Formalization of such actions is done through the description of the protocol. Protocol - a description of a distributed algorithm in the process of which two or more participants sequentially perform certain actions and exchange messages (Hereinafter, in this section, the definitions are based on [Cheremushkin: 2009] ).

By a participant (subject, party) of the protocol is understood not only people, but also applications, groups of people or entire organizations. Formally, participants are considered only those who play an active role within the protocol. Although when creating and describing the protocols, you should not forget about the passive sides either. For example, a passive cryptanalyst is not formally a participant in the protocols, but many protocols are developed taking into account protection from such “non-participants”.

The protocol consists of cycles (English round ) or passes (English pass ). A cycle is a time interval of activity of only one participant. With the exception of the very first protocol cycle, it usually starts with a message, and ends with a message.

A cycle (or passage) consists of steps (actions, English step, action ) - specific completed actions performed by a protocol participant. For example:

generation of a new (random) value;
calculation of function values;
verification of certificates, keys, signatures, etc .;
receiving and sending messages.

A past or even just theoretically described implementation of the protocol for specific participants is called a session . Each participant in the session performs one or more roles . In another protocol session, participants can switch roles and perform completely different functions.

We can say that the protocol prescriptively describes the rules for the behavior of each role in the protocol. A session is a descriptive description (possibly theoretically) of a protocol implementation that took place in the past.

An example of a protocol description.

A participant with the Sender role must send a message to a participant with the Recipient role.
A participant with the Recipient role must receive a message from a participant with the Sender role.

An example of a protocol session description.

On April 1st, at 13:00, Alice sent Bob a message.
On April 1st, at 13:05, Bob received a message from Alice.

A protected protocol or a security protocol will be called a protocol that provides at least one protective function [ISO: 7498-2: 1989] :

authentication of parties and data source,
access control
confidentiality,
integrity,
inability to refuse the fact of sending or receiving.

If a secure protocol is designed to perform the security functions of a cryptographic system, or if cryptographic algorithms are used during its execution, then such a protocol will be called cryptographic .

Protocol Recording

To record protocols related to the implementation of information protection functions, do not use expressions like “participant with the role of“ Sender ”, but replace them with short notations like“ sender ”or use generally accepted exemplifiers : Alice, Bob, Clara, Eva, etc., e. The following agreements are used.

Alice, Bob (from English A, B ) - sender and receiver.
Karl, Clara, Charlie (from the English. C ) - an equal third party.
Eve (from the English eavesdropper ) is a passive cryptanalyst.
Mellory (from the English malicious ) is an active cryptanalyst.
Trent (from the English trust ) is a trusted party.

There is no generally accepted protocol recording format; they can differ both in appearance and in completeness of description. For example, here is the most comprehensive Diffie-Hellman protocol recording format.

Preliminary stage.
- All parties have chosen common $g$ and $p$ .
Pass 1.
- Alice generates random $a$ .
- Alice calculates $A = g ^ a \ bmod p$ .
- Alice sends Bob $A$ .
Pass 2.
- Bob takes from Alice $A$ .
- Bob generates random $b$ .
- Bob is calculating $B = g ^ b \ bmod p$ .
- Bob sends Alice $B$ .
- Bob is calculating $s = A ^ b \ bmod p$ .
Pass 2.
- Alice Takes Off Bob $B$ .
- Alice calculates $s = B ^ a \ bmod p$ .
The result of the protocol.
- Parties calculated a shared session key $s$ .

Now compare with a short record of the same protocol.

$A \ to B: A = g ^ a \ bmod p$
$B \ to A: B = g ^ b \ bmod p$

In a brief record, initialization and prerequisites, calculations of non-transmitted data (in this example, a common session key, are omitted)

s

$s$ ), as well as any checks.

In this tutorial we will stick to an intermediate recording format.

Alice generates $a$ .

$Alice \ to \ left \ {A = g ^ a \ bmod p \ right \} \ to Bob$ .
Bob generates $b$ .

Bob is calculating $s = A ^ b \ bmod p$ .

$Bob \ to \ left \ {B = g ^ b \ mod p \ right \} \ to Alice$ .
Alice calculates $s = B ^ a \ bmod p$ .

We also agree on the rules for recording the case when an active cryptanalyst (Mellory) poses as a legal user.

\ begin {array} {llllc} (1) & A & \ to M \ left (B \ right) &: & A = g ^ a \ bmod p, \\ (2) & M \ left (A \ right ) & \ to B &: & A ^ * = g ^ {a ^ *} \ bmod p, \\ (3) & B & \ to M \ left (A \ right) &: & B = g ^ b \ bmod p, \\ (4) & M \ left (B \ right) & \ to A &: & B ^ * = g ^ {b ^ *} \ bmod p. \\ \ end {array}

$\ begin {array} {llllc} (1) & A & \ to M \ left (B \ right) &: & A = g ^ a \ bmod p, \\ (2) & M \ left (A \ right ) & \ to B &: & A ^ * = g ^ {a ^ *} \ bmod p, \\ (3) & B & \ to M \ left (A \ right) &: & B = g ^ b \ bmod p, \\ (4) & M \ left (B \ right) & \ to A &: & B ^ * = g ^ {b ^ *} \ bmod p. \\ \ end {array}$

Or, assigning a separate column for each participant.

\ begin {array} {lllclllc} (1) & A & \ to & M \ left (B \ right) & {} & {} &: & A = g ^ a \ bmod p, \\ (2) & {} & {} & M \ left (A \ right) & \ to & B &: & A ^ * = g ^ {a ^ *} \ bmod p, \\ (3) & {} & {} & M \ left (A \ right) & \ gets & B &: & B = g ^ b \ bmod p, \\ (4) & A & \ gets & M \ left (B \ right) & {} & {} & : & B ^ * = g ^ {b ^ *} \ bmod p. \\ \ end {array}

$\ begin {array} {lllclllc} (1) & A & \ to & M \ left (B \ right) & {} & {} &: & A = g ^ a \ bmod p, \\ (2) & {} & {} & M \ left (A \ right) & \ to & B &: & A ^ * = g ^ {a ^ *} \ bmod p, \\ (3) & {} & {} & M \ left (A \ right) & \ gets & B &: & B = g ^ b \ bmod p, \\ (4) & A & \ gets & M \ left (B \ right) & {} & {} & : & B ^ * = g ^ {b ^ *} \ bmod p. \\ \ end {array}$

To reduce the description and simplify the comparison of different protocols, use the following conventions for the designation of transmitted data.

$A$ , $B$ , $C$ , etc. - identifiers of protocol participants: Alice, Bob and Clara, respectively.
$M$ (from English message ) - a message in its original form, plaintext, regardless of the encoding. That is, under $M$ the source text can be understood as text or, for example, sound, or already a certain number or an array of bits that uniquely corresponds to this message.
$K$ (from English key ) - some key. Without further elaboration, it usually denotes a secret session key.
$K_A$ - a shared secret key between Alice and Trent (for symmetric cryptosystems).
$K_A$ - Alice's public key (for asymmetric cryptosystems).
$E_K \ left (\ dots \ right)$ (from the English encrypt ) - data encrypted on the key $K$ .
$E_A \ left (\ dots \ right)$ , $E_B \ left (\ dots \ right)$ - data encrypted on the keys of Alice and Bob, respectively.
$L$ (from the English lifetime ) - the lifetime of, for example, a certificate.
$S_K \ left (\ dots \ right)$ (from English sign ) - data and the corresponding digital signature on the public key $K$ .
$T_A$ , $T_B$ (from English timestamp ) - timestamps from the respective participants.
$R_A$ , $R_B$ (from the English random ) - random numbers selected by the respective participants.

Examples of using notation.

$E_ {K_B} (M)$ or simply $E_B (M)$ - message $M$ encrypted with Bob's key $K_B$ .
$S_A (R_A)$ - random number $R_A$ generated by Alice and signed by her. That is, the message will contain both a random number (in plain text) and an electronic signature of this number.
$S_T (A, K_A, T_T, L)$ - Alice’s identifier and key, time stamp and lifetime of this record, all together signed by the public key of the trusted center (Trent). That is, in fact, Alice’s key certificate .

Protocol Security Properties

A secure system and, accordingly, a secure protocol can perform various security functions. Many of these functions or goals (English goals ) can be formulated as resistance to a particular class of attacks. The most complete and relevant is considered to be the listing and interpretation of these goals in the AVISPA project document ( Automated Validation of Internet Security Protocols and Applications ) [AVISPA] , summarizing descriptions from various IETF documents ( Internet Engineering Task Force ). These goals are considered to be formalized - that is, such that for individual protocols there is the opportunity to formally prove or disprove the achievement of these goals.

Authentication (unidirectional).

English Authentication (unicast) .
- (G1) Subject Authentication.
  
  English Entity authentication (Peer Entity Authentication) .
  
  A guarantee for one side of the protocol through the presentation of evidence and / or credentials of the second party participating in the protocol, and that the second party actually participated in the current session of the protocol. It is usually done through the presentation of such data that could only be generated by the other side. Authentication of the subject implies that the received data can be unambiguously traced to the subject of the protocol, which implies authentication of the data source.
- (G2) Message Authentication.
  
  English Message authentication (Data Origin Authentication) .
  
  A guarantee that the received message or piece of data was created by a certain subject at some (usually unspecified) time in the past, and that this data was not damaged or tampered with. But without providing uniqueness or timeliness. Authentication of messages implies their integrity.
- (G3) Repeat protection.
  
  English Replay Protection
  
  Protection from the situation when some party will record some message and play it later (possibly in another protocol session), which will lead to incorrect interpretation of this side as authenticated.
Authentication when sending to many addresses or when connecting to a subscription / notification service.

English Authentication in Multicast or via a Subscribe / Notify Service .
- (G4) Explicit authentication of the recipient.
  
  English Implicit Destination Authentication .
  
  The protocol must ensure that the sent message is readable only to legitimate recipients. That is, only legal authorized participants will have access to relevant information, a multicast message or a group communication session. Includes distribution groups with very dynamic memberships.
- (G5) Source Authentication.
  
  English Source Authentication .
  
  Legal recipients will be able to authenticate the source and content of information or group communication. Includes cases when group members do not trust each other.
(G6) Authorization (by a third trusted party).

English Authorization (by a Trusted Third Party) .

The guarantee of the ability to authorize (in terms of the protocol) of one entity to access the resource of another using a third trusted party. It implies that the owner of the resource may not have their own access lists (Eng. Access Control List, ACL ) and relies on those of the trusted side.
Joint key generation.

English Key Agreement Properties .
- (G7) Key Authentication.
  
  English Key authentication .
  
  A guarantee for one of the entities that only legal users can access a specific secret key.
- (G8) Proof of ownership of the key.
  
  English Key confirmation (Key Proof of Possession) .
  
  A guarantee for one of the entities that the other entity actually owns a particular secret key (or the information necessary to obtain such a key).
- (G9) Perfect direct secrecy.
  
  English Perfect Forward Secrecy (PFS) .
  
  Ensuring that future compromise of master keys does not compromise session keys of past protocol sessions.
- (G10) Generation of new keys.
  
  English Fresh Key Derivation .
  
  Guaranteed to create new session keys for each protocol session.
- (G11) A secure opportunity to agree on security settings.
  
  English Secure capabilities negotiation (Resistance against Downgrading and Negotiation Attacks) .
  
  The guarantee is not only that the legal parties have the opportunity to agree on security parameters, but also that the illegal side did not intervene in the protocol and did not lead to the selection of its preferred (possibly the weakest) security parameters.
(G12) Confidentiality.

English Confidentiality (Secrecy) .

The guarantee that a particular data element (part of the message being transmitted) remains unknown to the attacker. For this purpose, the secrecy of the session key, the authentication of the key or the reliability of long-term master keys are not considered.
Anonymity.

English Anonymity .
- (G13) Protection of identifiers from listening (non-connectivity).
  
  English Identity Protection against Eavesdroppers .
  
  The guarantee that the attacker (the eavesdropper) is not able to connect the subject's messaging with his real identity.
- (G14) Protection of identifiers from other parties.
  
  English Identity Protection against Peer .
  
  A guarantee that the participant in the correspondence is not able to associate the subject’s messaging with a real person, but only with some pseudonym.
(G15) Limited protection against denial of service attacks.

English (Limited) Denial-of-Service (DoS) Resistance .

Ensuring that the protocol follows certain principles that reduce the likelihood (complicating the use) of certain classes of denial of service attacks.
(G16) Invariance of the sender.

English Sender Invariance .

A guarantee for one of the parties that the source of the message remains the same as the one that started the communication, although the actual identification of the source is not important for the recipient.
Indisputability.

English Non-repudiation .
- (G17) Accountability.
  
  English Accountability .
  
  Guaranteed ability to track the actions of subjects on objects.
- (G18) Proof of origin.
  
  English Proof of Origin .
  
  Guarantee of irrefutable evidence of the source of the message.
- (G19) Proof of delivery.
  
  English Proof of Delivery .
  
  Guarantee of irrefutable evidence of the fact of receiving the message.
(G20) Protected temporary property.

English Safety Temporal Property .

A guarantee of the ability to prove that the fact that a system is in one of the states means that once in the past the system was at least once in some other state. For example, that obtaining a subject access to a resource means that once in the past the subject successfully paid for this access.

Examples of security properties implemented by various protocols are given in the table.

Protocol classification

There is no universally accepted classification of security protocols. However, a set of objective and unambiguous features classifying the protocols can be distinguished.

Classification by the number of participants in the protocol:
- bilateral,
- tripartite, etc.,
- multilateral.
Classification by the number of transmitted messages:
- interactive (with the presence of mutual messaging);
- non-interactive (with one-time messaging), often called schemes . The definition is not entirely complete. Any scheme involves at least two stages. At the first preliminary stage, the trusted center distributes some information among peer participants. At the second stage (specific protocol sessions), participants exchange this information, receiving the original secret or a new secret session key. Moreover, the exchange of information can go more than between two participants. However, after mutual exchange of information, additional passes are not required to achieve the objectives of the scheme.
Classification by the number of passes (rounds):
Classification by cryptographic systems used:
- based on only symmetric cryptosystems;
- based on including asymmetric cryptosystems.
Classification by protected protocol properties:
- (G1) provides or not authentication of the first, second side of the protocol, etc .;
- (G2) provides or not message authentication;
- (G3) provides or not repetition protection;
- etc.
Classification by type of participants:
- Peer-to-peer, when all participants can fulfill any roles within the protocol;
- with a trusted intermediary when a third trusted party is always involved in the protocol;
- with a trusted arbitrator, when a third trusted party may participate in the protocol, if the other participants have not agreed.

A less objective and unambiguous classification may also be introduced based on a subjective assessment of the protocols.

Classification according to the purpose of the protocol:
- ... ensuring integrity
- ... digitally signed
- ... identification,
- ... privacy
- ... key distribution,
- … etc.
Classification of the "completeness" of the functions performed:
- primitive, are used as a basic component in the construction of application protocols;
- intermediate;
- applied, designed to solve practical problems.

The classification by purpose can also be reformulated as a classification by the protected properties of the protocol for which it was developed. In this case, it will be necessary to highlight the “basic properties” (for example, G10 - the formation of new keys), and most of the rest be attributed to additional ones (for example, G7 - key authentication, and G8 - confirmation of key ownership). Determining which of the properties are “basic” and which are “additional” will create an ambiguity in the classification according to the purpose of the protocol. If all the properties of the protocol are called “basic”, then such a classification will become too detailed.

Classification by "completeness" of the functions performed is problematic due to the fact that not a single protocol can be called fully "applied". Any protocol in itself is only part of a certain information (or organizational) system, which just performs the function required by users. However, it can be said that individual protocols (for example, TLS) are protocols of a higher level than protocols, for example, Diffie-Hellman, since the latter often acts as an integral part of the same TLS protocol.

Protocol Attacks

Protected properties of protocols can be declared when they are declared by the authors of the protocol themselves (and, usually, give various arguments in favor of performing these functions), and implied when the authors of some system rely on the implementation of protected properties by some protocol.

An attack on a secure protocol is understood as an attempt to analyze protocol messages and / or perform actions not foreseen by the protocol in order to violate the declared or implied properties of the protocol. (A modified definition from [Cheremushkin: 2009] is used . The difference is that Cheryomushkin in his definition does not describe what “protocol violation" is and leaves ambiguous cases of violation, for example, the properties of G9 / PFS and G20 / STP.)

An attack is considered successful if at least one of the declared or implied properties of the protocol is violated.

In the case of a successful attack on the implied properties, we will clarify that the attack on the use of the protocol in some system is successful. This will speak, of course, not about the flaws of the protocol itself, but about the wrong choice of the protocol (or its settings) by the authors of the system.

There are many types of protocol attacks. Many attacks have some general principles, which makes it possible to distinguish attack classes to simplify the analysis and development of protocols that are resistant to entire attack classes.

MitM Attack in the Middle

English man-in-the-middle attack

A class of attacks in which an attacker relays and, if necessary, modifies all messages between two or more protocol participants, and the latter do not know about the existence of an attacker, believing that they communicate directly with each other. All protocols that do not implement mutual authentication of the parties (target G1) are vulnerable to this attack. A classic example of an attack of this class is an attack on the Diffie-Hellman protocol.
Replay Repeat Attack

English replay attack

A class of attacks in which an attacker writes down all messages passing in one protocol session and then repeats them in a new one, posing as one of the participants in the first session. Examples of protocols to which this attack applies are the Wu-Lama protocols and the Shamir keyless protocol.
TF attack spoofing type

English type flaw attack

A class of attacks in which an attacker, using a message sent in a legitimate protocol session, constructs a new one, passing it on another pass (round) of the protocol under the guise of a message of a different type (with a different purpose). Such attacks are vulnerable, for example, the protocols Wide-Mouth Frog, Denning — Sako, Yahalom, and Otway — Riisa.
PS Attack with parallel sessions

English parallel-session attack

A class of attacks in which an attacker initiates several simultaneous protocol sessions in order to use messages from one session to another. An example of a protocol that is vulnerable to this class of attacks is the symmetric version of Needham — Schröder.
STS Attack with a known one-time key

English short term secret attack
KN Attack with a known session key

English known-key attack

Classes of attacks in which an attacker gains access to temporary secrets used in protocols (for example, new session keys), after which he can provide, for example, authentication or at least session establishment on behalf of one of the protocol parties.
UKS Session Key Attack

English unknown key-share attack

A class of attacks on protocols with key authentication, in which an attacker gets the opportunity to prove to one of the parties the ownership of the key (using, for example, retrying a message from a legal session), although the attacker himself does not know the key. Such a class of attacks is vulnerable, for example, the symmetric Needham-Schröder protocol.

It is important to note that unless otherwise stated, then in the framework of the analysis of cryptographic protocols (not specific systems), the assumption of the strength of all used cryptographic primitives is used.For example, it is assumed that while there is a secure exchange of information using a session key generated in a session of a certain cryptographic protocol, the attacker will not have enough resources and time to obtain this session key through an attack on the ciphers used or cryptographically-resistant hash functions.

On the other hand, it should be assumed that the session keys obtained within the framework of protocol sessions will after some time (however, be much longer than the communication session itself) be obtained by the attacker (attack classes STS and KN). And after much more time, the attacker will be able to gain access to the “master” keys - long-term use keys, so protocols with session key generation should be developed including the G9 / PFS property.

( .)

References

[ISO 7498-2:1989] ISO 7498-2:1989. Information processing systems — Open Systems Interconnection — Basic Reference Model — Part 2: Security Architecture: Standard / ISO/IEC JTC 1 Information technology. — 02.1989. — URL: www.iso.org/standard/15841.html .
[AVISPA] Automated Validation of Internet Security Protocols and

Applications (AVISPA): IST-2001-39252. Deliverable 6.1 'List of Selected Problems'. Properties (Goals). — 2003. — URL: www.avispa-project.org/delivs/6.1/d6-1/node3.html
[Cheremushkin] . . : // . - 2009. - Nov. - issue. 2. - p. 115-150.- URL: cyberleninka.ru/article/n/kriptograficheskie-protokoly-osnovnye-svoystva-i-uyazvimosti.pdf .

Afterword

The author will be grateful for factual and other comments on the text. The presentation and the text were prepared largely on the excellent lecture by Cheryomushkin (link above).

Cryptographic protocols: definitions, records, properties, classification, attacks