3
$\begingroup$

An EdDSA signature is (R, S) where R = r*B and S = r + H(R, A, M)*s. Notation from Wikipedia en.wikipedia.org/wiki/EdDSA.

Given that the hash function H, is indeed collision-resistant, would using S = r + H(A, M)*s be a secure variant?

In the original EdDSA paper, the authors mention the need for R to protect the signature scheme in case the hash function is not collision-resistant. To me, it indicates that the scheme could possibly be secure even when R is left out from the hash function input.

The reason I ask (in case it is of interest) is that using H(A, M) would be more threshold-friendly. Threshold signatures with that modification in place could be done using 1 round instead of 2 rounds.

$\endgroup$
6
$\begingroup$

This answer is assuming you are not removing the private key $a$ from the computation of $S$, and instead actually meant what is said in the title of the question:

$S = r + a H(A, M)$

Removing $a$ from the computation would be terrible.


The first issue that comes to mind is malleability, on top of collision resistance.

The signature process for EdDSA actually goes as follows:

Input: message $M$, secret key bits $(h_0, h_1, \ldots, h_{2b-1})$, basepoint $B$ and public key point $A$

  1. $a \gets 2^{b-2} + \sum_{3 \leq i \leq b-3} 2^i h_i$
  2. $h \gets H(h_b,\ldots,h_{2b-1},M)$
  3. $r \gets h\mod \ell$
  4. $R \gets r\cdot B$
  5. $h \gets H(R, A, M)$
  6. $S \gets (r + a h) \mod \ell$

Return: $(R,S)$

As you can see, if you do not include the value $R$ in the hash $h$, the value $S \gets (r + a h) \mod \ell$ can easily be modified in a way that would allow to produce new signatures for the same message:

  1. pick a random $k$
  2. compute the point $R' = R + k\cdot B$
  3. compute the value $S' = S + k \bmod \ell$

And you now have a new, different signature $(R', S')$ for the same public key $A$ that will verify for the message $M$. This is possible because the value $r$ behind computed with the secret key, it is not meant to be public and is not necessary for verification. This property was used in a fault attack in 2017.

Malleability is not necessarily unwanted in cryptographic scheme, but is often frowned upon since it can very easily lead to issue with implementations.

Threshold cryptography is rough and full of dangers, and I wouldn't advise coming up with a malleable scheme as these have already proven to cause issue with threshold schemes.

$\endgroup$
2
  • $\begingroup$ Thank you for the answer and for assuming a correcting of the question. Yes, I did not intend to remove the secret key! $\endgroup$ – Frans Lundberg Feb 10 at 17:34
  • $\begingroup$ @Lery I see malleability, I did not even think of it, thank you. That alone would not make it broken it as someone still cannot forge a signature for a message that the owner of key has not signed. It makes the scheme resistant to existential forgery (cannot forge a valid signature on message not signed by the owner) but not to strong existential forgery (can produce a valid signature of message that the owner has not produced) $\endgroup$ – Manish Adhikari Feb 11 at 11:42
4
$\begingroup$

would using S = r + H(A, M) be a secure variant?

Actually, it would become trivial to generate a signature for an abitrary message with just the public key.

The verification check would be:

$$2^h s G = 2^h R + 2^h H(A, M) A$$

where $h$ is the curve cofactor, $G$ is the curve generator, $A$ is the public key, $M$ is the message and $(R, s)$ is the signature.

So, what the attacker ould do is pick an arbitrary $s$ and try to solve:

$$2^h sG - 2^h H(A, M)A = 2^h R$$

Everything on the right side is known, and so it's easy to find an $R$ that satisfies this ($sG - H(A, M)A$ is one solution)

$\endgroup$
3
  • $\begingroup$ Oh my, I got carried away, because indeed if one is removing $a$ altogether, then it's completely broken. $\endgroup$ – Lery Feb 10 at 15:49
  • $\begingroup$ Sorry about the mistake. Of course, the secret scalar, s, must of course be included. I did a quick edit of the question. My 2-year old is disturbing me, so I hope I got it right now. $\endgroup$ – Frans Lundberg Feb 10 at 17:31
  • $\begingroup$ @FransLundberg: same answer; to verify, just write out the verification condition, and see if you can solve for $R$ (given everything else is known) $\endgroup$ – poncho Feb 10 at 17:50

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.