Independent Submission S. Smyshlyaev, Ed. Request for Comments: 8133 E. Alekseev Category: Informational I. Oshkin ISSN: 2070-1721 V. Popov CRYPTO-PRO March 2017 The Security Evaluated Standardized Password-Authenticated Key Exchange (SESPAKE) Protocol## Abstract

This document describes the Security Evaluated Standardized Password- Authenticated Key Exchange (SESPAKE) protocol. The SESPAKE protocol provides password-authenticated key exchange for usage in systems for protection of sensitive information. The security proofs of the protocol were made for situations involving an active adversary in the channel, including man-in-the-middle (MitM) attacks and attacks based on the impersonation of one of the subjects. Status of This Memo This document is not an Internet Standards Track specification; it is published for informational purposes. This is a contribution to the RFC Series, independently of any other RFC stream. The RFC Editor has chosen to publish this document at its discretion and makes no statement about its value for implementation or deployment. Documents approved for publication by the RFC Editor are not a candidate for any level of Internet Standard; see Section 2 of RFC 7841. Information about the current status of this document, any errata, and how to provide feedback on it may be obtained at http://www.rfc-editor.org/info/rfc8133. Copyright Notice Copyright (c) 2017 IETF Trust and the persons identified as the document authors. All rights reserved. This document is subject to BCP 78 and the IETF Trust's Legal Provisions Relating to IETF Documents (http://trustee.ietf.org/license-info) in effect on the date of publication of this document. Please review these documents carefully, as they describe your rights and restrictions with respect to this document.

## Table of Contents

1. Introduction ....................................................2 2. Conventions Used in This Document ...............................2 3. Notations .......................................................3 4. Protocol Description ............................................4 4.1. Protocol Parameters ........................................5 4.2. Initial Values of the Protocol Counters ....................7 4.3. Protocol Steps .............................................7 5. Construction of Points {Q_1,...,Q_N} ...........................11 6. Security Considerations ........................................13 7. IANA Considerations ............................................13 8. References .....................................................14 8.1. Normative References ......................................14 8.2. Informative References ....................................15 Appendix A. Test Examples for GOST-Based Protocol Implementation ..16 A.1. Examples of Points .........................................16 A.2. Test Examples of SESPAKE ...................................17 Appendix B. Point Verification Script .............................33 Acknowledgments ...................................................51 Authors' Addresses ................................................51## 1. Introduction

This document describes the Security Evaluated Standardized Password- Authenticated Key Exchange (SESPAKE) protocol. The SESPAKE protocol provides password-authenticated key exchange for usage in systems for protection of sensitive information. The protocol is intended to be used to establish keys that are then used to organize a secure channel for protection of sensitive information. The security proofs of the protocol were made for situations involving an active adversary in the channel, including man-in-the-middle (MitM) attacks and attacks based on the impersonation of one of the subjects.## 2. Conventions Used in This Document

The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this document are to be interpreted as described in [RFC2119].

## 3. Notations

This document uses the following parameters of elliptic curves in accordance with [RFC6090]: E an elliptic curve defined over a finite prime field GF(p), where p > 3; p the characteristic of the underlying prime field; a, b the coefficients of the equation of the elliptic curve in the canonical form; m the elliptic curve group order; q the elliptic curve subgroup order; P a generator of the subgroup of order q; X, Y the coordinates of the elliptic curve point in the canonical form; O zero point (point at infinity) of the elliptic curve. This memo uses the following functions: HASH the underlying hash function; HMAC the function for calculating a message authentication code (MAC), based on a HASH function in accordance with [RFC2104]; F(PW, salt, n) the value of the function PBKDF2(PW, salt, n, len), where PBKDF2(PW, salt, n, len) is calculated according to [RFC8018]. The parameter len is considered equal to the minimum integer that is a multiple of 8 and satisfies the following condition: len >= floor(log_2(q)).

