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

> -----Original Message-----
> From: Cfrg <cfrg-bounces@irtf.org> On Behalf Of Nico Williams
> Sent: Monday, December 03, 2018 5:21 PM
> To: Greg Hudson <ghudson@mit.edu>
> Cc: cfrg@ietf.org
> Subject: Re: [Cfrg] I-D Action: draft-irtf-cfrg-spake2-06.txt
> 
> On Sun, Dec 02, 2018 at 01:15:32PM -0600, Nico Williams wrote:
> > On Sun, Dec 02, 2018 at 12:06:40PM -0500, Greg Hudson wrote:
> > > On 12/01/2018 06:36 PM, Nico Williams wrote:
> > > >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.
> >
> > That post has an incorrect description of SPEKE, with H(P) as the
> > shared generator.
> 
> Ah, no, it was I who misremembered.
> 
> Indeed, in SPEKE/B-SPEKE the generator is H(P).  However, I think this
> construction works:
> 
> > 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)
> 
> 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.)

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
> Cfrg@irtf.org
> https://www.irtf.org/mailman/listinfo/cfrg