Are curve secp256k1 ECDSA signatures distinguishable from random data?

Question

Are the 64-byte curve secp256k1 ECDSA signatures distinguishable from random data?

I.e. Given a random private key and random data, will there be patterns?

Is there a proof or reasoning for this?

Answer 1

We know that the standard encoding of points of an elliptic curve is not uniformly random since they must satisfy the curve equation. In another look, we don't have $2*p^2$ points, and if we consider the curve and it's quadratic twist ($p>3$) then their total number of points is $2p+2$ which is way lower than possible.

In ECDSA, the $r$ is calculated as $r = x_1 \bmod n$ where $x_1 = x([k]G)$. Therefore the $r$ is not uniform random. Since we have $n \approx p$^‡ ( by Hasse's theorem $|n - (p+1)| \le 2 \sqrt{p}$), then we can consider that $r = x_1$ and use the curve equation to see that $r$ satisfies the curve equation or not. If satisfied then it is distinguished.

The $s$ on the other hand is uniform random if the private key $d_A$ and random $k$ are selected uniformly randomly.

Bonus :

• For the prime curves, like secp256k, one should use Elligator Squared as pointed out our Mehdi Tibouchi as the writer of the paper.

• For the curves with non-trivial 2-torsion, like Curve25519, Curve448 you can use Elligator This is the core of the paper. See on more on elligator.org

With this work, the suitable curves, and the points are indistinguishable from uniform random strings and make $r$ as uniform random.

---

_{^‡ For Secp256k1 $p-n = 432420386565659656852420866390673177326$, currently tested 1000000 random points on the curve and in all $r =x_1$. Looking for existence.}

1 . One example is found with random range in (n,p-1)$$\small{(115792089237316195423570985008687907853210556320040394375440737845891899649421 : 7121023256299234636881590140965649586172043956329380565516515841646015336371 )}$$

Answer 2

Reformulating slightly¹:

Can we distinguish from 64-byte of random data an ECDSA signature (without ASN.1 formatting) for curve secp256k1, unknown random key pair and message?

Yes, with excellent advantage.

For a valid signature with private key $d$, the first 32 bytes code (per big-endian convention) an integer $r=x\bmod n$ where $x$ is the X coordinate of a point $k\,G$ on the curve $y^2\equiv x^3+b\pmod p$, and the next 32 bytes code an integer $s=k^{−1}(e+r\,d)\bmod n$ where $e$ is a 256-bit hash of the message and $k$ is random in $[1,n)$ except it's not such that $s=0$. It follows that (where $p$, $n$ and $b=7$ are given for secp256k1):

1. It holds $0<r<n$
2. It holds $0<s<n$
3. There exists an integer $y$ with $y^2\equiv r^3+b\pmod p$. Given that $p$ is prime and $-b$ is not a cube modulo $p$, this is equivalent to $\displaystyle\left(\frac{r^3+b}p\right)=+1$ (see Legendre symbol), equivalently to $(r^3+b)^{(p-1)/2}\bmod p=1$, which is easily checked.

With probability just above $1/2$, a random 64-byte string parsed as $r$ and $s$ fails one of these three tests², in which case we are sure it's not an ECDSA signature for curve secp256k1. If it passes these three tests, then there exists a message and a public/private key pair making the signature valid. More precisely: for almost every message there exist exactly 2 key pairs (it can also be 0 or 4 in some edge cases). It's possible to find these key pairs, using ECDSA public key recovery.

Any valid ECDSA signature for secp256k1 pass these three tests. Hence the above distinguisher has advantage $>1/2$.

---

¹ In particular, replacing given with unknown: if the message and private key are given we can check the signature, and that's a hell of a distinguisher. And since an ASN.1 format allows a trivial distinguisher, we must suppose it is used the (usually more compact, and also common) format defined in IEEE Std 1363-2000 E.3.1, that I quote with adaptation of the notation:

(…) the output of the signature generation function is a pair of integers $(r,s)$. Let $n$ denote the order of the generator ($g$ or $G$) in the DL or EC settings, and let $\ell=\bigl\lceil\log_{256}n\bigr\rceil$ (i.e., $\ell$ is the length of $n$ in octets). The output $(r,s)$ may be formatted as an octet string as follows: convert the integers $r$ and $s$ to octet strings $R$ and $S$, respectively, of length $\ell$ octets each, using the primitive I2OSP, and output the concatenation $R\mathbin\|S$. To parse the signature, split the octet string into two components $R$ and $S$, of length $\ell$ each, and convert them to integers $r$ and $s$, respectively, using OS2IP. Note that it is essential that both $R$ and $S$ be of length $\ell$, even if it means that they have leading zero octets.

² Mostly, test 3: because $n$ of secp256k1 is just below $2^{256}$ (within $1.3\times2^{128}$), there is probability $<2^{-126}$ that condition 1 or 2 is exploitable to reject a 64-byte random value as a signature. As noted in comment, that's curve-specific, and for some curves test 1 and 2 are very selective. Also, for some curves, test 3 would need adaptation.