commit afdb4e94f857633ff12ec503ef2c1ab4da955c94
parent d65c994790737918340ef38a51ed02e7cae6315b
Author: Martin Schanzenbach <schanzen@gnunet.org>
Date: Fri, 19 Jul 2024 16:56:08 +0200
update
Diffstat:
1 file changed, 81 insertions(+), 83 deletions(-)
diff --git a/draft-schanzen-hpke-elligator-kem.xml b/draft-schanzen-hpke-elligator-kem.xml
@@ -125,6 +125,16 @@
</t>
</section>
</section>
+ <section anchor="notation" numbered="true" toc="default">
+ <name>Notation</name>
+ <t>
+ We use the notation and terminology of <xref target="RFC9180"/> throughout this document.
+ In addition we define the following:
+ </t>
+ <dl>
+ <dt>one</dt><dd>two</dd>
+ </dl>
+ </section>
<section anchor="primitives" numbered="true" toc="default">
<name>Cryptographic dependencies</name>
<section anchor="elligator" numbered="true" toc="default">
@@ -139,90 +149,96 @@
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>
+ <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).
+ 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.
+ 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:
+ </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.
+ We define "KeyGenElligator" as follows:
+ </t>
+ <artwork name="" type="" align="left" alt=""><![CDATA[
+ GenerateElligatorKeyPair():
+ VALID := 0
+ while(!VALID):
+ skX := random(Nsk)
+ skX[0] &= 24
+ 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>
+ <t>
+ The reason why we operate on the Edwards representation for the key generation is that 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 equivalen Montgomery form is always possible and found in
+ most cryptographic librarly implementations.
+ </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.
- In the presence of an active attacker this could lead to packet dropping based on this information,
- preventing communication between peers.
- The Elligator KEM defined in the following to produce random-looking encapsulations (referred to as a "representative").
- 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
+ The Elligator HPKE DHKEM 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.
+ We define our KEM analoguous 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>
- 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>
- <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>.
+ 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>
- 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:
+ 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.
</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:
+ 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
+ Legendre symbol of a field element with regard to the odd prime <tt>P</tt>.
+ Let <tt>sqrt()</tt> be a square root operation which in order 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.
+ For this Elligator <tt>{0,..., (P-1)/2}</tt> is set of positive numbers,
+ and <tt>{(P-1)/2 + 1,...,P-1}</tt> the set of the negative numbers.
+ The Elligator encoding requires us to define a constant non-square number of the finite field.
+ Let <tt>U := sqrt(-1)</tt> be this number as it reduces computation (citation needed).
+ The resulting serialization algorithm for the KEM can then be described as:
</t>
<artwork name="" type="" align="left" alt=""><![CDATA[
SerializeElligatorPublicKey(pkX):
- B := random(1)
- if B == 1:
- pkXm := sqrt(-X / ((X + A) * U))
+ if coinFlip() == "heads":
+ pkXm := sqrt(-pkX / ((pkX + A) * U))
else:
- pkXm := sqrt(-(X + A) / (U * X))
+ pkXm := sqrt(-(pkX + A) / (U * X))
return pkXm
]]></artwork>
</section>
@@ -233,7 +249,7 @@
</t>
<artwork name="" type="" align="left" alt=""><![CDATA[
DeserializeElligatorPublicKey(pkXm):
- V := -A / (1 + U * R^2)
+ V := -A / (1 + U * pkXm^2)
E := L(V^3 + A * V^2 + V)
pkX := E * V - (1 - E)(A / 2)
return pkX
@@ -246,13 +262,13 @@
<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
+ <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.
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.
+ 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
@@ -282,24 +298,6 @@
</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>
<!-- gana -->
<section>
<name>IANA Considerations</name>
