commit 2ce257e467c2cd9f3eeae77291eeb0240f0f252d
parent 6ea56b935a68fc71b1d4c12a1f9282c21c890646
Author: Martin Schanzenbach <schanzen@gnunet.org>
Date: Wed, 10 Jul 2024 15:34:28 +0200
reorder elligator definitions
Diffstat:
1 file changed, 45 insertions(+), 47 deletions(-)
diff --git a/draft-gnunet-communicators.xml b/draft-gnunet-communicators.xml
@@ -224,17 +224,32 @@
<section anchor="KeyGen" numbered="true" toc="default">
<name>Key Generation</name>
<t> TODO FIXME define "standard" KeyGens</t>
+<t>
+The general idea when generating an Elligator key pair is is to create both a random high-order curve point and a low-order curve point.
+Adding them together results in a curve point
+that is evenly distributed on the whole Curve25519. Not all Curve25519 points are eligible to be used with Elligator for a key exchange. In
+particular, not all points will have the property that the encoding and subsequent decoding result in the original point. The mathematical
+reasoning is elaborated in <xref target="security_elligator"/>.
+To create a valid Curve25519 point that can be used as an
+ephemeral key, one needs to generate as many curve points until the desired property holds.
+Let G be the generator of the prime order group of Ed25519, H the generator of the low order subgroup of Ed25519 and EdToCurve() a function
+ which converts Ed25519 points to their corresponding Curve25519 points, we define:
+An Elligator key pair is generated as follows.
+</t>
+<artwork name="" type="" align="left" alt=""><![CDATA[
+KeyGenElligator():
+ VALID := 0
+ while(!VALID):
+ a := random(256)
+ ED_high := clamps(a) * G
+ ED_low := (a mod 8) * H
+ ED := ED_high + ED_low
+ A := EdToCurve(ED)
+ if Dec(Enc(A)) == A:
+ VALID := 1
+ return (a, A)
+ ]]></artwork>
<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 + A * X^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
- 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 communication attempts, 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>
- 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, sqrt() a function which calculates the square root of the finite field element, U the number
sqrt(-1) which is a non-quadratic number in the finite field, and legendre() a function which computes the legendre symbol of a field element.
As each of the field elements have two roots, we need to define the notion of negative and non-negative numbers. This is especially important for the
@@ -249,42 +264,7 @@ Enc(X):
else:
REPR := sqrt(-(X + A) / (U * X))
return REPR
- ]]></artwork>
- <t>
- The encoding function is defined for the entire Curve25519. Most modern implementations of Curve25519 only generate points from its prime
- subgroup to circumvent known attacks for which points not within the prime subgroup are susceptible. In our case, those attacks are not an
- issue as we use the ephemeral secret key only once for computing key material. The exclusive use of the prime subgroup is a recognizable
- property that an outside observer can easily detect, even in the case of using the encoding function. An attacker could decode the suspected
- parts of packets to the corresponding Curve25519 points and check if the resulting points are always in the prime subgroup. To circumvent
- this attack, we need to choose the ephemeral key pair randomly from the whole curve. One way to generate such a key pair is depicted below,
- where G is the generator of the prime order group of Ed25519, H the generator of the low order subgroup of Ed25519 and EdToCurve() a function
- which converts Ed25519 points to their corresponding Curve25519 points:
- </t>
- <artwork name="" type="" align="left" alt=""><![CDATA[
-ElligatorKeyCreate():
- a := random(256)
- ED_high := clamps(a).G
- ED_low := (a mod 8).H
- ED := ED_high + ED_low
- A := EdToCurve(ED)
- return (a, A)
- ]]></artwork>
-<t>
-The general idea is to create both a random high-order curve point and a low-order curve point. Adding them together results in a curve point
-that is evenly distributed on the whole Curve25519. Not all Curve25519 points are eligible to be used with Elligator for a key exchange. In
-particular, not all points will have the property that the encoding and subsequent decoding result in the original point. The mathematical
-reasoning will be explained later after looking into Elligator's decoding function. To create a valid Curve25519 point that can be used as an
-ephemeral key, one needs to generate as many curve points until the property holds:
-</t>
-<artwork name="" type="" align="left" alt=""><![CDATA[
-KeyGenElligator():
- VALID := 0
- while(!VALID):
- (a, A) := ElligatorKeyCreate()
- if dec(enc(A)) == A:
- VALID := 1
- return (a, A)
- ]]></artwork>
+]]></artwork>
<t>
The corresponding decoding function which is used by the elligator decapsulation function in <xref target="decaps"/> to recover the
x-coordinate from the representative is defined below:
@@ -1455,11 +1435,29 @@ SetupCipher(REC_ID, MSK):
<name>Security and Privacy Considerations</name>
<section anchor="security_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 + A * X^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
+ 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 communication attempts, 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.
+ The Elligator encoding function "Enc" (also known as the "inverse map") and decoding function "Dec" (also known as the "direct map") implement this feature.
+ </t>
+ <t>
+ The encoding function is defined for the entire Curve25519. Most modern implementations of Curve25519 only generate points from its prime
+ subgroup to circumvent known attacks for which points not within the prime subgroup are susceptible. In our case, those attacks are not an
+ issue as we use the ephemeral secret key only once for computing key material. The exclusive use of the prime subgroup is a recognizable
+ property that an outside observer can easily detect, even in the case of using the encoding function. An attacker could decode the suspected
+ parts of packets to the corresponding Curve25519 points and check if the resulting points are always in the prime subgroup. To circumvent
+ this attack, we need to choose the ephemeral key pair randomly from the whole curve as defined in "KeyGenElligator".
+ </t>
<t>
Note that both for 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 of the corresponding encoding calls are
different. Conversely, this means that we can't decode both representatives back to their original x-coordinate. This is why the sender
- eventually makes multiple calls to ElligatorKeyCreate() in KeyGenElligator() in order to create a valid public key that can be used
+ eventually tries a number of random key pairs in KeyGenElligator() in order to create a valid public key that can be used
for a key exchange. Also note that this effectively reduces the entropy of our public keys by 1 bit, which is tolerable.
</t>
<t>
