commit b312f75e52503c1c853e319aedb58d322faa0695
parent 276dd76946d5e68323f3ee12f56520e837092ebd
Author: Pedram Fardzadeh <p.fardzadeh@protonmail.com>
Date: Mon, 12 Aug 2024 12:50:16 +0200
spelling error
Diffstat:
1 file changed, 40 insertions(+), 39 deletions(-)
diff --git a/draft-schanzen-hpke-elligator-kem.xml b/draft-schanzen-hpke-elligator-kem.xml
@@ -111,13 +111,13 @@
</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.
+ IETF consensus. It is published here to guide GNS implementers
+ and 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",
+ The keywords "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
@@ -145,30 +145,30 @@
<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,
+ 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 less options, either do nothing or intercept most random-looking packets,
+ 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 this document we define and use an Elligator transformation for X25519 curve points based on the Curve25519 transformations
+ 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).
To create a Curve25519 point that can be used with Elligator, one needs to find a curve point
for which this property holds.
- The general idea when generating a key pair suitable for Elligator is is to create both a random high-order point and a low-order point.
+ When generating a key pair suitable for Elligator, the general idea is to create both a random high-order point and a low-order point.
Adding them together results in a curve point that is evenly distributed on the whole curve.
- One heurisitic is to generate random key pairs until one such point is found:
+ One heuristic is to generate random key pairs until one such point is found:
</t>
<t>
Let <tt>G</tt> be the generator of the prime order group of Ed25519 and <tt>H</tt> the generator of the low order subgroup of
Ed25519.
- <tt>EdToCurve()</tt> is a function which converts Ed25519 points to their corresponding Curve25519 points.
+ <tt>EdToCurve()</tt> is a function that converts Ed25519 points to their corresponding Curve25519 points.
We define "GenerateElligatorKeyPair()" as follows:
</t>
<artwork name="" type="" align="left" alt=""><![CDATA[
@@ -187,7 +187,7 @@
return (skX,pkX)
]]></artwork>
<t>
- The reason why we operate on the Edwards representation for the key generation is that the necessary
+ We operate on the Edwards representation for the key generation because the necessary
low-order point additions are more efficient in most implementations than they would be in their Montgomery form.
A conversion from Edwards to their birationally equivalent Montgomery form is always possible and found in
most cryptographic library implementations.
@@ -197,9 +197,9 @@
<section anchor="elligator_dhkem" numbered="true" toc="default">
<name>Elligator DHKEM</name>
<t>
- The Elligator HPKE DHKEM utilizes Elligator for the encoding and decoding of the ephemeral public keys
+ 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 analoguous to <xref target="RFC9180"/> Section 4.
+ 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>
@@ -220,18 +220,18 @@
<name>SerializePublicKey()</name>
<t>
The serialization functions incorporate the Elligator inverse and direct map functions to obfuscate a curve
- point and are are defined in the following.
+ point, which are defined in the following.
The Elligator literature calls the obfuscated curve point a "representative".
</t>
<t>
Let <tt>A</tt> and <tt>P</tt> be the parameters for Curve25519 as specified in section 4.1 of <xref target="RFC7748"/>.
- Further, let <tt>X</tt> be any valid x-coordinate of a Curve25519 point, <tt>L()</tt> a function which computes the
+ Further, let <tt>X</tt> be any valid x-coordinate of a Curve25519 point, <tt>L()</tt> a function that computes the
Legendre symbol of a field element with regard to the odd prime <tt>P</tt>.
Let <tt>sqrt()</tt> denote the square root operation within the field. As each square number has two roots, we need to
define the notion of positive and negative numbers. There are multiple valid ways to partition the field
elements. For this Elligator, we follow the recommendations of the paper in section 5.1 of <xref target="BHKL13"/> and
choose <tt>{0,..., (P-1)/2}</tt> as the set of positive numbers, and consequently <tt>{(P-1)/2 + 1,...,P-1}</tt> as the
- set of the negative numbers. Both Elligator's inverse and direct map requires us to define a constant non-square number
+ set of the negative numbers. Both Elligator's inverse and direct map require us to define a constant non-square number
of the finite field. Let <tt>U := sqrt(-1)</tt> be this number. The resulting serialization algorithm for the KEM can then be
described as:
</t>
@@ -259,10 +259,10 @@
return pkX
]]></artwork>
<t>
- Note that SerializeElligatorPublicKey(pkX) represent Elligator's inverse map and DeserializeElligatorPublicKey(pkXm) Elligator's
+ Note that SerializeElligatorPublicKey(pkX) represents Elligator's inverse map and DeserializeElligatorPublicKey(pkXm) Elligator's
direct map with a slight modification: The resulting representative of the inverse map 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 by setting those bits back to zero.
+ the most and second most significant bits are always zero, an obvious property an attacker could observe. We avoid this
+ problem by randomly flipping both bits. The target peer will ignore these bits after reception by setting those bits back to zero.
</t>
</section>
</section>
@@ -271,56 +271,57 @@
<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
+ 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
- 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.
+ and verify if this property holds. While this property holds for any valid Curve25519 point, it only holds for a
+ random number in about 50% of the cases. By observing multiple communication attempts, an attacker can be sure 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 (also known as the "inverse map") and decoding function (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
+ 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 need to choose the ephemeral key pair randomly from the whole curve as defined in "GenerateElligatorKeyPair()".
+ this attack, we must randomly choose the ephemeral key pair from the whole curve as defined in "GenerateElligatorKeyPair()".
</t>
<t>
- The intution behind elligator is based on the following idea: The direct map (here DeserializeElligatorPublicKey(r))
+ 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.
One can show the pair of values V_1 := -A / (1 + U * r^2) and V_2 := -A * U * r^2 (1 + U * r^2) always fulfill this property,
based on the fact that U is a non-square number in the field. The direct map first computes V_1 and checks if V_1 fulfills the curve
equation. If it does, it returns V_1; otherwise, V_2 is computed and returned instead. The inverse map,
(here SerializeElligatorPublicKey(V)) reverses this process and computes the corresponding field element of a valid x-coordinate.
- Note that for the purpose of encoding and decoding public keys we reverse the call order of the direct and inverse map: First,
+ Note that for encode and decode public keys, we reverse the call order of the direct and inverse map: First,
the inverse map is called on the ephemeral public key to retrieve the representative r. This representative is then send to the
- receiving peer who calls the direct map to retrieve the corresponding public key.
+ receiving peer, who calls the direct map to retrieve the corresponding public key.
</t>
<t>
Note that both for a value r and its negative counterpart -r (in the finite field), the inverse map 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 GenerateElligatorKeyPair() in order to create a valid public key that can be used
+ different. Conversely, we can't decode both representatives back to their original x-coordinate. This is why the sender
+ eventually tries several random key pairs in GenerateElligatorKeyPair() 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 inverse map 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.
+ which of the two terms is used instead of our random selection. Due to
+ known attacks, 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 cryptosystems.
+ Nevertheless, the desired feature of Elligator is still ensured.
</t>
</section>
<section anchor="security_aead" numbered="true" toc="default">
<name>Combination with AEAD Encryption</name>
<t>
- When using the Elligator KEM in combination with AEAD encryption schemes care must be taken that the
+ When using the Elligator KEM in combination with AEAD encryption schemes, care must be taken to ensure that the
ciphertext produced by the AEAD cipher is also indistinguishable from random.
- The AEAD schemes listed in <xref target="RFC9180"/> use GCM and Poly1305 authentication tags which
- both should result in ciphertexts indistinguishable from random.
- However, future AEAD schemes and in particular their authenticators may not exhibit the same
+ The AEAD schemes listed in <xref target="RFC9180"/> use GCM and Poly1305 authentication tags, which
+ should result in ciphertexts that are indistinguishable from random.
+ However, future AEAD schemes and, in particular, their authenticators may not exhibit the same
cryptographic properties.
This should be considered when assembling HPKE suites with the Elligator KEM.
</t>
@@ -331,7 +332,7 @@
<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 "HPKE KEM Identifiers" registry is requested to be updated with
the values from <xref target="kemid-values"/>.
This section may be removed on publication as an RFC.
</t>