This document uses the following terms and definitions for the sets and operations on the elements of these sets: B_n the set of byte strings of size n, n >= 0; for n = 0, the B_n set consists of a single empty string of size 0; if b is an element of B_n, then b = (b_1,...,b_n), where b_1,...,b_n are elements of {0,...,255}; || concatenation of byte strings A and C, i.e., if A in B_n1, C in B_n2, A = (a_1,a_2,...,a_n1) and C = (c_1,c_2,...,c_n2), then A || C = (a_1,a_2,...,a_n1,c_1,c_2,...,c_n2) is an element of B_(n1 + n2); int(A) for the byte string A = (a_1,...,a_n) in B_n, an integer int(A) = 256^(n - 1)a_n +...+ 256^(0)a_1; bytes_n(X) the byte string A in B_n, such that int(A) = X, where X is an integer and 0 <= X < 256^n; BYTES(Q) for Q in E, the byte string bytes_n(X) || bytes_n(Y), where X, Y are standard Weierstrass coordinates of point Q and n = ceil(log_{256}(p)).## 4. Protocol Description

The main point of the SESPAKE protocol is that parties sharing a weak key (a password) generate a strong common key. An active adversary who has access to a channel is not able to obtain any information that can be used to find a key in offline mode, i.e., without interaction with legitimate participants. The protocol is used by subjects A (client) and B (server) that share some secret parameter that was established in an out-of-band mechanism: a client is a participant who stores a password as a secret parameter, and a server is a participant who stores a password-based computed point of the elliptic curve. The SESPAKE protocol consists of two steps: the key-agreement step and the key-confirmation step. During the first step (the key-agreement step), the parties exchange keys using Diffie-Hellman with public components masked by an element that depends on the password -- one of the predefined elliptic curve points multiplied by the password-based coefficient. This approach provides an implicit key authentication, which means that after this step, one party is assured that no other party, aside from a specifically identified second party, may gain access to the generated secret key. During

the second step (the key-confirmation step), the parties exchange strings that strongly depend on the generated key. After this step, the parties are assured that a legitimate party, and no one else, actually has possession of the secret key. To protect against online guessing attacks, counters that indicate the number of failed connections were introduced in the SESPAKE protocol. There is also a special technique for small-order point processing and a mechanism that provides protection against reflection attacks by using different operations for different sides.## 4.1. Protocol Parameters

Various elliptic curves can be used in the protocol. For each elliptic curve supported by clients, the following values MUST be defined: o the protocol parameters identifier, ID_ALG (which can also define a HASH function, a pseudorandom function (PRF) used in the PBKDF2 function, etc.), which is a byte string of an arbitrary length; o the point P, which is a generator point of the subgroup of order q of the curve; o the set of distinct curve points {Q_1,Q_2,...,Q_N} of order q, where the total number of points, N, is defined for the protocol instance. The method of generation of the points {Q_1,Q_2,...,Q_N} is described in Section 5. The following protocol parameters are used by subject A: 1. The secret password value PW, which is a byte string that is uniformly randomly chosen from a subset of cardinality 10^10 or greater of the set B_k, where k >= 6 is the password length. 2. The list of curve identifiers supported by A. 3. Sets of points {Q_1,Q_2,...,Q_N}, corresponding to curves supported by A. 4. The C_1^A counter, which tracks the total number of unsuccessful authentication trials in a row, and a value of CLim_1 that stores the maximum possible number of such events.

