3
$\begingroup$

Taking EdDSA as an example, given the length of a signature is 512-bits for a given data payload, what is the probability of a collision where there is another 512-bit value that is also a valid signature?

With symmetric crypto we know there is only one single key in the entire space that will validly decrypt data encrypted with the same key.

Can we provably state that for a given payload and given private key, there is only one valid signature in the 512-bit signature space? That is, no other signature exists that could be validated with the public key counterpart to the private key that created the signature.

Improve this question
$\endgroup$
5
  • $\begingroup$ Related Why is EdDSA collision-resilient with SHA-512? $\endgroup$
    – kelalaka
    Jul 6, 2020 at 10:20
  • 1
    $\begingroup$ "With symmetric crypto we know there is only one single key in the entire space that will validly decrypt data encrypted with the same key." - we know this? What's the proof (say, for AES)? $\endgroup$
    – poncho
    Jul 6, 2020 at 12:01
  • $\begingroup$ @poncho wow ok, so it's not provable that for say, 256-bit AES (or ChaCha) that there is definitely only 1 key in 2^256 permutations that will decrypt correctly? If so why do we say symmetric crypto has a bit-strength of 2^X where X is the key size?? $\endgroup$
    – Woodstock
    Jul 6, 2020 at 13:58
  • $\begingroup$ @Woodstock: because we don't know of any attack that will decrypt an unknown (or partially unknown) message faster than that... $\endgroup$
    – poncho
    Jul 6, 2020 at 14:03
  • $\begingroup$ right but I didn't know that was an assumption (based on empirical evidence and deduction of the key space) rather than a hard fact, so we are assuming AES-256 (for example) has an approximate brute force difficulty of 2^256 key, but it's not proven!? Surprised I don't see this caveat, that it's based on assumption there may be multiple keys in the space that decrypt correctly?...thanks for helping me learn $\endgroup$
    – Woodstock
    Jul 6, 2020 at 14:05

1 Answer 1

Reset to default
3
$\begingroup$

Can we provably state that for a given payload and given private key, there is only one valid signature in the 512-bit signature space?

No. If you consider EdDSA verification a legitimate signer can generate more than one signature of a given message, and all will pass EdDSA verification. However, only the signature generated with the EdDSA signing procedure will pass cofactorless verification.

More details about how to generate alternative valid signatures are provided in this answer.

Regarding the more broader question:

Taking EdDSA as an example, given the length of a signature is 512-bits for a given data payload, what is the probability of a collision where there is another 512-bit value that is also a valid signature?

Requiring specifically to pass cofactorless verification only (to avoid the other valid signatures generated by the above technique), there should be a valid $S$ for each possible value of $r$. Since $R$ depends fully on $r$, and $0 \le r < L$, there are at least $L$ possible valid signatures, where $L$ is the order of the large prime subgroup. For ed25519, $L = 2^{252}+27742317777372353535851937790883648493$

Improve this answer
$\endgroup$
2
  • $\begingroup$ Ah great, thanks @Ruggero, so it's at least unique within the finite cyclic group for Ed25519, but not in the 2^512 signature space, would that be a fair summation? $\endgroup$
    – Woodstock
    Jul 6, 2020 at 14:07
  • $\begingroup$ @Woodstock this is what I think for cofactorless verification. $\endgroup$
    – Ruggero
    Jul 6, 2020 at 19:29

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.