Copyright © 2019 for this paper by its authors. Use permitted under Creative Commons License Attribution 4.0 International (CC BY 4.0) Strengthening the password authenticated key exchange protocols due to the use of asymmetric execution of cryptosystems Varfolomeev A.A Department of «Information Security» of Bauman Moscow State Technical University (BMSTU) Moscow, Russia a.varfolomeev@mail.ru Abstract— Protocols for generating high-entropy exceeding 112 bits.. " cryptographic session keys from long-term low-entropy keys or The concept of low-entropy keys is often used in the passwords (PAKE - Password Authenticated Key Exchange) are literature, compared with the 256-bit high-entropy keys, which used to increase the security of information protection in are typical for modern standard encryption algorithms. Short information systems. The paper shows how to increase the keys can be classified as low-entropy, but a number of authors security of the PAKE protocols themselves by using the concept of asymmetric execution of cryptosystems proposed by the author attribute password words and even PIN-codes, whose entropy (see, for example, at SIBCON 2016, RusCrypto 2018). is less than 56 bits, to low-entropy keys. In [1], for symmetric ciphers, it was proposed to introduce Asymmetric execution of cryptosystems implies a deliberate asymmetry into the complexity of the work when encrypting significant increase in the complexity of performing operations plaintext and when decrypting a ciphertext by legitimate users. for one of the legitimate users (for example, for the server, due to In this regard, such ciphers and cryptosystems were called additional transformations of the plaintext, increasing the asymmetrically executed. The legitimate recipient of the password by a random value, choosing the mode of the cipher, ciphertext in this case spent significantly more time decrypting, hiding part of the information necessary for the operation), since he had to try out a random binary vector by which the resulting in significant increasing the complexity of finding the short key used in encryption was increased, which was known secret keys and for the attacker. to the sender and recipient of the message. To find the plaintext, the attacker had to try both the short key and the The proposed strengthening of cryptographic protocols is random vector added by the sender to the key. Of course, at the especially relevant in the context of restrictions on the same time, it is assumed that the sender has a high-quality parameters used in the primitives of cryptographic protocol. generator of random binary sequences, and for the model of the Keywords— cryptography, cryptographic protocols, keys, attacker, it is possible to use only the full testing method (brute complexity, resilience, ЕКЕ protocol, Diffie-Hellman key force attack) for decryption. agreement protocol, SESPAKE protocol. To increase security, other methods were proposed in [2], including preliminary conversion of plaintext such as AON I. INTRODUCTION conversion. The use of new (in comparison with GOST 28147- This work, in addition to independent significance, is a 89) operating modes of block ciphers according to the GOST 34.13 standard turned out to be essential for the continuation of a number of works by the author in the field of implementation efficiency. strengthening the security of cryptosystems with short keys. Short keys are understood as keys of symmetric and Further, at the RusCrypto 2018 conference [3], the author asymmetric cryptosystems defined by the restriction for proposed to use the PAKE protocols to strengthen the strength unlicensed use introduced by the well-known Decree of the of ciphers with short keys, where a short key should be used as Government of the Russian Federation dated 04.16.2012 No. a password word. For example, when using symmetric and 313. According to the Decree, without a license you can use a asymmetric ciphers with short keys in the EKE protocol [4], “symmetric cryptographic algorithm that uses a cryptographic the complexity of decryption is not the sum of the complexity key with a length not exceeding 56 bits, either an asymmetric of decryption of each of the ciphers, but is their product. cryptographic algorithm based either on the method of This paper shows how the introduction of asymmetry in the factoring integers whose size does not exceed 512 bits, or on complexity of operations performed by legitimate users of the the method of calculating a discrete logarithms in a finite field PAKE protocols themselves leads to an increase in the multiplicative group size not exceeding 512 bits, or a method complexity of solving cryptanalysis tasks for an attacker using of computing discrete logarithms in another group of size not well-known protocols as an example. 79 The concept of “asymmetric PAKE” was previously protocol only for the key transportation phase, omitting the considered in a number of works (see, for example, [5], [6]), second stage for brevity. but the reason for using the word “asymmetry” differs from 1 option for protocol amplification. that described in this paper. Asymmetric PAKE is the same • 1. A: [A, E (PW-Ra; PKa II h (PKa)]  B, where Ra is a PACK in the client-server architecture, where the server does random vector selected by user A and not known to user B. not store the password word itself, but the value of the one • 2. B iterates over Ra and searches for Pka by the criterion for way function from it. If the server is compromised, the plaintext. Then it sends E (PW; E_PKa (k))  A. attacker will have to perform an additional off-line attack to In step 1, a hash code from it was added to the plaintext find the password word. PKa in order to structure this plaintext so that user B could find the true public key PKa of user A. Decryption time for B II. THE BELLOWIN - MERRITT CRYPTOGRAPHIC PROTOCOL was increased by 2 ^ IRaI, where IRaI is the size vectors Ra. EKE AND PROPOSALS FOR ENHANCING ITS STRENGTH. But the criterion for plaintext also gets the attacker. Thus, this case is similar to the case of transmitting ciphertext The EKE protocol [4] is one of the first password- obtained by encrypting structural plaintext on the PW key based authentication key exchange protocols. The purpose of (text structure of the form PKa II h (PKa) is chosen for the protocol is to safely transport a high-entropy key from one clarity). To enhance the strength of encryption in this case, the user to another if they have a common low-entropy secret recommendations of previous works [1-2] can be applied. (password). The EKE protocol has been patented. For Option 2 protocol amplification. readability, we recall the steps and steps of the EКE protocol. At the first step, a certain set of public keys of user A is Let PW denote the password word known to users A and B. encrypted: PKa1, PKa2, ..., PKaN. Key transportation stage. • 1. A: sends the message [A, E (PW; PKa)]  B, • 1. A: [A, E (PW; PKa1, PKa2, ..., PKaN)]  B. where E (PW; PKa) is the encryption transformation with a • 2. B: After decrypting the ciphertext E (PW; PKa1, PKa2, symmetric cipher on the PW key, PKa is the public key of user ..., PKaN) and receiving the set of public keys {PKa1, PKa2, A for the asymmetric cipher. ..., PKaN}, user B randomly chooses one of them - the PKaJ • 2. B: produces a high-entropy key k and sends key. E (PW; E_PKa (k))  A. The step of confirming receipt of key k is “Request-response”. • Next, B generates a high-entropy key k and sends message A to user A (PW; E_PKaJ (k II h (k))  A. • 3. A: From E (PW; E_PKa (k)) receives k, sends E (k; R_a)  B. • 3. A, knowing the password word PW, decrypts E (PW; • 4. B: From E (k; R_a) it receives R_a, sends E_PKaJ (k II h (k)) and restores E_PKaJ (k II h (k), iterates E (k; h (R_a) II R_b) A, here h is some hash function. over its public keys PKa1, PKa2, ..., PKaN, looks for PKaJ and • 5. A: From E (k; h (R_a) II R_b) receives h (R_a) II R_b and key k. The criterion for finding the true key k is finding the key checks h (R_a) = ?, then sends E (k; h (R_b))  B. k with the correct value h (k) attached. • 6. B: From E (k; h (R_b)) receives and checks h (R_b) =?. User A in this option works more than B. In step 3, he must sort through all N sent to the user B public keys PKa1, According to the Dolev - Yao model, the attacker in PKa2, ..., PKaN. step 1 receives ciphertext E (PW; PKa) for off-line attacks. In step 1, as before, the sequence PKa1, PKa2, ..., Due to the relatively small number of options for choosing PKaN is not structured, which does not allow an attacker to PW, he can go through all of them and get options for the PKa recover the password word PW from the ciphertext E (PW; public key. But this key, which is clear text for E (PW; PKa), PKa1, PKa2, ..., PKaN)] even with full testing. has no structure and is similar to a random sequence of bits. At step 2, we have E_PKaJ (k II h (k)) - the ciphertext Therefore, he cannot isolate the true password word at this obtained by encrypting the text (k II h (k)) on the public key step. PKaJ of user A. It has no structure, which does not allow the In step 2, each selected PW option leads to the task of attacker to find PW from the ciphertext E (PW ; E_PKaJ (k II finding the key k by the corresponding public key PKa from h (k)) even by full testing. step 1 and the ciphertext E_PKa (k) obtained by decrypting E After step 1, an attacker can have IPWI variants of the (PW; E_PKa (k)) to PW. Even if it is possible to test all the set of public keys {PKa1, PKa2, ..., PKaN}, where IPWI is the secret keys of the asymmetric encryption algorithm, it is number of possible variants of the word PW. impossible to determine the true key k, since it also has no After 2 steps, the attacker has IPWI * N decryption structure. With short public and secret keys of the asymmetric tasks for the ciphertext E_PKaJ (k II h (k). To assess the algorithm (for example, 512 bits), a faster finding of k is complexity of decryption, one must proceed from the strength possible, but still among the options for PW. of the asymmetric algorithm used. It follows that, to increase the complexity of finding the 3 option for protocol amplification. key k by an attacker, it is necessary to increase the number of options for PW. • 1. A: [A, E (PW - Ra; PKa1, PKa2, ..., PKaN, h (*))]  B. Here are options for enhancing the strength of the EKE 80 • 2. B: Iterates over Ra and looks for a true set of public keys. password word is also used for this. There are many ways to The criterion is the structure of the text [PKa1, PKa2, ..., do this. PKaN, h (*)]. Selects one PKaJ key of user A. But first, we will demonstrate how to strengthen this protocol using asymmetric operations, but to modify the • E (PW-Ra; E_PKaJ (k II h (k))  A, k is a high-entropy key. Diffie-Hellman protocol to the transport protocol. • 3. A: iterates over its public keys PKa1, PKa2, ..., PKaN (Ra Gain option. - knows), searches for PKaJ and key k. The criterion is finding Participant A sends a set of {Ya1, ..., YaL} public keys the key k with the correct value h (k) attached. to Participant B. Participant B sends a set of {Yb1, ..., YbL} public keys to Participant A. 4 option protocol amplification. For clarity, the power sets of public keys are selected • 1. A: [A, E (PW - Ra; PKa1, PKa2, ..., PKaN, h (*))]  B. the same. In general, these capacities may be different. • 2. B: Iterates over Ra and looks for a true set of public keys. Participant A randomly selects the public key YbJ and The criterion is the structure of the text [PKa1, PKa2, ..., his private key XaS, builds a key of the form K = XaS * YbJ. PKaN, h (*)]. Selects one PKaJ key of user A. Then he can use this key, for example, to encrypt some • E (PW-Rb; E_PKaJ (k II h (k))  A, k is a high-entropy plaintext OT on the key K and send it to participant B: key. C = E (K, OT)  B. Participant B, in order to find K and decrypt C, must sort • 3. A: iterates over its public keys PKa1, PKa2, ..., PKaN and through L variants of his secret and L variants of Participant A Rb, searches for PKaJ and key k. The criterion is finding the public keys. The criterion for the correct choice is the criterion key k with the correct value h (k) attached. for clear text. The complexity for B is in order equal to the In the fourth embodiment, the complexity of the user A number L ^ 2 times the complexity of the operation of increases due to the unknown vector Rb and the choice of one decryption and application of the plain text criterion. For an of N public keys by the user B, and the complexity of the user attacker who also has all the public keys of the participants, the B increases due to the unknown vector Ra. task is to solve L ^ 2 discrete logarithm problems (albeit with a In option 3, the vector is Rb = Ra and is known to user parameter of 112 bits). A. But in all these cases, the complexity of the decryption In the proposed variant of protocol amplification, we lose in task for the attacker also increases. the so-called communication complexity of the protocol when transmitting sets of public keys L ^ 2 times. The complexity of the decryption process for participant B also increases by the Diffie-Hellman cryptographic key agreement same amount. The security parameter is 112 bits, selected by protocol and suggestions for enhancing its strength. license restriction, it suggests that plaintext and key can in Another type of key installation protocols, in addition principle be found, but at very high computational costs. The to key transportation protocols, are key agreement protocols choice of the parameter L may complicate this possibility. [7-8]. In the key agreement protocol, none of the participants knows in advance which key will be installed for communication with other participants. This key will be SESPAKE cryptographic protocol and suggestions generated as a result of the exchange of some information for enhancing its strength. between the participants in the interaction. The most famous An authentication channel for the Diffie-Hellman example of a key agreement protocol is the Diffie and protocol can be provided using digital signatures or a shared Hellman protocol [9]. secret (password). Many options are suggested for this. Recall it for the case of using a group of points of Consider the SESPAKE protocol, where participants are elliptic curves. supposed to have a common secret word PW. A, B - participants in the protocol. Recall the main steps of this protocol. Details can be P is the base point of the elliptic curve. 112 bits is a found in [6]. This protocol also uses a group of points of an security setting. elliptic curve (In our consideration, the security parameter is Xa is the secret key of participant A, a natural number. 112 bits). Ya = Xa * P - public key of A  B. A is the client, B is the server. Both store L points {Q_1, ..., Xb is the secret key of participant B, a natural number. Q_L} and point P of the elliptic curve. Participant B Yb = Xb * P - public key of B  A. additionally stores: A: calculates the shared key K = Xa * Yb = (Xa * Xb) *P number ind from the set {1, ..., L}, string salt, point B: computes the shared key K = Xb * Ya = (Xb * Xa) * Q_pw = int (f (PW, salt)) * Q_ind. Password words PW may P not be stored. It is known that for the safe use of this protocol, it is 1. B  A: ind, salt. necessary to add an authentication channel to it in order to 2. A computes Qa_pw = int (f (PW, salt) * Q_ind. (= exclude a “man in the middle” attack. In particular, the 81 Q_pw of server B). the computing power of the attacker and the computing power A  B: Ya = Xa * P - Qa_pw. (= Xa * P - Q_pw) of the legitimate participants in the interaction, as well as on the requirement for the speed of obtaining information, which 3. B calculates Qb = Ya + Q_pw, (= (Xa * P - Q_pw) + Q_pw in turn can be dictated by the necessary level of security in = Xa * P) each specific case. B A: Yb = Xb * P + Q_pw. III. CONCLUSIONS 4. A: Qa = Yb - Qa_pw = Xb * P + Q_pw - Qa_pw = Xb * P. The technology of asymmetric execution of Xa * Xb * P gets  Ka, cryptosystems in the PAKE protocol can increase the security of these protocols. In this paper, this is demonstrated on three B: Qb = Ya + Q_pw = (Xa * P - Qa_pw) + Q_pw = Xa * P. protocols. For each of them, specific methods for asymmetric Xb * Xa * P gets  Kb. execution are proposed. Ka = Kb. (Here it is omitted how specifically Ka and Kb are obtained, it is enough that the relation Xa * Xb * P = Xb * Xa REFERENCES * P is fulfilled). It can be seen from the above description that the [1] Varfolomeev А.А. Nekotorye rekomendacii po povysheniyu stojkosti shifra s malym razmerom klyucha k metodu polnogo SESPAKE protocol is a variant of the Diffie-Hellman protocol oprobovaniya. Voprosy kiberbezopasnosti [Cybersecurity issues], with public keys, distorted by the function of the password 2015, No 5(13), pp. 60-62. word PW, known only to legitimate participants. [2] Varfolomeev А.А. O nekotoryh predvaritel'nyh preobrazovaniyah otkrytogo teksta tipa «All-Or-Nothing» dlya usileniya stojkosti shifra k metodu polnogo oprobovaniya. SIBCON 2016. Option with asymmetric execution. http://ni.spbstu.ru/wp-content/uploads/2016/05/SibCon-2016- programa.pdf . The basic idea is not to pass the number ind. Participant [3] Varfolomeev А.А. Ob asimmetrichno vypolnimyh simmetrichnyh A randomly selects ind from the set {1, ..., L} and computes kriptosistemah (shifrah). RusKripto 2018. Ya, but participant B sends L public keys. [4] Bellovin, S. M.; M. Merritt (May 1992). Encrypted Key Exchange: A is the client, B is the server. Both store L points Password-Based Protocols Secure Against Dictionary Attacks. Proceedings of the I.E.E.E. Symposium on Research in Security and {Q_1, ..., Q_L} and point P of the elliptic curve. Participant B Privacy. Oakland. p. 72. doi:10.1109/RISP.1992.213269. additionally stores: string salt, points Q_pw1 = int (f (PW, ISBN 978-0-8186-2825-2. salt)) * Q_1, ...,. Q_pwL = int (f (PW, salt)) * Q_L. The [5] Jareck, S., Krawczyk H., Xu J. (2018). OPAQUE: An Asymmetric password word PW may not be stored. PAKE Protocol Secure Against Pre-Computation Attacks. Advances 1. B  A: salt. in Cryptology. Lecture Notes in Computer Science. 10822. pp. 456– 486. doi:10.1007/978-3-319-78372-7_15. ISBN 978-3-319-78371- 0. 2. A computes for random Qa_pwJ = int (f (PW, salt)) * Q_J. [6] RFC 8133. The Security Evaluated Standardized Password- Authenticated Key Exchange (SESPAKE) Protocol. A  B: YaJ = Xa * P - Qa_pwJ. https://tools.ietf.org/html/rfc8133 [7] Slovar' kriptograficheskih terminov. / Pod red. B. A. Pogorelova i 3. B  A: Yb1 = Xb + Q_pw1, ..., YbL = Xb + Q_pwL. V. N. Sachkova. - М.: МЦНМО, 2006. - 94 с. [8] Menezes A., van Oorschot P., Vanstone S., (1997). Handbook of A: chose YbJ and Qa = YbJ - Qa_pwJ = (Xb * P + Q_pwJ) - Applied Cryptography, Boca Raton, CRC Press. ISBN 0-8493- Qa_pwJ = Xb * P. 8523-7. (Available online) [9] Diffie W., Hellman M., New Directions in Cryptography, IEEE B calculates Qb1 = YaJ + Q_pw1, ..., QbL = YaJ + Q_pwL. Transactions on Information Theory, vol. IT-22, Nov. 1976, pp: Among them, with the right Q_pwJ. 644—654. [10] Smyshlyaev S., Oshkin I., Alekseev E., Ahmetzyanova L. (2015). QbJ = YaJ + Q_pwJ = (Xa * P - Qa_pwJ) + Q_pwJ = Xa * P. "On the Security of One Password Authenticated Key Exchange Protocol". Cryptology ePrint Archive (Report 2015/1237). 4. A: The Ka key is used to encrypt plaintext OT. This work does not provide specific parameters for enhancing durability, since in many respects they depend on 82