commit c6a1302c8cd28c2778a58435453d88aab6ebf132
parent b1c9211d19cb9ac983ba3cfba991f54ba15717cb
Author: Martin Schanzenbach <schanzen@gnunet.org>
Date: Wed, 10 Jul 2024 15:19:25 +0200
restructure primitives
Diffstat:
1 file changed, 99 insertions(+), 98 deletions(-)
diff --git a/draft-gnunet-communicators.xml b/draft-gnunet-communicators.xml
@@ -221,8 +221,102 @@
</section>
<section anchor="primitives" numbered="true" toc="default">
<name>General purpose primitives</name>
+ <section anchor="KeyGen" numbered="true" toc="default">
+ <name>Key Generation</name>
+ <t> TODO FIXME define "standard" KeyGens</t>
+ <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
+ sqrt() function. A straightforward choice is to define the set {0,..., (P - 1) / 2} as set of all non-negative numbers.
+ The encoding function used by the elligator encapsulation function in <xref target="encaps"/> can be defined as follows:
+ </t>
+<artwork name="" type="" align="left" alt=""><![CDATA[
+Enc(X):
+ B := rand(1)
+ if B == 1:
+ REPR := sqrt(-X / ((X + A) * U))
+ 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>
+ <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:
+ </t>
+ <artwork name="" type="" align="left" alt=""><![CDATA[
+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 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
+ for a key exchange. Also note that this effectively reduces the entropy of our public keys by 1 bit, which is tolerable.
+ </t>
+ <t>
+ In the original paper, Elligator's encoding function takes the sign of y-coordinate as 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 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="key_derivation" numbered="true" toc="default">
- <name>Key derivation</name>
+ <name>Key Derivation</name>
<t>
We use a hash-based key derivation function (HKDF) as defined in
<xref target="RFC5869" />, using SHA-256 <xref target="RFC6234"/> for the extraction
@@ -238,7 +332,7 @@ KDF(A,Z):
]]></artwork>
</section>
<section anchor="elligator_kem" numbered="true" toc="default">
- <name>Elligator KEM</name>
+ <name>Key Encapsulation</name>
<t>
GNUnet utilizes Elligator for the encoding and decoding of the ephemeral public keys
described in Section 5 of <xref target="BHKL13"/>.
@@ -272,7 +366,7 @@ KDF(A,Z):
</t>
<artwork name="" type="" align="left" alt=""><![CDATA[
(x, X) := KeyGenEd25519()
-(a, A) := ElligatorKeyCreate()
+(a, A) := KeyGenElligator()
Z := X25519(a, EdToCurve(X)) = X25519(x, A)
]]></artwork>
<t>
@@ -302,10 +396,10 @@ Decaps(x, A):
]]></artwork>
<t>
More details about the construction of the representative and Elligator's
- usage can be found in <xref target="Elligator"/>.
+ usage can be found in <xref target="KeyGen"/>.
</t>
</section>
- </section>
+ </section>
<section anchor="udp_comm" numbered="true" toc="default">
<name>UDP communicator</name>
<t>
@@ -1374,99 +1468,6 @@ SetupCipher(REC_ID, MSK):
<dd>Field as defined in the RRBLOCK message above.</dd>
</dl>
</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 + 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
- sqrt() function. A straightforward choice is to define the set {0,..., (P - 1) / 2} as set of all non-negative numbers.
- The encoding function used by the elligator encapsulation function in <xref target="encaps"/> can be defined as follows:
- </t>
-<artwork name="" type="" align="left" alt=""><![CDATA[
-Enc(X):
- B := rand(1)
- if B == 1:
- REPR := sqrt(-X / ((X + A) * U))
- 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[
-ElligatorGenerateKey():
- 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[
-ElligatorKeyCreate():
- VALID := 0
- while(!VALID):
- (a, A) := ElligatorGenerateKey()
- if dec(enc(A)) == A:
- VALID := 1
- return (a, A)
- ]]></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:
- </t>
- <artwork name="" type="" align="left" alt=""><![CDATA[
-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 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 ElligatorGenerateKey() in ElligatorKeyCreate() 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>
- In the original paper, Elligator's encoding function takes the sign of y-coordinate as 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 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="security" numbered="true" toc="default">
<name>Security and Privacy Considerations</name>
</section>
