Studying different implementations of Ed25519 I see that some of them check the order and canonicity of input public key and signature and some other not. Why this difference? Are these tests relevant in the sense that points specially chosen points to be non-canonical or have an small order reduce the strength of the algorithm against forgery or tampering?
$\begingroup$
$\endgroup$
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
2
Public key: Generally, no. If a legitimate signer is trying to pull a fast one on you, they already have the power to sign messages that you will accept. So why would they bother feeding you a point that is not generated by the standard base point, when they could just feed you bogus signed messages?
Signature: Generally, no. The verification equation for a signature $(R, s)$ under public key $A$ on a message $m$, where $A$ is a curve point, $R$ is a curve point, $s$ is a scalar, and $m$ is a bit string, is $$[8 s] B = [8] R + [8 H(R, A, m)] A.$$ If $A$ is an 8-torsion point, then the legitimate signer is already pulling a fast one on you—$(\mathcal O, \ell)$ is a valid signature on any message $m$. If two points $R$ and $R'$ differ by an 8-torsion point, i.e. if $[8](R - R') = \mathcal O$, then they will both make valid signatures—meaning if a forger could forge one they could forge the other. But a forger who doesn't know one signature to begin with still can't find one in the first place.
I add the ‘generally’ qualifier because maybe you rely on some properties that signature schemes are not generally expected to provide, such as uniqueness of signatures—as noted, it is easy given a signature $(R, s)$ under $A$ on a message $m$ to find another signature $(R', s') \ne (R, s)$ under $A$ on $m$: pick $s' = s$ and $R' = R + Q$, where $Q$ is any 8-torsion point other than the identity $\mathcal O$. The assumption of signature uniqueness caused Monero some trouble last year, but most applications do not rely on this.
answered Feb 15, 2018 at 2:46
-
$\begingroup$ Thanks. Bibliography over the wire is nor explicit enough in their conclusions. I just wanted a clear and justified answer to be sure that the code I'm using (not writing) is good for my purposes. $\endgroup$ Feb 15, 2018 at 10:55
-
1$\begingroup$ The informal argument in the answer for the "Public key" is fairly coarse, and can miss existing attacks. For example, there are signature schemes (such as RSA) that allow an attacker to produce a new key pair that verifies for a given signature, allowing the attacker to falsely claim that it produced the signature. This lead to an attack, e.g., on an early version of Let's Encrypt; this and more examples: eprint.iacr.org/2019/779.pdf $\endgroup$– user4621Jan 4, 2021 at 9:29
$\begingroup$
$\endgroup$
A safe answer is: yes, unless you have a great reason to avoid them, make sure the checks are performed, because you might avoid a lot of problems later.
More detailed arguments are given here: https://eprint.iacr.org/2020/823 , which explains (and gives proofs for) the exact security impact of such checks. However, if you are unsure, best err on the safe side, and add the checks; or just use Ed25519-LibSodium that does the checks for you.
If you can prove that your use case doesn't need the checks, you might be able to omit them, but it is rather subtle and experts have gotten it wrong before. Note also that the checks are computationally cheap (certainly compared to the other signature computations).
