[Cfrg] The SESPAKE protocol and PAKE requirements

["Stanislav V. Smyshlyaev" <[e-mail]>]

Dear colleagues,

We'd like to specify the evaluation of the Standardized Password
Authenticated Key Exchange (SESPAKE) protocol by PAKE requirements in
accordance with [1].

R1: A PAKE scheme MUST clearly state its features regarding
balanced/augmented versions.
Though one side (client) in SESPAKE protocol maintains the raw password as
a secret parameter and the other (server) maintains a password-based
computed point of the elliptic curve, actually the SESPAKE is not resistant
to Key Compromise Impersonation (KCI), which means that an adversary who
has successfully attacked server can automatically impersonate client
without offline dictionary attack. Given this, we can say that SESPAKE
protocol is balanced.

R2: A PAKE scheme SHOULD come with a security proof and clearly state its
assumptions and models.
There is an article [2], in which the models and assumptions used in the
SESPAKE protocol are set out with the proof of the protocol security and
the cryptographic properties analysis.

R3: It SHOULD be possible to implement the PAKE scheme in constant time.
The implementation of the SESPAKE protocol in constant time is achieved
with the common measures. These measures provide the computation in
constant time of some primary operations such as computation of a multiple
point or computation of the hash-function.

R4: The authors MAY show how to protect an implementation of their PAKE
scheme in hostile environments.
---

R5: In case the PAKE scheme is intended to be used with ECC, the authors
SHOULD discuss their requirements for a potential mapping or define a
mapping to be used with the scheme.
When a point on an elliptic curve is given to an input of a hash function,
affine coordinates for short Weierstrass form are used: an x coordinate
value is fed first, an y coordinate value is fed second, both in
little-endian format.

R6: A PAKE scheme MAY discuss its design choice with regard to performance,
i.e., its optimization goals.

If the server has limited computing resources it can store a point Q_PW
instead of the password PW in order to skip a step of the time-consuming
computation of the point Q_PW.

There is the optimized version of the SESPAKE protocol below (see Table 1).
We consider the case when the server and the client are the same on the
point of the computational resources: both store the same low-entropy value
Q_PW.  If the actions are in the same row it means that these actions can
be implemented in the parallel manner.
H is a hash-function. According to the definition
HMAC_{K}(M)=H(K+opad||H(K+ipad||M)). Let E is a subgroup of prime order q
in a group of the used elliptic curve points. P is a generator of the
subgroup E, m is the order of the group of used elliptic curve points, 0_E
is an identity element of the subgroup E.
The step of the Pre-Computations assumes its implementation before the
interactive protocol execution.


                Table 1: the SESPAKE protocol (optimized version)
-----------------------------------------------------------------------------------
                      Public information: E,P,m,q,TA,TB

-----------------------------------------------------------------------------------

 A stores:                          |        | B stores:

 * Q_PW                             |        | * Q_PW

 * A_ID                             |        | * B_ID

===============================================================
                 A                  |        |                   B

===============================================================
                                Pre-Computations

                                    |        |

 * a = random from {1,...,q-1}      |        | * b = random from
{1,...,q-1}
 * u'_1 = a * P                     |        | * u_2 = b * P + Q_PW

-----------------------------------------------------------------------------------
                                    |  A_ID  |

                                    |------->|
                                    |  B_ID  |

                                    |<-------|
 * z_A = 0                          |        | * z_B = 0

 * u_1 = u'_1 - Q_PW                |        |

                                    |  u_1   |

                                    |------->|

                                    |        | * if u_1 not on E => FINISH

                                    |  u_2   |

                                    |<-------|

 * if u_2 not on E => FINISH        |        |
 * Q_A = u_2 - Q_PW                 |        | * Q_B = u_1 + Q_PW

 * if (m/q) * Q_A = 0_E => Q_A = P  |        | * if (m/q) * Q_B = 0_E =>
Q_B = P
   => z_A = 1                       |        |   => z_B = 1

 * src = ( (m/q) * a mod q ) * Q_A  |        | * src = ( (m/q) * b mod q )
* Q_B
 * K_A = H(src)                     |        | * K_B = H(src)

-----------------------------------------------------------------------------------
                     * srcA_MAC = TA||A_ID||ind||salt||u_1||u_2

                     * srcB_MAC = TB||B_ID||ind||salt||u_1||u_2

-----------------------------------------------------------------------------------
 * M_A = HMAC_{K_A}( srcA_MAC )     |        | * M'_A = HMAC_{K_B}(
srcA_MAC )
                                    |  M_A   |

                                    |------->|

                                    |        |

                                    |        |

                                    |        | * if ( M'_A != M_A ) or (
z_B != 0 )
                                    |        |   => FINISH

                                    |        | * M_B = HMAC_{K_B}( srcB_MAC
)
                                    |  M_B   |

                                    |<-------|

* M'_B = HMAC_{K_A}( srcB_MAC )     |        |

* if ( M'_B != M_B ) or ( z_A != 0 )|        |

   => FINISH                        |        |

                                    |        |
-----------------------------------------------------------------------------------


Also the SESPAKE protocol can be optimized on the authentication step.
Indeed, on the step of the computation HMAC with tag srcA_MAC we can store
the result of the computations of the inside and outside compress functions
for the first block that depend on a key only. We will use these stored
values to compute the HMAC with the second tag srcB_MAC.

R7: The authors of a scheme MAY discuss variations of their scheme that
allow the use in special application scenarios. In particular, techniques
that allow agreeing on a long-term (public) key are encouraged.
---

R8: A scheme MAY discuss special ideas and solutions on privacy protection
of its users.
The SESPAKE protocol doesn’t assume the privacy protection of its users.
However, this property can be achieved with some additional measures. The
first is the usage of the PKC (Public Key Cryptography) (the client just
encrypts on server’s public key its identifier and sends this encrypted
value to the server). The second is the storage of the additional long-term
values. For example, the server chooses the random value s, computes the
hash-value L1 = H ( s || A_ID ) and sends it to the client A on the stage
of initialization, so client every time just chooses the random value salt,
computes the hash-value  L2 = H ( L1 || salt ) and sends a pair ( L2, salt
) to the server instead of his identifier. The server searches A_ID among
stored identifiers by verifying the condition L2 = H ( H (s || A_ID) ||
salt ). Both mechanisms can be implemented with the protocols that are
independent of the SESPAKE scheme.

R9: The authors MUST declare the status of their scheme with respect to
patents.
This protocol is approved in the standardization system of the Russian
Federation, has no patent and is available for free use.

XX: A PAKE scheme MUST include descriptions and usage recommendations of
the counters.
For the "online"-guessing every unsuccessful attempt leads to disconnection
caused by the validation failure according to the SESPAKE protocol. The
absence of the fail attempts limitation increases a probability of
"online"-guessing the password. That is the reason, why there is a
limitation of fail connections in a row, fail connections for the
particular password and a limitation of total successful and unsuccessful
connections in the SESPAKE protocol (for more detail see Section 3.9.1 of
the paper [2]).

[1] Schmidt, J., "Requirements for PAKE schemes", Internet-Draft
draft-irtf-cfrg-pake-reqs-01, October 2015
http://tools.ietf.org/html/draft-irtf-cfrg-pake-reqs-01
[2] Stanislav V. Smyshlyaev, Igor B. Oshkin, Evgeniy K. Alekseev, Liliya R.
Ahmetzyanova, “On the Security of One Password Authenticated Key Exchange
Protocol”
http://eprint.iacr.org/2015/1237.pdf


Best regards,

Stanislav V. Smyshlyaev, Ph.D.,

Head of Information Security Department,

CryptoPro LLC