commit 3fadd25e466069e141174376c0ec9b74a9028c22
parent 83c5e18af661aaa2e7f4fbfb9572b0403960f590
Author: Pedram Fardzadeh <p.fardzadeh@protonmail.com>
Date: Tue, 21 May 2024 18:21:29 +0200
Added key exchange and elligator chapter
Diffstat:
1 file changed, 119 insertions(+), 38 deletions(-)
diff --git 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;
