3
$\begingroup$

An ECDSA signature encodes the $(r,s)$ integers each in $[1,n)$, where $n$ is the order of the (sub)group generator. For a standard 256-bit prime curve one standard byte form for such signature is 64-byte, formed of the two components encoded big-endian over 32 bytes and concatenated. There are at least two other common ASN.1 formats: one re-encoding the previous form as a BITSTRING, another encoding $r$ and $s$ as a SEQUENCE of two INTEGERs.

Given a (message, signature) pair $(M,(r,s))$, the public key recovery operation allows to find one (of at least two) public keys $Q$ such that $M$ and $(r,s)$ pass verification against $Q$:

  • Compute the hash $H$ of $M$ and convert it to an integer $e$ as in steps 2 and 3 of the signing operation.
  • For each point $R$ of the curve which X coordinate $x_R$ is such that $r=\overline{x_R}\bmod n$ (where $\overline{x_R}$ is an integer representation of $x_R$, or just $x_R$ for prime curves)
    • compute candidate public key $Q=r^{-1}(s\;\!R-e;\!G)$ and somewhat validate it.

When $R$ is a candidate point, so is $-R$ sharing the same X coordinate $x_R$, leading to a different $Q$. Another reason for possibly multiple $Q$ is that there can be up to $h+1$ candidates $\overline{x_R}$ with $r=\overline{x_R}\bmod n$, and among these conceivably several which are the X coordinate of a curve point (where the multiplicity $h$ is the ratio of the curve size to the order of the generator, with $h=1$ for standard prime curves, $h\in\{2,4\}$ for standard binary curves). For standard prime curves over the field $\mathbb F_p$, the primary candidate is $x_R=r$, and there could be the other $x_R=r+n$ only for curves with $n<p$ (e.g. secp256k1 but not secp224k1) and then only if $r$ lie in $[1,p-n)$ which is extremely rare for random $r\in[1,n)$ due to Hasse's theorem, and then only if $x_R=r+n$ corresponds to some valid point (I see no reason why that later condition would not be with probability about 50%).

Thus absent a mean to weed out invalid candidates, standard public key recovery operation can't recover the intended public key with certainty. It's ambiguous. We want to fix that.

In principle, in order to define a format for ECDSA signature allowing unambiguous public key recovery, we need to add:

  • One bit to disambiguate between $R$ and $-R$, e.g. to tell if the first byte of the compressed representation of point $R$ is 02 or 03 (the parity of $y_R$ for prime curves). Another option is to require the signer to use $R$ making that byte 02. That's sometime done and enforced in order to avoid the issue that from a valid ECDSA signature of a message, it's easy to build one (single) other signature for the same message.
  • Extra data to reduce to a single $x_R$ for a given $r$. That could be the integer $j$ in $[0,h]$ with $\overline{x_R}=r+j\;\!n$. For prime curves that reduces to one bit, with the value $0$ in practical cases (so much that the other case could be ignored, or that it could be a requirement that $x_R<n$ when making the signature).

Questions:

  1. What are standard or common uses for ECDSA signature modified for unambiguous key recovery? What augmented signature format or other technique do they use?
  2. For some standard prime curve with $n<p$ like secp256k1, how hard would it be to build a valid (private key, message, signature) triplet $(d, M, (r,s))$ where the "extra data" is needed, that is with the ephemeral point's X coordinate $r+n$ rather than $n$ as usual?

Update: I'm told that Ethereum uses unambiguous public key recovery, for the curve secp256k1, thanks to a recovery identifier aka recID noted $v$, and formatting $(r,s,v)$ as a 65-byte bytestring with the last byte for $v$. I see conflicting information on the value of that byte, and the treatment of $x_R\ge n$: (311) in this states that $v$ can be in range $[0,3]$, but dismisses signature with $x_R\ge n$ as invalid thus reduce to $v\in\{0,1\}$ equal to the parity of $y_R$. That other source mentions adding the constant 0x1B=27, with values assigned for $x_R\ge n$ (by adding 2) and recovered public key in compressed format (by adding 4), and then more.

Improve this question
$\endgroup$
2
  • 1
    $\begingroup$ 1.) do you really think the [key-recovery] tag apply outside of cryptanalysis? 2.) I think you lean towards seeking standards - i.e. [reference requests]. 3.) the [elliptic-curve] tag should be added - it's meant to be used in augmentation with tags such as [dsa] and [dh] $\endgroup$ Commented Nov 27, 2024 at 12:39
  • $\begingroup$ @DannyNiu 1.) Yes I do. I kept key-recovery, because the name of the procedure is "Public Key Recovery Operation", and it's intend (saving space and communication) seems to fall into the tag's definition: "A means of recovering cryptographic keys when the usual means for obtaining them is unavailable". 2.) and 3.): very right, done, thanks. $\endgroup$ Commented Nov 27, 2024 at 13:07

1 Answer 1

Reset to default
2
+100
$\begingroup$

