Subject: Re: [Crypto-panel] Stage 5 of PAKE selection process

From: "Stanislav V. Smyshlyaev" <[email-masked]>
Date: Thu, 17 Oct 2019 10:43:58 +0300

Dear Bjoern, Scott, Russ, Yaron, Tibor (and myself :) ),

This is just a kind reminder that according to the plan of the PAKE
process, the overall reviews for the nominated PAKEs should be provided
until October, 30th (so that the chairs are able to make their
recommendations until the Singapore meeting).

All materials on the nominated PAKEs have been gathered (many thanks to
Yaron again) here: https://github.com/cfrg/pake-selection

Many thanks again!

Best regards,
Stanislav Smyshlyaev,
CFRG Secretary

пн, 23 сент. 2019 г. в 21:20, Stanislav V. Smyshlyaev <[email-masked]>:

> Dear Russ and Yaron,
>
> The security proof reviews were intended only to provide input information
> for the Crypto Review Members, who are intended to provide overall reviews
> - thus no PAKEs were dropped in any sense.
>
> In the PAKE selection process description it is assumed that during Stage
> 5 overall reviews are prepared with recommendations (of any kind) - and we
> have an option that after overall reviews (conducted by the Crypto Review
> Panel members) the CFRG chairs are not able to come to a decision. In that
> case at IETF 106 meeting we’ll have a revision of the process (and decide
> what to do next).
>
> In any case, after a PAKE (or two PAKEs...) is selected, the process of
> working on a CFRG document on Recommendations for PAKEs in IETF protocols
> will only start - and then all minor things (like options, parameters,
> implementation recommendations, etc.) can be handled.
>
> So, in my personal opinion, at the current stage we need to reflect the
> current understanding of pros and cons of each nominated PAKE - and then
> we’ll see whether this allows the chairs to make any decision (and move to
> specifying the winning PAKE in the CFRG document, taking into account all
> known issues) - or continue the process of selection in some way.
>
> Best regards,
> Stanislav
>
>
> пн, 23 сент. 2019 г. в 21:03, Yaron Sheffer <[email-masked]>:
>
>> The CPace/AuCPace paper was updated “in place” (in the IACR ePrint repo)
>> since the process started. Also, Hugo hinted that OPAQUE needs to be
>> updated, not the base protocol but some of the options.
>>
>>
>>
>> *From: *Crypto-panel <[email-masked]> on behalf of Russ
>> Housley <[email-masked]>
>> *Date: *Monday, 23 September 2019 at 20:05
>> *To: *"Stanislav V. Smyshlyaev" <[email-masked]>
>> *Cc: *<[email-masked]>
>> *Subject: *Re: [Crypto-panel] Stage 5 of PAKE selection process
>>
>>
>>
>> Stanislav:
>>
>>
>>
>> I just want to make sure that I understand.  Is it correct that none of
>> the algorithms is being dropped or revised based on the proof analysis?
>>
>>
>>
>> Russ
>>
>>
>>
>>
>>
>> On Sep 20, 2019, at 12:23 PM, Stanislav V. Smyshlyaev <[email-masked]>
>> wrote:
>>
>>
>>
>> Dear Bjoern, Scott, Russ, Yaron, Tibor (and myself :) ),
>>
>>
>>
>> Many thanks again for volunteering to provide overall reviews for the
>> nominated PAKEs on behalf of the Crypto Review Panel.
>>
>>
>>
>> According to the PAKE selection process plan, at Stage 5 Crypto Review
>> Panel members write overall reviews for all candidate PAKEs, based on the
>> materials that have been gathered and verified. According to the plan,
>> Stage 5 will last until October, 30th.
>>
>>
>>
>> Those materials (including all partial reviews) have been gathered (many
>> thanks, Yaron!) here: https://github.com/cfrg/pake-selection
>>
>>
>>
>> Best regards,
>>
>> Stanislav,
>>
>> CFRG secretary
>>
>> _______________________________________________
>> Crypto-panel mailing list
>> [email-masked]
>> https://www.irtf.org/mailman/listinfo/crypto-panel
>>
>>
>>
>> _______________________________________________ Crypto-panel mailing list
>> [email-masked] https://www.irtf.org/mailman/listinfo/crypto-panel
>>
> --
>
> С уважением,
>
> Станислав Смышляев, к.ф.-м.н.,
>
> Заместитель генерального директора
>
> ООО «КРИПТО-ПРО»
>
>

---

From: "Stanislav V. Smyshlyaev" <[email-masked]>
Date: Wed, 23 Oct 2019 18:09:22 +0300

Dear CFRG chairs,

