Curves with a Twist

Ripple Labs is considering the addition of a new elliptic curve implementation to the Ripple protocol to complement the existing cryptographic system. The addition of a Schnorr-based cryptosystem will produce more optimal and secure design schemes and provides a platform for robust and sophisticated functionality while preserving existing network structure and efficiency.

Currently, the Ripple protocol uses Koblitz curves with secp256k1 parameters and ECDSA signatures as defined in the Standards for Efficient Cryptography (SEC) by Certicom, which is the same cryptosystem that powers Bitcoin.

After months of analysis and testing, we’ve concluded that a Schnorr-based cryptosystem will greatly enhance the security, flexibility, and performance of the Ripple protocol. The system we’re currently testing is Ed25519.

The Ed25519 cryptosystem was designed by prominent cryptographer Daniel J. Bernstein. It consists of Curve25519, a Twisted Edwards curve, in conjunction with the Schnorr signature scheme. Ed25519 addresses many of the ongoing security concerns surrounding commonly used cryptosystems, which Bernstein outlines in a March blog post, and avoids several design constraints inherent to secp256k1 ECDSA. OpenSSH recently added support for Ed25519 based on this reasoning.

The elliptic curve: Curve25519

Image: secp256k1 (left) versus Curve25519 (right)

The open and transparent nature of how the curve parameters for Curve25519 were set mitigates the risk of a potential backdoor.

Summary of advantages versus secp256k1:

• Large absolute value for the CM field discriminant (large |D|)—although there is no evidence of security problems with small |D|.

• Supports simple, fast, complete constant-time single-scalar multiplication using a Montgomery ladder.

• A random curve point can be represented in a way that’s indistinguishable from random data.

• Faster performance (see below)

Our initial tests and analysis suggest significant performance gains with the new curve. Curve25519 halves verification time versus secp256k1 based on efficient implementations of both curves. These results were achieved with lower variance, which point to the constant time properties of Curve25519.

Also, the default signature format for Ed25519 allows batch signature verification, which promises twice the performance of DSA.

Benchmarking

• Raw test results
• Benchmark source code

In combination, the new curve implementation is expected to quadruple performance versus secp256k1 based on our preliminary benchmarking.

The signature scheme: Schnorr

The Schnorr signature scheme also adds key benefits in comparison to ECDSA. Adam Back, the inventor of Hashcash (the proof-of-work system used in Bitcoin), sums up the benefits of Schnorr as follows: "simple blinding, compact multi-sig, clearer security proofs, better security margin, less dependence on hash properties."

Summary of advantages versus ECDSA:

• Simpler to securely implement
• Composable threshold signatures without multi-party computation
  • Verification happens off-network allowing for sophisticated functionality without increasing network load or complexity
  • Conducive to highly distributed systems
• Less constraints allows for more optimal and secure design schemes

DSA schemes are difficult to manage because the schemes are easy to get wrong. An improper implementations is trivial to break, and what might seem like a minor misstep can precipitate a system-wide vulnerability—as demonstrated by the highly publicized Playstation hack in 2012.

Hackers were able to access full control of the PS3 employing “simple algebra” after Sony set a constant in its custom DSA implementation instead of a randomly generated number. The sensitivity of DSA signatures to human error allowed this single oversight to fully compromise the console’s encryption protections, exposing the platform and Sony’s partners to the perpetual threat of piracy.

Alternatively, Schnorr signatures are more forgiving and simpler to implement because its security is inherently more robust based on the scheme’s dynamic hash function. The ephemeral public value r is tightly bound to the message, which means that the security of the scheme is no longer dependent on the collision resistance of the hash function.

Independent verification and combining

Another advantage of Schnorr is related to threshold signatures, a useful alternative to multi-signature schemes when multiple parties need to sign a message.

Multi-signature schemes require the network to verify each signature, increasing load with the number of participants. Conversely, threshold signatures are generated offline and result in a single signature regardless of total number of parties participating.

ECDSA can create threshold signatures, but requires multi-party computation. This means that the number of participants required to generate a signature without revealing their secrets is twice the number of shares required to recover the key. In contrast, Schnorr has no such restriction. Shares of a signature can be independently verified and then composed.

Incidentally, composable threshold signatures allow the integration of sophisticated new features with fewer design constraints—especially when considering highly distributed systems—while preserving existing network structure and efficiency.

Powering the future

Ed25519 allows more optimal designs regarding security, distribution, and, performance. The added flexibility will become increasingly relevant going forward as we supplement sophisticated functionality to the Ripple network—particularly in the area of smart contracts and oracle systems (such as Reality Keys, winner of the Startup Challenge sponsored by Ripple Labs at Bitcoin 2014 in Amsterdam)—where we have dedicated significant efforts behind the scenes.

We’ll provide an update of our progress in a future post.