Brandon Goodell – Monero Research Labs

Expensive Coffee: Exploiting Subgroup Cofactors for Fun and Profit

The Monero cryptocurrency uses the elliptic curve group of Ed25519 for when constructing linkable ring signatures. The number of group elements in this elliptic curve group is 8p where the prime p = 2^252 + 27742317777372353535851937790883648493, so it should be clear that the (large) prime subgroup has cofactor 8. This introduces some implementation pitfalls; we show how a double-spend bug disclosed to the Monero development team in February of 2017 vitally depended upon this subgroup cofactor and was not exploited before being fixed. Lastly, we briefly describe the titular Ristretto, a technique for constructing prime-order elliptic curve groups from non-prime elliptic curve groups. Ristretto leverages isogenies between the Jacobi Quartic, the Montgomery curve, and the twisted Edwards curve, taking advantage of the 2-torsion property of the Jacobi Quartic to “kill” all small-order elements, eliminating cofactor-related implementation dangers.