Further explanation on the security warning within PrehashVerifier

[ArnaudBrousseau]

Hello! I found the following security warning in the comment on top of PrehashVerifier:

traits/signature/src/hazmat.rs

Lines 64 to 68 in 3be350f

	/// # ⚠️ Security Warning
	///
	/// If `prehash` is something other than the output of a cryptographically
	/// secure hash function, an attacker can potentially forge signatures by
	/// solving a system of linear equations.

I was wondering if it's possible to have more details on what this potential signature forgery attack is? Because it's defined on a trait rather than a concrete curve/signing algorithm, does it apply across the board? I'd be curious to know what the "system of linear equations" is in the case where a not-so-random digest is signed.

[tarcieri]

It's better explained here, perhaps:

https://docs.rs/signature/latest/signature/trait.PrehashSignature.html

Signature systems which leverage a message digest, such as those based on the Fiat-Shamir heuristic, are secure in the Random Oracle Model.

Removing the random oracle from such systems is a catastrophic breakage. These systems are fundamentally challenge/response protocols made non-interactive by picking the challenge using a hash function. Allowing the signer to pick the challenge arbitrarily destroys the security of these systems, because it definitionally ceases to be a challenge at that point.

There's an explanation of what this attack looks like when applied to ECDSA here: https://bitcoin.stackexchange.com/questions/81115/if-someone-wanted-to-pretend-to-be-satoshi-by-posting-a-fake-signature-to-defrau/81116#81116

[ArnaudBrousseau]

Thanks a lot for your explanation/links and the fast answer! Summarizing my understanding for posterity (and I think we're good to close this issue!): if the verifier doesn't hash the message themselves, they open themselves to the following attack (picking ECDSA for this example):

• attacker picks random $a, b \in F$ (where $F$ is the underlying field) and $P$ as a target public key to attack
• attacker computes $R=aG+bP$
• attacker presents the signature $(r = R.x, s = \frac{R.x}{b})$ and the "hash" $z=\frac{R.x*a}{b}$

For the signature to be valid we need $u_1\times G+u_{2}\times P$ to have $r$ as its $x$ coordinate.
($u_1$ and $u_2$ are defined in the ECDSA verification algorithm: $u_1=zs^{-1}$ and $u_{2}=rs^{-1}$)

Let's compute $u_1\times G+u_{2}\times P$:

• = $zs^{-1}G + rs^{-1}P$ (by definition of $u_1$ and $u_2$)
• = $\frac{R.x*a}{b} s^{-1}G + rs^{-1}P$ (by definition of $z$)
• = $\frac{R.x*a}{b} \times \frac{b}{R.x}G + R.x \times \frac{b}{R.x} \times P$ (by definition of $r$ and $s$)
• = $aG + bP$
• = $R$

We've shown $u_1\times G+u_{2}\times P$ = $R$; hence the signature is valid and the attacker has successfully produced a valid signature for $P$ without any knowledge of the associated private key! ⚠️