Skip to content

Instantly share code, notes, and snippets.

@sipa sipa/covert_ecdh.md
Last active Oct 23, 2019

Embed
What would you like to do?
Covert ECDH over secp256k1

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

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

Inverting the map

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.

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

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

@hkjn

This comment has been minimized.

Copy link

hkjn commented Mar 12, 2018

Cool stuff @sipa!

I'm sure I could be missing something here, but I hadn't heard of Elligator-style encodings before reading this text, and while searching for papers on it I came across Tibouchi's "Elligator Squared" paper:

They mention the restriction that Elligator "cannot be used with prime-order curves" and that their paper "propose[s] an approach to overcome all of these limitations" for the cost that "bit string representation is somewhat less compact (about twice as long as Elligator)".

I can't claim to follow the details, but thought I'd drop the link in case it could be useful!

@earonesty

This comment has been minimized.

Copy link

earonesty commented May 24, 2018

do this about 10 times:

- generate random 33 bytes, converting the first to 0x2 or 0x3 and then call secp256k1_ec_pubkey_parse on the compressed form
- keep the one that succeeds

seems to work ok... depending on your protocol and the security guarantee you need. in our case the only guarantee we need is on a remote observer operating on aggregate sets of thousands of keys ... which is a lot less worrisome than a local unprivileged observer!

@markblundeberg

This comment has been minimized.

Copy link

markblundeberg commented Jan 7, 2019

Nice -- I was looking around to see if a covert ephemeral ECDH was possible and found this. It's unfortunate that such contortions need to be done to get a covert diffie hellman on secp256k1, and I guess that in the end, most protocol designers won't want to use such a scheme. Still, thanks very much for writing it up!

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.