Subject: [Cfrg] Balanced PAKEs: new paper on SPAKE2

From: Karthik Bhargavan <[email-masked]>
Date: Fri, 25 Oct 2019 12:02:56 +0200

Hello All,

Michel Abdalla and Manuel Barbosa have just published a new paper the perfect forward security of SPAKE2: https://eprint.iacr.org/2019/1194

They say:
"In this version, we tried to address some of the issues that were raised in the CFRG mailing list and during our meeting. 
 
In particular, the proof handles explicitly the case M=N. The cases where M and N are chosen as the output of a random oracle also follows from the proof. This means for instance that M and N could be set the hash of two fixed points (or one point when M=N) or set as a function of the client and server, such as M=H(C,S) (where H is a hash-to-group function.)

The goal of the paper was not to compare it with the other submissions. It was simply to improve the security analysis of SPAKE2 and its possible variants”

With these new results in mind, I would recommend that the SPAKE2 draft use a connection-specific M=N=H(C,S,...) generated using hash-to-curve.
This will make the precomputation attack on SPAKE2 less worrisome.

Best regards,
Karthik

---

From: "Scott Fluhrer (sfluhrer)" <[email-masked]>
Date: Fri, 25 Oct 2019 12:22:49 +0000

> -----Original Message-----
> From: Cfrg <[email-masked]> On Behalf Of Karthik Bhargavan
> Sent: Friday, October 25, 2019 6:03 AM
> To: [email-masked]
> Subject: [Cfrg] Balanced PAKEs: new paper on SPAKE2
> 
> Hello All,
> 
> Michel Abdalla and Manuel Barbosa have just published a new paper the
> perfect forward security of SPAKE2: https://eprint.iacr.org/2019/1194
> 
> They say:
> "In this version, we tried to address some of the issues that were raised in
> the CFRG mailing list and during our meeting.
> 
> In particular, the proof handles explicitly the case M=N. The cases where M
> and N are chosen as the output of a random oracle also follows from the
> proof. This means for instance that M and N could be set the hash of two
> fixed points (or one point when M=N) or set as a function of the client and
> server, such as M=H(C,S) (where H is a hash-to-group function.)
> 
> The goal of the paper was not to compare it with the other submissions. It
> was simply to improve the security analysis of SPAKE2 and its possible
> variants”
> 
> With these new results in mind, I would recommend that the SPAKE2 draft
> use a connection-specific M=N=H(C,S,...) generated using hash-to-curve.

While it would certainly improve things, it wouldn’t actually make SPAKE2 fully "Quantum Annoying"

It would improve things in that solving a single global DLog problem wouldn't allow an easy one-exchange dictionary search.  However, the attacker could still perform a single on-line exchange (obtain the M=N value and the initial encrypted message that depends on that M value, solve the DLog problem for that specific M, and then perform the dictionary search).  It would mean that he would need to perform a DLog for every system he attacks, however it still remains an earier attack than any known attack against (for example) CPACE

On the plus side, there would not be an issue if the hash-to-curve routine is not constant time (which is a major concern with CPACE)

> 
> Best regards,
> Karthik
> _______________________________________________
> Cfrg mailing list
> [email-masked]
> https://www.irtf.org/mailman/listinfo/cfrg

---

From: Watson Ladd <[email-masked]>
Date: Fri, 25 Oct 2019 08:53:07 -0700

On Fri, Oct 25, 2019, 3:03 AM Karthik Bhargavan <
[email-masked]> wrote:

> "In this version, we tried to address some of the issues that were raised
> in the CFRG mailing list and during our meeting.
>
> In particular, the proof handles explicitly the case M=N. The cases where
> M and N are chosen as the output of a random oracle also follows from the

I'll add both of these as options and the higher level protocol will
specify which one to use. Will take some talking because SPAKE2 is
integrated into Kerberos and this might present some issues if we remove
the pregeneration.

Probably one can throw in a nonce as well.

---

From: "Scott Fluhrer (sfluhrer)" <[email-masked]>
Date: Fri, 25 Oct 2019 17:48:15 +0000

I am personally not in favor in asking the higher level application to make security trade-offs.  The people working on those higher level applications need not be cryptographical experts, and so may not have the background needed to make the correct decision – that is why they are asking us.

If we, as a group, decide that the fixed N, M parameters are appropriate, that is, we are not concerned that a large entity might be able to compute the single DLog, then we should mandate that as the single option.

On the other hand, if we, as a group, decide that having fixed N, M parameters is too much of a valuable target, then we should mandate hash-to-curve, and have that as the single option.

If we feel that having a fixed N, M a concern, then why would we want to endorse a solution that uses that?  If we are convinced that it is not a concern, then why would we insist on the extra complexity?

From: Cfrg <[email-masked]> On Behalf Of Watson Ladd
Sent: Friday, October 25, 2019 11:53 AM
To: Karthik Bhargavan <[email-masked]>
Cc: CFRG <[email-masked]>
Subject: Re: [Cfrg] Balanced PAKEs: new paper on SPAKE2

On Fri, Oct 25, 2019, 3:03 AM Karthik Bhargavan <karthikeyan.bhargavan@inria..fr<mailto:[email-masked]>> wrote:
Hello All,

I'll add both of these as options [both the fixed N and M parameters, and dynamically generating them via a hash-to-curve method] and the higher level protocol will specify which one to use. Will take some talking because SPAKE2 is integrated into Kerberos and this might present some issues if we remove the pregeneration.

Best regards,
Karthik
_______________________________________________
Cfrg mailing list
[email-masked]<mailto:[email-masked]>
https://www.irtf.org/mailman/listinfo/cfrg

---

From: Dan Harkins <[email-masked]>
Date: Wed, 30 Oct 2019 11:05:05 -0700

> On the plus side, there would not be an issue if the hash-to-curve routine is not constant time (which is a major concern with CPACE)

   So what are we evaluating then? I was leaning towards CPACE because 
SPAKE2 seems
a bit too much like "the Dual_EC_DRBG of PAKEs" but if it's going to 
become this:

both side share: w = MHF(pw) and M = hash2curve(Alice | Bob | ...)
Alice sends: A = xG + wM
Bob sends: B = yG + wM
secret = x(B - wM) = y(A - wM)

then it's looking more attractive for the reason you mention.

   regards,

   Dan.