5. The C_2^A counter, which tracks the total number of unsuccessful authentication events during the period of usage of the specific PW, and a value of CLim_2 that stores the maximum possible number of such events. 6. The C_3^A counter, which tracks the total number of authentication events (successful and unsuccessful) during the period of usage of the specific PW, and a value of CLim_3 that stores the maximum possible number of such events. 7. The unique identifier, ID_A, of subject A (OPTIONAL), which is a byte string of an arbitrary length. The following protocol parameters are used by subject B: 1. The values ind and salt, where ind is in {1,...,N} and salt is in {1,...,2^128-1}. 2. The point Q_PW, satisfying the following equation: Q_PW = int(F(PW, salt, 2000))*Q_ind. It is possible that the point Q_PW is not stored and is calculated using PW in the beginning of the protocol. In that case, B has to store PW and points {Q_1,Q_2,...,Q_N}. 3. The ID_ALG identifier. 4. The C_1^B counter, which tracks the total number of unsuccessful authentication trials in a row, and a value of CLim_1 that stores the maximum possible number of such events. 5. The C_2^B counter, which tracks the total number of unsuccessful authentication events during the period of usage of the specific PW, and a value of CLim_2 that stores the maximum possible number of such events. 6. The C_3^B counter, which tracks the total number of authentication events (successful and unsuccessful) during the period of usage of the specific PW, and a value of CLim_3 that stores the maximum possible number of such events. 7. The unique identifier, ID_B, of subject B (OPTIONAL), which is a byte string of an arbitrary length.

## 4.2. Initial Values of the Protocol Counters

After the setup of a new password value PW, the values of the counters MUST be assigned as follows: o C_1^A = C_1^B = CLim_1, where CLim_1 is in {3,...,5}; o C_2^A = C_2^B = CLim_2, where CLim_2 is in {7,...,20}; o C_3^A = C_3^B = CLim_3, where CLim_3 is in {10^3,10^3+1,...,10^5}.## 4.3. Protocol Steps

The basic SESPAKE steps are shown in the scheme below: +--------------------------+------------+---------------------------+ | A [A_ID, PW] | | B [B_ID, Q_PW, ind, salt] | +--------------------------+------------+---------------------------+ | if C_1^A or C_2^A or | | | | C_3^A = 0 ==> quit | | | | decrement C_1^A, C_2^A, | A_ID ---> | if C_1^B or C_2^B or | | C_3^A by 1 | | C_3^B = 0 ==> quit | | z_A = 0 | <--- | decrement C_1^B, C_2^B, | | | ID_ALG, | C_3^B by 1 | | | B_ID | | | | (OPTIONAL),| | | | ind, salt | | | Q_PW^A = int(F(PW, salt, | | | | 2000))*Q_ind | | | | choose alpha randomly | | | | from {1,...,q-1} | | | | u_1 = alpha*P - Q_PW^A | u_1 ---> | if u_1 not in E ==> quit | | | | z_B = 0 | | | | Q_B = u_1 + Q_PW | | | | choose beta randomly from | | | | {1,...,q-1} | | | | if m/q*Q_B = O ==> Q_B = | | | | beta*P, z_B = 1 | | | | K_B = | | | | HASH(BYTES(( m/q*beta* | | | | (mod q))*Q_B )) | | if u_2 not in E ==> quit | <--- u_2 | u_2 = beta*P + Q_PW | | Q_A = u_2 - Q_PW^A | | | | if m/q*Q_A = O ==> Q_A = | | | | alpha*P, z_A = 1 | | | | K_A = HASH(BYTES(( m/q* | | | | alpha(mod q))*Q_A )) | | | | | | |

| U_1 = BYTES(u_1), U_2 = | | | | BYTES(u_2) | | | | MAC_A = HMAC(K_A, 0x01 | DATA_A, | U_1 = BYTES(u_1), U_2 = | | || ID_A || ind || salt | MAC_A ---> | BYTES(u_2) | | || U_1 || U_2 || ID_ALG | | | | (OPTIONAL) || DATA_A) | | | | | | if MAC_A != HMAC(K_B, | | | | 0x01 || ID_A || ind || | | | | salt || U_1 || U_2 || | | | | ID_ALG (OPTIONAL) || | | | | DATA_A) ==> quit | | | | if z_B = 1 ==> quit | | | | C_1^B = CLim_1, increment | | | | C_2^B by 1 | | if MAC_B != HMAC(K_A, | <--- | MAC_B = HMAC(K_B, 0x02 || | | 0x02 || ID_B || ind || | DATA_B, | ID_B || ind || salt || | | salt || U_1 || U_2 || | MAC_B | U_1 || U_2 || ID_ALG | | ID_ALG (OPTIONAL) || | | (OPTIONAL) || DATA_A || | | DATA_A || DATA_B) ==> | | DATA_B) | | quit | | | | if z_A = 1 ==> quit | | | | C_1^A = CLim_1, | | | | increment C_2^A by 1 | | | +--------------------------+------------+---------------------------+ Table 1: SESPAKE Protocol Steps The full description of the protocol consists of the following steps: 1. If any of the counters C_1^A, C_2^A, or C_3^A is equal to 0, A finishes the protocol with an informational error regarding exceeding the number of trials that is controlled by the corresponding counter. 2. A decrements each of the counters C_1^A, C_2^A, and C_3^A by 1, requests open authentication information from B, and sends the ID_A identifier. 3. If any of the counters C_1^B, C_2^B, or C_3^B is equal to 0, B finishes the protocol with an informational error regarding exceeding the number of trials that is controlled by the corresponding counter. 4. B decrements each of the counters C_1^B, C_2^B, and C_3^B by 1.

