Using Elligator to Hide Key Exchanges

Public keys can be distinguished from random noise in several ways, and Elligator only addresses one of them. To address the others, we must avoid a couple of subtle issues.

Properly hiding a key exchange involves four steps:

1. Choose an ephemeral secret key at random, just like you would for a normal key exchange.
2. Generate a public key from that shared secret with a special procedure, described below.
3. Apply the Elligator 2 inverse map to your public key. If it does not work go back to step (1). Otherwise you get its representative.
4. Serialise the representative into a random-looking byte stream.

Step 1: Choose an ephemeral secret key

The goal is to hide public keys as random noise. It is trivial to detect if you’re sending representatives of the same key twice. Which is why the keys you are trying to hide as random noise must be used only once. Those are called “ephemeral keys”. Ephemeral keys may be used for several exchanges, our only constraint is that they’re sent only once.

Of course, ephemeral secret keys are chosen at random.

Step 2: Generate a “special” public key

Most key exchange algorithms do not work over the whole curve. To avoid leaking information, public keys always belong to the prime order subgroup, which comprises only a fraction of the curve. Eavesdroppers could trivially notice if we only used those, so we need a way to generate points on the whole curve and somehow make key exchange work regardless.

One obvious way to make it work is not to clear the cofactor. This means choosing a base point that generates the whole curve instead of the prime order subgroup, and choosing a uniformly random scalar between zero and the order of the whole curve.

It is more practical, however, to find a way to be compatible with existing key exchange algorithms. This lets us retain the proofs and guarantees of the original key exchange and streamline the APIs. The details depend on the particular key exchange we want to be compatible with. Here we will give an example based on X25519 and X448.

X25519 and X448

These two key exchanges have the same structure:

• They both use a prime field GF(q), whose characteristic is close to a power of two.
• The order of their curve is a big prime number ℓ, multiplied by a small cofactor h (h = 8 for Curve25519, and h = 4 for Curve448).
• They both use a base point G of prime order ℓ.
• They both “clamp” the scalar in the same way.
• They both use an x-only Montgomery ladder, which ignores the sign of the point. That is, they act as if P = (u, v) and −P = (u, −v) were the same point. In practice, this means we can ignore v altogether.

The key exchange itself proceeds as follows:

• Alice generates a key pair (a, A), and sends A to Bob.
• Bob generates a key pair (b, B), and sends B to Alice.
• Alice and Bob compute the shared secret S.

The private keys a and b are random numbers. The rest have the following values (the dot denotes scalar multiplication):

• A = clamp(a) . G
• B = clamp(b) . G
• S = clamp(a) . B = clamp(b) . A

The clamp() operation is defined thus:

clamp(s):
  clamped = s - s % h        # remove low bits
  clamped = clamped % 2^msb  # remove high bits
  clamped = clamped | 2^msb  # set high bit
  return clamped

Where msb = 254 for Curve25519 and msb = 447 for Curve 448. This has two effects:

• It fixes the position of the highest non-zero bit. This mitigates some side channel attacks that may occur with some faulty implementations.

• It clears the lowest bits (3 for Curve25519, 2 for Curve448), so clamp(s) is a multiple of the cofactor h. This avoids leaking information about scalars by ignoring the low order component of points multiplied by a clamped scalar. Every point A is the sum of a prime order point P and a low order point L. Clamping ignores L:

  clamp(s) . A = clamp(s) . (P + L)
  clamp(s) . A = clamp(s) . P + clamp(s) . L
  clamp(s) . A = clamp(s) . P
  

Normal public keys (almost) cover the whole prime order subgroup. To cover the whole curve, we just need to add a random low order point to it. That low-order component will be ignored in key exchanges, yielding the same shared secrets as we would have had with the normal public key.

There are two methods to add a random low order point:

1. Generate a normal public key, then add a random low order point, selected with the clamped bits of the secret key.
2. Use a generator that generates the whole curve (and not just the prime order subgroup), and tweak the scalar to counter the effects of clamping.

Done right, the two methods yield the exact same results.

Method 1: add a random low order point

This method is conceptually simple but it requires generic point addition, which is best done in Edwards space. This means performing the scalar multiplication in Edwards space, adding the low order point, then converting the final results to Montgomery space so Elligator can work.

The main advantage of this method is speed. Generic Edwards addition allow some impressive optimisations. On the other hand, this involves a fair bit of code and sizeable pre-computed tables. This may be a problem on constrained applications that do not already use Edwards code for other purposes, like signatures.

We start with the following:

• The random secret bit string s, freshly generated for a single key exchange (256 bits for Curve25519, 448 bits for curve448).
• the cofactor h of the curve (8 for Curve25519, 4 for Curve448).
• The generator G of the prime order group of the curve (the one used in Ed25519 or Ed448).
• The generator H of the low order group of the curve. It must be of order h. Curve25519 has 4 suitable candidates. Curve448 has 2.

The Edwards point E = (x, y) is generated from a as follows:

• E_high = clamp(s) . G
• E_low = (s mod h) . H
• E = E_high + E_low

Once E = (x, y) is generated, we convert it to the Montgomery point P = (u, v). The conversion formula depends on the curve.

