[lsd0007] branch master updated: Added key exchange and elligator chapter

[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 3fadd25  Added key exchange and elligator chapter
3fadd25 is described below

commit 3fadd25e466069e141174376c0ec9b74a9028c22
Author: Pedram Fardzadeh <p.fardzadeh@protonmail.com>
AuthorDate: Tue May 21 18:21:29 2024 +0200

    Added key exchange and elligator chapter
---
 draft-gnunet-communicators.xml | 157 +++++++++++++++++++++++++++++++----------
 1 file changed, 119 insertions(+), 38 deletions(-)

diff --git a/draft-gnunet-communicators.xml b/draft-gnunet-communicators.xml
index 45edef2..db6998e 100644
--- a/draft-gnunet-communicators.xml
+++ b/draft-gnunet-communicators.xml
@@ -203,42 +203,125 @@
    <section anchor="udp_comm" numbered="true" toc="default">
      <name>UDP communicator</name>
      <t>
-       The UDP communicator implements a basic encryption layer to protect from
-       metadata leakage.
-       The layer tries to establish a shared secret using an
-       Elliptic-Curve Diffie-Hellman key exchange in which the initiator of a
-       packet creates an ephemeral key pair to encrypt a message for the target
-       peer identity.
-       The communicator always offers this kind of transmission queue to a
-       (reachable) peer in which messages are encrypted with dedicated keys.
-       The performance of this queue is not suitable for high volume data 
transfer.
+       The UDP communicator implements an encryption layer which both protects
+       the payload to be sent and the communicator's specific metadata (not to 
be confused with the UDP-Header). 
+       In particular any packet send by the communicator is indistinguishable 
from a random noise for an outside observer.
+      </t>
+      <t>
+       For any new connection to a target peer the communicator tries to 
establish a shared secret using an
+       Elliptic-Curve Diffie-Hellman key exchange. The initiator of that 
connection creates an ephemeral 
+       key pair to encrypt the message for the target peer identity. The 
encrypted message is prepended by a
+       KX Header which contains the ephemeral public key and is than send to 
the target peer. For any subsequent 
+       packet this procedure is repeated with a new ephemeral key. The wire 
format for such an KX packet can 
+       be found in <xref target="figure_udp_initialkx"/>.
+       The communicator always offers this kind of message queue to a 
(reachable) peer but it is inefficient 
+       since for every packet, a new key exchange is carried out. The 
performance of this queue is therefore 
+       not suitable for high-volume data transfer.
      </t>
      <t>
-       If the UDP connection is bi-directional, or the TRANSPORT is able to
-       offer a backchannel connection, the resulting key can be re-used if the
-       recieving peer is able to ACK the reception.
-       This will cause the communicator to offer a new queue (with a higher
-       priority than the default queue) to TRANSPORT with a limited capacity.
-       The capacity is increased whenever the communicator receives an ACK for 
a
-       transmission.
-       This queue is suitable for high-volume data transfer and TRANSPORT will
-       likely prioritize this queue (if available).
+       Should however the target peer acknowledge the reception of a KX packet 
the resulting key can be re-used.
+       Such an ACK packet can be either send via a bi-directional UDP 
connection or a backchannel connection provided 
+       by TRANSPORT. The wire format for such an KX packet is depicted in 
<xref target="figure_udp_ack"/>.
+       This will cause the communicator to offer a new queue (with a higher 
priority than the default queue) to 
+       TRANSPORT with a limited capacity. The capacity is increased whenever 
the communicator receives an ACK for a 
+       transmission. This queue is suitable for high-volume data transfer and 
TRANSPORT will prioritize this queue 
+       if available.
      </t>
      <t>
-       Communicators that try to establish a connection to a target peer
-       authenticate their peer ID (public key) in the first packets by signing 
a
-       monotonic time stamp, its peer ID, and the target peerID and send this
-       data as well as the signature in one of the first packets.
-       Receivers should keep track (persist) of the monotonic time stamps for
-       each peer ID to reject possible replay attacks.
-     </t>
-     <t>
-       Until a shared secret has been established, messages sent from the 
sender peer to the receiver peer
-       are always encrypted and a key exchange metadata header is prepended.
-       The wire format can be found in <xref target="figure_udp_initialkx"/>.
-       This method of sending messages to a peer can be used indefinitely, but 
is ineffienct since for every
-       message, a new symmetric key must be established.
+       The initiating communicator tries to authenticate their peer ID (public 
key) in the first packets by signing 
+       a monotonic time stamp, its peer ID, and the target peerID and send 
this data as well as the signature in 
+       one of the first packets. Receivers should keep track (persist) of the 
monotonic time stamps for each 
+       peer ID to reject possible replay attacks.
      </t>
