4 ms·

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 th

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 2y ago
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 2y ago
  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 2y ago
    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.
    - mti 2y ago
      Elligator is only tangentially relevant to the hashing problem. If "doesn't have a problematic structure" is understood in a weak sense, then this was already solved by Shallue and van de Woestijne almost a decade prior to the Elligator paper. And if it is understood in the stronger sense of indifferentiability, then Elligator by itself doesn't actually fit the bill, and you need something like the Brier et al. approach or SwiftEC. The steganography stuff is the only actually novel contribution of the Elligator paper.
      - less_less 2y ago
        Perhaps it's a bit more than tangentially relevant? Yes, SW[U] predates it for hashing, and Brier et al builds indifferentiability on that. But Elligator2 is simpler and faster, and also works with Brier et al, though it only supports even-order curves. As a result, Elligator2 is specified in RFC 9380 along with SW[U], and has fairly broad implementation. Also yes, SwiftEC is faster than Elligator2 + Brier et al, at least if Jacobi symbols are fast with your parameters/hardware. But you can do something very similar to SwiftEC with Elligator2. This is simpler than SwiftEC and probably still faster, and was published earlier (https://eprint.iacr.org/2020/1513 https://eprint.iacr.org/2020/1513).
Retr0id 2y ago
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 2y ago
  If a single point matches the curve equation of a well-known curve then that’s pretty compelling evidence.
  - Retr0id 2y ago
    not for compressed point representations (hence "depending on format")
    - nmadden 2y ago
      So just X25519 then?
      - Retr0id 2y ago
        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-ecc/ https://datatracker.ietf.org/doc/draft-mattsson-tls-compact-...
  - kientuong114 2y ago
    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 2y ago
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 2y ago
  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 2y ago
    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 2y ago
      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 2y ago
        Only in theory. In practice, they're correlated with the other bits and adjacent pixels.
        NavinF 2y ago
        How correlated? I spent 2 minutes trying and failing to get chatGPT to generate code that downloads an image dataset and runs diehard on the LSBs. I'd expect the LSBs to pass the randomness test.

Y_Y 2y ago

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 2y ago
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 2y ago
  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.
  - mti 2y ago
    Elligator is only tangentially relevant to the hashing problem. If "doesn't have a problematic structure" is understood in a weak sense, then this was already solved by Shallue and van de Woestijne almost a decade prior to the Elligator paper. And if it is understood in the stronger sense of indifferentiability, then Elligator by itself doesn't actually fit the bill, and you need something like the Brier et al. approach or SwiftEC. The steganography stuff is the only actually novel contribution of the Elligator paper.
    - less_less 2y ago
      Perhaps it's a bit more than tangentially relevant? Yes, SW[U] predates it for hashing, and Brier et al builds indifferentiability on that. But Elligator2 is simpler and faster, and also works with Brier et al, though it only supports even-order curves. As a result, Elligator2 is specified in RFC 9380 along with SW[U], and has fairly broad implementation. Also yes, SwiftEC is faster than Elligator2 + Brier et al, at least if Jacobi symbols are fast with your parameters/hardware. But you can do something very similar to SwiftEC with Elligator2. This is simpler than SwiftEC and probably still faster, and was published earlier (https://eprint.iacr.org/2020/1513 https://eprint.iacr.org/2020/1513).

Retr0id 2y ago

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 2y ago
If a single point matches the curve equation of a well-known curve then that’s pretty compelling evidence.
- Retr0id 2y ago
  not for compressed point representations (hence "depending on format")
  - nmadden 2y ago
    So just X25519 then?
    - Retr0id 2y ago
      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-ecc/ https://datatracker.ietf.org/doc/draft-mattsson-tls-compact-...
- kientuong114 2y ago
  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 2y ago

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 2y ago
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 2y ago
  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 2y ago
    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 2y ago
      Only in theory. In practice, they're correlated with the other bits and adjacent pixels.
      - NavinF 2y ago
        How correlated? I spent 2 minutes trying and failing to get chatGPT to generate code that downloads an image dataset and runs diehard on the LSBs. I'd expect the LSBs to pass the randomness test.