Key distribution protocols using a loop. Key Management

Protocol public key distribution is a protocol that allows two or more participants to develop a common secret information (a shared secret key) by exchanging messages over eavesdropping channels. The protocol should exclude the possibility of obtaining information about the key by outsiders, as well as by any participant before the completion of the actions provided for by the protocol.

Statement of the problem of information security

Public key distribution protocols appeared due to the need to implement key exchange without using a secure communication channel. Two or more participants, as a result of performing the actions prescribed by the protocol, receive the same keys, which are then used in symmetric encryption schemes. The first research in this area was carried out by Whitfield Diffie and Martin Hellman, who published their public key distribution protocol in the 1970s. It was the first cryptosystem that made it possible to protect information without using secret keys transmitted over secure channels.

The public key distribution scheme proposed by Whitfield Diffie and Martin Hellman made a real revolution in the world of encryption, as it removed the main problem of classical cryptography - the problem of key distribution. The same article also introduced the basics of asymmetric cryptography.

A key generated using such a protocol is only valid for one session, or even part of such a session. Accordingly, the open distribution of encryption keys allows any pair of system users to independently develop their own common encryption key, thereby simplifying the procedure for distributing secret encryption keys. However, at the same time, the lack of a pre-distributed common encryption key among the correspondents before the communication session will not give them the opportunity to verify each other's authenticity using the exchange of messages over an open channel. Accordingly, man-in-the-middle attacks are possible.

Frequent rekeying of symmetric crypto schemes is necessary to ensure a sufficient level of resistance to cryptanalysis, since if the enemy has a large number cipher material encrypted with a single key, his task is made easier. Public key distribution allows you to change keys from desired frequency, since no secure communication channel is required and there are no associated costs.

Theoretical foundations for solving the problem

Fundamentally, public key distribution protocols are based on the use of one-way functions. The adversary, intercepting messages transmitted by protocol participants to each other, cannot calculate secret keys on their basis and then obtain the shared secret key developed by the participants.

The general scheme of the protocol is as follows:

preliminary stage

• get p - a large prime number;

• get a complete decomposition of the number (p -1) into factors;

• calculate the primitive root r modulo p (r mod p).

A composite number is decomposed into prime factors (into prime numbers or their positive integer powers, possibly zero), where p i are prime numbers; b i are powers of prime numbers.

To calculate the primitive root, it is necessary that for any number from the interval the condition . Under this condition, any number can be represented as , where x is some positive integer from the interval . A pair of numbers (p,r) is used as the public key.

working stage

Let and be two subscribers who need to get a shared secret key . Then:

1. generates an element , calculates and send the result

2. generates an element , calculates and send the result

3. calculates the value

4. calculates the value

After receiving the value and must be destroyed.

As a result of the protocol execution, each of the subscribers receives a common key, which can be used in symmetric encryption systems. At the same time, an adversary who knows the public key (p, r) will not be able to calculate the value of . When intercepting numbers, the enemy will also not be able to get the value.

Basic cryptographic constructions and their security

Diffie-Hellman Public Key Distribution Protocol

This protocol was proposed in 1976 and is the first protocol of its kind. It can also be called one of the most famous public key distribution protocols.

The Diffie-Hellman protocol provides neither authentication, nor key validation, nor authentication of protocol participants. An active adversary can build an attack on the protocol by inserting into a channel (Man-in-the-Middle attack).

When working with this algorithm, it is necessary to have a guarantee that user A received the public key from user B, and vice versa. This problem is solved with the help of an electronic signature, which is used to sign public key messages.

The advantage of the Diffie-Hellman method compared to the RSA method is that the formation of a shared secret key is hundreds of times faster. In the RSA system, the generation of new private and public keys is based on the generation of new prime numbers, which takes a long time.

ElGamal scheme

This cryptosystem was proposed in 1985. ElGamal proposed this scheme based on exponentiation modulo a large prime number. He improved the Diffie-Hellman system and obtained two algorithms that were used for encryption and for authentication.

Practical applications of cryptographic structures, features of their implementation

The first practical application of cryptosystems with public key– organization of key exchange between remote users through open communication channels

IKE (Internet Key Exchange)

