Re: [Cfrg] My review of the four balanced PAKE (SPAKE2, SPEKE, CPACE, J-PAKE)

["Scott Fluhrer (sfluhrer)" <[e-mail]>]

From: Hao, Feng <[e-mail]>


"Also, not formally a part of this review, but as I went through the RFCs (8236 and 8235), a potential improvement occurred to me.  The NIZKP in 8235 allows the proof to reference an OtherInfo field; this is a value used to specify the context (so that the proof is not valid in any other context).  OtherInfo is currently unused in J-PAKE, however suppose we were to insert (for example) all the currently seen points in each proof as OtherInfo.  For example, the initial client pass might have the values of (x1, x2) as the extra info in both of its NIZKPs; the server response (assuming the 1.5 pass version) might have (x1, x2, x3, x4, B) as its extra info, and the final client response might use (x1, x2, x3, x4, A, B)..  What this would mean is that the adversary has even less flexibility in his attack; he now cannot extract values from previous exchanges and reuse them in new ones (with the exception that he can exactly duplicate the initial client pass); he could (for example) modify the server response from an honest server, however he would have to select entirely fresh x3, x4, B values for which he knows the appropriate discrete logs.  Because the adversary has fewer options, this means that the proof could potentially be simplified (as there are fewer things that the proof has to prove can't happen), as well as giving a potentially better end security bound (everything the proof disallows does cause a small reduction in the provable security bound.  In fact, we might be able to limit the possible adversary strategies sufficiently that it would be practical to do a case analysis covering everything an attacker can attempt (which would be less rigorous, but considerably easier to understand).  In addition, this suggestion cannot hurt security (the existing proof is still valid, as the NIZPKs still meet the security assumptions), it would not increase bandwidth at all (the data inserted into the OtherInfo field is already present in the messages), and would only cause a tiny increase in the computation time (the extra info is just included in a hash).  Just a thought..."

[FH] Thanks for your suggestion. I don't object anyone doing the above, which is exactly why I defined OtherInfo (optional) in the RFC, to provide the flexibility to include the transcript of the key exchange (if people want) into the hash so to restrict the attacker even further and make the proof tighter. However, I didn't want to make it mandatory for two reasons. 1) I don't consider this is strictly necessary for the security of J-PAKE; 2) if we do it, we will end up with a protocol specification that depends on whether the protocol will be implemented as 2 rounds or 1.5 round. It's not neat, and makes things more complex. Between simplicity and complexity, I would err in favour of the former : )

Well, I just spent a disgusting amount of time slogging through four different simulation-based proofs of PAKE, and they were all pretty much clear as mud.   I did not find any problems with your proof, however I am not entirely convinced (because of the subtlety involved) that I didn't miss anything.
In contrast, with my idea, well, that severely limits the games that an attacker can play.  I suspect that we could simply list the various things that an adversary can try (e.g. keep the first message unchanged, replace the values in the second and third messages with values whose dlog he knows) and show that none of the attacks allows the adversary any unwarranted advantage.  Why would such a proof (which I have not worked out the details) be considered attractive?  Because it'd be clear that it covers everything an adversary can do, and between a proof which is opaque (and which might hide hidden flaws) and one which is obviously valid, I would err in favor of the latter. :)

Of course, as a compromise, you could have the responder's x3, x4 values have only (x3, x4) as the OtherInfo; that would make both the 2 pass and the 1.5 pass version identical.  It would allow the attacker more options (e.g. he could now leave x3 and x4 unchanged, but insert his own B value), but there might not be *that* many more cases...