How should ECDSA handle the null hash?

Question

In ECDSA, assume your public key is $Q=(x,y)$, then when performing the verification of any message leading to a null hash value (that is $H(M)=0$), the signature $(r,s)=(x,x)$ would always lead to a valid verification for that message, no matter what your public key is.

This is the case since upon verification you compute:

• $e = \textrm{H}(m) =0$.
• Let $z$ be the $L_n$ leftmost bits of $e$, so it's zero.
• $w = s^{-1}=x^{-1}\bmod\,n$ by my choice of $s$.
• $u_1 = zw\equiv 0\bmod\,n$ and $u_2 = rw=xw \equiv 1\bmod\,n$.
• the curve point $$(x_1, y_1) = u_1 \times G + u_2 \times Q= 0 \times G + 1 \times Q=Q$$
• The signature is valid if $r \equiv x_1 \pmod{n}$, invalid otherwise, but this is the case by choice of $r$.

I'm perfectly aware that the probability of finding a message $M$ hashing into $0$ is extremely low, let alone a useful message... But without going as far as considering some big companies with tons of computation power, the zero value might somehow happen for example because of targeted faults in the memory of the device or through some other means... Whatsoever it seems me to be an important value since it creates such a special case.

Yet, according to my reading of Sec1v2 and other standards concerning ECDSA, none consider this specific edge case.

I have done some tests with a few libraries, and at least OpenSSL, Go, and Crypto++ are completely falling for it. Only mbedTLS seems to reject it, and does so with an error "MBEDTLS_ERR_ECP_INVALID_KEY".

I know this does not imply much in term of practical security, but I believe this should still be considered in the frame of the so-called defense in depth, knowing such a special case exists.

Regarding signature generation, having $H(M)=0$ also has the consequence of rendering $s$ only dependent on $k^{-1}rd$, but this does not imply anything in term of key recovery as long as $k$ is a secret.

So, what should one do about this?
Should a library explicitly reject such a special case upon verification? If so, shall it reject the 0 value or signatures where $r=s$? In the later case, it would mean that signatures generated correctly with a null hash would still be verified correctly.

More generally, do you see any other implication of such a case? To which extent is a null hash something to be worried about for ECDSA?

Answer 1

This is true.

A conciser statement is: If an adversary can find a message $m$ for which $H(m) = 0$, then the adversary can forge the signature $(r, s)$ on $m$, where $r = x([k] Q)$ for some arbitrary ‘nonce’ $k$ (e.g., 1), and $s \equiv r k^{-1} \pmod n$, because $$x\bigl([H(m)\,s^{-1}] G + [r s^{-1}] Q\bigr) \equiv x\bigl([rr^{-1}k] Q\bigr) \equiv x([k] Q) \equiv r \pmod n,$$ satisfying the verification equation.

The obvious solution is to pick a hash function for which an adversary has no hope of finding preimages of 0, of which the streets of cryptography are littered with examples. Here's one: SHA-256.

Suppose an adversary can cause a signer to accidentally compute 0 for $H(m)$ via some fault attack and learns a ‘signature’ $(r, s)$ on a hypothetical message $m_0$ with $H(m_0) = 0$. Now what, supposing the adversary knows no such message $m_0$? From this the adversary learns a uniform random curve point's $x$ coordinate $r = x([k] G)$, and a uniform random scalar $s \equiv r k^{-1} d \pmod n$, where $d$ is the signer's secret scalar and $k$ is the signer's secret nonce.

These are not independent, but they are related by a discrete log: if the adversary can compute $d$ from $(r, s)$, then the adversary can also compute $k$, the discrete log of $R = \pm x^{-1}(r)$ from the base point $G$. And if the adversary can compute discrete logs, they might as well just compute $d$ offline from $Q = [d] G$ without bothering to apply a fault attack in the first place.

In other words, this does not really seem worse than a fault attack revealing an unintended signature on any other message with a nonzero hash. And the signer can always thwart fault attacks by verifying the signatures it computes before revealing them.