4
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ I think the idea of a signature verification algorithm is to confirm that the given signature has been issued by the specified party for the specified message. If these properties cannot be verified then the algorithm should return false. $\endgroup$ – SEJPM Jul 20 '17 at 19:47
  • $\begingroup$ @SEJPM True, but then this does not deserve any special treatment, since the same properties hold than for any other hash, don't they? I mean, hash have collisions by design and the null one should not have more collisions or whatsoever, so in that regard it is just like any other possible value. By the way, maybe I am simply wrong believing this is actually a special edge case... $\endgroup$ – Lery Jul 20 '17 at 20:49
1
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ The attack has some significance on the verifier side, because A) a fault injection that forces the hash to zero is easier to pull than one that forces the hash to the hash of a message for which a signature is known (or obtainable without the private key, see this answer for how); and B) on the verifier side, such fault injection forcing the hash to zero would allow a forgery to go thru the verification, using the signature $r=s=x_A\bmod n$, where $x_A$ is the $x$ coordinate of the public key, unless that's blocked somehow. $\endgroup$ – fgrieu Sep 4 '17 at 15:42
  • 1
    $\begingroup$ A fault injection on the verifier side could zero the return value of the sig_check routine that returns 0 on success or error code on failure including forgery. There are lots of things that can happen if you can inject faults into any system—but there's a marked qualitative difference between a fault injection on a single run of a single verifier, which implies no more long-term consequences than any other attack on that verifier, and a fault injection on the signer that leaks the private key or gives the attacker a valid signature for any verifier. I don't see a case of the latter here. $\endgroup$ – Squeamish Ossifrage Sep 4 '17 at 16:33
  • 2
    $\begingroup$ Good point. Yet targeted zeroing is among easiest fault attacks, esp. for output of dedicated hardware, hypothetically a hash engine. A lot of effort is put in defending against fault attack with hardare, or/and mathematical cross-check (block cipher run in reverse, RSA..). Security gizmos occasionally have failure mode where output is zero, example in 6.1.1 there (this one could be software, but not all are). $\endgroup$ – fgrieu Sep 4 '17 at 17:04

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.