Date: Wed, 18 Apr 2018 16:53:59 +0300 From: George Kadianakis desnacked@riseup.net
In this case, we can't use S as the replay cache index since the attacker can mutate it and still get the sig to verify. Can we use R as the replay cache index then? Can an attacker given (R,S) find (R',S') such that the sig still verifies?
The verification equation is
8*S*B = 8*R + 8*H(encode(R) || encode(A) || m)*A.
B is the standard base point of order l; 8 is the cofactor; A is the public key, a curve point; m is the message; (encode(R), encode(S)) is the signature, for R a curve point and S an integer.
Here's the leeway, if I haven't missed anything:
- The verification equation is true for any representative of the coset S + lZ.
Since l ~ 2^252 + 2^125, only about one in 2^127 possibilities _doesn't_ have two 252-bit integer representatives, and they all have a handful of 256-bit ones. (This is what you already discussed.)
- Each choice of R and m uniquely determines an equivalence class of values of S, the coset S + lZ.
The signer with knowledge of the private key can, using a nonstandard procedure, pick R = r*B for arbitrarily many different r on a single m and compute the corresponding S, yielding any of about l ~ 2^252 different valid signatures on on m. (They could even reuse R from one message to another, and leak their private key with wild abandon!)
If the signer with knowledge of the private key is in your threat model, the two possible 252-bit representatives of S + lZ are the least of your concern! If you want there to be a verifiably _unique_ signature on each possible message, you might just want a VRF like VXEdDSA.
- There may be multiple possible encodings of the point R, but only one canonical one, which figures into the hash.
If you accept a non-canonical one, decode it, and _re-encode_ it into the canonical one for H, then an attacker may have some leeway to vary R. (This would be a little stupid! But it's not unimaginable.)
The standard encoding, if I recall correctly, is the little-endian encoding of the integer
2^255 sgn x(R) + rep y(R),
where sgn x(R) is a single bit specifying which of two possible choices of x(R), and rep y(R) is the least integer representative of the y coordinate of R, which is always 255 bits. There are 19 field elements with two 255-bit integer representatives: 0 and 2^255 - 19, 1 and 2^255 - 18, 2 and 2^255 - 17, ..., 18 and 2^255 - 1.
This is unlikely to happen, because if you picked one of these, you would have to find log_B R in order to get an S to make a working signature.
- Same goes for the public key A.