commit af9b6d6479f2667375dfca9a9c949da37f9cadbf
parent b41ec1d897284983e79266bc998c6021ec082b19
Author: Pedram Fardzadeh <p.fardzadeh@protonmail.com>
Date: Mon, 1 Jul 2024 22:56:34 +0200
Added Elligator key creation
Diffstat:
1 file changed, 42 insertions(+), 13 deletions(-)
diff --git a/draft-gnunet-communicators.xml b/draft-gnunet-communicators.xml
@@ -266,11 +266,13 @@ KDF(A,Z):
Let G be the basepoint of Curve25519, EdToCurve() a function which converts Ed25519 points to their corresponding Curve25519 points,
Enc() Elligator's encoding function,
Dec() Elligator's decoding function, "X" the receiver's peer identity (a 256-bit EdDSA public key),
- "x" the corresponding secret key, "a" a 256-bit ephemeral secret key. Observe that:
+ "x" the corresponding secret key,
+ "A" an ephemeral public key (256-bit Curve25519 public key) and
+ "a" the corresponding 256-bit ephemeral secret key. Observe that:
</t>
<artwork name="" type="" align="left" alt=""><![CDATA[
(x, X) := KeyGenEd25519()
-(a, A) := KeyGenX25519()
+(a, A) := ElligatorKeyCreate()
Z := X25519(a, EdToCurve(X)) = X25519(x, A)
]]></artwork>
<t>
@@ -1401,15 +1403,42 @@ 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. (FIXME: Include our implementation).
- 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.
+ 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:
+<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 is defined below:
+ x-coordinate from the representative is defined below:
</t>
<artwork name="" type="" align="left" alt=""><![CDATA[
Dec(REPR):
@@ -1419,11 +1448,11 @@ Dec(REPR):
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 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.
+ 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
