[lsd0007] branch master updated: Rephrased Elligator

[gnunet]

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

pedram pushed a commit to branch master
in repository lsd0007.

The following commit(s) were added to refs/heads/master by this push:
     new 662a546  Rephrased Elligator
662a546 is described below

commit 662a5466c2e6b1978af3a4b9ba01797eba024824
Author: Pedram Fardzadeh <p.fardzadeh@protonmail.com>
AuthorDate: Mon May 27 15:00:10 2024 +0200

    Rephrased Elligator
---
 draft-gnunet-communicators.xml | 61 +++++++++++++++++++++++++-----------------
 1 file changed, 36 insertions(+), 25 deletions(-)

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

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