3
$\begingroup$

I read, here, that ECDSA signature is EUF-CMA but not SUF-CMA, aka sEUF-CMA (for strong existential unforgeability under adaptively chosen message attacks; see terminology there).

Specifically, the assertion is that given an ECDSA signature for a message, it is possible to transform it into a different signature that pass verification for that same message.

Is there such issue, and where exactly does it lie?

  • mathematical definition
  • standardized definition of signature in some edition of ANS X9.62 (paywalled), SEC-1, or FIPS 186
  • some implementations
$\endgroup$
4
$\begingroup$

From SEC1 v2.0 (§4.1, pp. 43–47), a public key is a point $Q \in E$, and a signature on a message $m$ is a pair of integers $(r, s)$ satisfying the signature equation (condensed from several steps):

\begin{equation*} r \stackrel?= f\bigl(x([H(m) s^{-1}]G + [r s^{-1}]Q)\bigr), \end{equation*}

where $f\colon \mathbb Z/p\mathbb Z \to \mathbb Z/n\mathbb Z$ projects the least nonnegative integer representative of an element of the coordinate field onto the scalar ring. Here $G$ is the standard base point, and $H$ is a hash function mapping messages to scalars.

This equation is invariant under the transformation $\phi\colon (r, s) \mapsto (r, -s)$ because $(-s)^{-1} = -(s^{-1})$, $[-\alpha]P = -[\alpha]P$, $(-A) + (-B) = -(A + B)$, and $x(P) = x(-P)$. It is also obviously invariant under the transformation $\psi\colon (r, s) \mapsto (r, s + n)$ because $s$ is used only as a scalar.

There are three additional requirements specified:

  1. $r$ and $s$ must lie in the interval $[1, n - 1]$, where $n$ is the order of the group.

  2. If $H$ returns invalid then the signature verification must fail.

  3. $[H(m) s^{-1}]G + [r s^{-1}]Q$ must not be the point at infinity.

The only requirement relevant to strong unforgeability is (1), because it rules out the transformations $\phi$ and $\psi$ individually. But it does not rule out, e.g., $\psi \mathbin\circ \phi$, equivalent to $(r, s) \mapsto \bigl(r, (-s) \bmod n\bigr)$.

Conceivably the signature scheme could require that $s$ be chosen to be ‘even’ like in ANSI X9.62 point compression, or be chosen to be in the lower half of the interval $[1, n - 1]$. But such requirements are not imposed by verifiers, and so ECDSA cannot provide strong unforgeability.

There are also other obvious ways that an implementation could fail to provide sEUF-CMA:

  • The implementation could fail to check the intervals of $r$ and $s$. (However, I don't know any that do.)

  • The implementation could allow for many different encodings of a single integer. For example, it could allow BER or DER encodings in some ASN.1 format—because the standard doesn't specify a byte encoding of integers; the signature scheme is really defined in terms of integers, a mistake avoided by EdDSA.

    This is the first source of transaction malleability that was reported in Bitcoin, prompting implementations to accept only the unique DER encodings of signatures and reject other encodings, before someone noticed the negation vector too a year and a half later. (Exercise for the reader aching for a trip down a rabbit hole: Chronicle the saga of transaction malleability in MtGox and figure out what's up with the bankruptcy proceedings these days.)

$\endgroup$
  • $\begingroup$ Yeah, that's common (for the requirement to be there, not the actual occurrence of it of course, most if not all input data is significantly smaller than 2,091,752 terabytes - assuming SHA-256). $\endgroup$ – Maarten - reinstate Monica Nov 3 at 0:25

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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