+
+    <section anchor="Key_exchange" numbered="true" toc="default">
+       <name>Key exchange</name>
+       <t>
+         In order to establish a shared secret, an X25519-based key exchange 
is initiated by the sending peer. The sender generates an 
+         ephemeral key pair first and uses the ephemeral private key and the 
receiver's peer identity to calculate the shared secret. 
+         To hide the fact that a key exchange is being performed, the sender 
peer projects the ephemeral public key into a random-looking 
+         byte stream (later referenced as the representative) before sending 
it to the receiver peer. The receiver peer can then recover 
+         the ephemeral public key of the sender peer and calculate the same 
shared secret with its own private key.
+        </t>
+        <t>
+         The projection of the ephemeral public key is necessary if one wants 
to hide the fact that an ECC-based key exchange is being performed.
+         This is due to the structure of ECC public keys, which are not 
equally distributed with respect to the underlying group of the curve and 
+         therefore distinguishable from random. The UDP communicator uses 
Elligator's encoding and decoding functions for the projection 
+         and recovery of the ephemeral public key. More details about the 
construction of the representative and Elligator can be found in
+         <xref target="Elligator"/>
+        </t>
+        <t>
+         Let G be the basepoint of Curve25519, Ed25519_To_Curve25519() a 
function which converts Ed25519 points to their corresponding Curve25519 
+         points, Enc() Elligator's encoding function, Dec() Elligator's 
decoding function, RECEIVER_PEER_ID a 256-bit EdDSA public key,
+         RECEIVER_SK the corresponding secret key and EPH_SK a 256-bit 
ephemeral secret key. 
+         We can than define the described key exchange as a KEM:
+        </t>
+        <artwork name="" type="" align="left" alt=""><![CDATA[
+Key_Gen() := (RECEIVER_SK, RECEIVER_PEER_ID) 
+Encap() := (R, MSK) = (Enc(G.EPH_SK, rand), X25519(EPH_SK, 
Ed25519_To_Curve25519(RECEIVER_PEER_ID)))
+Decap(R) :=  (MSK) = X25519(RECEIVER_SK, Dec(R))
+  ]]></artwork>
+        <t>
+         Note that the exchange of the receiver peer identity is not within 
the scope of 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 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>
+     </section>
+     <section anchor="Elligator" numbered="true" toc="default">
+       <name>Elligator</name>
+       <t>
+       The UDP Communicator will always perform atleast one Diffie-Hellman key 
exchange with the target peer independent on the type of message 
+       queue. The key exchange requires the transmission of an ephemeral 
public key from the sender peer to the target peer. If no additional 
+       measures are taken, an outside observer can recognize the transmission 
of that ephemeral key and deduce that an ECC-based key exchange 
+       is being performed. 
+       </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 + 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. 
+       </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:
+       </t>
+<artwork name="" type="" align="left" alt=""><![CDATA[
+Enc(X):
+  B := rand(1)
+  if B == 1:
+    R :=  (-X / ((X + A) U)^(1/2)
+  else:
+    R :=  (-(X + A) / (UX))^(1/2)
+  return R
+ ]]></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)
+  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 
+      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. 
+      </t>
+     </section>
      <section anchor="udp_key_schedule" numbered="true" toc="default">
        <name>Key schedule</name>
        <t>
@@ -284,8 +367,6 @@ DeriveKID(MSK,SEQ):
        <name>KX Header</name>
        <t>
          All metadata for headers is chosen such that they are 
indistinguishable from random.
-         For the use of (ephemeral) ECC public key material, this probably 
requires the use of additional randomization
-         techniques such as Elligator (TODO).
          There are three distinct message types that are sent and received by 
UDP communciators: KX, BOX, BROADCAST.
          In any case, the common header is 32 + 16 bytes in length. 
        </t>
@@ -293,7 +374,7 @@ DeriveKID(MSK,SEQ):
        <artwork name="" type="" align="left" alt=""><![CDATA[
 0           8           16          24    
 +-----+-----+-----+-----+-----+-----+-----+-----+
-|                EPHEMERAL PUBLIC KEY           |
+|                REPRESENTATIVE                 |
 |                                               |
 |                                               |
 |                                               |
@@ -312,11 +393,10 @@ DeriveKID(MSK,SEQ):
          ]]></artwork>
      </figure>
        <dl>
-         <dt>EPHEMERAL PUBLIC KEY</dt>
+         <dt>REPRESENTATIVE</dt>
          <dd>
-           A 256-bit EdDSA public key. This key is used as input to a 
Diffie-Hellman KEM to decapsulate
-           the symmetric secret used to establish a shared secret which can be 
used to
-           decrypt ENCRYPTED DATA.
+           An serialized Elligator encoded 256-bit Curve25519 public key. This 
encoded public key can be decoded and than used as part of an X25519-based
+           key exchange to establish a shared secret.
          </dd>
          <dt>GCM TAG</dt>
          <dd>
@@ -920,6 +1000,7 @@ SetupCipher(MSK):
          &RFC2119;
          &RFC5869;
          &RFC6234;
+         &RFC7748;
          &RFC8174;
          &RFC9000;
 

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