commit 662a5466c2e6b1978af3a4b9ba01797eba024824
parent b8a45c4be42e314c9141ef8c77958091235fd3a1
Author: Pedram Fardzadeh <p.fardzadeh@protonmail.com>
Date: Mon, 27 May 2024 15:00:10 +0200
Rephrased Elligator
Diffstat:
1 file changed, 36 insertions(+), 25 deletions(-)
diff --git a/draft-gnunet-communicators.xml b/draft-gnunet-communicators.xml
@@ -267,60 +267,62 @@ Decap(REPR) := (K,IV) = SetupCipher(X25519(REC_SK, Dec(REPR)), 0)
]]></artwork>
<t>
Note that the exchange of the receiver peer identity is not within the scope of the UDP communicator's key exchange and is already assumed to
- be known to the sender peer. It is also important to mention that the ephemeral public key, which is depicted in the KEM as G.EPH_SK, is a point
+ be known to the sending peer. It is also important to mention that the ephemeral public key, which is depicted in the KEM as G.EPH_SK, is a point
on the whole Curve25519 and not restricted to its prime subgroup. This is due to the fact that Elligator's encoding function is defined on the
whole Curve25519. The exclusive usage of the prime subgroup would restrict the set of potential representatives, which in turn an outside observer
can trivially recognize.
</t>
<t>
- (TODO) Explaination why KEM secure even if identities are used for signature
+ The use of the peer identities for both Ed25519 signatures and X25519-based KEM has been proven to be safe. For further details, refer to the
+ paper <xref target="E21"/>.
</t>
</section>
<section anchor="Elligator" numbered="true" toc="default">
<name>Elligator</name>
<t>
- In case of Montgomery curves such as Curve25519, a point [X,Y] on that curve (e.g. the ephemeral public key) follows the equation
- Y^2 = X^3 + AX^2 + X mod Q, whereas A and Q are parameters for Curve25519 specified in <xref target="RFC7748"/>. For any valid x-coordinate the left
- side of the equation is therefore always a quadratic number. An attacker could thus read the x-coordinate from the KX Header and check if
- this property holds. While this property holds for any valid Curve25519 point, it only holds in about 50% of the cases for a random number.
- Through the observation of multiple KX messages an attacker can be certain that curve points are being sent if the property holds over and
- over again. To circumvent this attack one would need to encode such curve points into property-less numbers. In other words, valid curve
- points and non valid curve points need to be indistinguishable for an outside observer.
+ In case of Montgomery curves, such as Curve25519, a point [X, Y] on that curve (e.g. the ephemeral public key) follows the equation
+ Y^2 = X^3 + AX^2 + X mod P, where A and P are parameters for Curve25519 specified in Section 4.1 of <xref target="RFC7748"/>. For any
+ valid x-coordinate, the left side of the equation is always a quadratic number. An attacker could read the x-coordinate from the KX Header
+ and verify if this property holds. While this property holds for any valid Curve25519 point, it only holds in about 50% of the cases for a
+ random number. By observing multiple KX packets, an attacker can be certain that curve points are being sent if the property consistently holds.
+ To circumvent this attack, curve points should be encoded into property-less numbers, making valid and invalid curve points indistinguishable
+ to an outside observer.
</t>
<t>
- Elligators encoding function (aka "inverse map") and decoding function (aka "direct map") implements this feature. Let X be a valid x-coordinate
- of a Curve25519 point and U an abbreviation for (-1)^(1/2) which is a non-quadratic number in the finite field of order Q.
- The encoding function can than be defined as follows:
+ 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:
</t>
<artwork name="" type="" align="left" alt=""><![CDATA[
Enc(X):
B := rand(1)
if B == 1:
- R := (-X / ((X + A) U)^(1/2)
+ REPR := (-X / ((X + A) * U)^(1/2)
else:
- R := (-(X + A) / (UX))^(1/2)
- return R
+ REPR := (-(X + A) / (U * X))^(1/2)
+ return REPR
]]></artwork>
<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[
-Dec(R):
- V := -A / (1 + UR^2)
- E := legendre(V^3 + AV^2 + V)
- X := EV - (1 - E)(A / 2)
+Dec(REPR):
+ V := -A / (1 + U * REPR^2)
+ E := legendre(V^3 + A * V^2 + V)
+ X := E * V - (1 - E)(A / 2)
return X
]]></artwork>
<t>
- Note that in the original paper Elligator's encoding function takes the y-coordinate is an additional input parameter. Its value determines which
- of the two terms is taken instead of our random selection. We also skip the calculation of the 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
+ Note that 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.
</t>
<t>
- Lastly, we want to emphasize that he resulting representative of the encoding function is strictly smaller than 2^254 - 9. The most and second
- most significant bit are thus always 0, which again is an obvious property an attacker could observe. We evade this problem by simply flipping
- both bits randomly. Those bits will be ignored by the target peer after reception.
+ Lastly, we emphasize that the resulting representative of the encoding function is strictly smaller than 2^254 - 9. Therefore, the most and second most
+ significant bit are always zero, which is an obvious property an attacker could observe. We avoid this problem by randomly flipping
+ both bits. These bits will be ignored by the target peer after reception.
</t>
</section>
<section anchor="udp_key_schedule" numbered="true" toc="default">
@@ -1008,6 +1010,15 @@ SetupCipher(MSK):
</references>
<references>
<name>Informative References</name>
+ <reference anchor="E21" target="https://eprint.iacr.org/2021/509.pdf">
+ <front>
+ <title>On using the same key pair for Ed25519 and an X25519 based KEM</title>
+ <author initials="E." surname="Thormaker"
+ fullname="Erik Thormarker">
+ </author>
+ <date month="April" year="2021" />
+ </front>
+ </reference>
</references>
</back>
</rfc>