I believe I am the original author of the secp256k1 "recoverable signature" format, which ended up as (with modifications) Ethereum's signature format, though it was originally intended for Message Signing in Bitcoin: the ability to sign a custom message with a Bitcoin address (which at the time was a hash of a public key), and verify it against just the address (without needing to separately convey the public key for that address). Note that this is distinct from normal Bitcoin transaction signing, and not used for that purpose.

The format is, as you already seem to have linked to:

  • A 1-byte "recovery id", which is 27 plus a 3-bit integer, whose bits mean:
    • 0/1: even/odd $\overline{y_R}$
    • 0/2: whether $\overline{x_R} \geq n$.
    • 0/4: corresponding public key is to be in uncompressed/compressed format (because Bitcoin addresses at the time were all pay-to-pubkey-hash addresses, it is essential that not just the public key, but also the exact encoding of that public key can be recovered).
  • A 32-byte big endian encoding of the signature's $r$ value ($r = \overline{x_R} \operatorname{mod} n$).
  • A 32-byte big endian encoding of the signature's $s$ value.

This is implemented in the libsecp256k1 library in the "recovery" module, though the exact encoding of the recovery byte is left to higher layers (the addition of the 27 constant, as well as the uncompressed vs. compressed notion; it just exposes a "recid" in range 0-3).

The format was inspired by reading the "Public Key Recovery Operation" section in the SEC 1 specification you link to, and assigning recovery id numbers to each of the choices (outer loop controling the addition of the curve order, inner loop controlling the sign of $\overline{y_R}$). The addition of the 27 constant was to make sure the format couldn't be confused for typical other public key or signature formats at the time. The addition of the 4 constant to indicate compressed public keys was added later. Ethereum inherited the format, but outlawed all but the lowest two recovery ids (which for honest signers isn't a concern).

In retrospect, I believe it would have been possible to create a more compact format:

  • Instead of indicating even/odd $\overline{y_R}$ coordinate in a separate bit, it would have been possible to make $\overline{y_R}$ for example implicitly even, by making the signer negate the $R$ point (and corresponding private nonce $k$) prior to signing if $\overline{y_R}$ was odd. I do not believe this introduces a vulnerability, since it is attacker-simulatable: in the existing scheme, the attacker can choose to ignore any signatures with odd $\overline{y_R}$ to make it equivalent, so adding this rule can at most mean the attacker needs to see twice as many signatures to pull of an equivalent attack.
  • Instead of indicating $\overline{x_R} \geq n$ in a separate bit, it would have been possible to make the 32-byte field of the signature encode $\overline{x_R}$ directly instead of $\overline{x_R} \operatorname{mod} n$. Or, of course, $\overline{x_R} \geq n$ could have just been outlawed, as Ethereum apparently did.

Of course, dropping the recovery id byte would have left no means of encoding the compressed/uncompressed notion, but depending on your use case, that might be considered a layer violation anyway.

As for your second question:

  1. For some standard prime curve with $n<p$ like secp256k1, how hard would it be to build a valid (private key, message, signature) triplet $(d, M, (r,s))$ where the "extra data" is needed, that is with the ephemeral point's X coordinate $r+n$ rather than $n$ as usual?

I believe that if you require the private key $d$ to be produced, that this is impossible.

For any $(d, M, (r, s))$ such that $(r, s)$ is a valid ECDSA signature for message $M$ and public key $dG$, the corresponding private nonce $k$ such that $R = kG$ can be recovered as $k = s^{-1}(H(M) + rd)$ (this follows from the ECDSA verification equation, substituting the public key $Q = dG$).

Thus, any algorithm that is capable of producing such a tuple is equivalent to being able construct a $k$ such that $\overline{x_{kG}} \geq n$. On curves where the ratio of $k$ values for which this holds ($\frac{p}{n} - 1$) is negligible, this feels impossible to me, though perhaps not exactly reducible to ECDLP.

Improve this answer
$\endgroup$
2
  • $\begingroup$ For the second problem (kudos for simplifying it), on secp256k1 one of the least prohibitively costly algorithm I come up with takes $G'=((p+1)/2)G$ (which has an unusually small $\overline{x_{kG}}$, allowing slightly optimized point addition) then computes $k'G'$ for $k'$ increasing from $1$, until one has $\overline{x_{k'G'}}\geq n$. It's then easy to get your $k$ from $k'$. We expect $p/(p-n)\approx2^{127.7}$ point additions of $G'$. This indeed in only marginally less costly than ECDLP. However that a brute force algorithm is impractical is far from proof that there is no practical one. $\endgroup$ Commented Dec 8, 2024 at 6:05
  • 1
    $\begingroup$ @fgrieu You can do faster iteration by doing repeated doubling, rather than adding a constant (the multiplicative order of 2 mod $n$ is high enough to never cycle), and for each iteration you can consider 6 points (original, its negation, and for each the 3 points obtained by multiplying the X coordinate with powers of $\sqrt[3]{1}$, exploiting the GLV endomorphism). Also, you can batch convert from jacobian to affine coordinates to avoid ~all modular inverses. But yes, none of this changes the fact that it needs close to $2^{128}$ operations. $\endgroup$ Commented Dec 8, 2024 at 15:55

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.