0
$\begingroup$

How feasible is it if someone is able to forge a signature for any arbitrary message hashes, given the public key of a secret key? If it is feasible, then what implications would this have?

What I mean by arbitrary in this case is randomly, without getting to choose what exactly it is or should be, just random.

$\endgroup$
1
  • 1
    $\begingroup$ Hashing messages is part of digital signatures since the first signature, Rabin's signature. This answer might teach you why the collision is too bad for signatures. $\endgroup$ Commented Aug 21 at 17:34

1 Answer 1

3
$\begingroup$

If you can do this only for message hashes, then it is of no significance. If you can do it for messages, then you have broken the signature scheme.


If, given a public key $Q = (x(Q),y(Q))$, you are able to find a hash $H$ and a signature $(r,s)$ that passes the subroutine of verification parametrized by the hash rather than the message, this is unremarkable.

For example, let $H$ be the all-zero hash, $r = x(Q)$, and $s = r^{-1} \bmod n$, where $n$ is the order of the group. Then $r$ and $s$ lie in the necessary interval $[1,n-1]$, and the integer interpretation $e$ of the hash $H$ is zero, so

$$R_1 = [e s^{-1}] G + [r s^{-1}] Q = [0]G + [1]Q = Q,$$

so $x(R_1) = x(Q) \equiv r \pmod n$ as required by the ECDSA verification procedure.1

But good luck finding a message with all-zero hash under a hash function anyone uses for ECDSA.


If, on the other hand, given a public key, you are able to find a message $M$ and a signature $(r,s)$ that passes the full verification routine—which internally computes $H = \operatorname{Hash}(M)$���then this would break ECDSA. This is the winning condition of the EUF-CMA game, existential unforgeability under (adaptive) chosen-message attack, which has been the standard notion of signature security since 1988.2

What I mean by arbitrary in this case is randomly, without getting to choose what exactly it is or should be, just random.

This is what existential forgery means: the adversary may not have any control over the form of the message, but they win the game anyway. A stronger adversary—i.e., an adversary against a more broken signature scheme—might be able to forge signatures on arbitrary messages of their choice, or somewhere in the middle (forge signatures on selective modifications to messages, for example). But in cryptography we don't bother with these degrees of adversary strength or security weakness; we consider the signature scheme broken, and toss it in the dustbin, if there is a merely existential forgery attack against it.


1 Digital Signature Standard, FIPS 186-5, § 6.4.2: ECDSA Signature Verification Algorithm, p. 23

2 Goldwasser, Micali, and Rivest, “A Digital Signature Scheme Secure Against Adaptive Chosen-Message Attacks”, SIAM Journal on Computing 17(2), pp. 281–308, 1988, DOI: 10.1137/0217017

$\endgroup$
1
  • $\begingroup$ What you are suggesting implies that it could be detrimental to any signature scheme, if such a scenario is feasible. $\endgroup$ Commented Aug 21 at 13:06

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.