IKE is a standard IPsec protocol used to secure communication in virtual private networks. The IKE protocol allows the negotiation of algorithms and mathematical structures for the Diffie-Hellman key exchange procedure, as well as authentication processes.

IPsec (IP Security) - a set of protocols for ensuring the protection of data transmitted over the Internet protocol IP. Allows for authentication (authentication), integrity checking and/or encryption of IP packets. IPsec also includes protocols for secure Diffie-Hellman key exchange over the Internet.

IKE protocols serve three purposes:

Authenticate the interacting parties, agree on encryption algorithms and key characteristics that will be used in a secure information exchange session;

Manage connection parameters and protection against certain types of attacks, control the implementation of all agreements reached;

Provide creation, management of key connection information, direct exchange of keys (including the possibility of their frequent change).

PGP (Pretty Good Privacy)

PGP is a popular program for encrypting, decrypting and digital signature messages Email, files and other information provided in electronic form. It works on the principle of asymmetric encryption, which allows the exchange of public keys through insecure communication channels. Private keys are not transmitted, so the program is organized in such a way that all commands for sending and exchanging keys operate only with public keys.

Key accumulation

Key generation

Key management

Key information is understood as the totality of all active keys in the IS.

Key management is information process, which includes 3 elements:

generation of keys;

accumulation of keys;

distribution of keys.

It is known that you should not use non-random keys. Serious ICs use special software and hardware methods to generate random keys. As a rule, sensors of random and pseudo-random numbers are used. The degree of randomness must be high. Ideal generators are devices based on natural random processes. The physical random number generator is built into the core of the Pentium 3 processor.

Mathematically, random numbers can be obtained using the decimal places of transcendental numbers, such as π or e, which are calculated using standard mathematical methods. IS with medium security requirements uses software to obtain random numbers.

Accumulation of keys - organization of their accounting, storage and deletion. Since there are many keys, they are stored in the key information database. The keys themselves must be stored in the database in encrypted form.

The key that encrypts the key information is called the master key.

It is desirable that the user knows it by heart. You can break the master keys into parts and store one part on a magnetic card, and the other part in the computer's memory.

An important condition for storing key information is the periodic updating of keys and master keys. In particularly critical cases, you can update daily.

Key distribution is the most critical process in key management. It has two requirements:

· Efficiency and accuracy of distribution.

· Secrecy of distribution of keys.

Users in symmetric cryptosystems must exchange a shared secret key, which will be used for both encryption and decryption.

Key distribution in symmetric cryptosystems can take place in the following ways:

1) it is possible to deliver the key through a courier, but since the keys must be updated, it is expensive and inefficient to deliver

2) receipt by two users of a common key from the central authority (Key Distribution Center - CDC). The transmitted key is encrypted with the CRC key. Disadvantage: an attacker may appear in the CRC. It is possible to organize the storage of keys in the CRC in the form of a tree.

3) The third method was proposed by scientists Diffie and Hellman - an open channel key exchange protocol. A protocol is a sequence of steps that 2 or more parties take to jointly solve a problem. All steps follow in order of priority.

A cryptographic protocol is a protocol based on a cryptographic algorithm and all participants in the protocol must be notified in advance about all the steps that they have to go through.

Diffie-Hellman public channel key exchange protocol.

Purpose: two users A and B get a shared secret key.

1. User A generates a random number X.

2. User B generates a random number Y.

3. A calculates: La=a^x mod m

4. B computes: Lb=b^y mod m

5. A sends user B La.

6. B sends Lb to user A.

7. A computes Kab =(Lb)^x mod m=(a^y mod m)^x mod m=a^xy mod m.

8. B computes Kab =(La)^y mod m=(a^x mod m)^y mod m=a^xy mod m.

Thus, both users now have the same Kab private key.

Public key management can be organized using an online or offline directory service. The main issues are authenticity, integrity and validity. Authenticity - make sure that this is the key of this particular user.

In all cases of key exchange, the authenticity of the communication session must be ensured, which is ensured using:

1. "request-response" mechanism (procedure "handshake" = setting up a virtual channel);

2. time stamping mechanism.

The problem of key distribution is reduced to the construction of a distribution protocol that provides:

1. Mutual authentication of session participants.

