Subject: Re: [Cfrg] PAKE review

From: "Hao, Feng" <[email-masked]>
Date: Fri, 1 Nov 2019 11:41:58 +0000

Dear Bjoern,
  
> Efficiency. CPACE and SPEKE are the most efficient proposals, followed by SPAKE2 which needs more exponentiations. J-PAKE is far less efficient than all other candidates, both in terms of computation and communication.
   
I would like to stress the importance that a fair comparison on efficiency must be based on "fully specified" protocols. So far many hidden costs intrinsic to the construction of the protocol have been neglected. Therefore, I would suggest the submitters of the candidate protocols or their collaborators also provide reference implementations, so we can evaluate and compare efficiency more concretely. We can also evaluate possible side channel leakage as that's closely related to not only the implementation, but also the inherent theoretical design of the protocol. 

I did two basic reference implementations for J-PAKE many years ago for the finite field and EC settings respectively. 

https://www.dcs.warwick.ac.uk/~fenghao/files/JPAKEDemo.java
https://www.dcs.warwick.ac.uk/~fenghao/files/EllipticCurveJPAKEDemo.java

There are also a more formal J-PAKE implementation (finite field) in Bouncycastle and a commercial C implementation (EC) in mbed, done by third parties. The source code is all open. All these can be easily adapted for a fair side-by-side comparison with other candidates under the same test conditions.

Cheers,
Feng

---

From: Björn Haase <[email-masked]>
Date: Fri, 1 Nov 2019 17:45:11 +0100

> Björn Tackmann wrote:
 >
 >As balanced scheme, CPACE seems best, with SPAKE2 coming in somewhat
close second.
 > [...]
 > The following is under the assumption, which has been discussed on
the CFRG list recently and seems
 > plausible to me, that CPACE can be implemented without the additional
session ID round.

After some additional analysis, the statement of Ran Canetti and after
studying the recent eprint of
Julia Hesse I also conclude that we could let the initiator party alone
choose the session id.
This will result in CPace having only one single message round.

There is only one aspect that needs special consideration when doing
this, in my opinion: When calculating
the CPace session key sk1 = h(sid || K) from the DH result group element
K, we did intentionally prepend
the session id and relied on having both parties contribute to it's value.

The simulator needs to program the an externally chosen input value to
an already known and defined sk1 value
under some conditions. Of course this programming would fail if the
externally chosen input value *is* already
programmed to another value. This would result in distinguishable
behaviour between ideal and real world
and invalidate the proof.

When having the separate sid round, entropy from both parties did
contribute to the sid value, thus ruling out
a collision problem if at least one party is not honest.

Now that the session id would be provided by the initiator only, i.e.
without involving
entropy generated by the responder, I'd see the need to choose a
construction where it is guaranteed that
entropy from both sides enters any sk1 hash calculation that needs to be
programmed during the proof for an
external input. We could argue that K does include entropy from both
sides, but this argument would require
possibly complicated reasoning in the proof.
For this reason, for the calculation of sk1, I'd switch to sk1 = h(sid
|| Y_a || Y_b || K), i.e. including the transcripts.
This way, it is guaranteed (without the need of further reasoning) that
entropy generated
by the responder is entering this calculation and no "collision" problem
needs to be considered
when the simulator needs to program the hash for sk1. This change also
resolves the malleability issues
that did concern Stanislav and Björn Tackmann in their reviews.

Brian Warner's use-case and perfectly symmetric CPace:

In our paper, we also did prepend the sid to the hash query that we used
for calculating the generator G,
however in this case in the proof the input value for the random-oracle
hash is chosen by the simulator,
and we would not be facing such a"collision" issue. In my opinion
letting the initiator choosing sid is no
problem here.

Removing the sid also for the hash operation used for calculating the
generator G would make the protocol
perfectly symmetric. This would be desirable in Brian Warner's use case.
My gut feeling is that this should not
at all be a problem security-wise. We would be ending up fairly close or
identical with SPEKE. However, I fear
that then there might be some technical difficulties with the UC
framework which invalidate part of the proof and the
composability guarantees. We would be having some state (within the RO
implementation) which would be shared
and used in several concurrent sessions and in my understanding the
abscence of shared state is one important
component for meaningfully defining and prooving composability in UC.

