Elligator for indistinguishable public key

[Gowee]

Hi.

Thanks for this great project.

As noise and snow are famous for providing excellent security guarantees while requiring few efforts to adopt, I am trying to use snow in my (yet another) proxy tool (prototype) which aims at circumventing Internet censorship. I start with Noise_NNpsk0_25519_ChaChaPoly_BLAKE2s as it looks pretty straightforward.

But then I realize that, in initial handshake messages, public keys (e of -> psk, e, e of <- e, ee in my case) are sent as plaintext, which leaves opportunities for an eavesdropper to distinguish a handshake from a uniform random byte string. As noted in the spec §10.5, elligator could be used to generate/encode public keys that are indistinguishable from random bytes.

Is there any plan to support it in the future?

[mcginty]

Hey @Gowee,

Yes, support for Elligator could be added (or possibly just adding "codec" functions to the keys being transmitted over the wire so folks could take control of it themselves, as it's not an official part of the Noise framework).

How far along on your project are you, and do you have any ideas on how you'd like to see it implemented?

[Gowee]

Hi, @mcginty.

It is here: https://github.com/Gowee/noisy-shuttle. A just-working prototype for now.

Considering that handshake messages are written out as opaque bytes instead of structs, I think a "codec" function (Fn(&[u8; 32]) -> [u8; 32] ?) would be straightforward. (Or is there an alternative way to get handshake messages as structured? Say, something like, struct Psk_E { pubkey: [u8; 32], aead_tag: [u8; 16] } ?)

[SnowyCoder]

I'm trying to create a proof of concept using Elligator, here are some exploratory notes:

To really provide a bitstream indistinguishable from random numbers, you should have a key that has also a random low-order component, there are ways to add and remove it, but since the low-order component is cleared when performing a DH operation, I would suggest to use it only with ephemeral keys:

Ephemeral keys don't have to be checked for authenticity, so even if they get randomized, they shouldn't be used for any other purpose than to just get an ephemeral DH value. This way static keys won't get Elligator-encoded, it should not be a problem unless static keys get sent unencrypted (Immediate Handshakes), and those have no identity hiding anyways.
The problem with this path is that key generation, encoding and decoding needs to be splitted, so code complexity will need to be Handled by the CryptoResolver/Dh traits and implementation.

Also, the feature will only be compatible with backends that support Elligator2 forward and reverse mapping (no backend has it for now, I'm working on a curve25519-dalek fork).

[aumetra]

I would also be interested in having some functionality to obfuscate handshakes. In my opinion a design with key codecs would be more flexible (and also enable things such as obfuscating keys using a known key and IV and a block cipher; such as in I2P's NTCP2 protocol).

Implementing Elligator2 directly would not only be rather inflexible (it wouldn't apply to any of the PQ patterns for one), it would also require adding group mappings to this crate.

I would maybe provide a draft PR later to have something concrete to discuss over.