Re: [Cfrg] The SESPAKE protocol and PAKE requirements

[Schmidt, Jörn-Marc <[e-mail]>]

Dear Stanislav,

thank you for you evaluation. That covers exactly what I had in mind when defining the requirements.
Only a minor comment on R5: my main concern was the mapping of a random value or the password to a curve point, which is not required in SESPAKE . 

Best regards,

Jörn

-----Ursprüngliche Nachricht-----
Von: Stanislav V. Smyshlyaev [mailto:[e-mail]] 
Gesendet: Donnerstag, 11. Februar 2016 12:03
An: [e-mail]; Schmidt, Jörn-Marc; [e-mail]; Paterson, Kenny; Mike Hamburg; Paul Lambert
Betreff: The SESPAKE protocol and PAKE requirements

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