[curves] encoding points -> bitstrings: indistinguishability, PAKE?
Joe
joe at celo.io
Wed Jun 23 16:30:15 PDT 2021
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
More information about the Curves
mailing list