Subject: Re: [Cfrg] I-D Action: draft-irtf-cfrg-spake2-06.txt

From: Nico Williams <[email-masked]>
Date: Sat, 1 Dec 2018 15:10:39 -0600

Comments:

 - section 3.2, typo in first para:

     A picks x randomly and uniformly from the integers in [0,ph)
                                                           ^^^^^^

   but the second para says:

     B selects y randomly and uniformly from the integers in [0,p*h),
                                                             ^^^^^^^

   So, one says "ph", the other says "p*h".

 - many people know PAKEs as ZKPPs; can we add a blurb somewhere saying
   that this is a ZKPP?

   E.g., the Abstract could read:

     This document describes SPAKE2, a Zero-Knowledge Password Proof
     (ZKPP) protocol, which allows two parties that share a password to
     derive a strong shared secret key with no risk of disclosing the
     password to eavesdroppers.  This method is compatible with any group,
     is computationally efficient, and has a security proof.

     This document also describes SPAKE2+, a ZKPP that allows one party to
     store only an asymmetric verifier of the shared password, rather than
     a password equivalent.

   This version also points out that this is intended to be secure
   relative to eavesdroppers, and mentions SPAKE2+, which I think is a
   good idea for the abstract.

 - section 3.3 should really say that SPAKE2+ is an augmented SPAKE

   (Section 5 kinda says it, but it seems misplaced.)

   I propose section 3.3 get a paragraph inserted before the current
   first paragraph:

"
   SPAKE2 requires that A and B share a secret.  This is inconvenient in
   many applications.  Therefore we also specify a SPAKE2+ which is an
   augmented PAKE that requires that B store only a verifier rather than
   a shared secret.
"

   The current next-to-last paragraph in section 5 can then be removed.

 - Section 3.3 should probably call what B stores a "verifier" and point
   out that it is not a password-equivalent.  I.e., that B cannot
   impersonate A to any other B sharing the same verifier for A's
   password.

 - Section 5 should point out that the verifier stored by B is can be
   subjected to an off-line dictionary attack, therefore it must be
   guarded carefully.

 - Sections 3.2 and 3.3 differ stylistically in a way that makes it hard
   to read.

   Section 3.2 says this sort of thing:

"
   A picks x randomly and uniformly from the integers in [0,ph)
   divisible by h, and calculates X=x*G and T=w*M+X, then transmits T to
   B.
"

   While section 3.3 says this:

"
   When executing SPAKE2+, A selects x uniformly at random from the
   numbers in the range [0, p*h) divisible by h, and lets X=x*G+w0*M,
   then transmits X to B.  B selects y uniformly at random from the
   numbers in [0, p*h) divisible by h, then computes Y=y*G+w0*N, and
   transmits it to Alice.
"

   So, in SPAKE2 A sends x*G+w*m and in SPAKE2+ A sends x*G+w0*M -- very
   similar things.

   But in SPAKE2 we have X=x*G and T=w*M+X, while in SPAKE2+ we have
   X=x*G+w0*M, but X is not reused in the text in SPAKE2.

   This difference is purely stylistic, but I had to stop and think
   about it to see that that's all it was.  Perhaps that's a feature,
   but I'd have written section 3.2 in the same way as 3.3.

   Unified diffs:

     3.2.  SPAKE2

        A picks x randomly and uniformly from the integers in [0,ph)
    -   divisible by h, and calculates X=x*G and T=w*M+X, then transmits T to
    +   divisible by h, and calculates X=w*m+x*G, then transmits X to
        B.

        B selects y randomly and uniformly from the integers in [0,p*h),
    -   divisible by h and calculates Y=y*G, S=w*N+Y, then transmits S to A.
    +   divisible by h and calculates Y=w*N+y*G, then transmits Y to A.

        Both A and B calculate a group element K.  A calculates it as
    -   x(S-wN), while B calculates it as y(T-w*M).  A knows S because it has
    -   received it, and likewise B knows T.
    +   x(Y-wN), while B calculates it as y(X-w*M).  A knows Y because it has
    +   received it, and likewise B knows X.

        This K is a shared value, but the scheme as described is not secure.
        K MUST be combined with the values transmitted and received via a
        hash function to prevent man-in-the-middle attackers from being able
        to insert themselves into the exchange.  Higher-level protocols
        SHOULD prescribe a method for incorporating a "transcript" of the
        exchanged values and endpoint identity information into the shared
        secret.  One such approach would be to compute a K' as H(len(A) ||
    -   A || len(B) || B || len(S) || S || len(T) || T || len(K) || K ||
    +   A || len(B) || B || len(Y) || Y || len(X) || X || len(K) || K ||
        len(w) || w) and use K' as the key.

   I believe these are just stylistic, semantically neutral changes.

 - It might be useful to explain why not other well-known PAKEs, such as
   SPEKE/B-SPEKE and J-PAKE.  There's clearly no hard requirement to
   explain why, but it may well prove useful to do it.  If we're not
   doing this sort of thing in other CFRG documents, that's fine, and a
   reply on the list listing these reasons should suffice.

   SPEKE/B-SPEKE would have made implementation easier by requiring only
   scalar point multiplication, thus enabling cheap curve25519
   implementations.  It would also be faster, as it requires fewer
   operations, and as scalar point multiplication is generally faster
   than point addition/subtraction.  This hardly matters now, since
   SPAKE2+ is getting real-world deployment via implementations of
   draft-ietf-kitten-krb-spake-preauth.

   IIRC the security issues found in SPEKE/B-SPEKE thus far have to do
   with insufficient transcript and identity binding, so those wouldn't
   be reasons not to use SPEKE/B-SPEKE.  Indeed, SPAKE2/SPAKE2+ have
   text making such binding a requirement, for the same reasons.  The
   SPEKE/B-SPEKE patents are now expired, so those wouldn't be good
   reasons not to use SPEKE/B-SPEKE either.

