RFC 8133
The Security Evaluated Standardized Password-Authenticated Key Exchange (SESPAKE) Protocol
Pages: 51
Informational
Informational
Part 1 of 3 – Pages 1 to 15
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) ProtocolAbstract
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 ................................................511. 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>.
(next page on part 2)