Ed25519 signature verification is not performed consistently by different implementations

[abacabadabacaba]

Different implementations of Ed25519 signature verification do not work in the same way. There are signatures that are accepted by some implementations but not the others. This may lead to multiple ways to attack the network:

• If some nodes accept a signature but other nodes don't, an attacker can submit such a signature to make them diverge.
• If some light clients don't accept signatures that are accepted by nodes, an attacker can prevent such light client from operating.
• If some light clients accept signatures that are not accepted by nodes, a malicious validator can present conflicting approval signatures to light clients without risk of being slashed.

At the moment, I am aware of the following implementation-specific behaviors:

• libsodium rejects signatures where either the key or the R value is a small-order point. This behavior is not prescribed by any standard.
• Both libsodium and ed25519-dalek check that sB = R + hA, rather than 8sB = 8R + 8hA. The latter equation, which is less strict, is prescribed by RFC 8032 and the Ed25519 paper, although both mention the former as an alternative.

This issue underscores the importance of having a full specification of all aspects of blockchain verification behavior, including all cryptographic operations. Merely pointing to external standards is not sufficient, because they may not prescribe a single correct behavior, and having such a behavior is necessary for consensus safety.

Note: in the past, Bitcoin had a similar issue with ECDSA-secp256k1 signatures that it uses. After that, new implementations were developed with the aim of having a consistent behavior across all implementation (and also preventing signature malleability, which fortunately doesn't affect the newer Ed25519 implementations). Therefore, the current use of ECDSA-secp256k1 signatures is likely not affected by a similar issue, but this still needs to be checked.

[SkidanovAlex]

Can those issues be handled by restricting what keys we accept for accounts / validators?

If no, what is the best course of action?
Shall we send a PR to dalek?

[abacabadabacaba]

I checked a few Ed25519 implementations, and here are the results:

• Checking that sB = R + hA is a common optimization used by all implementations that I checked. In fact, they compute R = sB ‒ hA and compare it with the value in the signature.
• Besides libsodium, ed25519-dalek rejects keys and Rs which are small-order points when using PublicKey::verify_strict(). We use PublicKey::verify(), which doesn't do that.
• In near-api-js, we use tweetnacl library. This library doesn't check that the value s is canonically encoded, so it may accept invalid signatures. However, it looks like no one uses near-api-js to verify signatures.

Overall, I think that the behavior of ed25519-dalek (specifically, PublicKey::verify() method, not PublicKey::verify_strict()) is good for us and we can state that all implementations that we use should behave in the same way. I already changed the Solidity implementation used by Ethereum bridge. If we actually make near-api-js verify signatures, we'll need to change it as well. Is there any other software that verifies signatures in NEAR?

[ilblackdragon]

@abacabadabacaba should we just switch to verify_strict?
Specifically, question if Ethereum adds pre-compile for ED25519 - how do we make sure right now that we are compliant with it?

CC @damons @nearmax @SkidanovAlex

[abacabadabacaba]

@ilblackdragon verify_strict() is not really strict, it actually rejects some potentially valid keys and signatures. I even filed an issue regarding this method's documentation: dalek-cryptography/ed25519-dalek#130.

Regarding Ethereum's EIP 665, it has a couple of problems: in addition to depending on libsodium's implementation with its nonstandard behavior, it requires the message to be exactly 32 bytes long for no good reason. Anyway, I don't think that we should adapt our behavior to an EIP that is not even accepted. By the time they accept it (if it ever happens), we may already switch to using aggregate signatures or even something different.

[MaksymZavershynskyi]

On a second thought, we might even switch the bridge.

[ilblackdragon]

So are we closing this issue and just document exact formula for verification? @abacabadabacaba

[abacabadabacaba]

Yes, and open separate issues for every implementation that doesn't follow the expected behavior. For near-api-js, this is near/near-api-js#343.