Nico
--

---

From: Greg Hudson <[email-masked]>
Date: Sat, 1 Dec 2018 17:10:04 -0500

>     X=x*G+w0*M, but X is not reused in the text in SPAKE2.
[...]
>      +   divisible by h, and calculates X=w*m+x*G, then transmits X to

This change would have some minor downstream ripples:

* draft-ietf-kitten-krb-spake-preauth contains X, Y, T, and S values in 
its test vectors.

* MIT krb5's shipped implementation of the above draft uses T and S in 
comments and variable names.

While those are fixable without any interop impact, my preference is to 
change the SPAKE2+ terminology rather than the SPAKE2 terminology.  I 
also think it is mildly useful to have separate names for the unmasked 
and masked DH points.

The other SPAKE2 implementation I am aware of (BoringSSL's, which isn't 
draft-conformant for reasons having to do with M and N generation and 
cofactors) uses P and Pstar as variable names, so wouldn't really be 
affected.

>     implementations.

I know that in discussions of PAKE algorithms for Kerberos, we wanted to 
avoid requiring hash-to-curve if possible.  From what I can find online, 
if you use SPEKE with curve25519 and simply hash to the x coordinate, 
you leak one bit of the hashed password, which isn't necessarily a huge 
problem but isn't an attractive property.

I believe I wound up with a SPAKE2-edwards25519 implementation based on 
the BoringSSL 25519 code which is pretty competitive with X25519 
implementations, although I don't have test results handy.  Point 
addition and subtraction are not expensive operations; they're just not 
necessarily part of a crypto API geared towards X25519 or ed25519.  But 
neither is hash-to-curve.

---

From: Nico Williams <[email-masked]>
Date: Sat, 1 Dec 2018 17:36:30 -0600

On Sat, Dec 01, 2018 at 05:10:04PM -0500, Greg Hudson wrote:
> * draft-ietf-kitten-krb-spake-preauth contains X, Y, T, and S values in its
> test vectors.
> 
> change the SPAKE2+ terminology rather than the SPAKE2 terminology.  I also
> think it is mildly useful to have separate names for the unmasked and masked
> DH points.

That's quite fair.

Speaking of SPAKE2+, I said draft-ietf-kitten-krb-spake-preauth uses
SPAKE2+, but it's SPAKE2.  I'm wondering how to extend krb-spake-preauth
to use SPAKE2+ some day.  I think we might need to overload the group ID
to mean {PAKE, group} rather than just {group}.  But we can do that some
time in the future.

> avoid requiring hash-to-curve if possible.  From what I can find online, if
> you use SPEKE with curve25519 and simply hash to the x coordinate, you leak
> one bit of the hashed password, which isn't necessarily a huge problem but
> isn't an attractive property.

Can you explain this a bit more, that is, how hash-to-curve leaks a bit?

A leak of one bit per-exchange is absolutely disastrous if it means that
with each exchange an eavesdropper can eliminate half the passwords in
their dictionary, as then observing N exchanges lets you eliminate all
but 2^-N of passwords in your dictionary.

> I believe I wound up with a SPAKE2-edwards25519 implementation based
> on the BoringSSL 25519 code which is pretty competitive with X25519
> addition and subtraction are not expensive operations; they're just
> not necessarily part of a crypto API geared towards X25519 or ed25519.
> But neither is hash-to-curve.

OK.

Nico
--

---

From: Greg Hudson <[email-masked]>
Date: Sun, 2 Dec 2018 12:06:40 -0500

> Can you explain this a bit more, that is, how hash-to-curve leaks a bit?

