Subject: [Cfrg] The SESPAKE protocol and PAKE requirements

From: "Stanislav V. Smyshlyaev" <[email-masked]>
Date: Thu, 11 Feb 2016 14:02:48 +0300

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

---

From: Schmidt, Jörn-Marc <[email-masked]>
Date: Wed, 17 Feb 2016 16:17:31 +0000

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:[email-masked]] 
Gesendet: Donnerstag, 11. Februar 2016 12:03
An: [email-masked]; Schmidt, Jörn-Marc; [email-masked]; 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,

CryptoPro LLC

---

From: "Stanislav V. Smyshlyaev" <[email-masked]>
Date: Sat, 20 Feb 2016 11:36:08 +0300

Dear Jörn!

Thank you very much for your comment on R5!

What do you think about defining a policy of algorithm usage in PAKE
protocols?
For example, in the current version of SESPAKE RFC draft we are based on
Russian standards – GOST R 34.11-2012 hash and HMAC, but of course the
document that refers only to GOSTs cannot become a CFRG document.

Shouldn't we require multi-algorithm support – as in the PAKE requirements,
as in our SESPAKE?

Best regards,

Stanislav

С уважением,

Станислав Смышляев, к.ф.-м.н.,

Начальник отдела защиты информации

ООО «КРИПТО-ПРО»

2016-02-17 19:17 GMT+03:00 Schmidt, Jörn-Marc <
[email-masked]>:

> 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
>
> An: [email-masked]; Schmidt, Jörn-Marc; [email-masked];
> Paterson, Kenny; Mike Hamburg; Paul Lambert
> R6: A PAKE scheme MAY discuss its design choice with regard to
> performance, i.e., its optimization goals.
>
> 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
> 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]).
>
> [2] Stanislav V. Smyshlyaev, Igor B. Oshkin, Evgeniy K. Alekseev, Liliya
> R. Ahmetzyanova, “On the Security of One Password Authenticated Key
> Exchange Protocol”

---

From: Schmidt, Jörn-Marc <[email-masked]>
Date: Tue, 23 Feb 2016 06:52:31 +0000

Dear Stanislav,

Thank you for your input!

>What do you think about defining a policy of algorithm usage in PAKE protocols? 
>For example, in the current version of SESPAKE RFC draft we are based on Russian standards – GOST R 34.11-2012 hash and HMAC, but of course the >document that refers only to GOSTs cannot become a CFRG document. 

>Shouldn't we require multi-algorithm support – as in the PAKE requirements, as in our SESPAKE?

You mean to add a requirement to state which algorithms can be used as underlying primitives? 
I haven't analyzed SESPAKE in detail - but wouldn't it work with any cryptographic hash function? 
In case a PAKE requires a special property of the underlying hash function/cipher/etc., I think this could be covered with
"R2: A PAKE scheme SHOULD come with a security proof and clearly state its assumptions and models." by adding a sentence about useful primitives.

I personally would leave it up to the designer of the PAKE scheme to decide whether the scheme mentions a specific primitive (e.g. is specified using AES & SHA2) or leaves it up to the implementer (e.g. speaking of block cipher & hash function in an abstract manner). Do you think we should push in one direction in the requirements draft?

Best regards,

Jörn

---

From: "Stanislav V. Smyshlyaev" <[email-masked]>
Date: Thu, 25 Feb 2016 08:39:56 +0300

Dear Jörn,
Thank you very much for your comments! SESPAKE will of course work with any
underlying hash/HMAC/elliptic curve/PBKDF and we’ll prepare a new version
of our draft which will explicitly stress it.
I do not insist on addition of any specific words about primitives
specification in the requirements draft. In contrary to the question with
counters handling (our previous discussion), I think it is ok if this issue
will be addressed by any author of a draft at his own discretion.

Kindest regards,
Stanislav

2016-02-23 9:52 GMT+03:00 Schmidt, Jörn-Marc <[email-masked]
>:

> In case a PAKE requires a special property of the underlying hash
> function/cipher/etc., I think this could be covered with
> "R2: A PAKE scheme SHOULD come with a security proof and clearly state its
> assumptions and models." by adding a sentence about useful primitives.
>
> I personally would leave it up to the designer of the PAKE scheme to
> decide whether the scheme mentions a specific primitive (e.g. is specified
> using AES & SHA2) or leaves it up to the implementer (e.g. speaking of
> block cipher & hash function in an abstract manner). Do you think we should
> push in one direction in the requirements draft?
>
> Best regards,
>
> Jörn
>
>
>
>