commit 1a689942fc8ee6398b7ae73a5409863f9edf21bc
parent bce32abca61fba2c52407946ce5dc1321078c4da
Author: Pedram Fardzadeh <p.fardzadeh@protonmail.com>
Date: Mon, 17 Jun 2024 18:52:13 +0200
Updated Elligator
Diffstat:
1 file changed, 19 insertions(+), 4 deletions(-)
diff --git a/draft-gnunet-communicators.xml b/draft-gnunet-communicators.xml
@@ -490,8 +490,8 @@ DeriveKID(MSK,SEQ):
return KID
]]></artwork>
<t>
- The sequence number SEQ for any shared secret is initially 0 and incremented on the senders side with each
- successive encryption and on the receivers side on each decryption.
+ The sequence number SEQ for any shared secret is initially 0 and incremented on the senders side for each
+ successive encryption and on the receivers side for each decryption.
</t>
</section>
<section anchor="udp_message_exchange" numbered="true" toc="default">
@@ -1339,7 +1339,7 @@ SetupCipher(MSK):
The Elligators encoding function (also known as the "inverse map") and decoding function (also known as the "direct map") implements this feature.
Let X be a valid x-coordinate of a Curve25519 point, U the number (-1)^(1/2) which is a non-quadratic number in the finite field of order P and
legendre() a function which computes the legendre symbol of a field element.
- The encoding function used by the UDP communicator can be defined as follows:
+ The encoding function used by both the UDP and TCP communicator can be defined as follows:
</t>
<artwork name="" type="" align="left" alt=""><![CDATA[
Enc(X):
@@ -1351,6 +1351,14 @@ Enc(X):
return REPR
]]></artwork>
<t>
+ The encoding function is defined for the entire Curve25519. In modern cryptoghraphic systems, mostly public keys from the prime
+ subgroup of Curve25519 are used. The exclusive use of the prime subgroup is a recognizable property that an outside observer can
+ easily detect. To circumvent this issue, we need to randomly choose an curve point from the whole curve. Two methods to achieve
+ this are described in (FIXME: include source). By ensuring that the x-coordinate is from a randomly chosen curve point on the entire
+ curve, the resulting representatives do not possess any properties that could be used by an attacker to identify them as curve point
+ coordinates anymore.
+ </t>
+ <t>
The x-coordinate of the encoded Curve25519 point can be recovered via the decoding function below:
</t>
<artwork name="" type="" align="left" alt=""><![CDATA[
@@ -1361,7 +1369,14 @@ Dec(REPR):
return X
]]></artwork>
<t>
- Note that in the original paper, Elligator's encoding function takes the sign of y-coordinate is an additional input parameter. Its value determines
+ Note that both for the a value REPR and its negative counterpart -REPR (in the finite field), the decoding function will result in the
+ same x-coordinate. Moreover, for two different valid x-coordinates the resulting representatives are different. Conversely,
+ this means that we can't decode both representatives back to their original x-coordinate. This effectivly reduces the entropy of our
+ public keys by 1 bit, which is torelable. With this in mind, the sender need test that the generated ephemeral public key result in the
+ same public key after an encoding and subsequent decoding call.
+ </t>
+ <t>
+ In the original paper, Elligator's encoding function takes the sign of y-coordinate is an additional input parameter. Its value determines
which of the two terms is used instead of our random selection. We also skip the calculation of the corresponding y-coordinate in the decoding function.
We omitted the y-coordinate parts of both functions because Curve25519 points are solely represented by their x-coordinate in modern crypto systems due to
known attacks. Nevertheless, the desired feature of Elligator is still ensured.
