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?

Ie. That no other signature exists that could be validated with the public key counterpart to the private key that created the signature.

$\endgroup$
  • $\begingroup$ Related Why is EdDSA collision-resilient with SHA-512? $\endgroup$ – kelalaka Jul 6 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 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 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 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 at 14:05
2
$\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$
  • $\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 at 14:07
  • $\begingroup$ @Woodstock this is what I think for cofactorless verification. $\endgroup$ – Ruggero Jul 6 at 19:29

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.