5. B sends the values of ind, salt, and the ID_ALG identifier to A. B also can OPTIONALLY send the ID_B identifier to A. All subsequent calculations are done by B in the elliptic curve group defined by the ID_ALG identifier. 6. A sets the curve defined by the received ID_ALG identifier as the used elliptic curve. All subsequent calculations are done by A in this elliptic curve group. 7. A calculates the point Q_PW^A = int(F(PW, salt, 2000))*Q_ind. 8. A chooses randomly (according to the uniform distribution) the value alpha; alpha is in {1,...,q-1}; then A assigns z_A = 0. 9. A sends the value u_1 = alpha*P - Q_PW^A to B. 10. After receiving u_1, B checks to see if u_1 is in E. If it is not, B finishes with an error and considers the authentication process unsuccessful. 11. B calculates Q_B = u_1 + Q_PW, assigns z_B = 0, and chooses randomly (according to the uniform distribution) the value beta; beta is in {1,...,q-1}. 12. If m/q*Q_B = O, B assigns Q_B = beta*P and z_B = 1. 13. B calculates K_B = HASH(BYTES(( m/q*beta*(mod q))*Q_B )). 14. B sends the value u_2 = beta*P + Q_PW to A. 15. After receiving u_2, A checks to see if u_2 is in E. If it is not, A finishes with an error and considers the authentication process unsuccessful. 16. A calculates Q_A = u_2 - Q_PW^A. 17. If m/q*Q_A = O, then A assigns Q_A = alpha*P and z_A = 1. 18. A calculates K_A = HASH(BYTES(( m/q*alpha(mod q))*Q_A )). 19. A calculates U_1 = BYTES(u_1), U_2 = BYTES(u_2). 20. A calculates MAC_A = HMAC(K_A, 0x01 || ID_A || ind || salt || U_1 || U_2 || ID_ALG (OPTIONAL) || DATA_A), where DATA_A is an OPTIONAL string that is authenticated with MAC_A (if it is not used, then DATA_A is considered to be of zero length). 21. A sends DATA_A, MAC_A to B.

22. B calculates U_1 = BYTES(u_1), U_2 = BYTES(u_2). 23. B checks to see if the values MAC_A and HMAC(K_B, 0x01 || ID_A || ind || salt || U_1 || U_2 || ID_ALG (OPTIONAL) || DATA_A) are equal. If they are not, it finishes with an error and considers the authentication process unsuccessful. 24. If z_B = 1, B finishes with an error and considers the authentication process unsuccessful. 25. B sets the value of C_1^B to CLim_1 and increments C_2^B by 1. 26. B calculates MAC_B = HMAC(K_B, 0x02 || ID_B || ind || salt || U_1 || U_2 || ID_ALG (OPTIONAL) || DATA_A || DATA_B), where DATA_B is an OPTIONAL string that is authenticated with MAC_B (if it is not used, then DATA_B is considered to be of zero length). 27. B sends DATA_B, MAC_B to A. 28. A checks to see if the values MAC_B and HMAC(K_A, 0x02 || ID_B || ind || salt || U_1 || U_2 || ID_ALG (OPTIONAL) || DATA_A || DATA_B) are equal. If they are not, it finishes with an error and considers the authentication process unsuccessful. 29. If z_A = 1, A finishes with an error and considers the authentication process unsuccessful. 30. A sets the value of C_1^A to CLim_1 and increments C_2^A by 1. After the procedure finishes successfully, subjects A and B are mutually authenticated, and each subject has an explicitly authenticated value of K = K_A = K_B. Notes: 1. In cases where the interaction process can be initiated by any subject (client or server), the ID_A and ID_B options MUST be used, and the receiver MUST check to see if the identifier he had received is not equal to his own; otherwise, it finishes the protocol. If an OPTIONAL parameter ID_A (or ID_B) is not used in the protocol, it SHOULD be considered equal to a fixed byte string (a zero-length string is allowed) defined by a specific implementation.

