Covert ECDH over secp256k1

covert_ecdh.md

Covert ECDH over secp256k1

If ECDH is used to establish a shared session secret for an encrypted connection, two elliptic curve points need to be transmitted (one in each direction) before encryption starts. In order to avoid being identifiable as a (specific) ECDH negotiation, ideally those two points are sent in a way that is indistinguishable from random.

This problem is easily addressed by using curves that support Elligator-style encodings: functions that encode a (subset of) elliptic curve points as sequences of bytes with no observable bias: (almost) every byte sequence corresponds to exactly one point, and the others correspond to none.

Unfortunately, no Elligator-style encoding is known for secp256k1.

In the rest of this document, another approach is given that is weaker, but sufficient for ECDH. It allows someone to randomly generate EC points (with known discrete logarithm) and encode the result in unbiased bytes. However, it does not work for arbitrary EC points. It will be necessary to generate multiple points until an acceptable encoding is found, and the resulting points being encoded will be slightly biased (by approximately 1 bit). The bytes will be indistinguishable from random however, even for someone who knows about this algorithm.

This is an ugly and complicated approach, and if you need these covertness properties, you're most likely better off choosing a different curve. However if you're somehow stuck with secp256k1, the approach applies.

A function from field elements to EC points

In Indifferentiable Hashing to Barreto-Naehrig Curves, the authors describe three functions

• f₁(s) = (c - 1)/2 - cs/(1 + b + s)
• f₂(s) = (-c - 1)/2 + cs/(1 + b + s)
• f₃(s) = 1 - (1 + b + s)²/(3s)

where c = sqrt(-3), and b the curve parameter in y² = x³ + b which is 7 for secp256k1.

They show that when s is a nonzero square field element (where the field is the integers modulo 2²⁵⁶ - 2³² - 977 for secp256k1), at least one of these functions will produce the x coordinate of a point on the curve.

From this it is possible to define a fuction f(s) as:

• If s is a square, the first of [f₁(s),f₂(s),f₃(s)] which is a valid x coordinate on the curve, and the corresponding y coordinate that is square.
• If s is not a square, the first of [f₁(-s),f₂(-s),f₃(-s)] which is a valid x coordinate on the curve, and the corresponding y coordinate that is not square.

This function maps every nonzero field element to a valid curve point. In total, very close to 9/16 of the curve points are reached, so some are the image of multiple s values.

Inverting the map

The three functions above have simple inverse functions as:

• f₁^-1(x) = (b + 1)(c + 2x + 1)/(c - 2x - 1)
• f₂^-1(x) = (b + 1)(c - 2x - 1)/(c + 2x + 1)
• f₃^-1(x) = c(±(3x² + (4b - 2)x + (1 - 4b))^1/2 - 3x + (1 - 2b))/2

For f₁ and f₂ there is always exactly one s for every x. For f₃ there may be two s values for a given x. This means there may be up to four s values for every x.

Note that only s values which have the same squareness as y are acceptable. Furthermore, the s values that come out of inverting f₂ or f₃ may not map back to the original x value through f(s)—a lower-indexed function may instead give another x.

Overall, we can partition the set of nonzero curve points into 5 sets X₀...X₄, based on the number of s values for which f(s) maps to that point. The sizes of these partitions are very close to 7/16, 7/32, 9/32, 1/32, and 1/32 of the total number of points respectively.

Uniformly mapping x coordinates to s values

We want an algorithm that given an x coordinate (and more generally, a point) either returns nothing, or it returns a uniformly random unbiased s value that maps to that point. Then we can loop and attempt this many times on random points until something is returned.

A naive approach would be to start from an x coordinate, return nothing if x is in X₀, and otherwise randomly pick one of the t values that correspond to that x. This will indeed reach all nonzero field elements, but the t values for x values in X₁ would be reached 7/32 of the time, while those for x values in X₄ only 1/128 of the time.

In order to make things uniform, we need a bias in the choice of x to compensate for the nonuniformity of the inverse of f. When we reject 27/28 of x values in X₁, 17/18 of those in X₂, 1/4 of those in X₃ and none of those in X₄ we get uniformity: 1/128 of x values will be from X₁, 2/128 from X₂, 3/128 from X₃, and 4/128 from X₄.

Overall algorithm

Loop:

• Generate a random point (x,y) on the curve (with known discrete logarithm).
• Compute the set S as the values s that come out of f₁^-1(x), f₂^-1(x), and f₃^-1(x) that are squares and for which f(s) = x.
• If S is empty: continue
• Generate a random integer r in [0..251] (252 possibilities)
• If S has size 1 and r≥9: continue
• If S has size 2 and r≥14: continue
• If S has size 3 and r≥189: continue
• Pick s = S[r mod n]
• If y is a square, return s; otherwise, return -s.

Overall, 10/128 of the iterations a result will be returned. This means that on average 12.8 iterations of the loop will be necessary.