[lsd0007] branch master updated: restructure primitives

[gnunet]

This is an automated email from the git hooks/post-receive script.

martin-schanzenbach pushed a commit to branch master
in repository lsd0007.

The following commit(s) were added to refs/heads/master by this push:
     new c6a1302  restructure primitives
c6a1302 is described below

commit c6a1302c8cd28c2778a58435453d88aab6ebf132
Author: Martin Schanzenbach <schanzen@gnunet.org>
AuthorDate: Wed Jul 10 15:19:25 2024 +0200

    restructure primitives
---
 draft-gnunet-communicators.xml | 197 +++++++++++++++++++++--------------------
 1 file changed, 99 insertions(+), 98 deletions(-)

diff --git a/draft-gnunet-communicators.xml b/draft-gnunet-communicators.xml
index e5832cb..7ad96c1 100644
--- 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>

-- 
To stop receiving notification emails like this one, please contact
gnunet@gnunet.org.