Comment by FiloSottile | Hacker News Reader

Comment by FiloSottile | Hacker News Reader

Elligator is a bidirectional map from random bytes to elliptic curve points, which is mainly useful for censorship resistance. Its state-of-the-art protocol integration as far as I know is obfs4 (https://gitlab.com/yawning/obfs4), one of the Tor circumvention pluggable transports (https://tb-manual.torproject.org/circumvention/). The others rely on disguising as other protocols rather than looking random.

Elligator implementations have a history of subtle bugs, arguably because there was not a spec, only a paper, although it looks like there are some third-party test vectors now.

In general the "inverse map" from random bytes to point is used only for censorship-resistance use cases, but the "direct map" turning random bytes (like a CSPRNG output or a hash) into a point is useful for a number of purposes in cryptography, like VRFs. That led to the direct map being specified more rigorously, like in https://www.rfc-editor.org/rfc/rfc9496.html#name-element-der... and https://datatracker.ietf.org/doc/html/rfc9380.

IMHO a map from a fixed amount of random bytes should be part of the fundamental group abstraction, and that's what Ristretto provides. The CFRG approach is slightly different, providing full domain-separated hash "suites" that go straight into a curve point.

As a historical note, the first time I recall seeing the anti-censorship use case was in “Telex” [1] which uses it to steganographically embed a ciphertext into a TLS random nonce, so that a router in the middle can detect whether the connection should go to its terminus or be routed somewhere else. However the authors of that paper didn’t have a standard primitive for doing this and so they had to make their own approach. Ironically, an even older use of the general approach is the NSA’s Dual EC DRBG generator [2], which has to encode elliptic curve points into random-looking bit sequences as part of its design as a PRNG. They ended up homebrewing that using standard curves by dropping several bits of each X coordinate, which in theory is all they need because there’s no need to go in the inverse direction. However the conjecture is that Dual EC is backdoored, and the backdoor requires an inverse mapping from bitstrings back to points; this has to be achieved by brute-forcing every possible point and testing.

None of this has anything to do with your comment but I love the history of these steganographic tricks.

[1] https://www.usenix.org/conference/usenix-security-11/telex-a... [2] https://en.m.wikipedia.org/wiki/Dual_EC_DRBG

Koblitz in "Elliptic Curve Cryptosystems" [1] dedicated section 3 to how to embed binary strings into points and back, which is of course necessary for elliptic curve ElGamal.

[1] https://doi.org/10.1090/S0025-5718-1987-0866109-5

Reply on news.ycombinator.com