I was looking at
https://crypto.stackexchange.com/questions/51888/an-efficient-speke-protocol-with-curve25519
which notes that if you just hash to an x coordinate, an observer can 
see whether the chosen x coordinate is on the curve or the twist.  Of 
course using a proper hash-to-curve algorithm such as elligator2 avoids 
this problem.

> but 2^-N of passwords in your dictionary.

It's the same bit every time.  It would let an attacker filter out half 
of a password dictionary offline before conducting an online attack, 
perhaps.

---

From: Nico Williams <[email-masked]>
Date: Sun, 2 Dec 2018 13:15:32 -0600

On Sun, Dec 02, 2018 at 12:06:40PM -0500, Greg Hudson wrote:
> which notes that if you just hash to an x coordinate, an observer can see
> whether the chosen x coordinate is on the curve or the twist.  Of course
> using a proper hash-to-curve algorithm such as elligator2 avoids this
> problem.

That post has an incorrect description of SPEKE, with H(P) as the shared
generator.

SPEKE is just DH w/ a password-derived generator, yes, but the method of
generating the generator involves the DH operation:

A, B:  G' = G*H(P)
A->B:  X=G'*x
B->A:  Y=G'*y
A, B:  K_shared = Y*x == X*y  # (then bind in transcript, identities)

In a curve25519 instantiation of SPEKE G is the x-coordinate of a
generator, H(P) is a scalar, and x and y are ephemeral scalars.  The
scalars don't have to be on the curve.  G' is on the curve, therefore X
and Y are on the curve, therefore there is no 1-bit leak as decribed in
the linked SE post.

> It's the same bit every time.  It would let an attacker filter out half of a
> password dictionary offline before conducting an online attack, perhaps.

If so I could live with that.  However, see above.

Nico
--

---

From: Nico Williams <[email-masked]>
Date: Mon, 3 Dec 2018 16:21:09 -0600

> That post has an incorrect description of SPEKE, with H(P) as the shared

Ah, no, it was I who misremembered.

Indeed, in SPEKE/B-SPEKE the generator is H(P).  However, I think this

> A, B:  K_shared = Y*x == X*y  # (then bind in transcript, identities)

because g'=g*H(P) will be a point on the curve and will be usable as a
generator for ECDH key agreement.  (One does have to check that g' is
not 1.)

Nico
--

---

From: "Scott Fluhrer (sfluhrer)" <[email-masked]>
Date: Mon, 3 Dec 2018 22:51:30 +0000

> -----Original Message-----
> From: Cfrg <[email-masked]> On Behalf Of Nico Williams
> Sent: Monday, December 03, 2018 5:21 PM
> To: Greg Hudson <[email-masked]>
> Cc: [email-masked]
> Subject: Re: [Cfrg] I-D Action: draft-irtf-cfrg-spake2-06.txt
> 
> > > https://crypto.stackexchange.com/questions/51888/an-efficient-speke-
> > > protocol-with-curve25519 which notes that if you just hash to an x
> > > coordinate, an observer can see whether the chosen x coordinate is
> > > on the curve or the twist.  Of course using a proper hash-to-curve
> > > algorithm such as elligator2 avoids this problem.
> >
> > That post has an incorrect description of SPEKE, with H(P) as the
> > shared generator.
> 
> generator for ECDH key agreement.  (One does have to check that g' is not
> 1.)

I do not believe that works as a PAKE, as it would allow an adversary to test multiple potential passwords from a single exchange.

Suppose B is the adversary with a dictionary of the possible password values, and A will be the first one to use the shared key in the protocol (e.g. use it to derive an encryption key and encrypt a message to B with it).

Then, what B can do is pick an arbitrary 'r', compute G*r, and send that as its 'Y' value.

A sends its X = G'*x = G*(x H(P)) value

A will then compute Y*x = G*(x r) and use that to derive the encryption key.

What B can do for every guess P' of the password in this dictionary, and compute X*(r H(P')^{-1} ); and use that to derive the encryption key, and attempt to decrypt the message with it.

We have X*(r H(P')^{-1}) = G*(x r H(P')^{-1} H(P)).  If P = P', then this simplifies to G*(x r), which is the same point that A derived as its K_shared, and so the decryption will succeed.  If P != P', then the encryption key will not work.

This allows the adversary to test every password in his dictionary with a single exchange.

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

---

From: Nico Williams <[email-masked]>
Date: Mon, 3 Dec 2018 17:15:03 -0600

On Mon, Dec 03, 2018 at 10:51:30PM +0000, Scott Fluhrer (sfluhrer) wrote:
> I do not believe that works as a PAKE, as it would allow an adversary
> to test multiple potential passwords from a single exchange.

Ay, you're right.  We end up with

Ka = G*(x r)
Kb = G*(H(P) y)

and then B can test P values until B finds a P where Kb matches Ka.

Well done!

Nico
--