2. Session validation by challenge-response mechanism or timestamps.

3. Using the minimum number of messages in the key exchange.

4. The possibility of excluding abuse by the CRC (up to the refusal of its services).

It is advisable to separate the procedure for verifying the identity of partners from the actual key distribution procedure.

A method to achieve both authenticity and integrity in the distribution of public keys is through the use of certificates.

A certificate-based system assumes that there is a central authority, and that each user can securely interact with the central authority, for this each user must have the public key of the central authority.

A public key certificate C A is a message from a central authority that certifies the integrity of some public key of object A (may be a paper or electronic document).

For example: a public key certificate for user A, designated C A, contains a timestamp T, identifier Id A , public key K A , encrypted with the secret key CRK K crc:

C A \u003d E K crk (T, Id A, K A)

The timestamp T is used to validate the validity of the certificate and thereby prevent repetition of old certificates. The secret key K of the CRC is known only to the manager of the CRC, and the public key of the CRC is known to all subscribers

A system that provides encryption with a public key and digital signature is called a public key infrastructure.

The certification authority creates user certificates by digital signature using its private key and signs the following data set:

1. Full name user (number, password).

2. Public key of the user.

3. Certificate validity period.

4. Specific operations for which this key can be used (identification, encryption, or both).

Kerberos authentication

To solve the problem of authentication, which would be based on encryption, a security system was developed at the Massachusetts Institute of Technology in 1985. information systems from intrusions, with a special ticketing service. It was named Kerberos after the three-headed dog Cerberus, who guarded the gates to hell in Greek mythology.

This name was chosen because three parties were involved in authentication: the user, the server the user wishes to access, and the authentication server, or key distribution center (KDC). A special authentication server was proposed as a trusted third party, whose services can be used by other servers and clients of the information system.

The Kerberos system holds the secret keys of the served subjects and helps them to perform mutual authentication.

1. receipt by the user of a ticket TGT for tickets;
2. receipt by the user server access ticket;
3. user authentication by the server;
4. server authentication by the user.

Let's consider authentication in the Kerberos system in more detail ( rice.), which is performed in four steps:

1) The session begins with the user receiving A ticket to receive a ticket - Ticket-Granting Ticket (TGT) from CRC.

2) When a user wants to access some server B, he first sends a request to ticket to access this server along with your ticket TGT V CRC. TGT contains information about the login session of user A and allows CRC operate without constantly maintaining information about the login session of each user.

3) In response to his request, user A receives an encrypted session key S A and server access ticket C. The session key is encrypted with a secret key known only to user A and CRC. Server access ticket B contains the same session key, but it is encrypted with a private key known only to server B and CRC.

4) Authentication occurs when user A and the server prove knowledge of their private key. The user encrypts the timestamp and sends it to server B. The server decrypts the timestamp, increments it by one, re-encrypts it, and sends the ciphertext to user A. User A decrypts the response, and if it contains the incremented timestamp value, authentication succeeds, otherwise, it fails. After mutual authentication the session key can be used to encrypt messages exchanged between user A and server B. Obviously, the parties must trust CRC, since it keeps copies of all secret keys.

As complex and secure as the cryptosystem itself is, it is based on the use of keys. If the process of exchanging keys is trivial to ensure the confidential exchange of information between two users, then in a system where the number of users is tens and hundreds, key management is a serious problem.

The key information is understood as the totality of all keys operating in the system. If the key information is not securely managed, then, having taken possession of it, the attacker gets unlimited access to all information.

Key management is an information process that includes three elements:

Key generation;

Accumulation of keys;

Key distribution.

Key generation. IN real systems special hardware and software methods for generating random keys are used. As a rule, random number generators are used. However, the degree of randomness of their generation should be sufficiently high. Ideal generators are devices based on “natural” random processes. For example, key generation based on white radio noise. Another random mathematical object is the decimal places of irrational numbers, such as p or e, which are calculated using standard mathematical methods.

In systems with medium security requirements, software key generators are quite acceptable, which calculate random numbers as complex function from the current time and (or) the number entered by the user.

Key accumulation. Under the accumulation of keys is understood the organization of their storage, accounting and deletion.

Since the key is the most attractive object for an attacker, opening the way for him to confidential information, the issues of key accumulation should be given special attention.

