On Cofactored Verification of EdDSA Signatures

Abstract

EdDSA is a Schnorr signature scheme instantiated on top of Edwards curves, which admit fast, constant-time arithmetic, but suffer from the presence of a non-trivial cofactor, where the order of the group of points is a large prime times a small integer ($4$ or $8$). Current standards permit for points present in the signature (commitment and/or public key) to have a component in the small-order subgroup of the group of points. This is done by sanctioning two variants of the signature verification equation and specifying precedence of one over the other. This last point, however, seems to be widely misunderstood and the two variants are given equal footing, allowing different ``compliant'' implementations to use different verification algorithms. This in turn lets malicious actors create signatures which are accepted by some parties, but rejected by others, threatening, e.g., consensus in a blockchain network setting. We add to the discussion on practical consequences of such discrepancies by formulating the consensus problem in the context of load-shedding attacks. We argue that the standards \emph{are} in fact very specific about the set of valid signatures, despite lacking in explicitness and emphasis. We further show that two mainstream cryptographic libraries, namely, OpenSSL and CIRCL, accidentally (and in a manner not immediately apparent when inspecting the code) use the correct variant of the verification equation for one parameter set of EdDSA, but incorrect for another. In OpenSSL, this is traced back to careless copying of refcode. We conclude by proposing remedies to the chaotic status quo described.