Method 2: use a generator of the whole curve

This method reuses the x-only Montgomery ladder we use for regular key exchanges, and allows very compact code. On the other hand, it is about twice as slow as method 1.

We start with the following:

• The random secret bit string s, freshly generated for a single key exchange (same as method 1).
• the cofactor h of the curve (8 for Curve25519, 4 for Curve448).
• The generator G of the prime order group of the curve. We use the same as method 1.
• The generator H of the low order group of the curve. We use the same as method 1.

We can then pre-compute the special base point K:

• Find m such that m ℓ ≡ 1 (mod h) (m = 5 for X25519, m = 3 for X448)
• K = G + (m . H)

With K hard coded, we can compute the rest entirely in Montgomery space, with a single scalar multiplication:

• s_clamp = clamp(s)
• s_low = (s mod h) ℓ
• P = (s_clamp + s_low) . K

This gives us the exact same point P as method 1.

Curve parameters for methods 1 and 2

Curve25519:

Curve448:

Step 3: Apply the inverse map

Once we have the public key P = (u, ?) we can try and apply the inverse map. To do this we suggest you use our optimised formulas.

Note that not all public keys are eligible for the inverse map, so depending on the value of u this step will fail half the time on average. When it does, just go back to step (1) and generate a new random ephemeral key.

Step 4: Properly serialise the representative

The inverse map only generates non-negative representatives. That is, half of all possible representatives. If we sent that directly over the network, it would be easy for an eavesdropper to notice that one bit is effectively always zero, and suspect our use of Elligator. There are two ways to mitigate this problem:

• We can flip the sign of r at random. That is, half the time, we choose −r instead of r (use constant time selection to do this). This will not affect the direct map when we try to recover the point P because map(r) = map(−r).
• If the bit-string representation of a non-negative representative systematically leaves one of its bits cleared then we can replace it by a random bit instead, which is to be ignored when parsing the bit-string.

Furthermore, we generally send byte-strings over the network. If the length of the bit-string is not a multiple of 8, the remaining bits must be filled with random data for the whole byte string to look random. When parsing the bit-string, these additional random bits must be ignored.

Suggested API design

There are two main routes the API could go: It could be deterministic, or it could call an RNG internally. The former is easier to test while the latter is easier to use. If you can, we suggest that you write a low-level deterministic API that you can thoroughly test, then implement an easy to use high-level API on top of it.

Here’s what a good low level deterministic API might look like:

void generate_public_key(uint8_t       public_key[KEY_SIZE],
                         const uint8_t secret_key[KEY_SIZE]);

int inverse_map(uint8_t       representative[KEY_SIZE],
                const uint8_t public_key    [KEY_SIZE],
                uint8_t       random_tweak);

void direct_map(uint8_t       public_key    [KEY_SIZE],
                const uint8_t representative[KEY_SIZE]);

The first function generates a public key from a secret key. It can be implemented with method 1 or method 2, depending on your use case (method 1 is potentially faster, method 2 potentially requires less code). Implementing both methods and verifying that they behave identically can also be a good test.

The direct and inverse maps behave as expected. Note the added random_tweak for the inverse map, that provides the randomness needed to select the sign of the v-coordinate and properly serialising the representative.

In practice the inverse map is only used with a fresh public key that was generated with the special procedure (method 1 or method 2). On top of that it fails half the time, forcing us to generate a new key pair and try again until it works. It makes sense to provide a higher-level function that handles the whole procedure:

void key_pair_deterministic(uint8_t representative[KEY_SIZE],
                            uint8_t secret_key    [KEY_SIZE],
                            uint8_t random_seed[32]);

The random_seed can be expanded with a stream cipher to provide enough randomness for an unlimited number of retries so that the whole function never fails. And it should be automatically wiped after use, which is why it is not const.

Note that this function does not need to provide the public key itself: the party that generates it will send the representative over the network, then only use the secret_key for key exchanges. Of course, the recipient will need the direct_map() to convert the representative they received and complete their end of the key exchange.

Finally, you can provide one high-level function that gathers the randomness itself:

void key_pair_easy(uint8_t representative[KEY_SIZE],
                   uint8_t secret_key    [KEY_SIZE]);

It could call key_pair_deterministic() under the hood, or use the low level functions directly.

Alternative low-level API

Edwards curves and Ristretto implementations tend to have readily available point addition, which we can leverage to simplify the low-level API. The idea is to use the regular public key generation then add a random low order point in the same function that applies the inverse map.

This effectively removes one function from the low level API:

int inverse_map(uint8_t       representative[KEY_SIZE],
                const uint8_t public_key    [KEY_SIZE],
                uint8_t       random_tweak);

void direct_map(uint8_t       public_key    [KEY_SIZE],
                const uint8_t representative[KEY_SIZE]);

There is one crucial difference however: now the tweak determines the value of the low order component, which influences whether the inverse map succeeds or fails. Make sure you don't reuse the random bits of the tweak in this case.

Though this low-level API may be less error prone than the first, writing a high-level one is still recommended. We suggest you implement key_pair_deterministic() and key_pair_easy() on top of regular public key generation and the inverse_map() above.