Secret keys should never be written explicitly on a medium that can be read or copied.

In a fairly complex system, one user can work with a large amount of key information, and sometimes it even becomes necessary to organize minidatabases of key information. Such databases are responsible for accepting, storing, recording and deleting the keys used.

Each information about the keys used must be stored in encrypted form. Keys that encrypt key information are called master keys. It is desirable that each user knows the master keys by heart and does not store them at all on any material media.

A very important condition for information security is the periodic updating of key information in the system. In this case, both ordinary keys and master keys should be reassigned. In especially critical systems, key information must be updated daily.

The issue of updating key information is also related to the third element of key management - key distribution.

Key distribution. Key distribution is the most critical process in key management. It has two requirements:

Efficiency and accuracy of distribution;

Secrecy of distributed keys.

Recently, there has been a noticeable shift towards the use of public key cryptosystems, in which the problem of key distribution disappears. Nevertheless, the distribution of key information in the system requires new efficient solutions.

The distribution of keys between users is implemented by two different approaches:

1 By creating one or more key distribution centers. The disadvantage of this approach is that the distribution center knows to whom and which keys are assigned, and this allows you to read all the messages circulating in the system. Possible abuses significantly affect protection.

2 Direct key exchange between system users. In this case, the problem is to reliably authenticate the subjects.

In both cases, the authenticity of the communication session must be guaranteed. This can be provided in two ways:

1 The request-response mechanism, which is as follows. If user A wants to be sure that the messages he receives from user B are not false, he includes an unpredictable element (request) in the message sent to B. When answering, user B must perform some operation on this element (for example, add 1). This cannot be done in advance, since it is not known what random number will come in the request. After receiving a response with the results of the actions, user A can be sure that the session is genuine. The disadvantage of this method is the ability to establish, albeit complex, patterns between the request and the response.

2 Time stamp mechanism. It implies fixing the time for each message. In this case, each user of the system can know how “old” the incoming message is.

In both cases, encryption should be used to ensure that the response was not sent by an attacker and that the timestamp has not been altered.

When using timestamps, there is a problem with the allowable delay time interval for session authentication. After all, a message with a timestamp, in principle, cannot be transmitted instantly. In addition, the computer clocks of the recipient and sender cannot be perfectly synchronized.

Public key cryptosystems can be used for key exchange using the same RSA algorithm.

But the Diffie-Hellman algorithm turned out to be very effective, allowing two users to exchange a key without intermediaries, which can then be used for symmetric encryption.

Diffie-Hellman algorithm. Diffie and Helman proposed a discrete exponentiation function for creating public-key cryptographic systems.

The irreversibility of the transformation in this case is ensured by the fact that it is quite easy to calculate the exponential function in a finite Galois field consisting of p elements ( p is either prime or prime to any power). Calculating logarithms in such fields is a much more time-consuming operation.

To exchange information, the first user chooses a random number x 1 , equiprobable of integers from 1 to p– 1. He keeps this number a secret, and sends the number to another user y 1 = , where α is a fixed element of the Galois field GF(p), which together with p is pre-distributed among users.

The second user does the same, generating x 2 and calculating y 2 , sending it to the first user. As a result, both of them can calculate the shared secret key k 12 = .

In order to calculate k 12 , the first user raises y 2 to the power x 1 and finds the remainder after dividing by p. The second user does the same, only using y 1 and x 2. Thus, both users have a common key k 12 , which can be used to encrypt information with conventional algorithms. Unlike the RSA algorithm, this algorithm does not allow encryption of the actual information.

Not knowing x 1 and x 2 , an attacker might try to compute k 12, knowing only intercepted y 1 and y 2. The equivalence of this problem to the problem of calculating the discrete logarithm is a major and open question in public key systems. A simple solution has not been found to date. So, if the direct transformation of 1000-bit prime numbers requires 2000 operations, then the inverse transformation (calculating the logarithm in the Galois field) will require about 1030 operations.

As can be seen, despite the simplicity of the Diffie-Hellman algorithm, its disadvantage compared to the RSA system is the absence of a guaranteed lower estimate of the complexity of key disclosure.

