[tor-dev] HS desc replay protection and ed25519 malleability
Taylor R Campbell
campbell+tor-dev at mumble.net
Wed Apr 18 15:19:51 UTC 2018
> Date: Wed, 18 Apr 2018 16:53:59 +0300
> From: George Kadianakis <desnacked at 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
- 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
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
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
- Same goes for the public key A.
More information about the tor-dev