11
$\begingroup$

In a Schnorr signature (Wikipedia style), we have:

  • $R = kG$, where $0<k<n$ is a nonce and $G$ is the generator point.
  • $e = H(R \| M) \bmod n$, where $H()$ is a hashing function and $M$ is the message.
  • Finally $s = k - xe \bmod n$, where $x$ is the private key. The signature is then either $(R,s)$ or $(e,s)$ depending on convention.
  • Verifiers check that $R = sG + eP$, where $P = xG$ is the public key.

Strangely, if $e=0$ then no knowledge of $x$ is proven, as all steps can be carried out by someone who knows only $M$. So, why is $e=0$ not disallowed?

The only answer I can find to this is that breaking the hash function to obtain $e=0$ should generally have twice the security level (in bits) of that required to directly break the public key. And, it is most convenient to skip the extra steps of checking zero-ness of $e$, so for practical reasons the case of $e=0$ is glossed over.

$\endgroup$
  • 3
    $\begingroup$ Well the probability of accidentally hitting $0$ during honest signing is $1/n$ which is negligible... $\endgroup$ – SEJPM Jan 8 at 7:26
  • $\begingroup$ And, publish the input that makes the hash output 0. It is an interesting hit. $\endgroup$ – kelalaka Jan 8 at 7:36
  • $\begingroup$ @SEJPM Still, checking such corner cases seems a good idea. The problem is of course that the function then doesn't have any other means than reporting failure for that specific nonce / message pair - altering $k$ doesn't seem like a good idea. Still, I'd prefer an "extremely out of luck" exception in case the hash function is terribly broken, replaced or anything similar. $\endgroup$ – Maarten Bodewes Jan 8 at 13:52
10
$\begingroup$

Strangely, if $e=0$ then no knowledge of $x$ is proven, as all steps can be carried out by someone who knows only $M$. So, why is $e=0$ not disallowed?

Because $e = 0$ is not unique in this regard. Every single $e$ is equally "insecure", i.e. you may as well ban $e = 23$ with the same reasoning.

To exemplify, assume $e = 23$ arbitrarily (holds for any value of $e$ with the same reasoning). For that $e$, I can easily compute a signature by choosing a random scalar $0 \leq s < n$ and computing $R = sG+eP$. By definition, $(R,s)$ is a valid signature. For $e = 0$, this is probably the attack you had in mind.

Of course, in reality this attack is not going to be successful because if I try to choose $R$ "cleverly" for a specific $e$, with overwhelming probability this is not going to be the $e$ with $e = H(R||M)$ (assuming the hash function is good). The trick here is that $e$ is only fixed after $R$ is already chosen, which makes it secure.

There is a deeper reason behind all this linked to the security proof, which does not at all care about any $e$. I'm not doing the proof justice with the following sketch, but very, very, very roughly, the reduction runs the attacker twice: once with $e$ and once with some other hash value $e'\neq e$ (modeling $H$ as a random oracle). The reduction only requires $e - e' \neq 0$ (which is the actual "weak spot 0", but it only occurs in the security proof) to compute the signature's secret key given a successful attacker. If you are interested, I recommend a look into Pointcheval, David, and Jacques Stern. "Security arguments for digital signatures and blind signatures.

$\endgroup$
  • $\begingroup$ So in short, "if I can grind k (R=kG) until e=0, then I can equally well grind s (R=sG+e'P) until e=e' for any chosen e'." Does that paraphrasing do justice? (Only one funny thing with e=0 -- the result can be reused on all public keys. But pubkey-prefixing schemes solve that.) $\endgroup$ – Mark Lundeberg Jan 8 at 20:53
  • $\begingroup$ That's a pretty good summary, yes. And hence overall, $e = 0$ is allowed because it's just as bad a hash value as any other $e$. $\endgroup$ – Jan Bobolz Jan 8 at 20:55

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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