[tor-dev] HS desc replay protection and ed25519 malleability

[Taylor R Campbell]

> 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.