Reliable and safe generation of synthetic signatures

The ECDSA public key recovery algorithm is used to recover the ethereum address from a message digest and ECDSA signature.

The ECDSA signing algorithm will produce a “valid” signature, in the sense of permitting a successful public key recovery, by using a ECDSA private key.

A synthetic signature is one that is not derived from a private key.

We would like an algorithm to derive a predictable and valid synthetic signature from a given source of public random numbers. It must have negligible chance of a collision — i.e. two random numbers implying the same synthetic signature . We also require that it is infeasible to find the public key from the signature and message digest.

A synthetic externally owned account (SEOA) is the account corresponding to the public key or ethereum address, recovered from a valid synthetic signature with a fixed digest.

Applications

The infeasibility property prevents anyone from controlling the SEOA, with some exceptions:

  1. If the digest is an Ethereum transaction, that transaction will be authorised by the synthetic EOA. See Nick Johnson’s biog post.
  2. If the digest is an EIP-3074 digest (which is derived from an Invoker contract address), and EIP-3074 were included in an ethereum upgrade, that contract could make arbitrary calls to other accounts – calls which would be authorised by the synthetic EOA. This is the application we are most interested in at statechannels.org: see Gas efficient contract architectures for escrowing assets.

If the infeasability property fails to hold, anyone can drain funds from the EOA or otherwise act as the EOA.

The problem

An ECDSA signature is a pair of 32 byte numbers r and s. Let c be another random 32 byte number which is input to our desired algorithm. (This would be the channelId in a statechannels application).

Naive approaches to the generation of synthetic signatures are likely to fall foul of the fact that roughly half of randomly generated r parameters will imply an invalid ECDA signature.

During the ECDSA signing algorithm, r is generated as the x-coordinate of a point on an elliptic curve. Ethereum uses the secp256k1 curve.:

y^2 \text{mod }p= (x^3+7) \text{mod }p

Where p = 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEFFFFFC2F.

(Side note 1: Both r and s should be less than p – but since p is very large, the probability of randomly generating a 32 byte number larger than p is tiny).

(Side note 2: Since EIP-2, transaction signatures must have s < p / 2 + 1. This is to prevent the easy construction of a second signature from a first, on the same digest, which recovers to the same address. At present there’s no proposal to have the same prevention strategy for EIP-3074 signatures. One question we could discuss on this thread is whether that should happen).

The main reason a synthetic signature can be invalid, then, is that r is chosen as not a point on the curve. This happens if (r**3 + 7) is not a quadratic residue modulo p. Non-integer values of y aren’t even the right type of number to lie on the curve.

Proffered Solutions

  1. Inelegant, but deterministic and safe: try {r = c, s = c} and check for validity. On failure, increment r++ and try again. Eventually we will find a valid signature – and quite quickly, in fact, as roughly half of all possibilities will work.
  2. More efficient, but unsafe: use {r = publicKey(c).x, s = c}. We treat c as a random ECDSA private key, and derive a public key from it — this is guaranteed to give a point on the elliptic curve, and therefore setting r to the x coordinate gives a valid signature. The problem, however, is that since c is public this approach is effectively leaking the ECDSA so-called k parameter. This parameter, which plays the role of a private key, is sometimes called a nonce. It is known that this leads to the private key corresponding the SEOA being computable, violating infeasibility.
  3. Even more efficient, unsafe in a slightly subtler way: use {r = constant, s = c} . This will always work as long as the constant lies on the curve. For example, r = 0x4fe3e35437197d331ab44a90afd24052540e02c129b7e2083344b8e4684c2153. This option is more efficient because we didn’t need to do any elliptic curve operations to generate the signature. The problem is that the SEOA private key may still computable for an attacker who intercepts multiple synthetic signatures generated using this scheme with the same constant, since they can compute the k parameter and from there get the SEOA private key.

For more detail on the security holes in some of these solutions, see programmingbitcoin/ch03.asciidoc at master · jimmysong/programmingbitcoin · GitHub

Related ideas