2. The ind, ID_A, ID_B, and salt parameters can be agreed upon in advance. If some parameter is agreed upon in advance, it is possible not to send it during a corresponding step. Nevertheless, all parameters MUST be used as corresponding inputs to the HMAC function during Steps 20, 23, 26, and 28. 3. The ID_ALG parameter can be fixed or agreed upon in advance. 4. It is RECOMMENDED that the ID_ALG parameter be used in HMAC during Steps 20, 23, 26, and 28. 5. Continuation of protocol interaction in a case where any of the counters C_1^A or C_1^B is equal to zero MAY be done without changing the password. In this case, these counters can be used for protection against denial-of-service attacks. For example, continuation of interaction can be allowed after a certain delay period. 6. Continuation of protocol interaction in a case where any of the counters C_2^A, C_3^A, C_2^B, or C_3^B is equal to zero MUST be done only after changing the password. 7. It is RECOMMENDED that during Steps 9 and 14 the points u_1 and u_2 be sent in a non-compressed format (BYTES(u_1) and BYTES(u_2)). However, point compression MAY be used. 8. The use of several Q points can reinforce the independence of the data streams when working with several applications -- for example, when two high-level protocols can use two different points. However, the use of more than one point is OPTIONAL.## 5. Construction of Points {Q_1,...,Q_N}

This section provides an example of a possible algorithm for the generation of each point Q_i in the set {Q_1,...,Q_N} that corresponds to the given elliptic curve E. The algorithm is based on choosing points with coordinates with known preimages of a cryptographic hash function H, which is the GOST R 34.11-2012 hash function (see [RFC6986]) with 256-bit output if 2^254 < q < 2^256, and the GOST R 34.11-2012 hash function (see [RFC6986]) with 512-bit output if 2^508 < q < 2^512.

The algorithm consists of the following steps: 1. Set i = 1, SEED = 0, s = 4. 2. Calculate X = int(HASH(BYTES(P) || bytes_s(SEED))) mod p. 3. Check to see if the value of X^3 + aX + b is a quadratic residue in the field F_p. If it is not, set SEED = SEED + 1 and return to Step 2. 4. Choose the value of Y = min{r1, r2}, where r1, r2 from {0,1,...,p-1} are such that r1 != r2 and r1^2 = r2^2 = R mod p for R = X^3 + aX + b. 5. Check to see if the following relations hold for the point Q = (X, Y): Q != O and q*Q = O. If they do, go to Step 6; if not, set SEED = SEED + 1 and return to Step 2. 6. Set Q_i = Q. If i < N, then set i = i + 1 and go to Step 2; otherwise, finish. With the defined algorithm for any elliptic curve E, point sets {Q_1,...,Q_N} are constructed. Constructed points in one set MUST have distinct X-coordinates. Note: The knowledge of a hash function preimage prevents knowledge of the multiplicity of any point related to generator point P. It is of primary importance, because such knowledge could be used to implement an attack against the protocol with an exhaustive search for the password.

## 6. Security Considerations

