[HN Gopher] Elligator: Elliptic-curve points indistinguishable f...
___________________________________________________________________
Elligator: Elliptic-curve points indistinguishable from uniform
random strings (2013)
Author : NavinF
Score : 89 points
Date : 2024-07-14 04:58 UTC (4 days ago)
(HTM) web link (dl.acm.org)
(TXT) w3m dump (dl.acm.org)
| NavinF wrote:
| Also see https://elligator.org/
| commandersaki wrote:
| This isn't meant to protect against real-time detection. For
| example GFW will block streams that appear high entropy from the
| get-go. This is more to conceal the fact a key exchange has
| occurred in captured traffic that is flagged for expert/human
| analysis.
| Y_Y wrote:
| Wouldn't it be a good candidate for steganography then? If I
| hide this string in my paragraph of innocuous text then I have
| some plausible deniability if Eve successfully guesses what aim
| doing.
| Retr0id wrote:
| The trouble with this is that whatever steganographic feature
| you're embedding it into would (likely) not be uniformly
| random by default. So although nobody could prove you were
| transmitting an EC point, they could reasonably assume you
| were transmitting some form of encrypted data, given enough
| samples.
|
| I think steganography is the right idea in general, but it
| needs to be more clever than the classic text/image-based
| techniques.
| less_less wrote:
| Elligator is appropriate for use as a component in a
| steganography system, but in most cases the problem it
| solves isn't the hardest part of the system.
|
| It's also useful in cases where you need to hash to a curve
| in a way that provably (in the ROM) doesn't have
| problematic structure. This comes up fairly often: OPRF,
| Boneh-Boyen short sigs, password-auth key exchanges like
| SPEKE and PAK, etc. It also was useful in SIKE, before that
| was broken.
| Retr0id wrote:
| Being indistinguishable from uniform random bytes means you can
| undetectably embed it within anything else that's _supposed_ to
| be uniformly random.
|
| Also, an expert human can't distinguish a _single_ regular EC
| point from uniform random bytes, depending on the format. You
| 'd still need to look at the statistics over a number of points
| (i.e. by writing a distinguisher).
| nmadden wrote:
| If a single point matches the curve equation of a well-known
| curve then that's pretty compelling evidence.
| Retr0id wrote:
| not for compressed point representations (hence "depending
| on format")
| nmadden wrote:
| So just X25519 then?
| Retr0id wrote:
| No, most curves support a compressed (x coord,
| parity/sign bit) representation. It's what you'd probably
| be using if Elligator didn't exist, so makes sense as the
| point of comparison.
|
| https://datatracker.ietf.org/doc/draft-mattsson-tls-
| compact-...
| kientuong114 wrote:
| The point is that _any_ random byte string can be decoded
| by Elligator to become a point matching the curve equation.
| This means that such a check is virtually useless and tells
| you nothing about whether there is a hidden key exchange
| happening or not.
| notfed wrote:
| You can make a random (high e) signal look non-random (low e)
| by adding strings of zeros and ones to it. Or you can embed it
| into known formats.
| ZenMikey wrote:
| I was always fascinated by stuff like LSB stenography where
| you hide a message (or another image) in the least
| significant bits of an image. Not visible to the human eye,
| mathematically should look like thermal noise in the image at
| most.
| Retr0id wrote:
| Image sensor noise is not a uniform distribution (I believe
| it's typically modeled as a Gaussian distribution, but even
| that's an approximation).
|
| Thus, it is mathematically/statistically distinguishable.
| NavinF wrote:
| The LSB of samples from a gaussian distribution is
| uniformly distributed: 50/50 chance of 0/1
|
| (Assuming you have enough bits per sample which image
| sensors provide IRL)
| Retr0id wrote:
| Only in theory. In practice, they're correlated with the
| other bits and adjacent pixels.
| FiloSottile wrote:
| 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.
| matthewdgreen wrote:
| 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
| pbsd wrote:
| 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
| ganzuul wrote:
| I have been thinking about local privacy preserving AI lately and
| stenography circumscribes much of the challenge. Having access to
| sensitive data means you have to limit access to a lot of tools.
| That's how it would work in a privacy context but the same tools
| are neutral to being used in a censorship context.
|
| It's over 10 years since but it would be nice if important
| research like this at least touched on the egalitarian issues
| rather than presenting a partisan agenda. E.g. someone somewhere
| who has to deal with private data now also has to deal with even
| stricter restrictions, without any doubt.
|
| Sometimes I worry about researchers working on important issues
| with apparently blinders on. If we don't self-supervise we just
| outsource the work, and in this case that means we are back to
| square one.
| NavinF wrote:
| Research like this does not touch on that issue because it's
| completely unrelated. Why would someone trying to exfiltrate
| private data have to do key exchange?
|
| Moreover, if you try to enforce anything by placing a bump in
| the wire (the only thing defeated by this), you're gonna lose
| every time.
|
| This "what if a bad guy has access to technology too!?"
| argument is tiresome.
| jerry1979 wrote:
| Here's a mathy explanation of its use in the real world (for peer
| to peer communications): https://github.com/bitcoin-
| core/secp256k1/blob/master/doc/el...
___________________________________________________________________
(page generated 2024-07-18 23:07 UTC)