2
$\begingroup$

ECDSA signatures are malleable. Given a valid signature (r, s), one can create a second valid signature by negating the s value.

I have searched workaround for this issue, and https://yondon.blog/2019/01/01/how-not-to-use-ecdsa says:

One solution to defend against signature malleability based attacks is to enforce a single canonical signature for a given public key and hash which is the approach taken by Bitcoin. More specifically, the Bitcoin core client software will only accept “low s-value” ECDSA signatures where a signature has a low s-value if s is less or equal to half the curve order [3]. The secp256k1 curve library used by the client will always generate signatures in low s-value form and the verifier expects provided signatures to also be in low s-value form [4].

Another solution is to avoid using signatures in identifiers or at the very least making sure to use unique values in the identifier creation process i.e. a nonce in the signed message. Unless there is a single canonical signature for a given public key and hash, signatures cannot be relied upon as unique identifiers.

What I wonder is, is it okay to use r-value instead of s-value for replay detection? One the first thought one should use s-value, because it is derived from a given message. r-value is not derived from a given message, but it uses k-value, which should be a random value. If duplicated k-values are used with same private key the key can be leaked, so signer have to generate distinct k-values. This makes me think r-value can be used to prevent replay attack.

Is there any problem if I use r-value to prevent replay attack?

Improve this question
$\endgroup$
4
  • $\begingroup$ It is already well known that random reuse can expose your private key. Which version do they use? RFC 6979 provides deterministic usage. This question-answer the attack $\endgroup$
    – kelalaka
    Mar 15, 2021 at 7:18
  • $\begingroup$ Also Is it safe to reuse a ECDSA nonce for two signatures if the public keys are different? $\endgroup$
    – kelalaka
    Mar 15, 2021 at 7:26
  • $\begingroup$ @kelalaka That is not quite the question being asked here. What is needed is a way to stop a signature being used to validate the same transaction twice. Cryptocurrencies keep a record of all signatures and so if the same signature is used twice the transaction can be blocked. Malleable signatures allow non-signers to generate other distinct signatures and submit the same transaction twice. $\endgroup$
    – Daniel S
    Mar 15, 2021 at 7:35
  • $\begingroup$ @DanielShiu Thank you for the comment. That is exactly what I asked. $\endgroup$
    – Plum Lee
    Mar 15, 2021 at 8:12

2 Answers 2

Reset to default
2
$\begingroup$

I have to be honest and say that I never really understood why systems use the signature as the record rather than just the hash of the message that was signed. If that was used, then there would be no problem with using malleable signatures. If someone has a reason why not to just do what I said, please let me know and I'll change the answer.

More to the point of the question, there is no reason why not to just use the $r$ portion. If this repeats in two different valid signatures, then the signers can each learn the other party's private key. This is because by dividing the $s$ portions in the signatures, the $k^{-1}$ part falls away. Then, given one of the private keys it is easy to learn the other private key. As such, this should not be a concern to anyone (i.e., if it could happen then malleability is far from the problem).

Improve this answer
$\endgroup$
5
  • $\begingroup$ Thank you. This answer is exactly same as me. For the hash of the message, I also want to use the hash of the message instead of the signature, but what we are working on is embedded device with little amount of computational power. r part of the message could be easily parsed from the given packet, but hashing message needs additional computation. If hashing is fast enough I would prefer hashing the message. $\endgroup$
    – Plum Lee
    Mar 15, 2021 at 8:11
  • $\begingroup$ What do you have in your system? Do you have the message and signature? You could always just store the hash as well. I guess if you don't want to waste that space, then you could just use $r$ as I pointed out. $\endgroup$
    – Yehuda Lindell
    Mar 15, 2021 at 8:13
  • $\begingroup$ I'm working on the IEEE 1609.2 vehicular communication, and what receiver got from the sender is a packet including message, signature, and the certificate. In my thought, since sender does not include a hash of a message in packets, even if receiver calculates and stores the hash of the message from a given packet, receiver still has to calculate hash of the message from any new packet to do a replay detection $\endgroup$
    – Plum Lee
    Mar 15, 2021 at 8:39
  • $\begingroup$ Upon receiving the message, the receiver has to calculate the hash anyway in order to verify the signature. Once it computes it, it can store it for replay detection. For any new packet, it has to verify the signature as well. The only thing you gain by what you are proposing is that you can do replay detection before verifying the signature. If that's important, then it makes sense. $\endgroup$
    – Yehuda Lindell
    Mar 15, 2021 at 8:50
  • $\begingroup$ Thank you, that makes perfect sense. $\endgroup$
    – Plum Lee
    Mar 15, 2021 at 9:18
1
$\begingroup$

There's one potential problem that I can foresee. If two users generate the same ephemeral $r$ and $k$ values (or $\ell -k$), an $r$-only scheme would flag these up as a replay even thought they are not. There should be a negligible chance of this happening, but given a common signature implementation with less than perfect random number generation and a large community of users it could happen, even if individual users take care never to repeat ephemeral values. This would also flag up to the two parties that they can each recover the others private key. Collisions between two different signing keys using $(r,s)$-replay detection should only be possible if the second signing key is specifically generated by someone in possession of the first signing key.

Improve this answer
$\endgroup$
4
  • $\begingroup$ Thank you for the reply. I have several related questions. ECDSA private key is known to be exposed when random value for r (that is, k) is reused. Could this imply that every user should always carefully generate random values? If that is the case then it might be reasonable to regard random values to be unique, and the collision of r-value will happen nearly the same probability to the s-value (which is related to hash output of the message). $\endgroup$
    – Plum Lee
    Mar 15, 2021 at 8:00
  • $\begingroup$ Every user should carefully generate $r$ values (they can do this deterministically by taking a secret hash of the message, or using strong random). If strong random values are used then we should not expect a reuse of $r$-values until we have seen $\approx\ell^{1/2}$ signatures and a similar value for $s$-value repeats, but we should not expect to see repeated $(r,s)$-values across the community until we have seen $\approx\ell$ signatures. I believe that repeated $(r,s)$-values is what it is currently checked for. $\endgroup$
    – Daniel S
    Mar 15, 2021 at 8:10
  • $\begingroup$ @DanielShiu As I point out in my answer, if you see a repeated $r$ then the private key of each party can be extracted by the other. Malleability is the least of your problems here. $\endgroup$
    – Yehuda Lindell
    Mar 15, 2021 at 8:14
  • $\begingroup$ @YehudaLindell Agreed. I also point this out in my answer. $\endgroup$
    – Daniel S
    Mar 15, 2021 at 8:26

Your Answer

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

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