search

jedisct1 / libsodium

A modern, portable, easy to use crypto library.
https://libsodium.org
Other
12.19k stars 1.74k forks source link

Elligator inverse map #924

Closed nitrieu closed 4 years ago

nitrieu commented 4 years ago

Hi there,

From what I understand, your code supports the map in the forward direction (e.g. takes a random field element and produces a group element). Do you have a code for backward direction, which represents the group element as a field element like this?

Thanks.

jedisct1 commented 4 years ago

Hi!

While Elligator is useful for the hash-to-group-element operation, I've never found any practical use case for the inverse map. DPI circumvention isn't a very compelling argument, as encrypted channels are simply detected using entropy evaluation instead of trying to spot public keys. If necessary, public keys can be encrypted to hide the sender in addition to providing indistinguishability from randomness.

So, it is not implemented in libsodium or wasm-crypto.

It should be pretty straightforward to implement, but I don't have any code for this at the moment.

LoupVaillant commented 4 years ago

If necessary, public keys can be encrypted to hide the sender in addition to providing indistinguishability from randomness.

(Emphasis mine)

Sorry to bother you on a closed issue, but you may have written that part a bit quickly: initiating a first connection requires an unencrypted ephemeral key to bootstrap the process, and those are not indistinguishable from random. Curve25519 points are encoded in 255 bits, and they satisfy a condition that only half random numbers fulfil. That's 2 bits of bias, and easily distinguished from random. (Of course one of those bits is easily masked. The other requires Elligator or equivalent.)

Whether we need indistinguishability from random is another question, which I am not qualified to answer.

jedisct1 commented 4 years ago

To encrypt the public key in the initial handshake, you need a PSK or a previous session key (as in 0 RTT schemes).

I've still never seen any compelling use case for the foward map.

LoupVaillant commented 4 years ago

Yep. I was just insisting that when cold contacting someone, you don't have a PSK yet, and therefore can't encrypt your ephemeral key. What you wrote was accurate, but I was afraid people might get the wrong idea, and think the ephemeral key is as good as random.

I was probably overreacting.