19
$\begingroup$

I'm working on some EC-Schnorr signature code. Reading various papers on that, it seems EC-Schnorr is not standardized as well as ECDSA.

For example, I found two main differences in two main actors specs (also found other minor variants in other papers);

according to BSI Schnorr signature is computed as:

  1. $k$ a random
  2. $Q$ = $kG$, $r = Q_x$
  3. $h = H(M \mathbin\Vert Q_x)$
  4. $s = k − h \times d \mod n$
  5. Output $(h, s)$

and according to libsecp256k1:

  1. $k$ a random
  2. $Q = kG$, $r = Q_x$
  3. $h = H(r \mathbin\Vert m) = H(Q_x \mathbin\Vert M)$
  4. $s = k - h \times d \mod n$
  5. Output $(r, s)$.

Difference are located in:

  • step 3 : order of data to hash
  • step 5 : value to return

Of course, signature verification algorithm differ a bit according to that.

So, I wonder:

  1. if there is specification more standard than another?
  2. in case of several standards how to choose one?
  3. what about interoperability?
  4. what about security (for eg: $H(Q_x \mathbin\Vert M)$ is better than $H(M \mathbin\Vert Q_x)$ in my opinion)?
| improve this question | |
$\endgroup$
  • 4
    $\begingroup$ "The nice thing about standards is that you have so many to choose from." (Andy Tanenbaum). I don't see any difference in security with regards to the hash order, as long as the boundary between $Qx$ and $M$ is well defined. The return value difference would be more interesting to take a look at. $\endgroup$ – Maarten Bodewes♦ Apr 26 '16 at 15:05
  • 3
    $\begingroup$ You have forgotten two further variants. Some standards calculate s=k + h d. Some standards require to put the whole point Q into the hash instead of only the x coordinate. $\endgroup$ – user27950 Mar 10 '17 at 14:38
9
$\begingroup$

Adding to other answers, I note that both schemes are related to (but clearly different from) those standardized in ISO/IEC 14888-3:2016 (non-functional preview):

  • The BSI's EC-Schnorr original specification was similar to ISO/IEC 14888-3's EC-SDSA-opt, standing for Elliptic Curve Schnorr Digital Signature Algorithm optimized version, except that EC-Schnorr outputs $H(M\mathbin\|Q_x)$ but EC-SDSA-opt outputs $H(Q_x\mathbin\|M)$.
    ISO/IEC 14888-3 also defines EC-SDSA which outputs $H(Q_x\mathbin\|Q_y\mathbin\|M)$.
    The BSI's current specification now matches the definition of EC-SDSA in ISO/IEC 14888-3.
  • The question's libsecp256k1 (possibly matching this source) is similar to ISO/IEC 14888-3's EC-FSDSA (where the F stands for full), except that libsecp256k1 outputs (and later hashes) $Q_x$ where EC-FSDSA uses $Q_x\mathbin\|Q_y$. It follows that EC-FSDSA has a significantly larger signature than libsecp256k1 does (for $b$-bit security it is $6b$-bit, rather than $4b$-bit).

There are more variants related to libsecp256k1. A comment links to BIP-Schnorr.