In addition, although the described algorithm circumvents the problem covert transmission key, the need for authentication remains. Without additional funds, one of the users cannot be sure that he exchanged keys with the exact user he needs.

Elliptic curves are a mathematical object that can be defined over any field (finite, real, rational, or complex). Finite fields are commonly used in cryptography. An elliptic curve is a set of points (x, y), satisfying the following equation:

y 2 = x 3 + ax + b,

as well as a point at infinity. For points on a curve, it is quite easy to introduce the addition operation, which plays the same role as the multiplication operation in RSA and ElGamal cryptosystems.

In real cryptosystems based on elliptic equations, the equation is used

y 2 = x 3 + ax + b mod p,

Where R- simple.

The discrete logarithm problem on an elliptic curve is as follows: given a point G on an elliptic curve of order r (the number of points on the curve) and another point Y on the same curve. Need to find a single point x such that Y = x G, that is, Y is X th degree G.

Public key distribution

So far, the benefits of public key encryption methods have not been apparent. However, based on them, it is easy to solve the problem of developing a common secret key for a communication session of any pair of users of an information system. Back in 1976, Diffie and Hellman proposed a public key distribution protocol for this. It involves the independent generation of each of the pair of communicating users of their random number, its transformation through a certain procedure, the exchange of the converted numbers over an open communication channel, and the calculation of a common secret key based on information received from the partner during communication. Each such key exists only during one communication session or even part of it. Thus, open key distribution allows each pair of system users to develop their own shared secret key, thereby simplifying the procedure for distributing secret keys. Although everything is not so simple - the absence of a pre-distributed common secret key among subscribers before a communication session, in principle, does not allow them to verify each other's authenticity by exchanging messages over an open channel. For example, you can also send keys using the ElGamal algorithm described above in Shamir's modification, but how can you be sure that you are dealing with a partner and not an interceptor? To confirm the identity, each of the participants in the secret network must still have their own secret key, known only to him and distinguishing him from all other subscribers. In this case, the Diffie-Hellman algorithm will provide such a password presentation procedure that its repeated use does not reduce the reliability of the proof of the owner's identity. As a result, the two functions of the shared secret key, usually delivered over a secret channel, such as protecting information in the communication channel from a third party and verifying the identity of each of the subscribers to the partner, are separated.

The Diffie-Hellman public key distribution algorithm looks like this:

Let there be two subscribers open network A And B who know the public key pair R And d. In addition, at A have a secret key X from the interval (1, n), while B have a secret key y from the same interval.

Subscriber A sends Bx mod p, and the subscriber B sends A encryption of your key Z"=D** y mod p.

After that they calculate the common key Z as Z=Z"** y=Z""** x.

With the help of special techniques, the time for generating a common key in the Diffie-Hellman system can be reduced by 5 times compared to the ElGamal system in the Shamir modification, and by 30 times compared to RSA at the same security level. This, from the point of view of most practical applications, turns out to be a noticeable advantage, since encryption and decryption using the RSA algorithm is about a thousand times slower than classical algorithms such as DES. Note that for many applications of public-key cryptographic systems, the computational time for cryptographic transformations is not of great importance. For example, when identifying users by credit cards, there will be no difference - whether it takes one microsecond or one second. The same applies to the choice of a shared encryption key for another, faster, but lacking the ability to exchange keys, cryptographic system.

The need in open key distribution systems to have individual secret passwords distributed in advance from the center to authenticate users does not seem to be such a burdensome task as the production and distribution from the center of pairs of secret keys for connecting subscribers to each other. The validity period of such a password can be significantly longer than the validity period of the communication key, say, a year, and their total number in the communication network is equal to the number of subscribers. In addition, with some types of communication, confirmation of the identity of a partner can be achieved by recognizing him by physical signs. For example, by voice telephone communication or by appearance and voice when communicating through television channels. It should be noted that the distribution of keys using public key cryptographic systems has the only advantage - the need for each secret communication node to have only one key. For classical symmetric cryptographic systems, there should be as many keys as the subscriber node has. However, public key systems have weaknesses. So, if breaking an encryption containing a key is fundamentally impossible in a classical system, since the plaintext is meaningless and does not contain redundant information, then in systems with a public key, a cryptanalyst always has a hope of success. Further, if the number D is common to all participants in the network, then its compromise, in the form of the discovery of special properties that facilitate the logarithm, will lead to the compromise of the entire network. If D is individual for each pair of subscribers, then, firstly, because of the abundance of keys, it is easier to find a weak one among them, and, secondly, although the distribution and storage of non-secret keys is incomparably easier than secret ones, it also causes a lot of trouble. Therefore, if a cryptographer has the opportunity to use the services of a secret channel, then he will always prefer it to public key distribution.

