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

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

> -----Original Message-----
> From: Cfrg <[e-mail]> On Behalf Of Björn Haase
> Sent: Friday, September 06, 2019 2:35 PM
> To: [e-mail]
> Subject: Re: [Cfrg] My review of the four balanced PAKE (SPAKE2, SPEKE,
> CPACE, J-PAKE)
> 
> Dear Scott,
> 
> I would like to thank you for your review. In you came up with some
> questions regarding CPace which I would like to answer. Secondly in a
> subsequent section, I would like to respond to your analysis.
> 
> You pointed out a weak point that you identified in the security proof.
> You will not be astonished
> to hear, that we believe that our proof holds. Still, in fact, we actually might
> agree on all essential aspects of your analysis!
> In our opinion, the essence of your result might actually point to the
> problems might come with the strongly idealizing assumptions regarding the
> concept of the random oracle that we did use in the proof.
> 
> I would appreciate your feedback regarding the point, wether our re-
> phrased version of your feedback that you will find below correctly captures
> your reasoning or not.
> 
> Yours,
> 
> Björn
> 
> 
> 1) Answers to the questions raised regarding CPace:
> 
>  > Scott Fluhrer wrote:
>  >In addition, it is also not clear whether an explicit mutual authentication
> step is a  >required part of CPACE.  That step is shown in Figure 4; however,
> that lists the AuCPace protocol  >(which is not reviewed here) which does
> the mutual authentication step as a pass after the  >"CPace substep"); figure
> 5 (which is specific to CPace) does not list it at all  >(on the other hand, it
> doesn't actually list any exchanged messages).
> 
> It is common for simulation-based proofs in the UC framework to specify the
> protocol in form of an algorithm running on interactive Turing machines
> which exchange messages by "send" operations.
> As such, the two protocol messages show up in figure 5 as "CPace initiator"
> and "CPace responder". As you see there, CPace is defined solely for implicit
> authentication.
> I.e. explicit key confirmation is out of the scope of both F_{pwKE} and CPace.
> 
> As a consequence figure 5 does not include any authenticator message and
> the ideal functionality does not provide any guarantees that might parties
> abort further communication in case that the authentication failed.
> 
> The AuCPace paper mainly focuses on presenting the augmented protocol
> and CPace was actually only a side-aspect. As such the "protocol boundaries"
> might benefit from some additional text.
> 
> 
> 2) Replies regarding your analysis.
> 
> First let me again thank you for your review. My perception is that we
> actually might have consensus regarding the most relevant points.
> 
>  > Scott Fluhrer wrote:
>  >The problem is that [in the proofs of SPAKE2, SPEKE and CPace] these
> simulations have a model  >of what the adversary is allowed to do, and I
> >managed to find potential actions that an adversary might try to accomplish
> that is not accounted  >for by the simulator's adversary model (and hence
> the security proof would not be valid when facing  >such an adversary).
> 
>  > [...]
> 
>  >The major issue is the security proof [of CPace], which would appear to be
> invalid.
>  >It's a simulation-based proof; but I don't see how they cover cases where
> the adversary  >doesn't play by the rules the simulator assumes.
> 
> Actually in the proof we did not make any assumption regarding the
> adversary's strategy. In the wording of the UC framework we show
> "simulability when facing dummy adversaries".
> Note that properly handling the UC dummy adversary was at the core of the
> "proof update" that you did mention.
> (BTW: Thank you Björn Tackmann, for your careful reading and advice and for
> providing your preliminary review of AuCPace that allowed us to fix this
> topic.).
> Note that the example that you gave also does not refer to a specific attack
> strategy of the adversary but to the properties of the hash function that she
> uses.
> 
> What we, however actually do is that we base our proof on strong
> assumptions regarding the properties of the *cryptographic primitives* that
> we use as a building block in our protocol.
> Specifically we had to model the hash function as a programable random
> oracle.
> 
>  >For example, in G2, they switch the standard hash/mapping function with
> one where they  >know the discrete log (and note that this does not change
> the observed distribution),  >and so later assume that the simulator knows
> the discrete logs.
> 
>  >However, the adversary is not bound to using the standard hash/mapping
> function with his accesses,  >and so the simulator might not know the
> discrete log.  It is not clear how the simulator is  >supposed to proceed in
> such a case, and hence the indistinguishability results from the  >various
> simulators may be invalid.
> 
> What we indeed do in G2 is that we replace the real-world hash function with
> a programable random oracle.
> 
> This is true and we agree that this could be a problem.
> We program the hash value to chosen values that are indistinguishable from
> random values for the observing environment Z.
> 
> So regarding this part of your analysis we disagree in that we think that we
> did not actually make any assumption on "how the adverary is playing the
> game". Your main point, however, might rather an aspect on which we will
> agree.

Let me try to rephrase my objection: in the protocol, legitimate parties will always invoke Map2Point(H(something)) to generate a point; hence when dealing with legitimate parties, it is totally reasonable in G3 to replace H with something where you always know the dlog of the point generated.

However, with a PAKE, we can't limit the adversary to only using points of the form Map2Point(H(something)); they can pick anything (see my repeated pleas to "please do input checking", because inserting things which aren't points at all can really mess things up).  My concern was that if you assumed you always knew the discrete log, well, the adversary can forbid that.

Now, going over the proof again, I do see where you try to deal with this, I'd need to review this further.