Summary of the schemes discussed: $$ \begin{array}{l|rllr} \text{scheme}&\text{public}&\,\,\,\text{ first}&\,\,\text{ second}&\text{sign. }\,\\ &\text{key }\,\,&\text{component}&\text{component}&\text{size }\,\,\,\\ \hline \text{[Sc91]}&-d\,G&H(Q,M)&k+d\;h&b+2b\\ \text{EC-SDSA}&-d\,G&H(Q_x\mathbin\|Q_y\mathbin\|M)&k+d\;h&2b+2b\\ \text{EC-SDSA-opt}&-d\,G&H(Q_x\mathbin\|M)&k+d\;h&2b+2b\\ \text{EC-FSDSA}&-d\,G&Q_x\mathbin\|Q_y&k+d\;H(Q_x\mathbin\|Q_y\mathbin\|M)&4b+2b\\ \text{EC-Schnorr old}&d\,G&H(M\mathbin\|Q_x)&k-d\;h&2b+2b\\ \text{libsecp256k1}&d\,G&Q_x&k-d\;H(Q_x\mathbin\|M)&2b+2b\\ \text{BIP-Schnorr}&d\,G&Q_x&k+d\;H(Q_x\mathbin\|\text{Pub}\mathbin\|M)&2b+2b\\ \end{array} $$

  • $M$ is the message to be signed.
  • $G$ is the group generator.
  • $k$ is the secret drawn by the signer (randomly or pseudo-randomly) at each signature.
  • $Q=k\,G=\underbrace{G+\ldots+G}_{k\text{ terms}}$.
  • $Q_x$ (resp. $Q_y$) is the $x$ (resp. $y$) component of $Q$ as a bytestring.
  • $b$ is the intended security in bits; the group size $n$, $Q_x$ and $Q_y$ are about $2b$-bit.
  • $H$ is the hash function, and $h$ is the result of the hash, often also the signature's first component. For $\text{[Sc91]}$, $h$ is $b$-bit wide, and the input of $H$ combines an unspecified fraction of $Q$ with $M$. In other schemes, $h$ is $2b$-bit wide.
  • $\text{Pub}$ is the public key. Including it in the hashed data simplifies (perhaps strengthens) security reduction in a multi-users configuration.
  • An implicit $\bmod n$ is omitted for the signature's second component.
  • Conversion between integer and bistring is omitted (though essential for interoperability).

$\text{[Sc91]}$ is Claus-Peter Schnorr, Efficient Signature Generation by Smart Cards, in Journal of cryptology, 1991; refer to this for an exposition and more bibliography.

In $\text{EC-Schnorr}$, the signature's first component is an ASN.1 integer rather than a bytestring.

$\text{EC-Schnorr}$ (resp. $\text{EC-SDSA}$, $\text{EC-SDSA-opt}$, $\text{EC-FSDSA}$ ) have registered Object IDentifier 0.4.0.127.0.7.1.1.4.3 (resp. 1.0.14888.3.0.11, 1.0.14888.3.0.13, 1.0.14888.3.0.12).

These 7 schemes are incompatible; Andrew S. Tanenbaum's "The nice thing about standards is that you have so many to choose from" is an understatement!

ETSI's Electronic Signatures and Infrastructures (ESI); Cryptographic Suites TS 119 312 V1.2.1 (2017-05) states:

For interoperability reasons only one version (EC-SDSA-opt) from the EC-XDSA Schnorr variants defined in ISO/IEC 14888-3 is selected by the present document. EC-SDSA in the optimized version has the small advantage of minimal data transfer for smart cards.

but that rationale works only against EC-FSDSA as far as I can tell. If the Smart Card itself computes or verifies the signature, as it should, what's transferred is the signature, which is $4b$-bit in both EC-SDSA-opt and EC-SDSA.

Hashing $M$ first is a specificity of EC-Schnorr; my guess is that it was designed for constrained environments like Smart Cards, where it allows offloading the bulk of the hashing of $M$ externally (also, on a multicore CPU, that allows hashing $M$ in a separate thread). As long as the hash is secure, it should not make any difference in security.

| improve this answer | |
$\endgroup$
6
$\begingroup$

The $(r,s)$ version in theory is more secure than $(h,s)$. Bellare, Namprempre, Neven 2004 paper "Security Proofs for IBI and Signature Schemes" showed that Schnorr signature in the form of $(r,s)$ (which they named as BNN signature) can achieve semi-strong unforgeability (ss-euf); while the signature in the form of $(h,s)$ can only achieve normal unforgeability.

The security proof of the ss-euf can be found related to the security of Okamoto-IBI and BNN-IBI in the paper. These 2 IBI schemes are not captured by the transformation framework which transform a standard identification scheme to IBI. So they need to provide direct proofs, by considering additional security from the underlying standard signature scheme, which is the BNN signature. In order for the 2 IBI to be secure, the underlying signature has to be at least semi-strong secure, that is why the authors showed the security of semi-strong for the signature.

Back to Schnorr signature, in the non-EC version, $(r,s)$ is $(Q,s)$, whose size is significantly larger than that of $(h,s)$ and not preferable in practice. In EC version both are of the same length, but I guess $(r,s)$ would be slower during verification. If there is no limitation on verification side, I would prefer to use $(r,s)$ due to its stronger security property.

