commit d65c994790737918340ef38a51ed02e7cae6315b
parent 411556aa19cd9912a2f39da75796f3d75b86ee48
Author: Martin Schanzenbach <schanzen@gnunet.org>
Date: Fri, 19 Jul 2024 16:06:05 +0200
update
Diffstat:
1 file changed, 435 insertions(+), 422 deletions(-)
diff --git a/draft-schanzen-hpke-elligator-kem.xml b/draft-schanzen-hpke-elligator-kem.xml
@@ -46,89 +46,103 @@
submissionType="independent"
xml:lang="en"
version="3">
- <!-- xml2rfc v2v3 conversion 2.26.0 -->
- <front>
- <title abbrev="The HPKE Elligator KEM">
- The HPKE Elligator KEM
- </title>
- <seriesInfo name="Internet-Draft" value="draft-schanzen-hpke-elligator-kem-00"/>
- <author fullname="Martin Schanzenbach" initials="M." surname="Schanzenbach">
- <organization>Fraunhofer AISEC</organization>
- <address>
- <postal>
- <street>Lichtenbergstrasse 11</street>
- <city>Garching</city>
- <code>85748</code>
- <country>DE</country>
- </postal>
- <email>martin.schanzenbach@aisec.fraunhofer.de</email>
- </address>
- </author>
- <author fullname="Pedram Fardzadeh" initials="P." surname="Fardzadeh">
- <organization>Technischen Universität München</organization>
- <address>
- <postal>
- <street>Boltzmannstrasse 3</street>
- <city>Garching</city>
- <code>85748</code>
- <country>DE</country>
- </postal>
- <email>pedram.fardzadeh@tum.de</email>
- </address>
- </author>
+ <!-- xml2rfc v2v3 conversion 2.26.0 -->
+ <front>
+ <title abbrev="The HPKE Elligator KEM">
+ The HPKE Elligator KEM
+ </title>
+ <seriesInfo name="Internet-Draft" value="draft-schanzen-hpke-elligator-kem-00"/>
+ <author fullname="Martin Schanzenbach" initials="M." surname="Schanzenbach">
+ <organization>Fraunhofer AISEC</organization>
+ <address>
+ <postal>
+ <street>Lichtenbergstrasse 11</street>
+ <city>Garching</city>
+ <code>85748</code>
+ <country>DE</country>
+ </postal>
+ <email>martin.schanzenbach@aisec.fraunhofer.de</email>
+ </address>
+ </author>
+ <author fullname="Pedram Fardzadeh" initials="P." surname="Fardzadeh">
+ <organization>Technischen Universität München</organization>
+ <address>
+ <postal>
+ <street>Boltzmannstrasse 3</street>
+ <city>Garching</city>
+ <code>85748</code>
+ <country>DE</country>
+ </postal>
+ <email>pedram.fardzadeh@tum.de</email>
+ </address>
+ </author>
- <!-- Meta-data Declarations -->
- <area>General</area>
- <workgroup>Independent Stream</workgroup>
- <keyword>transport protocols</keyword>
- <abstract>
- <t>
- This document contains the GNUnet communicator
- specification.
- </t>
- <t>
- This document defines the normative wire format of communicator protocols,
- cryptographic routines and security
- considerations for use by implementers.
- </t>
- <t>
- This specification was developed outside the IETF and does not have
- IETF consensus. It is published here to inform readers about the
- function of GNUnet communicators, guide future communicator implementations, and ensure
- interoperability among implementations including with the pre-existing
- GNUnet implementation.
- </t>
- </abstract>
- </front>
- <middle>
- <section anchor="introduction" numbered="true" toc="default">
- <name>Introduction</name>
- <t>
- This document defines the normative wire format of resource
- records, resolution processes, cryptographic routines and
- security considerations for use by implementers.
- </t>
- <t>
- This specification was developed outside the IETF and does not have
- IETF consensus. It is published here to guide implementers of GNS
- and to ensure interoperability among implementations.
- </t>
- <section numbered="true" toc="default">
- <name>Requirements Notation</name>
- <t>
- The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT",
- "SHOULD", "SHOULD NOT", "RECOMMENDED", "NOT RECOMMENDED", "MAY", and
- "OPTIONAL" in this document are to be interpreted as described in
- BCP 14 <xref target="RFC2119"/> <xref target="RFC8174"/> when, and only
- when, they appear in all capitals, as shown here.
- </t>
- </section>
- </section>
- <section anchor="primitives" numbered="true" toc="default">
- <name>Cryptographic dependencies</name>
- <section anchor="elligator_dhkem" numbered="true" toc="default">
- <name>Elligator DHKEM</name>
+ <!-- Meta-data Declarations -->
+ <area>General</area>
+ <workgroup>Independent Stream</workgroup>
+ <keyword>transport protocols</keyword>
+ <abstract>
+ <t>
+ This document contains the GNUnet communicator
+ specification.
+ </t>
+ <t>
+ This document defines the normative wire format of communicator protocols,
+ cryptographic routines and security
+ considerations for use by implementers.
+ </t>
+ <t>
+ This specification was developed outside the IETF and does not have
+ IETF consensus. It is published here to inform readers about the
+ function of GNUnet communicators, guide future communicator implementations, and ensure
+ interoperability among implementations including with the pre-existing
+ GNUnet implementation.
+ </t>
+ </abstract>
+ </front>
+ <middle>
+ <section anchor="introduction" numbered="true" toc="default">
+ <name>Introduction</name>
+ <t>
+ This document defines the normative wire format of resource
+ records, resolution processes, cryptographic routines and
+ security considerations for use by implementers.
+ </t>
+ <t>
+ This specification was developed outside the IETF and does not have
+ IETF consensus. It is published here to guide implementers of GNS
+ and to ensure interoperability among implementations.
+ </t>
+ <section numbered="true" toc="default">
+ <name>Requirements Notation</name>
+ <t>
+ The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT",
+ "SHOULD", "SHOULD NOT", "RECOMMENDED", "NOT RECOMMENDED", "MAY", and
+ "OPTIONAL" in this document are to be interpreted as described in
+ BCP 14 <xref target="RFC2119"/> <xref target="RFC8174"/> when, and only
+ when, they appear in all capitals, as shown here.
+ </t>
+ </section>
+ </section>
+ <section anchor="primitives" numbered="true" toc="default">
+ <name>Cryptographic dependencies</name>
+ <section anchor="elligator" numbered="true" toc="default">
+ <name>Elligator</name>
+ <t>
+ Diffie-Hellman-based KEMs (DHKEMs) allow us to securely establish a secret between two parties.
+ However, an observer can easily identify the exchanged encapsulation in DHKEMs as public keys.
+ In the presence of a passive eavesdropping attacker this could lead to packet dropping based on this information,
+ preventing communication between peers as outlined in <xref target="BHKL13"/>.
+ The presented solution in <xref target="BHKL13"/> is called "Elligator" and allows us to produce random-looking
+ representations of curve points.
+ This leaves an attacker with less options, either do nothing or intercept most random-looking packets,
+ thereby potentially disrupting a large part of today's internet communication.
+ </t>
+ </section>
+ </section>
+ <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.
@@ -138,372 +152,371 @@
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>
- Elligator KEM utilizes Elligator for the encoding and decoding of the ephemeral public keys
- as 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>
<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).
+ Elligator KEM utilizes Elligator for the encoding and decoding of the ephemeral public keys
+ as 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>
<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>.
+ 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).
</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>
- <section anchor="security" numbered="true" toc="default">
- <name>Security and Privacy Considerations</name>
- <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".
+ 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="security" numbered="true" toc="default">
+ <name>Security and Privacy Considerations</name>
+ <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 <xref target="BHKL13"/>, 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 part 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>
<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.
+ TRANSPORT API: GNUNET_TRANSPORT_MessageCompletedCallback, GNUNET_TRANSPORT_communicator_receive, and
+ GNUNET_TRANSPORT_MessageCompletedCallback should follow a generic API for all communicator types.
</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.
+ UDP Communicator: RTT (Round-Trip Time) measurement is missing. Values such as the number of shared secrets could be adapted based on the RTT.
</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.
+ TCP Communicator: Currently, the only sanity check for a valid TCP handshake message is the verification of the signature. Additional checks, such as
+ verifying the sender's peer identity, are needed.
+ 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>
- <section anchor="work_in_progress" numbered="true" toc="default">
- <name>Work in Progress</name>
- <t>
- TRANSPORT API: GNUNET_TRANSPORT_MessageCompletedCallback, GNUNET_TRANSPORT_communicator_receive, and
- GNUNET_TRANSPORT_MessageCompletedCallback should follow a generic API for all communicator types.
- </t>
- <t>
- UDP Communicator: RTT (Round-Trip Time) measurement is missing. Values such as the number of shared secrets could be adapted based on the RTT.
- </t>
- <t>
- TCP Communicator: Currently, the only sanity check for a valid TCP handshake message is the verification of the signature. Additional checks, such as
- verifying the sender's peer identity, are needed.
- 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">
- <name>GANA Considerations</name>
+ <section anchor="gana" numbered="true" toc="default">
+ <name>GANA Considerations</name>
</section>
- <!-- gana -->
+ <!-- gana -->
<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>
+ <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>
- <name>Implementation and Deployment Status</name>
- <t>
+ <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>
+ <name>Implementation and Deployment Status</name>
+ <t>
FIXME
- </t>
- </section>
- <section>
- <name>Acknowledgements</name>
- <t>
- FIXME
- </t>
- </section>-->
- </middle>
- <back>
- <references>
- <name>Normative References</name>
- &RFC2119;
- &RFC5869;
- &RFC7748;
- &RFC8174;
- &RFC9180;
-
- </references>
- <references>
- <name>Informative References</name>
- <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">
- <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> </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
+ </t>
+ </section>
+ <section>
+ <name>Acknowledgements</name>
+ <t>
+ FIXME
+ </t>
+ </section>-->
+ </middle>
+ <back>
+ <references>
+ <name>Normative References</name>
+ &RFC2119;
+ &RFC5869;
+ &RFC7748;
+ &RFC8174;
+ &RFC9180;
- 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>
+ </references>
+ <references>
+ <name>Informative References</name>
+ <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">
+ <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> </references>
+
+
<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
+ <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
- 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
+ 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 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
+ 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
+ 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
+ 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
+ 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>
+ 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>
- </section>
- </back>
+ </back>
</rfc>