So as a general rule I would not recommend CPace without session ID for
calculating the generator.
When considering Brian's use case, however, I don't see any real problem
since if I recall correctly, Brian
did use low-entropy passwords that were to be used exactly one single
time in his application.
This would mean that we probably could disregard the case of the same
password being used in several sessions by honest parties in this
application. So here the outer protocol construction
would guarantee that a specific generator is used only in one single
session.

Yours,

Björn.

---

From: Bjoern Tackmann <[email-masked]>
Date: Tue, 19 Nov 2019 21:10:12 +0100

Hi all,

sorry for my late response. I wanted to answer some things below.

> On Nov 1, 2019, at 3:49 AM, Hugo Krawczyk <[email-masked]> wrote:
> 
>> Assumptions. All augmented schemes depend on similar assumptions (CDH and hash function as random oracle). OPAQUE and AUCPACE require the random oracle to be programmable, but that seems to be related to the stronger security statements.
> 
> DH-OPRF requires the Gap-One-More-DH assumption so both OPAQUE and Strong AuCPace need that too.

Thanks, that is of course correct.

>> Properties. The major difference in properties seems to be whether schemes support security against precomputation, which is proved for OPAQUE and also claimed for BSPAKE. The "strong" variant of AUCPACE also achives this property, whereas standard AUCPACE and VTBPEKE do not. For OPAQUE and VTBPEKE, solving a single dlog attacks multiple sessions. It is important to differentiate here, though, between VTBPAKE where all protocol sessions globally are affected, whereas in the case of OPAQUE it only affects one subset of users at a time.
>  
> Why a subset of users and a single user? Note that he OPRF key k is unique per user. The setting where this may be relevant is with quantum computers that can break dlog efficiently, and as I commented in another email, OPAQUE seems better positioned in the sense of preparedness for the PQ (and transition) era.

If one uses one k per user, then it only affects one user. I wanted to emphasize that, in contrast to the case of VTBPAKE, such an attack does not affect every user; sorry if that formulation caused confusion.

>> Implementation. AUCPACE and BSPAKE need map_to_curve.
> 
> OPAQUE too.

Thanks for the correction.

>> Integration. All candidates except for OPAQUE seem difficult to integrate with TLS, in particular the message pattern of AUCPACE and BSPAKE does not seem to fit well, and possibly require some out-of-band communication. For IKEv2, all candidates seem compatible, of course those with better round complexity seem preferable.
> 
> I expect most applications to integrate the aPAKE with some existing mechanism, at the very least, a mechanism that uses the key derived from the aPAKE to protect communication (a standalone key exchange without an application that uses the key is not too useful in general). Today TLS would be the natural choice for such integration but there are other cases (e.g. IKEv2/IPsec). The modular design of OPAQUE eases integration in these cases too, in particular allowing to reuse the existing AKE mechanism (if so desired). Yet another reason to integrate aPAKE with existing (non-password-based) AKE protocols is the need to protect user account information.

Sure. I find it hard to select a “best” aPAKE without considering a specific application. For TLS, I find OPAQUE clearly the best option. Other protocols may also benefit from OPAQUE’s round efficiency. At the same time I envision that other protocols may have a different profile...

>> Conclusion. One main question for me related to augmented PAKEs is: which application scenarios does IETF aim for? If the goal is to retrofit existing protocols in the typical TLS scenario with improved security, then OPAQUE is the best option for its strong security and its compatible communication pattern. (In particular, TLS should use OPAQUE.) TLS and the likes aside, however, I see the "strong" version of AUCPACE as a strong contender: it is efficient in terms of computation and communication; the most significant drawback over OPAQUE appears to be the additional message.
> 
> also (though possibly less significant) Strong AuCPace requires an additional (variable-base) exponentiation per party to achieve security against pre-computation attacks.

True, I just found the additional message more significant. But, as stated above, that may depend on the application.

Cheers,
Björn