commit 529af424ea18a0c6fd4faf58adb0b2b6d22f0db0
parent 2546015ffee2d100ab481ddf9af042ee94ff3e3a
Author: Martin Schanzenbach <schanzen@gnunet.org>
Date: Wed, 16 Apr 2025 14:13:25 +0200
remove dependencies again
Diffstat:
1 file changed, 38 insertions(+), 44 deletions(-)
diff --git a/draft-schanzen-hpke-elligator-kem.xml b/draft-schanzen-hpke-elligator-kem.xml
@@ -104,6 +104,16 @@
<section anchor="introduction" numbered="true" toc="default">
<name>Introduction</name>
<t>
+ Diffie-Hellman-based KEMs (DHKEMs) allow us to securely establish a secret between two parties.
+ However, an observer can quickly identify the exchanged encapsulation in DHKEMs as public keys.
+ In the presence of a passive eavesdropping attacker, packets could drop 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 fewer options: either do nothing or intercept most random-looking packets,
+ thereby potentially disrupting a large part of today's internet communication.
+ </t>
+ <t>
In the case of Montgomery curves, such as Curve25519, a point [X, Y] on that curve (e.g., the ephemeral public key) follows the equation
<tt>Y^2 = X^3 + A * X^2 + X mod P</tt>, 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
@@ -114,7 +124,8 @@
The Elligator encoding function (also known as the "inverse map") and decoding function (also known as the "direct map") implement this feature.
</t>
<t>
- This document defines an Elligator Key Encapsulation Mechanims (KEM) for use
+ In this document, we define and use an Elligator transformation for X25519 curve points based on the Curve25519 transformations
+ in <xref target="BHKL13"/> to be used in a Key Encapsulation Mechanim (KEM) for use
in HPKE <xref target="RFC9180"/>
and its security considerations for use by implementers.
</t>
@@ -148,23 +159,23 @@
returned with a likelihood of 50%.
</dd>
</dl> </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 quickly identify the exchanged encapsulation in DHKEMs as public keys.
- In the presence of a passive eavesdropping attacker, packets could drop 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 fewer options: either do nothing or intercept most random-looking packets,
- thereby potentially disrupting a large part of today's internet communication.
- </t>
+ <section anchor="elligator_dhkem" numbered="true" toc="default">
+ <name>Elligator DHKEM</name>
+ <t>
+ The Elligator HPKE DHKEM utilizes Elligator to encode and decode the ephemeral public keys
+ as described in Section 5 of <xref target="BHKL13"/>.
+ We define our KEM analogous to <xref target="RFC9180"/> Section 4.
+ The <tt>kem_id</tt> in the <tt>suite_id</tt> for the Elligator KEM is <tt>TBD</tt>
+ </t>
+ <t>
+ The <tt>ExtractAndExpand()</tt>, <tt>Encap()</tt>
+ and <tt>Decap()</tt> functions (and their authenticated variants) can remain unchanged and <bcp14>MUST</bcp14> be
+ implemented as defined in Section 4.1 of <xref target="RFC9180"/>.
+ The serialization functions <tt>SerializePublicKey</tt> and <tt>DeserializePublicKey</tt> are defined in the following for Curve25519.
+ </t>
+ <section anchor="elligator_dhkem_keygen" numbered="true" toc="default">
+ <name>GenerateKeyPair()</name>
<t>
- In this document, we define and use an Elligator transformation for X25519 curve points based on the Curve25519 transformations
- in <xref target="BHKL13"/>.
First, not all X25519 key pairs are suitable candidates for 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).
@@ -201,28 +212,11 @@
A conversion from Edwards to their birationally equivalent Montgomery form is always possible and found in
most cryptographic library implementations.
</t>
- </section>
- </section>
- <section anchor="elligator_dhkem" numbered="true" toc="default">
- <name>Elligator DHKEM</name>
- <t>
- The Elligator HPKE DHKEM utilizes Elligator to encode and decode the ephemeral public keys
- as described in Section 5 of <xref target="BHKL13"/>.
- We define our KEM analogous to <xref target="RFC9180"/> Section 4.
- The <tt>kem_id</tt> in the <tt>suite_id</tt> for the Elligator KEM is <tt>TBD</tt>
- </t>
- <t>
- The <tt>ExtractAndExpand()</tt>, <tt>Encap()</tt>
- and <tt>Decap()</tt> functions (and their authenticated variants) can remain unchanged and <bcp14>MUST</bcp14> be
- implemented as defined in Section 4.1 of <xref target="RFC9180"/>.
- </t>
- <section anchor="elligator_dhkem_keygen" numbered="true" toc="default">
- <name>GenerateKeyPair()</name>
<t>
The <tt>GenerateKeyPair</tt> algorithm <bcp14>MUST</bcp14> be implemented to produce a key pair suitable for
Elligator.
- The <tt>GenerateElligatorKeyPair()</tt> algorithm from <xref target="elligator"/> <bcp14>MAY</bcp14>
- be used.
+ The <tt>GenerateElligatorKeyPair()</tt> algorithm defined here is <bcp14>RECOMMENDED</bcp14>.
+ Other, more efficient key generation algorithms <bcp14>MAY</bcp14> be used.
</t>
</section>
<section anchor="elligator_dhkem_serialize" numbered="true" toc="default">
@@ -286,14 +280,14 @@
<name>Security and Privacy Considerations</name>
<section anchor="security_elligator" numbered="true" toc="default">
<name>Elligator</name>
- <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. Those attacks are not an
- issue in our case 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 when 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 must randomly choose the ephemeral key pair from the whole curve as defined in "GenerateElligatorKeyPair()".
- </t>
+ <t>
+ 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. Those attacks are not an
+ issue in our case 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 when 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 must randomly choose the ephemeral key pair from the whole curve as defined in "GenerateElligatorKeyPair()".
+ </t>
<t>
The intuition behind elligator is based on the following idea: The direct map (here DeserializeElligatorPublicKey(r))
expects a random field element r. The value r is mapped to two values, for which only one coordinate is a valid Curve25519 x-coordinate.
