Re: [Crypto-panel] Soliciting reviews of submitted PAKE algorithms

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

Good afternoon,

Please find below my own partial reviews (regarding the security proofs and
security claims) for the balanced PAKEs - to be taken into account by the
Crypto Review Panel members on Stage 5 of the review process.

Document: PAKE selection process, Stage 4, balanced PAKEs (reviews of
security proofs and claims)

Reviewer: Stanislav Smyshlyaev

Review Date: 2019-09-12


CPace
The CPace protocol is a balanced PAKE protocol based on the same idea as
the SPEKE protocol. This protocol is described as a part of the augmented
version of the protocol and assumes parties and session identifiers to be
negotiated previously. To consider CPace as an independent protocol there
is a need to provide a full description of the balanced version including
sid, pid (DH group?) negotiation.
The authors consider the key differences between CPace and SPEKE protocol.
The original SPEKE version is vulnerable to several attacks such as
reflection attack, unknown key share attack, exponential equivalence. The
CPace protocol was designed having in mind all these attacks. However, the
protocols of SPEKE types have the undesirable property called key
malleability where an adversary has the possibility to modify both honest
parties’ resulting DH keys unless the whole transcript of the communication
is used for generating the session key. CPace has this property too.
Although this property is believed not to affect security in practice, it
is not clear why the authors did not include the transcript of the
connection into the session key generation procedure. Including
transcription is useful to protect against downgrade and cross-protocol
attacks (if the protocol includes a group negotiation phase). Moreover,
when using the group with cofactor we have the following property: for any
connection with Ya and Yb DH public keys there are another Y’a and Y’b DH
public keys that produce the same session key (e.g. Y’a = Ya * T, where T
has the order c (cofactor)). In order to negate these undesirable
properties we'd recommend including the whole connection transcript into
the session key generation procedure.
The protocol security is proven within the UC framework. The
simulation-based model is well defined. Due to the UC approach using, the
case assuming some users using the same passwords for different protocols
and, more generally, the case where passwords are chosen according to some
arbitrary distribution are taken. The used assumptions are well-known and
well-investigated. The main disadvantage of the security analysis is the
absence of quantitative bounds that are very useful for practice. However,
the considered ideal functionality allows to state that an adversary can
test only one password in a single impersonation.

SPEKE
The author provided the reference https://eprint.iacr.org/2014/585 to the
description of the protocol. The article contains several variants of the
SPEKE protocol, so it is not absolutely clear, which variant is nominated.
Therefore, the version presented in the article containing the security
proof was chosen for the reivew.
The provided proof is simulation-based. The proof shows that in a single
impersonation attempt an adversary can gain information about at most two
possible passwords. The protocol (only for Z*p) security is proven under
the hardness of the DIDH problem in the random oracle model. This problem
is not well investigated for concrete groups and it was just shown that a
lower bound for solving DIDH in the generic model asymptotically matches
the lower bound for solving DDH in the generic model.
The main element of the protocol is a function that is required to map a
string to an element from a large subgroup, such that the discrete
logarithm of the point is unknown. Since the protocol is defined only for
specific group Z*p with p = 2q+1, the mapping function is fixed only for
this case and the proof is essentially based on this function (that treated
as a random oracle). The protocol security in the general case should be
considered for using it with other groups.
SPAKE2
The SPAKE2 is a balanced PAKE protocol based on the clear idea to mask the
low entropy secret before sending it to the channel. The authors of
nomination claim that the protocol does not have a trusted setup needs to
be discussed, since the terminology may differ. The protocol uses three
generators of the used groups and the discrete logarithm relationship
between these group elements in the system setup must be unknown. Note that
draft-irtf-cfrg-spake2-08 clearly states this security assumption and
contains the description of the algorithm used for point generation.
The security is proven in the concurrent indistinguishability-based model.
In the model the passwords are assumed to be uniformly distributed, the
parties cannot be both client and server, each client has only one
password.  Also this model does not provide the corruption interface
allowing an adversary to adaptively compromise client’s passwords. Such
properties can be treated as model disadvantages.

J-PAKE
The J-PAKE is a balanced PAKE protocol based on the NIZK proofs. The main
disadvantage of the protocol is its inefficiency: two rounds and a lot of
group scalar multiplications.  However, this protocol does not require any
trusted setup and additional Map2Point functions.
The protocol security is proven in the concurrent
indistinguishability-based model. In the model the passwords are assumed to
be uniformly distributed, the parties cannot be both client and server
(that can lead to missing reflection attacks), each client has only one
password.  Such properties can be treated as model disadvantages.
The proof states that the protocol is secure under the hardness of the DSDH
problem, the existence of computational randomness extractors, and the
simulation-sound extractability and unbounded zero-knowledge of the used
NIZK proof system. Note that the Schnorr proof, which was recommended for
the J-PAKE protocol, satisfies this strong security assumption only in a
model with algebraic adversaries and random oracles. So, unlike SPAKE2 and
CPace, the J-PAKE protocol requires a lot of trust to the used primitives.
Note that including labels (party’s identifiers) only in ZKP protects
against UKS and reflection attacks.  Nevertheless, we recommend including
the whole transcript into the key generation procedure.
In addition, the RFC does not explicitly describe how to deal with groups
where cofactor is not equal to one.


Best regards,
Stanislav


ср, 7 авг. 2019 г. в 21:12, Stanislav V. Smyshlyaev <[e-mail]>:

> Dear Alexey, I would be happy to do this.
>
> I’d prefer to deal with the balanced ones.
>
> I’ll do the verification of security proofs of the 4 balanced nominated
> PAKEs by September, 15th, and I’ll be ready to do the following overall
> reviews for them afterwards.
>
> Kind regards,
> Stanislav
>
> ср, 7 авг. 2019 г. в 20:58, Alexey Melnikov <[e-mail]>:
>
>> Dear Crypto Review Panel members!
>>
>> According to the plan, the most important parts of the PAKE selection
>> process is done by the Crypto Review Panel members.
>> More precisely, the Crypto Review Panel members will need to do the
>> following:
>> 1) Crypto Review Panel members do the verification of security proofs of
>> the candidates and overall security assessment by September 15th 2019.
>> 2) Crypto Review Panel members review all gathered materials (including
>> independent reviews). If additional explanations are needed, Crypto
>> Review Panel members ask for them from the designers. Crypto Review
>> Panel members write overall reviews for all candidate PAKEs, based on the
>> materials that have been gathered and verified. This is to be done by
>> October 30th 2019.
>>
>> We have 8 nominated PAKEs: 4 balanced and 4 augmented.
>> Each member is asked to provide reviews for either all 4 balanced or all
>> 4 augmented PAKEs (or for all 8 PAKEs, if the member is happy to do that).
>>
>> Please reply to this message and tell the CFRG chairs about your
>> willingness to do this and, if yes, would you prefer to deal with 4
>> balanced PAKEs or with 4 augmented PAKEs (or, maybe, with all 8 of them).
>>
>> Best Regards,
>> Alexey (on behalf of CFRG chairs)
>>
>