Bytewise signature malleability

[twitchyliquid64]

Firstly, I apologize if this is a stupid question! I'm very much trying to learn but crypto implementation details are all very new.

Given knowledge of a valid signature + its message + the verification key, can an attacker produce a valid signature with a different bytewise encoding? (i.e. a digest over the message + signature would change)

I'm assuming honestly-generated signing/verification keys outside of attacker influence. EG: calling GenerateKey using crypto/ed25519.

I was originally thinking the answer to this question would be 'no', but the zip 215 spec says that its not required that R be a canonical encoding. So couldn't an attacker represent R in a different encoding? (maybe finding such an encoding without knowledge of the signing key is infeasible?)

[twitchyliquid64]

Possibly answering my own question: R is part of the hashing computation for k so attackers can't fuck with it without breaking the signature?

[FiloSottile]

Hi! That's a good question! Honestly generated signatures are not malleable because of two reasons:

• First, as you point out, the original encoding of R is hashed into k (not its canonical re-encoding)

https://github.com/hdevalence/ed25519consensus/blob/c00d1f31bab3e2c79c55705ad930e04e241d3451/ed25519.go#L36

• Second, the only points that have non-canonical encodings are those with a y coordinate between 2^255-19 and 2^255-1, or those with x equal to 0, and a honestly generated signature has negligible probability of generating such an R