The HPKE Elligator KEM

3.1. Elligator

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 [BHKL13]. The presented solution in [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.¶

In this document, we define and use an Elligator transformation for X25519 curve points based on the Curve25519 transformations in [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 Section 5.1 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. 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 heuristic is to generate random key pairs until one such point is found:¶

Let G be the generator of the prime order group of Ed25519 and H the generator of the low order subgroup of Ed25519. EdToCurve() is a function that converts Ed25519 points to their corresponding Curve25519 points. We define "GenerateElligatorKeyPair()" as follows:¶

      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)

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.¶

4.1. GenerateKeyPair()

The GenerateKeyPair algorithm MUST be implemented to produce a key pair suitable for Elligator. The GenerateElligatorKeyPair() algorithm from Section 3.1 MAY be used.¶

4.2. SerializePublicKey()

The serialization functions incorporate the Elligator inverse and direct map functions to obfuscate a curve point, which are defined in the following. The Elligator literature calls the obfuscated curve point a "representative".¶

Let A and P be the parameters for Curve25519 as specified in section 4.1 of [RFC7748]. Further, let X be any valid x-coordinate of a Curve25519 point, L() a function that computes the Legendre symbol of a field element with regard to the odd prime P. Let sqrt() 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 [BHKL13] and choose {0,..., (P-1)/2} as the set of positive numbers, and consequently {(P-1)/2 + 1,...,P-1} as the 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 U := sqrt(-1) be this number. The resulting serialization algorithm for the KEM can then be described as:¶

      SerializeElligatorPublicKey(pkX):
        if coinFlip() == 1:
          pkXm :=  sqrt(-pkX / ((pkX + A) * U))
        else:
          pkXm :=  sqrt(-(pkX + A) / (U * X))
        if coinFlip() == 1:
          pkXm[31] |= 128
        if coinFlip() == 1:
          pkXm[31] |= 64
        return pkXm

4.3. DeserializePublicKey()

      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

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 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.¶

5.1. Elligator

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 Y^2 = X^3 + A * X^2 + X mod P, where A and P are parameters for Curve25519 specified in Section 4.1 of [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 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.¶

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()".¶

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 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.¶

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, 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.¶

In [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. 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.¶

5.2. Combination with AEAD Encryption

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 [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.¶