Any cryptographic algorithms -- particularly HASH functions and HMAC functions -- that are used in the SESPAKE protocol MUST be carefully designed and MUST be able to withstand all known types of cryptanalytic attacks. It is RECOMMENDED that the HASH function satisfy the following condition: o hashlen <= log_2(q) + 4, where hashlen is the length of the HASH function output. It is RECOMMENDED that the output length of hash functions used in the SESPAKE protocol be greater than or equal to 256 bits. The points {Q_1,Q_2,...,Q_N} and P MUST be chosen in such a way that they are provably pseudorandom. As a practical matter, this means that the algorithm for generation of each point Q_i in the set {Q_1,...,Q_N} (see Section 5) ensures that the multiplicity of any point under any other point is unknown. Using N = 1 is RECOMMENDED. Note: The specific adversary models for the protocol discussed in this document can be found in [SESPAKE-SECURITY], which contains the security proofs.## 7. IANA Considerations

This document does not require any IANA actions.

## 8. References

## 8.1. Normative References

[GOST3410-2012] "Information technology. Cryptographic data security. Signature and verification processes of [electronic] digital signature", GOST R 34.10-2012, Federal Agency on Technical Regulating and Metrology (in Russian), 2012. [GOST3411-2012] "Information technology. Cryptographic Data Security. Hashing function", GOST R 34.11-2012, Federal Agency on Technical Regulating and Metrology (in Russian), 2012. [RFC2104] Krawczyk, H., Bellare, M., and R. Canetti, "HMAC: Keyed-Hashing for Message Authentication", RFC 2104, DOI 10.17487/RFC2104, February 1997, <http://www.rfc-editor.org/info/rfc2104>. [RFC2119] Bradner, S., "Key words for use in RFCs to Indicate Requirement Levels", BCP 14, RFC 2119, DOI 10.17487/RFC2119, March 1997, <http://www.rfc-editor.org/info/rfc2119>. [RFC6090] McGrew, D., Igoe, K., and M. Salter, "Fundamental Elliptic Curve Cryptography Algorithms", RFC 6090, DOI 10.17487/RFC6090, February 2011, <http://www.rfc-editor.org/info/rfc6090>. [RFC6986] Dolmatov, V., Ed., and A. Degtyarev, "GOST R 34.11-2012: Hash Function", RFC 6986, DOI 10.17487/RFC6986, August 2013, <http://www.rfc-editor.org/info/rfc6986>. [RFC7091] Dolmatov, V., Ed., and A. Degtyarev, "GOST R 34.10-2012: Digital Signature Algorithm", RFC 7091, DOI 10.17487/RFC7091, December 2013, <http://www.rfc-editor.org/info/rfc7091>.

[RFC7836] Smyshlyaev, S., Ed., Alekseev, E., Oshkin, I., Popov, V., Leontiev, S., Podobaev, V., and D. Belyavsky, "Guidelines on the Cryptographic Algorithms to Accompany the Usage of Standards GOST R 34.10-2012 and GOST R 34.11-2012", RFC 7836, DOI 10.17487/RFC7836, March 2016, <http://www.rfc-editor.org/info/rfc7836>. [RFC8018] Moriarty, K., Ed., Kaliski, B., and A. Rusch, "PKCS #5: Password-Based Cryptography Specification Version 2.1", RFC 8018, DOI 10.17487/RFC8018, January 2017, <http://www.rfc-editor.org/info/rfc8018>.## 8.2. Informative References

[RFC4357] Popov, V., Kurepkin, I., and S. Leontiev, "Additional Cryptographic Algorithms for Use with GOST 28147-89, GOST R 34.10-94, GOST R 34.10-2001, and GOST R 34.11-94 Algorithms", RFC 4357, DOI 10.17487/RFC4357, January 2006, <http://www.rfc-editor.org/info/rfc4357>. [SESPAKE-SECURITY] Smyshlyaev, S., Oshkin, I., Alekseev, E., and L. Ahmetzyanova, "On the Security of One Password Authenticated Key Exchange Protocol", 2015, <http://eprint.iacr.org/2015/1237.pdf>.

© 2005-2022 Tech-invite, All Rights Reserved.