[curves] Fwd: Re: Fw: Aw: SPEKE using Curve25519 - elligator2 required or recommended?

Gregory Maxwell gmaxwell at gmail.com
Wed Oct 25 13:58:06 PDT 2017

On Wed, Oct 25, 2017 at 8:39 PM, Andy Isaacson <adi at hexapodia.org> wrote:
> I'd like to understand this attack better (the description above is
> pretty surprising to me), is there a canonical treatment or a phrase I
> should look up in the literature?

I don't know if there is a standard term for it, but it isn't that complicated.

When you coerce a random hash into a point you'll randomly end up with
a point on the curve or the twist. It will stay on its respective
group through things like blinding operations.  So by observing the
protocol you can tell which one each interaction used (e.g. by
multiplying to check the order).

Assuming your hash value used a session ID visible to the attacker
like H(session_id||H(password)), then the attacker can-- offline--
pick a candidate password and check it with the session IDs they
observed to see if it matches the pattern of curve vs twist. If it
does, it's the right password with probability 1-1/2^observations.

While I'm posting in this thread, most PAKE schemes I looked at in the
past had a bad property of losing their authentication strength if an
attacker can break the underlying cryptosystem (e.g. solve EC DLP).
It seemed to me that they could easily be upgraded by again hashing
the KDFed password into the returned shared secret once the protocol
completes.  Such an alteration would reduce the ZK property to
computational for an attacker that can solve ECEL, but this seems to
me to be a good tradeoff vs someone with an unknown attack on the
curve you're using being able to falsely authenticate to everything.
Do any well analyzed PAKE schemes bake this in?

More information about the Curves mailing list