[curves] encoding points -> bitstrings: indistinguishability, PAKE?

[Joe]

On 6/22/21 9:14 PM, Mike Hamburg wrote:
> Hi Trevor,
> 
> I think it’s elligator squared, yeah.  In the ROM, you can probably replace the first component with the hash of a smaller number of random bytes.  I’m not sure on the statistics there in general, but if the point you’re hashing is random then as few as 2 bytes might suffice (needs proof though).
> 
> I’m wary of xoring with the hash of the password.  I don’t see an obvious attack on it, but I suspect that to prove security of EKE you need an ideal cipher, not just xor.  If you expand the first component of elligator squared from a hash, then by hashing the password into that, you should get one of the PAK variants.  Of course, you’d again have to prove that it’s not only a secure PAKE, but also indistinguishable from random.
> 

I was recommended Elligator 2 rather than Elligator^2 (very unfortunate 
naming) when I played with EKE a few years ago, so it may be worth 
checking out both.

You probably want a PRP (or key-wide block cipher) to avoid scenarios 
where flipping individual bits lead to weird corner cases. At the very 
least an attacker could structure their key such that e.g. two guesses 
would decode to related keys, which weakens the properties of your EKE 
PAKE ever so slightly (no longer one guess per interaction).

The encrypted public key acts as a commitment; if you can 
pre-compute/structure your inputs such that your commitment is ambiguous 
you can gain a speedup over the idealized algorithm in the EKE construction.
Note that this might already be the case with the various Elligator 
schemes, but intuitively it feels like XOR yields the best possible 
conditions for such an attack; wide-block encryption with a shared 
random salt makes that harder.

Even 2x EBC mode would probably be better than XOR if you are worried 
about implementation complexity of the wide-block cipher.

Also note that most (if not all) EKE instantiations are slightly broken; 
I looked at the hostapd implementation of the WPA-EKE scheme in late 
2016, and at the time it was pretty trivial to partition the keyspace by 
looking for DH keys > p to rule out passphrases in an offline attack, 
but I don't know if it has improved since then. Each attempted handshake 
would yield another distinguisher from the router, allowing offline 
bruteforce after collecting a bunch of those.

In OBFS (a steganographic tool for Tor bridge connections) they used a 
scheme called UniformDH (Ian Goldberg?) that somewhat closed the gap for 
distinguishers with classic DH, but not completely IIRC. I don't think 
that was ever incorporated in the WPA specs. Elligator also has a few 
corner cases like that, but in practice it should be less of a problem 
(statistically speaking).

Joe