3
$\begingroup$

I've got a question regarding the signing algorithm on elliptic curves (EdDSA). In ed25519 signature scheme there is no nonce $k$, instead every message has its own different hash. From what I know the $s$ value of the signature is computed as following:

$$s = r_\mathrm{val} + h(r_\mathrm{val} * G \mathbin\| \mathrm{pub} \mathbin\| m)\cdot d\label{q1}\tag{1}$$

where $d$ is user private key, $r_\mathrm{val}$ is generated with the hash of private key and message, $G$ is the base point and $\mathrm{pub}$ is user's public key. The signature is pair of values: $\left(r_\mathrm{val}*G,\;s\right)$.

I wonder if this can be broken when you use $r_\mathrm{val}$ as the hash multiplier and $d$ as addition as following (swapping $r_\mathrm{val}$ and $d$ places):

$$s = d +h\left(r_\mathrm{val}*G \mathbin\| \mathrm{pub} \mathbin\| m\right)\cdot r_\mathrm{val}\label{q2}\tag{2}$$

Of course you could verify. The signature is pair of values $(R=r_\mathrm{val}*G,\;s)$. Having the signature, let's multiply both sides of $\ref{q2}$ by $G$:

$$\begin{align}s * G &= (h(r_\mathrm{val} * G \mathbin\| \mathrm{pub} \mathbin\| m) \cdot r_\mathrm{val}) * G + d * G\\ &=h(r_\mathrm{val} * G \mathbin\| \mathrm{pub} \mathbin\| m)*(r_\mathrm{val} * G) + d * G\\ &=h(R \mathbin\| \mathrm{pub} \mathbin\| m)*R+ \mathrm{pub}\label{q3}\tag{3} \end{align}$$

So the signature is valid when multiplying $R$ by the recomputed hash value and adding the public key gives value of $s*G$

Are there any vulnerabilities regarding this modified signature scheme? Could the attacker recover $d$ value when having more than one signature pair?

$\endgroup$
2
  • $\begingroup$ [Note: this issue in the original question is now fixed] This is a variation of EdDSA, not of ECDSA. Notice that in EdDSA and the question, the input of the hash depends on the ephemeral elliptic curve point (here $r_\mathrm{val}*G$), when it does not in ECDSA. $\endgroup$
    – fgrieu
    Commented Jan 12 at 16:08
  • $\begingroup$ I took the liberty to revise the question so that capital letters are used for all elliptic curve points, and making it more apparent that we can recompute the hash in the verification procedure, without knowing the ephemeral secret $r_\mathrm{val}$. Also I used $*$ for scalar multiplication of elliptic curve point, $\cdot$ for multiplication in the field $\mathbb F_n$ (with $n$ the prime order of $G$). $+$ remains used both for addition in $\mathbb F_n$ and elliptic curve point addition. The verification is feasible and always succeeds absent alteration. $\endgroup$
    – fgrieu
    Commented Jan 17 at 12:24

1 Answer 1

2
$\begingroup$

This looks secure. It's easier to analyze if you treat this as modifying the Schnorr protocol since it's a simpler protocol and EdDSA is roughly based on it, just replacing the challenge with a hash of the message.

In Schnorr (https://crypto.stanford.edu/cs355/19sp/lec5.pdf) the prover is proving that they know the discrete-log of a public key, $\mathsf{pub}=G^d$.

To do so, the prover samples $r\leftarrow Z_p$, computes $R=G^r$ and sends $R$ to the verifier. The verifier sends back a random challenge, $c$. The prover then computes $s=r+cx$ and the verifier verifies that $G^s=R\mathsf{pub}^c$.

This protocol is secure because it is zero knowledge (proven through "honest verifier" zero knowledge, HVZK) and sound (via "special soundness"). Honest verifier ZK is exactly what it sounds like (the verifier is always honest (but curious)) and a simulator gets the challenge in advance and must create a transcript without knowing the secret, $d$. Special soundness is where we must be able to extract the witness given two accepting transcripts with the same first message but different challenges (sometimes generalized to $n$ transcripts).

We can see that your modification (setting $s=d+cr$) satisfies both these properties:

If we have two accepting transcripts ($R,c,s$ and $R,c',s'$), we can extract $d$ by doing $d=cc'(s/c-s'/c')/(c'-c)$. Verifying this:

$d=cc'((d+cr)/c-((d+c'r)/c')/(c'-c)$

$d=((d+cr)c'-((d+c'r)c)/(c'-c)$

$d=(dc'+cc'r-dc+cc'r)/(c'-c)$

$d=(dc'-dc)/(c'-c)$

$d=d(c'-c)/(c'-c)$

Then, we can satisfy HVZK by setting $s$ randomly, then computing: $R=(G^s/\mathsf{pub})^{1/c}$, which is identically distributed to a real transcript.

This shows that the ZK protocol underlying the signature scheme is secure. I'm not entirely sure how that translates to security for the signature scheme, but I'd guess it means it's secure. When you transform this into EdDSA, the challenge, $c$ would be $c=h(G^r||\mathsf{pub}||m)$

$\endgroup$
1
  • $\begingroup$ Going from the security of the HVZK to the security of the signature scheme is thru the Fiat-Shamir heuristic (or transform), and identical in EdDSA and the question's scheme. The classic reference is David Pointcheval and Jacques Stern: Security Proofs for Signature Schemes, in proceedings of Crypto 1996 (open access). There's also a treatment in many textbooks, e.g. Dan Boneh and Victor Shoup's Graduate Course in Applied Cryptography. $\endgroup$
    – fgrieu
    Commented Jan 18 at 8:29

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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