Insecure signature verification algorithm for ed25519

[calctopian]

As currently implemented, the verification algorithm is not strongly unforgeable under chosen message attacks (SUF-CMA), that is, an adversary can construct an alternative signature for a given signed message; moreover, it doesn't provide guarantees of malicious strong universal exclusive ownership (M-S-UEO) to prevent key substition attacks. Furthermore, it doesn't guarantee Message-Bound Signatures (MBS), i.e., there exist no two distinct messages for which the same signature would verify with respect to a given (potentially maliciously generated) public key.

Warning: failing to patch this vulnerability could lead to double-spending attacks on cothority.

Fixed by pull request #427
Supersede issue #311

[ineiti]

Thanks for the warning for double-spending attacks ;) I'd have to look into our verifications to make sure this is not possible.

[calctopian]

About the exploitability of this issue:

If a malicious attacker adds one of points of the subgroups of small order (i.e., non-identity torsion points) to a key image, up to 7 double spends could be performed for each authentic spend on the cothority: this is now prevented by the Ge25519HasSmallOrder function.

This happens because multiplying the sum of a torsion point by a multiple of 8 and a "normal" point will return the same point, because multiplying small subgroup points by 8 returns the identity element. Without the function Ge25519HasSmallOrder, signatures verify on malicious key images derived from the authentic ones.

[ineiti]

Just for naming: cothority is the big project that includes a lot of smaller projects. The biggest of the smaller projects is byzcoin, which implements a blockchain using a BFT algorithm. So the attack would be against byzcoin.

I wonder how feasible such an attack would be, given that each transaction that is signed also has a nonce in it. So it is not possible to 'double spend' or 'replay' a transaction - you would need to be able to increase the nonce and still have a valid signature, which, if I understand the attack correctly, is not possible.

Also, can you please elaborate what you call a key image?

[calctopian]

Byzcoin using nonces is great because nonces provide extra protection: additionally, Byzcoin is using blscosi and not EdDSA as was previously used with cosi: thus transactions seem to remain safe from this attack.

But Darcs are broken, because their identities are using ed25519: although instead of using EdDSA, Darcs are using a compatible Schnorr signature scheme, also implemented in Kyber.

And Darcs are used everywhere, or even Schnorr (e.g., viewchanges, roster extension, authproxy, evoting, ...)

[ineiti]

As always, there is an issue for that: dedis/cothority#2186

[calctopian]

It's not the same thing: issue dedis/cothority#2186 is suggesting the introduction of a new darc-identity that uses EdDSA.

What I'm talking here is about fixing schnorr.Verify too, much like eddsa.Verify was being fixed by PR #427.

Fortunately, my latest commit also fixes schnorr.Verify: the awesome cothority is a bit more secure now :)