Of the practically operating communication networks using a public key distribution system, the most seriously protected is telephone state network USA based on STU-III devices. It began functioning in 1987 and now contains more than 150 thousand subscribers. In Russia, a similar network, also called ATS-1 or "turntable", is also reliably protected, but there are hundreds of times fewer subscribers there. By the early 1980s, cryptologists had come to realize the benefits of so-called hybrid systems, in which public-key encryption procedures are used only to transfer keys and digital signatures. And the information that needs to be transmitted is protected by a classic DES-type algorithm, the key for which is transmitted using public key encryption. First serial device of this type was a Racal-Milgo Datacryptor released in 1979. The Datacryptor Encryption Key Management Apparatus is intended primarily for government communications networks and is certified to comply with the British standard for protecting non-secret but sensitive information. It provides signaling of violations of cryptographic requirements and error notifications. This device uses an algorithm for establishing encrypted communication by generating and transmitting a shared secret key using the RSA algorithm. In the future, devices of this type for information protection were released a lot. Other examples of the use of new cryptographic ideas are demonstrated by many commercial networks, especially banking ones, such as SWIFT. In addition, the RSA digital signature system is used in the nuclear test limitation treaty verification equipment developed by Sandia Laboratories in 1982, the BPMIS network, and other systems.

One of the most challenging tasks key management, arising in cryptography, is the formation of shared secret keys of participants in cryptosystems. In this section, we will briefly get acquainted with the main methods for solving this problem, note their advantages, disadvantages, and areas of possible application.
2.2.1. Basic concepts and definitions
A key establishment protocol is a cryptographic protocol in which a shared secret is made available to two or more parties for subsequent use for cryptographic purposes.
Key distribution protocols fall into two classes: key transport and key exchange protocols.
Key transport protocols are key distribution protocols in which one party creates or otherwise acquires a secret and securely transfers it to other parties.
Key agreement (key exchange) protocols are key distribution protocols in which a shared secret is generated by two or more participants as a function of the information contributed by each of them (or associated with them) in such a way that (ideally) no other party can predetermine their shared secret.
There are two additional forms of key distribution protocols. A protocol is said to perform a key update if the protocol generates a completely new key, which does not depend on keys generated in previous protocol execution sessions. The protocol performs the generation of derivative keys (key derivationJ, if the new key is “derived” from the cryptosystem participants already existing.
Key distribution protocols can be classified in another way.
Key pre-distribution protocols are key distribution protocols in which the resulting keys are fully determined a priori by the initial key material. Secret sharing schemes can be attributed to a special type of such protocols.
Dynamic key establishment protocols are key distribution protocols in which the keys generated by a fixed pair (or group) of participants are different in different protocol sessions. This process is also called session key distribution.
Key distribution protocols can also be classified according to whether they use symmetric or asymmetric crypto schemes.
The classification of the key distribution protocols considered below according to the criteria listed above is shown in Table. 2.1.
Table 2.1. Classification of key distribution protocols Protocol classes Key distribution protocols Key transport Key exchange Protocols based on symmetric crypto schemes Needham - Schroeder, Otway - Rees, Kerberos, Shamir's three-way protocol Sharada Merkle Bpoma scheme Secret sharing schemes
Protocol classes Key distribution protocols Key transport Key exchange Protocols based on asymmetric crypto schemes Needham-Schroeder, X.509, Beller-Yacobi, SSL Diffie-Hellman, ElGamal, MTl, STS, Gunther Secret sharing schemes Dynamic key distribution Protocols with pre-shared keys
Key distribution protocols can be built both without the participation of a "third party" and with its participation. A trusted "third party" can perform various functions: an authentication server, a key distribution center, a key translation center, a certification center, etc.