commit c769e1d37e86470107f139917eb095b6a6339b38
parent 2cd813f016cdb9909fffb94471fa5d69d693a1ff
Author: Pedram Fardzadeh <p.fardzadeh@protonmail.com>
Date: Tue, 6 Aug 2024 07:32:38 +0200
tvg test vector
Diffstat:
1 file changed, 52 insertions(+), 134 deletions(-)
diff --git a/draft-schanzen-hpke-elligator-kem.xml b/draft-schanzen-hpke-elligator-kem.xml
@@ -169,7 +169,7 @@
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:
+ We define "GenerateElligatorKeyPair()" as follows:
</t>
<artwork name="" type="" align="left" alt=""><![CDATA[
GenerateElligatorKeyPair():
@@ -190,9 +190,9 @@
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 equivalent Montgomery form is always possible and found in
- most cryptographic librarly implementations.
+ most cryptographic library implementations.
</t>
- </section>
+ </section>
</section>
<section anchor="elligator_dhkem" numbered="true" toc="default">
<name>Elligator DHKEM</name>
@@ -219,7 +219,7 @@
<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
+ The serialization functions incorporate the Elligator inverse and direct map functions to obfuscate a curve
point and are are defined in the following.
The Elligator literature calls the obfuscated curve point a "representative".
</t>
@@ -227,15 +227,13 @@
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:
+ 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
+ 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>
<artwork name="" type="" align="left" alt=""><![CDATA[
SerializeElligatorPublicKey(pkX):
@@ -243,21 +241,29 @@
pkXm := sqrt(-pkX / ((pkX + A) * U))
else:
pkXm := sqrt(-(pkX + A) / (U * X))
+ if coinFlip() == "heads":
+ pkXm[31] |= 128
+ if coinFlip() == "heads":
+ pkXm[31] |= 64
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):
+ pkXm[31] &= 63
V := -A / (1 + U * pkXm^2)
E := L(V^3 + A * V^2 + V)
pkX := E * V - (1 - E)(A / 2)
return pkX
]]></artwork>
+ <t>
+ Note that SerializeElligatorPublicKey(pkX) represent 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.
+ </t>
</section>
</section>
<section anchor="security" numbered="true" toc="default">
@@ -280,26 +286,32 @@
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".
+ this attack, we need to choose the ephemeral key pair randomly 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))
+ 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,
+ 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.
</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
+ Note that both for a value R and its negative counterpart -R (in the finite field), the inver 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 KeyGenElligator() in order to create a valid public key that can be used
+ eventually tries a number of random key pairs in GenerateElligatorKeyPair() 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
+ 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.
</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 anchor="security_aead" numbered="true" toc="default">
<name>Combination with AEAD Encryption</name>
@@ -415,120 +427,26 @@
<section>
<name>Elligator implementation</name>
<t>
- This section provides test vectors for the different Elligator functions and should aid in verifying implementations.
+ This section provides a test vector for the Elligator KEM 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
+ within the finite field, as described in section 5.1 of <xref target="BHKL13"/>. 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.
+ sqrt(-1). The depicted coin flips are used in the order of the coinFlip() calls in SerializeElligatorPublicKey(pkX), namely
+ coin flip 1 for choosing the pkXm term, coin flip 2 for the MSB and coin flip 3 for the second MSB.
+ 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>
-
+ <name>Elligator KEM:</name>
<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
+ coin flip 1: 0
+ coin flip 2: 1
+ coin flip 3: 1
+ pkEm: 3f73ee0dd1970ff957f7ec15e0b5151166be3046e6a8b0ee53beca395b74e42c
+ skEm: 09395966d6d1c493b9917dd12c8dd24e2c05c081c98a67eb2d6dff622ec9c069
+ skRm: f33887a8562dad5151e9289a0afa1301ccc698917850d56ea409a9949497baa4
+ pkRm: 3febadac122d397725ff580f6ce9a3e1c1c4a7de19807f13d383f2f9b6467136
+ enc: da0f7edaefed18a99f0b73a789e51c4c6e80664190ae3c8ae4e95b9d926a34f7
+ key: 46eff65b5313f41fbaffc7adf98f5df03ab4e4f46ae62a2c7ecbe1f0ae83280b
]]></artwork>
</section>
</section>
