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

[Feng Hao <[e-mail]>]

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).

 * 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.

 * 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.

 * 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?

 * 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.

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 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