commit 9e934ea6b0ee325364ff21724b26ef7058b731f1
parent 271c7dc0dac845c139e891fde5075f84951b2fa0
Author: Pedram Fardzadeh <p.fardzadeh@protonmail.com>
Date: Mon, 10 Jun 2024 03:22:41 +0200
Updated TCP Communicator handshake and key exchange
Diffstat:
1 file changed, 204 insertions(+), 73 deletions(-)
diff --git a/draft-gnunet-communicators.xml b/draft-gnunet-communicators.xml
@@ -278,54 +278,6 @@ Decap(REPR) := (K,IV) = SetupCipher(X25519(REC_SK, Dec(REPR)), 0)
paper <xref target="T21"/>.
</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 + 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 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>
- 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:
- REPR := (-X / ((X + A) * U)^(1/2)
- else:
- 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(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 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 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">
<name>Key schedule</name>
<t>
@@ -399,7 +351,7 @@ DeriveKID(MSK,SEQ):
<dl>
<dt>REPRESENTATIVE</dt>
<dd>
- 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
+ A 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>
@@ -674,7 +626,23 @@ DeriveKID(MSK,SEQ):
</t>
<section anchor="tcp_handshake" numbered="true" toc="default">
<name>Handshake</name>
- <figure anchor="figure_tcp_handshake" title="The wire format of a TCP handshake.">
+ <t>
+ The main purpose of the handshake is to establish shared key material for each direction of the communication
+ channel. The initiating TCP Communicator starts the handshake by sending an ephemeral Curve25519 public key,
+ which is necessary to perform the X25519-based key exchange defined in <xref target="tcp_KEM"/>. As the
+ public key can not be encrypted at this stage of the communication channel it <bcp14>MUST</bcp14> be encoded
+ using the Elligator encoding function.
+ In contrast to the plain public key, the encoded public key (also called the representative) is indistinguishable
+ from a random-looking byte stream, which protects against censors targeting messages containing cryptographic
+ material. More information about Elligator and its usage can be found in <xref target="Elligator"/>.
+ </t>
+ <t>
+ The sent public key <bcp14>MUST</bcp14> be directly followed by an encrypted TCP handshake packet as shown
+ in <xref target="figure_tcp_handshake"/>. In addition to the peer identity of the sender and a timestamp, it
+ contains a nonce as a challenge for the receiving TCP communicator. All this data is authenticated via a
+ signature, which is also included in the TCP handshake packet.
+ </t>
+ <figure anchor="figure_tcp_handshake" title="The binary representation of the TCP handshake packet.">
<artwork name="" type="" align="left" alt=""><![CDATA[
0 8 16 24 32 40 48 56
+-----+-----+-----+-----+-----+-----+-----+-----+
@@ -720,7 +688,10 @@ DeriveKID(MSK,SEQ):
A 256-bit random value used as a challenge to be signed in a TCP acknowledgment.
</dd>
</dl>
- <figure anchor="figure_tcp_handshake_sig" title="The wire format used for creating the signature of the identification packet.">
+ <t>
+ The data scheme used for computing the signature is depicted in <xref target="figure_tcp_handshake_sig"/>.
+ </t>
+ <figure anchor="figure_tcp_handshake_sig" title="The wire format used for creating the signature of the tcp handshake packet.">
<artwork name="" type="" align="left" alt=""><![CDATA[
0 8 16 24 32 40 48 56
+-----+-----+-----+-----+-----+-----+-----+-----+
@@ -736,7 +707,7 @@ DeriveKID(MSK,SEQ):
| |
| |
+-----+-----+-----+-----+-----+-----+-----+-----+
-| EPHEMERAL PUBLIC KEY |
+| REPRESENTATIVE |
| |
| |
| |
@@ -766,7 +737,7 @@ DeriveKID(MSK,SEQ):
<dt>PURPOSE</dt>
<dd>
A 32-bit signature purpose flag in network byte order. The value of this
- field <bcp14>MUST</bcp14> be XXXX. It defines the context in which
+ field <bcp14>MUST</bcp14> be 31. It defines the context in which
the signature is created so that it cannot be reused in other parts
of the protocol including possible future extensions.
The value of this field corresponds to an entry in the
@@ -780,10 +751,100 @@ DeriveKID(MSK,SEQ):
<dd>
A 256-bit EdDSA public key.
</dd>
- <dt>EPHEMERAL PUBLIC KEY</dt>
+ <dt>REPRESENTATIVE</dt>
+ <dd>
+ A 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>MONOTONIC TIMESTAMP</dt>
+ <dd>
+ FIXME.
+ </dd>
+ <dt>NONCE</dt>
+ <dd>
+ A 256-bit random value.
+ </dd>
+ </dl>
+ <t>
+ Upon reception of the ephemeral public key, the receiving TCP communicator carries out the decapsulation step of the
+ KEM and retrieves the shared key material. The subsequently received TCP handshake packet is then decrypted and verified.
+ If the signature is invalid, the connection is dropped. (FIXME: Other checks such as sender peer identity etc needed).
+ In the case of a valid signature, the receiving TCP communicator sends its own TCP handshake packet to establish
+ shared key material for outgoing messages and also replies with an encrypted TCP handshake acknowledgment packet as defined
+ in <xref target="figure_tcp_handshake_ack"/>.
+ </t>
+ <figure anchor="figure_tcp_handshake_ack" title="The binary representation of the tcp handshake acknowledgement packet.">
+ <artwork name="" type="" align="left" alt=""><![CDATA[
+0 8 16 24
++-----+-----+-----+-----+-----+-----+-----+-----+
+| SIZE | TYPE (0x0X) |
++-----+-----+-----+-----+-----+-----+-----+-----+
+| SENDER PEER ID |
+| |
+| |
+| |
+| |
+| |
+| |
+| |
++-----+-----+-----+-----+-----+-----+-----+-----+
+| RECEIVER PEER ID |
+| |
+| |
+| |
+| |
+| |
+| |
+| |
++-----+-----+-----+-----+-----+-----+-----+-----+
+| SIGNATURE |
+| |
+| |
+| |
+| |
+| |
+| |
+| |
++-----+-----+-----+-----+-----+-----+-----+-----+
+| MONOTONIC TIMESTAMP |
+| |
++-----+-----+-----+-----+-----+-----+-----+-----+
+| NONCE |
+| |
+| |
+| |
+| |
+| |
+| |
+| |
++-----+-----+-----+-----+-----+-----+-----+-----+
+ ]]></artwork>
+ </figure>
+ <dl>
+ <dt>SIZE</dt>
+ <dd>
+ A 16-bit value containing the length of the message in bytes
+ in network byte order.
+ </dd>
+ <dt>TYPE</dt>
+ <dd>
+ A 16-bit signature type flag in network byte order. The value of this
+ field <bcp14>MUST</bcp14> be 1453.
+ </dd>
+ <dt>SENDER PEER ID</dt>
+ <dd>
+ A 256-bit EdDSA public key.
+ </dd>
+ <dt>RECEIVER PEER ID</dt>
<dd>
A 256-bit EdDSA public key.
</dd>
+ <dt>Signature</dt>
+ <dd>
+ A 512-bit EdDSA signature. The signature is calculated over
+ the data as defined in <xref target="figure_tcp_handshake_ack_sig"/>.
+ </dd>
<dt>MONOTONIC TIMESTAMP</dt>
<dd>
FIXME.
@@ -794,12 +855,10 @@ DeriveKID(MSK,SEQ):
</dd>
</dl>
<t>
- If the handshake data is invalid, the connection is dropped. (FIXME define invalid, signature invalid OR sender invalid etc).
- Otherwise, we send our own TCP handshake to establish a shared secret for outgoing messages and reply with a TCP handshake acknowledgment message.
- The TCP handshake acknowledgement message is defined in <xref target="figure_tcp_handshake_ack_sig"/> and is encrypted
- with the
+ The data scheme used for computing the signature for the acknowledgement packet is depicted
+ in <xref target="figure_tcp_handshake_ack_sig"/>.
</t>
- <figure anchor="figure_tcp_handshake_ack_sig" title="The wire format used for creating the response for the identification packet.">
+ <figure anchor="figure_tcp_handshake_ack_sig" title="The wire format used for creating the signature of the tcp handshake acknowledgement packet.">
<artwork name="" type="" align="left" alt=""><![CDATA[
0 8 16 24
+-----+-----+-----+-----+-----+-----+-----+-----+
@@ -843,7 +902,7 @@ DeriveKID(MSK,SEQ):
<dt>TYPE</dt>
<dd>
A 16-bit signature type flag in network byte order. The value of this
- field <bcp14>MUST</bcp14> be XXXX.
+ field <bcp14>MUST</bcp14> be 39.
</dd>
<dt>SENDER PEER ID</dt>
<dd>
@@ -862,20 +921,34 @@ DeriveKID(MSK,SEQ):
A 256-bit random value.
</dd>
</dl>
- <t>
- Once outgoing and incoming shared secrets are established, actual payload can be exchanged
- bi-directionally using TCP Box messages. FIXME hmac, MtE discussion, padding-oracle, etc
+ <t>
+ The initiating TCP communicator also replies with a TCP handshake acknowledgement packet after receiving
+ a valid TCP handshake packet. Lastly, each party verifies both the signature and the challenge within the received
+ TCP handshake acknowledgement packet, thus completing the handshake. Once the handshake is finished, actual payloads
+ can be exchanged bi-directionally using TCP Box messages. (FIXME: hmac, MtE discussion, padding-oracle, etc).
</t>
</section>
- <section anchor="tcp_key_schedule" numbered="true" toc="default">
- <name>Key schedule</name>
+ <section anchor="tcp_KEM" numbered="true" toc="default">
+ <name>Key exchange</name>
+ <t>
+ During the initial handshake, each communication channel performs an X25519-based KEM, which provides the key material
+ for encrypting packets via AES-CTR and computing MACs via HMAC.
+ </t>
<t>
- This key is used to derive an initial symmetric key which is used to decrypt
- the following data.
- Let MSK be the symmetric key decapsulated from the ephemeral public key with
- the receiving peer's private key.
+ Let G be the basepoint of Curve25519, Ed_To_Curve() a function which converts Ed25519 points to their corresponding
+ Curve25519 points, Enc() Elligator's encoding function, Dec() Elligator's decoding function, REC_ID the receiver's peer
+ identity (a 256-bit EdDSA public key), REC_SK the corresponding secret key, EPH_SK a 256-bit ephemeral secret key and
+ SetupCipher() the HKDF defined in <xref target="setup_cipher_tcp"/>. We can then define the TCP communicator’s key
+ exchange as a KEM:
+ </t>
+ <artwork name="" type="" align="left" alt=""><![CDATA[
+Key_Gen() := (REC_SK, REC_ID)
+Encap(REC_ID) := (REPR, (K,IV,K_mac)) = (Enc(G.EPH_SK, rand), SetupCipher(X25519(EPH_SK, Ed_To_Curve(REC_ID))))
+Decap(REPR) := (K,IV, K_mac) = SetupCipher(X25519(REC_SK, Dec(REPR)))
+ ]]></artwork>
+ <t>
</t>
- <artwork name="" type="" align="left" alt=""><![CDATA[
+ <artwork anchor="setup_cipher_tcp" name="" type="" align="left" alt=""><![CDATA[
SetupCipher(MSK):
PRK_k := HKDF-Extract ("TCP-key", MSK)
K := HKDF-Expand (PRK_k, PEERID, 256 / 8)
@@ -886,9 +959,19 @@ SetupCipher(MSK):
return K,IV,K_mac
]]></artwork>
<t>
- The above K and IV are used to decrypt the following 136 bytes of data
- which are expected to consist of a TCP handshake message as defined in
- <xref target="tcp_handshake"/> below.
+ Note that the initiating TCP communicator can already perform the encapsulation step after generating the ephemeral
+ key pair and immediately encrypt the TCP handshake packet before sending it. As soon as the receiving TCP communicator
+ receives and decodes the ephemeral public key, it can perform the decapsulation step of the KEM and decrypt the
+ following TCP handshake packet. The same applies for the TCP handshake packet send by the receiving TCP communicator.
+ </t>
+ <t>
+ Similarly to the usage of Elligator in the UDP communicator, it's important to note that in the TCP communicator, the
+ exchange of receiver peer identity is not part of the key exchange scope and is assumed to be known to the sending peer.
+ Additionally, the ephemeral public key utilized in the key exchange process, represented as G.EPH_SK, resides on the entire
+ Curve25519, not solely within its prime subgroup. This decision is driven by Elligator's encoding function, which operates
+ across the entire Curve25519. Exclusively using the prime subgroup would limit the potential representatives, allowing an
+ outside observer to easily recognize them. As mentioned beforehand, the usage of peer identities for both Ed25519 signatures
+ and X25519-based KEM is proven to be secure. For more comprehensive information, please refer to the paper [T21].
</t>
</section>
</section>
@@ -973,6 +1056,54 @@ SetupCipher(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 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>
+ 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:
+ REPR := (-X / ((X + A) * U)^(1/2)
+ else:
+ 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(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 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 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>
