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

[Greg Hudson <[e-mail]>]

On 12/01/2018 06:36 PM, Nico Williams wrote:
>> 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.
> 
> 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.

> 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.

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.