On the other hand, I did manage to find a counterexample to Theorem 1 (as stated); the protocol is broken if:
	- We're on a curve where the DDH problem is easy
	- H2 is the identity function (or otherwise doesn't hide the value K); theorem 1 makes no assumptions on H2.

The attack is fairly straight-forward:
-	 The honest initiator transmits G^y (for password-dependent G, secret y)
-	The adversary responds with H (for an arbitrary point H)
-	The honest initiator computes H^y, and output the sk (which includes H^y).
-	The adversary somehow hears the sk (and thus gets H^y)

Then, the attacker goes through his dictionary, and for each password, he computes the corresponding G', and then checks if (G', G^y, H, H^y) is a Diffie-Hellman set; for the correct password, it will be.

Now, this attack makes quite improbable assumptions (e.g. that H2 is the identity); however as far as I can see, everything it does is pedantically within the assumptions of Theorem 1; and so there's something there that could use a bit of tightening up.  I haven't gone through the proof myself to track down where it fails in this case; I don't expect that to cause a major change in your proof...

> 
> Possibly your objection could be re-phrased using the wording
> 
> "The issue of the security proof of CPace is that the authors did base the
> analysis on the idealized assumption of availability of a programable random
> oracle (PRO). The proof requires the simulator to be given the power to
> program the output of the hash function to chosen values that could not be
> distinguished from random values. The simulator makes specific choices that
> give it access to secret exponents. This cannot happen in the real-world,
> because the hash-functions don't behave like random oracles. Without the
> RO-assumption it cannot be proven that real-world adversaries are given no
> more capabilities than what they were permitted in the ideal-world
> protocol."?
> 
> If this re-phrased sentence captures the essence of your review, we have
> consensus.
> 
> Note that the awareness with respect to the many problems related to
> random oracles as idealization of hash functions is one of the two aspects
> which made us choose the 256-bit-security-level hash SHA512 in conjunction
> with the 128-bit-security-level primitives used elsewhere in our reference
> implementation AuCPace25519.
> We thought that it might be wise to be particularly conservative with respect
> to the choice of the hash, specifically due to the risks associated with the RO
> idealization.
> (The second reason was: "When using Curve25519, it is likely that
> Ed25519 is interresting
> and then SHA512 might be required anyway.")
> 
>  > Scott Fluhrer wrote
>  > The specified CPACE protocol involves a Verify() function to validate points
> received from the  > other side; however I believe that function is
> underspecified.
>  > They try to be more general (see the last paragraph in section 3.4);
> however, it would  > appear unlikely that an average implementor would be
> able to cover all cases.
> 
> I agree on this. We did fully specify how to run Verify() for x-coordinate-only
> implementations on curves with a secure twist. For any other case we only
> have defined the requirements for the Verify() primitive. As such, the paper
> is not sufficient for an implementation spec. but "only" a scientific paper
> presenting a proof with one specific reference implementation example.
> 
>  > I believe that it would be cleaner if we mandated that we support only
> curves with twist  > security (e.g. Curve25519 and Curve448), and that we
> exchange only the X coordinate  > (and that the Verify(X) function is precisely
> the check that hX is not the neutral element  > (where h is the cofactor -
> specifically, the lcm of the cofactors of the curve and the twist).
> 
> I agree that it would have been cleaner and simpler. Still, there might be use-
> cases where implementers might be forced to using other curves. Imagine
> for instance the case of american/french/german/chinese government
> applications which require their own favorite choice of curves. Also there
> might be legacy hardware-accellerators or CC/FIPS-certified software
> libraries which only cover some short-weierstrass curves. You might be
> loosing FIPS/CC approvals :-(.

Actually, X25519 is NIST approved (and CC follows FIPS in terms of the crypto primitives), and so FIPS/CC should be fine.

> 
> For this reason, we see the use-case and need for dealing also with the
> somehwat more complex case of Short-Weierstrass curves. (Note that I also
> see the need for this requirement from a crypto-agility point of view).

In that case, if you transmit (x, y) coordinates (possibly compressed), you really need to check them against the curve equation (if they're not on the curve, they can be of any order); you really need to mandate this (as well as checking hP != 0).

> 
>  > Note that, unlike SPAKE-2, the validity checking does not have to check
> whether points are on the twist, 
> as twisted points cannot yield any
> additional information to the attacker.
> Yes. In my opinion, this is one of the advantages of CPace.
> 
>  > The paper does mention the possibility of using other curves (such as short
> Weierstrass curves),  > I would suggest that we disallow those curves, as they
> would require alternative validity checking  > (such as checking the received
> x, y coordinates into the curve equation),  > and while this is not difficult, it is
> a change, without (as far as I can see) any  > compensating benefit.
> 
> Again I agree. Security-wise adding support for short-weierstrass might
> actually even increase the risk of implementation pitfalls. Still, I strongly
> believe that we should not strictly disallow this choice, specifically when
> considering secure element chips designed for specific short-weierstrass,
> curves only.

Fair enough.  Just make sure you specify everything...

> 
> As you noted for short-weierstrass curves, Verify() would boil down to what
> we do at various places today ("Verify that the point is on the right curve.")
> and doing this might be easily merged with a point decompression. So, for
> short-weierstrass, there might actually be no benefit of using the x-
> coordinate-only approach.

Well, it does save one byte of bandwidth :-)

>  > In addition, the protocol is defined only at a fairly high level; any real
> definition will need to  > specify a number of things (the curves that we work
> in, the format of the identifiers sid, Pi, Pj,  > the actual hash and method to
> convert these identifiers and the password into the value G, the  > format of
> the exchanged messages [...].
> 
> Yes. As mentioned. The AuCPace paper was meant to be a scientific paper
> discussing the need of PAKE in real-world settings together with the proof
> and an optimized reference implementation example.
> As such it is yet not sufficiently specific as to allow for writing inter-operable
> implementations.
> However we believe that this step would be somewhat straight-forward.

Still needs to be done (and reviewed; It's astonishing how many devils there are in the details)