| improve this answer | |
$\endgroup$
  • $\begingroup$ I saw the paper you are referring to, where exactly the authors point out that $(h,s)$ is more secure than $(r,s)$? $\endgroup$ – 111 Mar 10 '17 at 12:07
  • 1
    $\begingroup$ It is in Section 6.1, pg. 39. The BNN signature can be proven secure in the ss-euf-cma because the hash value $h$ for message is still unknown to the forger, even the signature $(r,s)$ of the message is known to the forger. If the signature is $(h,s)$, the same trick cannot be used. $\endgroup$ – Tan Mar 11 '17 at 14:20
  • $\begingroup$ Here is the paper :iacr.org/archive/eurocrypt2004/30270269/bnn.pdf There is not section 6.1 either page 39. Can you provide the link of the paper you are talking to? $\endgroup$ – 111 Mar 11 '17 at 22:04
  • 1
    $\begingroup$ The full version is here: eprint.iacr.org/2004/252.ps $\endgroup$ – Tan Mar 13 '17 at 6:56
  • 1
    $\begingroup$ @Tan, answering above comment: yes $4\log_2(q)$-bit is calculated using both coordinates, because that's what the standardized EC-FSDSA does (see my answer). I do agree that $r$ can be represented by using only the x-coordinate plus 1 bit. And it does not seem that omitting this 1 bit (as performed in the question's libsecp256k1 description) removes much security. $\endgroup$ – fgrieu♦ Jul 17 '17 at 22:56
3
$\begingroup$

Probably the most widely deployed Schnorr-type signature scheme over elliptic curve groups today is EdDSA, in its instantiation Ed25519 over Curve25519 with SHA-512. A public key is the encoding of a point $A$ in the $\mathbb F_q$-rational points of an elliptic curve $E/\mathbb F_q$ of order $h \ell$ for large prime $\ell$, over a finite field of odd prime power $q$; a signature on a message $m \in \{0,1\}^*$ is a pair $(R, s)$ of a point $R \in E(\mathbb F_q)$ and a scalar $s \in \mathbb Z/\ell\mathbb Z$ satisfying $$[h \cdot s]B = [h] R + [h \cdot H(\underline R \mathbin\Vert \underline A \mathbin\Vert m)]A$$ where $B \in E(\mathbb F_q)$ is the standard base point of order $\ell$ and $H\colon \{0,1\}^* \to \mathbb Z/\ell\mathbb Z$ is a uniform random function. The signer knows the secret scalar $a \in \mathbb Z/\ell\mathbb Z$ such that $A = [a]B$; choosing $r = H(k \mathbin\Vert m)$ and $R = [r]B$, where $k$ is a long-term secret, the signer can then compute $$s \equiv r + H(\underline R \mathbin\Vert \underline A \mathbin\Vert m) \cdot a,$$ which straightforwardly satisfies the verification equation.

In your notation, this corresponds to

  1. $k$ chosen pseudorandomly from $m$ via long-term secret
  2. $Q = [k]G$
  3. $h = H(\underline Q \mathbin\Vert \underline{[d]G} \mathbin\Vert m)$
  4. $s \equiv k + h \times d \mod n$
  5. Output $(\underline Q, s)$

Here $\underline Q$ denotes the standard encoding of the point $Q$, which consists of an encoding of its $x$ coordinate and a single bit for the sign of its $y$ coordinate.

Choosing $k$ as a pseudorandom function of the message under a long-term secret obviates the need for an entropy source at signing time. Hashing the public key $[d]G$ into $h$ limits the malleability of public keys and provides confidence in multi-user security of the system. Encoding $Q$ instead of $h$ enables fast batch verification, though I'm not sure I've ever heard of anyone caring about that in practice. Since $H$ need not be collision-resistant, you could follow Schnorr's original recommendation to save space in signatures by using a smaller, say 128-bit, hash, and transmitting $(h, s)$ instead of $(\underline Q, s)$—but the size benefit in the elliptic curve setting is modest, and the multi-user security story isn't as clear.

More discussion of the design space.

| improve this answer | |
$\endgroup$
0
$\begingroup$

The original Schnorr signature is byproduct of the Schnorr id-signature scheme using the Fiat-Shamir trick. The construction was given in the paper of C.P.Schnorr. In the signature Scheme the output is $(h,s)$ and not $(r,s)$. So I would prefer the first implementation.

| improve this answer | |
$\endgroup$

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.