commit dba8e77640c7c7fda541c2139ff0401545a9db99
parent 2f150acd715d4f655875e61dd90fdceaa927f8cb
Author: Martin Schanzenbach <schanzen@gnunet.org>
Date: Sat, 27 Jul 2024 12:24:40 +0200
cleanup; reference LSD0011
Diffstat:
1 file changed, 26 insertions(+), 313 deletions(-)
diff --git a/draft-gnunet-communicators.xml b/draft-gnunet-communicators.xml
@@ -222,105 +222,24 @@
</section>
<section anchor="primitives" numbered="true" toc="default">
<name>Cryptographic dependencies</name>
- <t>
- GNUnet communicators utilize Elligator for the encoding and decoding of the ephemeral public keys
- described in Section 5 of <xref target="BHKL13"/>.
- The general idea when generating an Elligator key pair is 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 suitable for use with Elligator.
- In particular, not all Curve25519 points have the property that the Elligator encoding and subsequent
- decoding result in the original point (See <xref target="security_elligator"/> for details).
- To create a Curve25519 point that can be used with Elligator, one needs to find a curve point
- for which this property holds.
- One heurisitic is to generate random key pairs until one such point is found.
- </t>
<section anchor="elligator_dhkem" numbered="true" toc="default">
<name>Elligator DHKEM</name>
<t>
- While standard Diffie-Hellman-based KEMs securely establish a secret between two parties, an observer can easily identify
- the encapsulation as a public key.
+ GNUnet communicators utilize en Elligator KEM for the encoding and decoding
+ the ephemeral public keys.
+ While standard Diffie-Hellman-based KEMs securely establish a secret between
+ two parties, an observer can easily identify the encapsulation as a public key.
In the presence of an active attacker this could lead to packet dropping based on this information,
preventing communication between peers.
- The UDP and TCP communicators use the Elligator KEM defined in the following to produce random-looking
- encapsulations (referred to as a "representative").
+ The UDP and TCP communicators use the Elligator KEM defined in
+ <xref target="LSD0011"/>.
This leaves the attacker with the option to either do nothing or intercept all random-looking packets,
thereby potentially disrupting a large part of today's internet communication.
</t>
<t>
- We define our KEMs analoguous to <xref target="RFC9180"/> Section 4.
- The <tt>kem_id</tt> in the <tt>suite_id</tt> for the Elligator KEM is <tt>256</tt> (NOTE: This value is not registered in IANA yet).
+ We use the KEMs and their notations as defined in <xref target="RFC9180"/> and
+ <xref target="LSD0011"/>.
</t>
- <t>
- The value of <tt>suite_id</tt> depends on the KEM used. The <tt>ExtractAndExpand()</tt>, <tt>Encap()</tt>
- and <tt>Decap()</tt> functions are used as defined in <xref target="RFC9180"/> for standard DHKEMs.
- The communicators use the standard <tt>DHKEM(X25519, HKDF-SHA256)</tt> and a special Elligator-based KEM
- defined below which we call <tt>DHKEM(X25519Elligator, HKDF-SHA256)</tt>.
- </t>
- <section anchor="elligator_dhkem_keygen" numbered="true" toc="default">
- <name>GenerateKeyPair()</name>
- <t>
- Let G be 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.
- We define "KeyGenElligator" as follows:
- </t>
-<artwork name="" type="" align="left" alt=""><![CDATA[
-GenerateKeyPair():
- VALID := 0
- while(!VALID):
- skX := random(256)
- skX[0] &= 248
- skX[31] &= 127
- skX[31] |= 64
- E_high := skX * G
- E_low := (skX mod 8) * H
- E := E_high + E_low
- pkX := EdToCurve(E)
- if ElligatorDec(ElligatorEnc(pkX)) == pkX:
- return (skX,pkX)
- ]]></artwork>
- </section>
- <section anchor="elligator_dhkem_serialize" numbered="true" toc="default">
- <name>SerializePublicKey()</name>
- <t>
- The serialization functions incorporate the Elligator encoding and decoding functions to obfuscate a curve
- point and are are defined in the following.
- The obfuscated curve point is called the Elligator "Representative".
- Let A and P be the parameters for Curve25519 as specified in section 4.1 of <xref target="RFC7748"/>.
- Further, let X be any valid x-coordinate of a Curve25519 point, L() a function which computes the legendre symbol
- of a field element with regard to the odd prime P.
- In order for the square root operation sqrt within the encoding function to work deterministically, we need to
- define the notion of positive and negative numbers within the field. There are multiple valid ways to partition
- the field elements, but a common choice is to define the set {0,..., (P-1)/2} as the set of positive numbers,
- and {(P-1)/2 + 1,…,P−1} as the set of the negative numbers. The encoding function also requires a non-square number
- U of the finite field. While U could be chosen arbitrarily, small numbers like sqrt(-1) are preferred due to reduce
- computation.
- The elligator implementations of both peers <bcp14>MUST</bcp14>
- use the same definition regarding positive and negative numbers and U to be interoperable.
- The encoding function algorithm is:
- </t>
-<artwork name="" type="" align="left" alt=""><![CDATA[
-SerializeElligatorPublicKey(pkX):
- B := random(1)
- if B == 1:
- pkXm := sqrt(-X / ((X + A) * U))
- else:
- pkXm := sqrt(-(X + A) / (U * X))
- return pkXm
-]]></artwork>
- </section>
- <section anchor="elligator_dhkem_deserialize" numbered="true" toc="default">
- <name>DeserializePublicKey()</name>
- <t>
- The corresponding decoding agorithm is:
- </t>
- <artwork name="" type="" align="left" alt=""><![CDATA[
-DeserializeElligatorPublicKey(pkXm):
- V := -A / (1 + U * R^2)
- E := L(V^3 + A * V^2 + V)
- pkX := E * V - (1 - E)(A / 2)
- return pkX
- ]]></artwork>
- </section>
</section>
<section anchor="key_derivation" numbered="true" toc="default">
<name>Key derivation</name>
@@ -529,7 +448,7 @@ DeserializeElligatorPublicKey(pkXm):
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
- GANA "GNUnet Signature Purpose" registry <xref target="gana"/>.
+ GANA "GNUnet Signature Purpose" registry <xref target="GANA"/>.
</dd>
<dt>SENDER PEER ID</dt>
<dd>
@@ -832,7 +751,7 @@ DeriveKID(MSK,SEQ):
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
- GANA "GNUnet Signature Purpose" registry <xref target="gana"/>.
+ GANA "GNUnet Signature Purpose" registry <xref target="GANA"/>.
</dd>
<dt>SENDER PEER ID</dt>
<dd>
@@ -976,7 +895,7 @@ DeriveKID(MSK,SEQ):
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
- GANA "GNUnet Signature Purpose" registry <xref target="gana"/>.
+ GANA "GNUnet Signature Purpose" registry <xref target="GANA"/>.
</dd>
<dt>SENDER PEER ID</dt>
<dd>
@@ -1373,7 +1292,7 @@ SetupCipher(REC_ID, MSK):
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
- GANA "GNUnet Signature Purpose" registry <xref target="gana"/>.
+ GANA "GNUnet Signature Purpose" registry <xref target="GANA"/>.
</dd>
<dt>SENDER PEER ID</dt>
<dd>
@@ -1465,7 +1384,7 @@ SetupCipher(REC_ID, MSK):
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
- GANA "GNUnet Signature Purpose" registry <xref target="gana"/>.
+ GANA "GNUnet Signature Purpose" registry <xref target="GANA"/>.
</dd>
<dt>EXPIRATION</dt>
<dd>
@@ -1487,45 +1406,6 @@ SetupCipher(REC_ID, MSK):
This use of a KEM and its safety has been investigated by <xref target="T21"/>.
</t>
</section>
- <section anchor="security_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.
- The Elligator encoding function "ElligatorEnc" (also known as the "inverse map") and decoding function "ElligatorDec" (also known as the "direct map") implement this feature.
- </t>
- <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 as defined in "KeyGenElligator".
- </t>
- <t>
- Note that both for a value R and its negative counterpart -R (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 tries a number of random key pairs 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>
<section anchor="work_in_progress" numbered="true" toc="default">
<name>Work in Progress</name>
@@ -1542,47 +1422,13 @@ SetupCipher(REC_ID, MSK):
The use of the mac-then-encrypt approach within the TCP BOX messages should be analyzed further, specifically regarding padding-oracle attacks.
</t>
</section>
- <section anchor="gana" numbered="true" toc="default">
+ <!-- <section anchor="gana" numbered="true" toc="default">
<name>GANA Considerations</name>
- </section>
+ </section>-->
<!-- gana -->
- <section>
+ <!--<section>
<name>IANA Considerations</name>
- <t>
- This document defines a new KEM as allowed in <xref target="RFC9180"/>.
- It is requested that the "HPKE KEM Identifiers" registry is updated with
- the values from <xref target="kemid-values"/>.
- This section may be removed on publication as an RFC.
- </t>
- <table anchor="kemid-values" align="center" pn="table-2">
- <name slugifiedName="name-kem-ids">KEM IDs</name>
- <thead>
- <tr>
- <th align="left" colspan="1" rowspan="1">Value</th>
- <th align="left" colspan="1" rowspan="1">KEM</th>
- <th align="left" colspan="1" rowspan="1">Nsecret</th>
- <th align="left" colspan="1" rowspan="1">Nenc</th>
- <th align="left" colspan="1" rowspan="1">Npk</th>
- <th align="left" colspan="1" rowspan="1">Nsk</th>
- <th align="left" colspan="1" rowspan="1">Auth</th>
- <th align="left" colspan="1" rowspan="1">Reference</th>
- </tr>
- </thead>
- <tbody>
- <tr>
- <td align="left" colspan="1" rowspan="1">0x0120</td>
- <td align="left" colspan="1" rowspan="1">DHKEM(X25519Elligator, HKDF-SHA256)</td>
- <td align="left" colspan="1" rowspan="1">32</td>
- <td align="left" colspan="1" rowspan="1">32</td>
- <td align="left" colspan="1" rowspan="1">32</td>
- <td align="left" colspan="1" rowspan="1">32</td>
- <td align="left" colspan="1" rowspan="1">yes</td>
- <td align="left" colspan="1" rowspan="1">
- <xref target="LSD0007"/></td>
- </tr>
- </tbody>
- </table>
- </section>
+ </section>-->
<!-- <section>
<name>Implementation and Deployment Status</name>
<t>
@@ -1620,160 +1466,27 @@ SetupCipher(REC_ID, MSK):
<date month="April" year="2021" />
</front>
</reference>
- <reference anchor="BHKL13" target="https://eprint.iacr.org/2013/325.pdf">
- <front>
- <title>Elligator: Elliptic-curve points indistinguishable from uniform random strings</title>
- <author initials="D.J" surname="Bernstein"
- fullname="Daniel J. Bernstein">
- </author>
- <author initials="M." surname="Hamburg"
- fullname="Mike Hamburg">
- </author>
- <author initials="A." surname="Krasnova"
- fullname="Anna Krasnova">
- </author>
- <author initials="T." surname="Lange"
- fullname="Tanja Lange">
- </author>
- <date month="August" year="2013" />
- </front>
- </reference>
- <reference anchor="LSD0007" target="https://lsd.gnunet.org/lsd0007">
+ <reference anchor="LSD0011" target="https://lsd.gnunet.org/lsd0011">
<front>
<title>The GNUnet communicators</title>
<author initials="M" surname="Schanzenbach"
fullname="Martin Schanzenbach">
</author>
- <author initials="C." surname="Grothoff"
- fullname="Christian Grothoff">
- </author>
<author initials="P." surname="Fardzadeh"
fullname="Pedram Fardzadeh">
</author>
<date month="July" year="2024" />
</front>
+ </reference>
+ <reference anchor="GANA" target="https://gana.gnunet.org">
+ <front>
+ <title>The GNUnet communicators</title>
+ <author fullname="GNUnet e.V.">
+ </author>
+ <date month="July" year="2024" />
+ </front>
</reference> </references>
- <section>
- <name>Elligator implementation</name>
- <t>
- This section provides test vectors for the different Elligator functions and should aid in verifying implementations.
- Note that Elligator has two parameters: the set of positive and negative numbers, and a non-square number U
- within the finite field, as described in FIXME. The displayed test vectors assume that the set of positive
- numbers is defined as {0,...,(P-1)/2}, the set of negative numbers as {(P-1)/2 + 1,...,P−1} and U is the non-square number
- sqrt(-1). Unless indicated otherwise, the test vectors are provided as little-endian hexadecimal byte arrays.
- </t>
- <section>
- <name>ElligatorEnc():</name>
- <artwork name="" type="" align="left" alt=""><![CDATA[
- Ephemeral public key (little-endian):
- 99 9b 59 1b 66 97 d0 74
- f2 66 19 22 77 d5 54 de
- c3 c2 4c 2e f6 10 81 01
- f6 3d 94 f7 ff f3 a0 13
-
- Representative (little-endian):
- 99 9b 59 1b 66 97 d0 74
- f2 66 19 22 77 d5 54 de
- c3 c2 4c 2e f6 10 81 01
- f6 3d 94 f7 ff f3 a0 13
- ]]></artwork>
- </section>
- <section>
- <name>ElligatorDec():</name>
- <t>
- The Most Significant Bit (MSB) and the second MSB of the representative should be randomly flipped (serialized) before
- transmission. The resulting public key for both the original (unserialized) representative and the serialized representative
- must be the same.
- </t>
- <artwork name="" type="" align="left" alt=""><![CDATA[
- Representative unserialized (little-endian):
- 95 a1 60 19 04 1d be fe
- d9 83 20 48 ed e1 19 28
- d9 03 65 f2 4a 38 aa 7a
- ef 1b 97 e2 39 54 10 1b
-
- Representative serialized (little-endian):
- 95 a1 60 19 04 1d be fe
- d9 83 20 48 ed e1 19 28
- d9 03 65 f2 4a 38 aa 7a
- ef 1b 97 e2 39 54 10 9b
-
- Ephemeral public key (little-endian):
- 79 4f 05 ba 3e 3a 72 95
- 80 22 46 8c 88 98 1e 0b
- e5 78 2b e1 e1 14 5c e2
- c3 c6 fd e1 6d ed 53 63
- ]]></artwork>
- </section>
- <section>
- <name>Encap():</name>
- <t>
- Refer to <xref target="elligator_dhkem"/> for the definition of the utilized Encap and Decap functions. Note
- that the receivers public key (aka peer identity) is an Edwards Curve point and need to be transformed
- into an X25519 public key. The denoted Representative is the elligator encoding of the ephemeral
- public key for which the most significant bit and second most significant bit are set to zero (unserialized).
- </t>
-
- <artwork name="" type="" align="left" alt=""><![CDATA[
- Receivers Edwards public key (little-endian):
- 3f eb ad ac 12 2d 39 77
- 25 ff 58 0f 6c e9 a3 e1
- c1 c4 a7 de 19 80 7f 13
- d3 83 f2 f9 b6 46 71 36
-
- Ephemeral private key sender (little-endian):
- 09 39 59 66 d6 d1 c4 93
- b9 91 7d d1 2c 8d d2 4e
- 2c 05 c0 81 c9 8a 67 eb
- 2d 6d ff 62 2e c9 c0 69
-
- Ephemeral public key sender (little-endian):
- 3f 73 ee 0d d1 97 0f f9
- 57 f7 ec 15 e0 b5 15 11
- 66 be 30 46 e6 a8 b0 ee
- 53 be ca 39 5b 74 e4 2c
-
- Representative (little-endian):
- 1d 93 07 7a b5 e9 ae c4
- 93 1a 92 21 ad fa 48 a4
- 6f 40 1b 69 9b 8e e7 44
- a2 0b 07 e5 7e 5c c5 be
-
- Key Material (little-endian):
- 68 6d 3c e6 08 a6 b8 77
- 42 4b a2 fb 71 b1 03 f2
- c0 d4 f7 ab e5 f1 e5 2b
- 30 97 a8 4a 71 4a c7 7b
- ]]></artwork>
- </section>
- <section>
- <name>Decap():</name>
- <t>
- The depicted "receivers edwards private key" is the corresponding private key of the "receivers Edwards public key"
- defined above. The resulting key material should therefore be the same for the same Representative.
- </t>
- <artwork name="" type="" align="left" alt=""><![CDATA[
- Receivers Edwards private key (little-endian):
- f3 38 87 a8 56 2d ad 51
- 51 e9 28 9a 0a fa 13 01
- cc c6 98 91 78 50 d5 6e
- a4 09 a9 94 94 97 ba a4
-
- Representative (little-endian):
- 1d 93 07 7a b5 e9 ae c4
- 93 1a 92 21 ad fa 48 a4
- 6f 40 1b 69 9b 8e e7 44
- a2 0b 07 e5 7e 5c c5 be
-
- Key Material (little-endian):
- 68 6d 3c e6 08 a6 b8 77
- 42 4b a2 fb 71 b1 03 f2
- c0 d4 f7 ab e5 f1 e5 2b
- 30 97 a8 4a 71 4a c7 7b
- ]]></artwork>
- </section>
- </section>
</back>
</rfc>
