Re: [Cfrg] J-PAKE and Schnorr NIZK for informational RFCs

[Watson Ladd <[e-mail]>]

On Wed, Nov 16, 2016 at 2:25 AM, Feng Hao <[e-mail]> wrote:
> Hi Watson,
>
> On your comments about comparing costs between SPAKE2 and J-PAKE
>
>  * It's not a fair comparison as the setup assumptions are different. SPAKE2 requires a trusted setup, while J-PAKE doesn't. Instead, you should compare SPAKE2 with KOY, Jiang-Gong and GL protocols as they require the same trusted setup. J-PAKE should be compared with EKE, SPEKE and Dragonfly (which is based on SPEKE).

Different setup assumptions do not make it impossible to compare
different protocols.

>
>  * When you say "SPAKE2 with M and N generated by hashing is secure, and the proofs found in the SPAKE2 paper do work", it's best that you write up the full details how you do the hashing, proofs that why it's secure and why
> it doesn't affect the original proofs in the SPAKE2 paper in any way. Then people can check and verify your proofs instead of having to take your word for it. I see you are always rigorous in asking "security proofs" from others for everything they do (which is good), so you should consider applying the same rigor to yourself.

This a) cannot be done with standard foundations and b) is a trivial
exercise with any kind of ideal hash/ROM model. I'll sit down and do
it, but while drafting this email someone went and did it.

>
>  * The KOY, Jiang-Gong and GL papers are relevant as they are the same type of CRS-based designs as SPAKE2. These papers state that the setup needs to be done by a trusted party and they don't specify using a hash.
> SPAKE2 is in the same model. It's appropriate you compare these protocols and definitions. This is necessary especially since you're doing something not specified in the original SPAKE2 paper and other related peer-reviewed papers.

Except I'm not interested in writing a review paper. I'm interested in
looking at all the proposals before us for PAKE, and determining which
should be promoted.

>
>  * You will need to convince IETF users that there is no possibility of trapdoor for M and N (which may prove a bit tricky). Knowledge (or partial knowledge) of the relation between M and N may allow one to
> systematically break all instances of the protocol execution.
>
>  * Kindly note that if you can manage to convince IETF users that M and N are completely random, one might just plug M and N as the input of two random points to DUAL_EC and make it work?

Are you aware that DUAL_EC included a point generation mechanism that,
if used, would have completely avoided the backdoor? Do you think that
the hashing argument presented downthread is wrong.
>
>  * What you say about the 4 exponentiations in the subgroup is correct (consistent with the original paper), but this hasn't included the validation of the public key (which is free in EC but takes one full exponentiation in the finite field setting). See my further comment below.

The next part of my email did describe the validation costs: 1
exponentiation per element to be validated. That is not a full
exponentation: if the subgroup is the unique subgroup of order q in
the finite field, we need only check x^q=1. I said the validation
doubled the cost of SPAKE2: this is not exactly right, as only one
point needs to be validated.

>
> I read again the original SPAKE2 paper as well as your I-D. I have the following comments
>
>  * I think SPAKE2 is underspecified in the original paper. It doesn't state the requirements for M and N, but it should be clear that they must be completely random. Also, it doesn't state if the discrete logarithm between M and g (and symmetrically between M and g) must be unknown. It's not immediately clear to me if knowledge of the discrete logarithm for M and g will break anything, but all these should have been explicitly specified in the paper.
>
>  * I'm a bit worried that in the actual protocol specification in the original paper, there is no step to perform public key validation. This could be due to two reasons: 1) an inadvertent omission by the authors; 2) an intentional design choice. In case of ambiguity like this, one normally takes it as the latter. The reason is simple: if public key validation is considered essential, it MUST be clearly specified, which is the case with most key agreement protocols. However, from early 2000s, some researchers called for abandoning the public key validation, as long as the protocol has formal security proofs (HMQV is one notable example, but it backfired in the end).

The draft completely specifies an equivalent protection. This is the
reason we use the cofactor. I believe I explicitly required on-curve
checks, but will make it more clear if you don't think so.

>
>  * The above observation reminds me of a paper " Multi-Factor Authenticated Key Exchange" by Poincheval and Zimmer in 2008 [1] where the protocol is specified in a similar manner as SPAKE2 without public key validation. We analysed the protocol and it took us a while to conclude that it is insecure without public key validation (despite the security proofs in the paper) [2]. We contacted authors of [1] and they kindly acknowledged the attack and also confirmed that public key validation needed to be added in their protocol. The attack can be traced to a subtle deficiency in their theoretical model which implicitly assumes that a server is trusted when it communicates with a client. This assumption is clearly invalid, but it is implicit in the model/proofs and it took 5 years for peer researchers to identify it!
>
>  * At the moment, I don't see an obvious attack due to the missing public key validation in the SPAKE2 specification (as in the original paper), but it's a potential issue that needs some attention.
>
> Cheers,
> Feng
>
> [1] D. Pointcheval and S. Zimmer, "Multi-Factor Authenticated Key Exchange," Proceedings of Applied Cryptography and Network Security (ACNS¹08), pp. 277-295, LNCS 5037, 2008.
>
> [2] Security Analysis of a Multi-Factor Authenticated Key Exchange Protocol  https://eprint.iacr.org/2012/039.pdf
>
> On 15/11/2016 19:14, "Watson Ladd" <[e-mail]> wrote:
>
>>Dear Feng,
>>
>>Let me make this very clear, to avoid your misunderstandings: J-PAKE
>>is substantially less efficient than SPAKE2 over the same group.
>>SPAKE2 with M and N generated by hashing is secure, and the proofs
>>found in the SPAKE2 paper do work for this case. If we use a small
>>subgroup of a finite field group, then the necessary validations for
>>group membership double the cost of SPAKE2, but J-PAKE is still
>>slower. J-PAKE requires an additional round, while SPAKE2 fits into
>>the same flow as Diffie-Hellman. There is no relevance of KOY, or
>>Jiang-Gong, or any other paper that may or may not (I didn't bother to
>>look) present its own definitions and security model.
>>
>>SPAKE2 requires exactly 4 exponentations in the subgroup if we do not
>>do anything smart about them. Two of these can be combined and
>>replaced with a dual base exponentiation via Strauss's algorithm.
>>
>>Do you have anything to say to this?
>>
>>Sincerely,
>>Watson
>



-- 
"Man is born free, but everywhere he is in chains".
--Rousseau.