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.
In Indifferentiable Hashing to Barreto-Naehrig Curves, the authors describe three functions
- f1(s) = (c - 1)/2 - cs/(1 + b + s)
- f2(s) = (-c - 1)/2 + cs/(1 + b + s)
- f3(s) = 1 - (1 + b + s)2/(3s)
where c = sqrt(-3), and b the curve parameter in y2 = x3 + b which is 7 for secp256k1.
They show that when s is a nonzero square field element (where the field is the integers modulo 2256 - 232 - 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 [f1(s),f2(s),f3(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 [f1(-s),f2(-s),f3(-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.
The three functions above have simple inverse functions as:
- f1-1(x) = (b + 1)(c + 2x + 1)/(c - 2x - 1)
- f2-1(x) = (b + 1)(c - 2x - 1)/(c + 2x + 1)
- f3-1(x) = c(±(3x2 + (4b - 2)x + (1 - 4b))1/2 - 3x + (1 - 2b))/2
For f1 and f2 there is always exactly one s for every x. For f3 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 f2 or f3 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 X0...X4, 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.
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 X0, 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 X1 would be reached 7/32 of the time, while those for x values in X4 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 X1, 17/18 of those in X2, 1/4 of those in X3 and none of those in X4 we get uniformity: 1/128 of x values will be from X1, 2/128 from X2, 3/128 from X3, and 4/128 from X4.
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 f1-1(x), f2-1(x), and f3-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.