Please find below my review of the nominated PAKEs (a Stage 5 review -
i.e., an overall review, taking into account the partial reviews published
at https://github.com/cfrg/pake-selection) with my opinion about possible
recommendations.
According to the PAKE selection process plan, it is one of the Crypto
Review Panel experts reviews, which are to be taken into account by the
CFRG chairs at Stage 6 ("01.11.2019-16.11.2019: CFRG chairs discuss the
obtained reviews and make their recommendations to CFRG/convey to CFRG that
they can’t make a recommendation yet.") – so I am not sure that we want to
disclose these reviews to the group beforehand.

Documents: 8 PAKEs, nominated to the PAKE selection process; partial
reviews provided at Stage 4 (see https://github.com/cfrg/pake-selection).
Reviewer: Stanislav Smyshlyaev
Review Date: 2019-10-23
Summary:
*I would recommend selecting two PAKEs (one balanced and one augmented):
SPAKE2 and OPAQUE. *
*No strong objections against: CPace, AuCPace, VTBPEKE*

1. Balanced
1.1. SPAKE2
The main issue with SPAKE2 is potential existence of a backdoor in case
when the parameters M and N have not been selected in a way that their
joint discrete logarithm is guaranteed to be unknown. A variant of the
protocol has been proposed, which is using a hash-to-curve function – but
such a change would lead to a different protocol, which requires a separate
security analysis. Another possible issue is that the protocol is not
“quantum annoying”, since one needs to calculate only one discrete
logarithm to break any instance of the protocol.
In my opinion, this is not an important issue for the current PAKE
selection process. From the security point of view (regarding “classical”
attacks on key exchange protocols), SPAKE2 has such an advantage as absence
of known attacks exploiting small subgroups. Nevertheless, the checks
related to cofactors are mentioned in the draft, which is good. The experts
do not see major issues with integrating SPAKE2 into TLS 1.3, while there
is a note about minor issues with mixing-in a password value into KDF (but
it seems to be possible to mix it as ePSK). There does not seem to be any
major issues with integrating into IKEv2 also or IoT applications also.
1.2, 1.3. CPace and SPEKE
SPEKE and CPace are based on the same basic scheme, but SPEKE has been
initially defined for the finite fields with the proof only for that case.
Therefore, it seems that it is worth considering CPace, since it is defined
in the general case.
The main issue with CPace seems to be about the stage of negotiating “sid”
parameter. Such a stage turns the CPace into a 2-RTT protocol, which
eliminates its main advantage, efficiency. Such a sid is needed to provide
a proof in UC-framework.  The existence of sid for UC-framework may be more
a technical issue for the approach, so CPace without negotiating the sid
could be considered. The important part of the protocol is a Map2Point
function, which impacts the overall security of the protocol, hence a
careful choice of such a primitive is required.  The CPace without
negotiating sid seems to be easily integrated into TLS 1.3, IKEv2 and IoT
protocols.
Nevertheless, CPace should be separately defined and described (not only as
a part of AuCPace) and carefully studied for the case without sid. In my
opinion, if CPace is selected as recommended PAKE, these actions can be
done during the further steps of writing a CFRG RFC on recommendations for
PAKEs.
1.4. J-PAKE
The main advantage of J-PAKE seems to be that it does not use any
hash-to-curve functions, that can lead to some vulnerabilities or
backdoors. At the same time, it has significant problems with efficiency.
Therefore, it seems to be much more problematic to integrate it into TLS
and IKEv2. Moreover, since IKEv2 and IoT protocols are very sensitive to
the message sizes, long messages (with up to three points in a single
message) in J-PAKE look like a real problem for practical usage.
There are no major problems with the security of the protocol, although
some improvements of the proofs could be made (SE-NIZK-proofs, but “none of
them would be nearly as practical”).
1.5. Balanced: overall
Two ideas compete: DH on password-based points as generators (CPace и
SPEKE) and DH on points, which are masked with password-based points
(SPAKE2).
In my opinion, only CPace and SPAKE can be considered in the current
selection process. For CPace the security without pre-negotiation of sid
should be studied.
Since the only issue with SPAKE2 seems to be eliminating the discrete
logarithm (between M and N) problem and since it can be done (in my
opinion) during the further steps of writing a CFRG RFC on recommendations
for PAKEs, I would recommend SPAKE2 as a balanced PAKE.

2. Augmented
2.1. OPAQUE
OPAQUE is more a “converter” of AKEs to PAKEs using a secure OPRF. The main
advantage of OPAQUE is security against precomputations, which is desirable
for applications, for which augmented PAKEs are preferred.
OPAQUE can be integrated into TLS 1.3 (the method of this integration has
already been specified) without any changes in the protocol.
The authors have recently updated the security proof, addressing the raised
concerns about it; nevertheless, in my opinion, the security assessment is
already mature enough and sufficient for considering it secure.
The protocol is also not “quantum annoying”, but, in my opinion, that
cannot be treated as a major disadvantage of the protocol.
2.2. AuCPace
AuCPace is an augmented version of CPace. AuCPace itself is not secure
against precomputations, but preventing precomputation is a minor change –
a strong version of AuCPace is called strong AuCPace.
There are some questions to the security proof of AuCPace (one of the
reviewers treats the initially subitted version of it as “rather sketchy”),
but, as well as OPAQUE, the security assessment seems to be already mature
enough and sufficient for considering it secure.
AuCPace is a «quantum annoying» PAKE.
Integrating AuCPace into TLS 1.3 is deeply studied in the materials – there
exist some issues, but none of them seems to be critical.
2.3. BSPAKE
BSPAKE – is an augmented Elligator-version of SPAKE2. The main disadvantage
of it is absence of a complete security proof (the authors just say that
the security follows from the security of the underlying elements of the
construction).
The blind salt mechanism is similar to the one used in OPAQUE (OPRF); the
mechanism of using blind salt in AuCPace is different: in AuCPace the salt
is chosen by the client during registration phase.
BSPAKE is «quantum annoying».
BSPAKE is 2-RTT, so it needs certain efforts to be integrated into TLS 1.3.
It seems that a separate work of modifying the PAKE in a way similar to
OPAQUE for TLS 1.3.
BSPAKE does not seem to be a solid construction with detailed security
analysis, in my opinion it should not be considered to be recommended as a
selected PAKE.
2.4. VTBEKE
VTBEKE – is an augmented version of TBEKE (a modified SPEKE). VTBEKE is not
secure against precomputations, but it can be modified to be such by adding
blind salt.
The game-based security proof is sufficient to consider the protocol
secure. The situation with integrating AuCPace into TLS 1.3 is similar to
the one with AuCPace, several issues have to be resolved.
2.5. Augmented: overall
In my opinion, only AuCPace, VTBEKE and OPAQUE can be considered in the
current selection process. Currently only OPAQUE provides security against
precomputations – and in my opinion, it is important for an augmented PAKE
(otherwise, balanced PAKEs are not much less convenient for the same
client-server applications).
Blind-salt versions of AuCPace и VTBEKE should be considered instead of the
"plain" versions of them, but the corresponding detailed security proofs
should be obtained to do so.
In addition, since integration of OPAQUE into TLS 1.3 also seems to be
studied more deeply, I would recommend OPAQUE as an augmented PAKE, if no
patent issues occur to be preventing it.

3. Remarks
To be considered in the future for the selected PAKEs: while integrating a
PAKE into protocol, it is important to decide, on which step to negotiate
PAKE parameters (e.g., elliptic curve group); cross-cipher suite security
must also be taken into account.

4. Overall recommendations
Overall recommendations about the anticipated results of the PAKE
selection. If we are to use PAKEs for IKEv2 or other peer-to-peer
protocols, a balanced PAKE is desirable. To address the remote access
applications or other client-server scenarios, it is better to also have an
augmented PAKE.
Therefore, I would recommend selecting one balanced PAKE and one augmented
PAKE.
*I would recommend selecting two PAKEs (one balanced and one augmented):
SPAKE2 and OPAQUE*. In my opinion, these protocols are mature enough and do
not have any significant problems; all existing concerns can be addressed
during the work on a CFRG RFC on recommendations for PAKEs. CPace, AuCPace
and VTBPEKE are also strong candidates (I wouldn't have any strong
objections against CFRG recommending any of them).

Best regards,
Stanislav Smyshlyaev

---

From: Russ Housley <[email-masked]>
Date: Thu, 24 Oct 2019 13:00:28 -0400

Reviewer: Russ Housley
Review Date: 24 October 2019

CFRG is looking for a PAKE to support TLS 1.3 and IKEv2.  TLS 1.3 has
a very rigid handshake in terms of the number of messages that are
exchanged.  IKEv2 has mechanisms to accomodate the exchange os many
messages as part of authentication.  As a result, I focus on TLS 1.3.
Any PAKE that will work with TLS 1.3 will also work with IKEv2.

RECOMMENDATION: OPAQUE

Observations about each of the candidates follow.

J-PAKE

J-PAKE requires significant computation, even when elliptic curve is
used.

J-PAKE has big messages, even when elliptic curve is used.

J-PAKE is a two round (or three round) protocol, so it does not easily
fit into the TLS handshake.

CPace

CPAKE requires two elliptic curve operations by each party, one to
compute an ephemeral public value from the ephemeral random (private)
value and one to compute the shared secret.

CPake requires the pre-establishment of an session identifier (sid).
Perhaps this is done when the password is established, but the
requirements are not clear to me.  The sid is sent by both the initiator
and the responder.  Assuming the sid is not bigger than an ephemeral
public value, the message sizes seem reasonable.

CPAKE is a one round protocol, so it easily fits into the TLS handshake.

CPake requires a check that the "point order is sufficient for
security parameter 2k".  I could not figure out the check to be
performed.  Maybe I did not spend enough time searching for it ...

AuCPace

AuCPAKE requires two elliptic curve operations by each party, one to
compute an ephemeral public value from the ephemeral random (private)
value and one to compute the shared secret.

AuCPake requires the pre-establishment of an session identifier (sid).
Perhaps this is done when the password is established, but the
requirements are not clear to me.  It also requires a sub-session
identifier (ssid) that can be a concatenation of the nonces from the
TLS handshake or computed from them.  Assuming the sid is not bigger
than an ephemeral public value, the message sizes seem reasonable.

AuCPAKE requires more than one round trip, so it does not easily fits
into the TLS handshake.

AuCPake requires a check that the "point order is sufficient for
security parameter 2k".  I could not figure out the check to be
performed.  Maybe I did not spend enough time searching for it ...

OPAQUE

OPAQUE computational cost is determined by OPRF, Diffie-Hellman, and
authentication.  The OPRF requires two elliptic curve operations for the
client and one for the server.  The Diffie-Hellman requires two elliptic
curve operations for each party.  If authentication uses signature, then
each party will have to generate and verify one signature.

OPAQUE requires two private key operations by each party during
registration, and then just one private key operation by each party
to compute the shared secret.

OPAQUE is a one round protocol; it easily fits into the TLS handshake.

If one is willing to employ an extra round trip, OPAQUE can provide
confidentiality of the user's name by encrypting it in the TLS
handshake key.  It seems like this could be implemented as TLS-in-TLS.

OPAQUE needs an AEAD that includes "key committing".  AES-GCM mode does
not provide this property, but I think that AES-KEY-WRAP mode does.  It
seems straightforward to enhance an AEAD to get this property by adding
a all-zero block to the plaintext and checking it on decryption.

SPAKE2

SPAKE2 computational cost is four elliptic curve operations for each
party after the pre-provisioning takes place.

SPAKE2 is a two round protocol, but the pre-provisioning will take place
prior to any handshake, so it easily fits into the TLS handshake.  That
said, if the point associated with the system-wide elements M and N
become known, then an offline dictionary attack becomes possible.

I found this part odd:

           TT = len(A) || A || len(B) || B || len(S) || S
             || len(T) || T || len(K) || K || len(w) || w

   If an identity is absent, it is omitted from the transcript entirely.

So, if A or B is absent, the inputs quite similar:

           TT = len(B) || B || len(S) || S || len(T) || T
             || len(K) || K || len(w) || w

           TT = len(A) || A || len(S) || S || len(T) || T
             || len(K) || K || len(w) || w

Somehow, using a zero length for the missing identity seems safer:

           TT = len(nil)    || len(B) || B || len(S) || S
             || len(T) || T || len(K) || K || len(w) || w

           TT = len(A) || A || len(nil)    || len(S) || S
             || len(T) || T || len(K) || K || len(w) || w

SPEKE

SPEKE computational cost is two elliptic curve operations for each
party.

SPEKE is a one round protocol, so it easily fits into the TLS
handshake.  Also, the TLS 1.3 Finished message provides the
optional key confirmation.  Finally, identity and session-unique
values are easily accommodated by the client and server Hello
messages.

VTBPEKE

VTBPEKE computational cost is four elliptic curve operations for each
party.

VTBPEKE is not a one round protocol, cannot be accommodated by the
TLS 1.3 handshake.

VTBPEKE offers forward secrecy.  However, if the points associated with
the system-wide element U and V become known, then an offline dictionary
attack becomes possible.

BSPAKE

BSPAKE computational cost is five elliptic curve operations for the
client and four elliptic curve operations for the server.

BSPAKE requires two-round trips in the protocol, so it cannot be
accommodated by the TLS 1.3 handshake.

---

From: Yaron Sheffer <[email-masked]>
Date: Fri, 25 Oct 2019 15:25:08 +0300

Dear CFRG chairs,

Please see my review in the attached (two formats). 

Thanks,
	Yaron

PS: this is formatted as an I-D, but I have not submitted it, at least while the chairs are deliberating their selections.

On 24/10/2019, 20:00, "Crypto-panel on behalf of Russ Housley" <[email-masked] on behalf of [email-masked]> wrote:

    Reviewer: Russ Housley

    RECOMMENDATION: OPAQUE

    J-PAKE

    

    CPace

    

    AuCPace

    

    OPAQUE

    

    SPAKE2

    
    I found this part odd:

    

    

    SPEKE

    VTBPEKE

    

    BSPAKE