6
$\begingroup$

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?

$\endgroup$
1
  • 3
    $\begingroup$ Note that DER encoded signatures consist of a SEQUENCE (byte value 30) with two INTEGER (byte value 02 encoded values) for ECDSA. So if the signature is of X9.62 form then it will be recognizable and obviously not random data. However, the "flat" representation - just $r$ and $s$ concatenated - then it is up to the values of $r$ is $s$. $\endgroup$
    – Maarten Bodewes
    Nov 21, 2023 at 21:44

2 Answers 2

9
$\begingroup$

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 )}$$

$\endgroup$
8
  • $\begingroup$ I'll hash the signature to fix any issues. Thanks. $\endgroup$
    – fadedbee
    Nov 21, 2023 at 8:58
  • 1
    $\begingroup$ Yes, a hash is a usual solution to remove any structure of the inputs like we did in ECDE or signatures. $\endgroup$
    – kelalaka
    Nov 21, 2023 at 10:02
  • 2
    $\begingroup$ Elligator won't work on a prime order curve like secp256k1, but you can use Elligator Squared. $\endgroup$ Nov 21, 2023 at 10:09
  • $\begingroup$ @MehdiTibouchi you are right. Updated the answer. Thanks. $\endgroup$
    – kelalaka
    Nov 21, 2023 at 10:20
  • 1
    $\begingroup$ @kelalaka: you beat me at fixing it: it's easy to generate a point on secp256k1 with $n\le x<p$ thus $r=x-n\ne x$. One example is $(x,y)=(p−3,y)$ with the above $y$ that you found. However it is hard find a $k$ matching such $r$ and AFAIK it was never done. Without it, I don't see how to generate a valid signature with such $r$, even when choosing message and public key. $\endgroup$
    – fgrieu
    Nov 21, 2023 at 19:40
7
$\begingroup$

Reformulating slightly1:

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 tests2, 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$.


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

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

$\endgroup$
2
  • 1
    $\begingroup$ Just a small note that e.g. Brainpool curves may have an $n$ that's not so close to the nearest power of two - or rather power of 256 if we assume bytes. And for the prime curves there is of course secp512r1 which definitely isn't on a byte boundary. It won't help you distinguish anything about the private key, but detecting a (sufficiently large) set of signatures would be easy. $\endgroup$
    – Maarten Bodewes
    Nov 21, 2023 at 17:04
  • $\begingroup$ @MaartenBodewes Yes. And there is also secp224k1 which ECDSA signatures sans ASN.1 should be 58 bytes including one always and another almost always 0x00, except if we invent a convention to try another $k$ should it happen otherwise. I wonder if that's done IRL, and how many makeshift parsers / signature / verification gear get the edge cases wrong. $\endgroup$
    – fgrieu
    Nov 21, 2023 at 17:09

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.