# [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
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.
```