What implementions of Ed25519 exist?

Question

The new SQRL authentication scheme relies on Curve Ed25519 encryption developed by Daniel Bernstein. However, in order to start implementing this scheme there needs to be a mature implementation of Curve Ed25519 first.

Does anyone know of any mature, implementations? For Java, .NET or any other popular platform?

Tennietenniel

Curve25519 and Ed25519 implementations are usually different. They're using the same underlying curve, but in different representations. – Storebought

For a c implementation go with LibSodium, for .net the best version is probably my own, but it isn't really mature yet. – Storebought

For a stable .NET implementation of Curve25519 you can try my own version on GitHub. I have been using it in production without any issues. – Harrington

@Harrington That one isn't a constant time implementation. So it's potentially vulnerable to side channel attacks, especially those of the cross VM or cross process variant. – Storebought

@Storebought Thanks for pointing that out. I've implemented a timing attack countermeasure. Please feel free to review the change. – Harrington

@Harrington That change halved performance, but didn't really fix the side channels. The best solution is to remove all branches and array indices that depend on secrets. Alternatively you could use blinding, but I'm not a big fan of that. | I'm not sure if the side channels are actually exploitable. I suspect the timing side channel is not enough, but a cache based cross-VM attack seems more dangerous. – Storebought

@Storebought Thanks for the input. I decided to clone your constant time implementation from Gisthub. If you don't mind I'll do some changes to your code (like removing the unsafe code). – Harrington

@Harrington For my donna port you just need to comply with google's original BSD license, my contributions are public domain. It's probably a better idea to extract the code you want from Chaos.NaCl (which is entirely public domain). It doesn't contain any unsafe code in the first place, and it should be a bit faster. – Storebought

Answer 1

Curve25519 vs. Ed25519

First of all, Curve25519 and Ed25519 aren't exactly the same thing. They're based on the same underlying curve, but use different representations. Most implementations are either for Curve25519 or Ed25519, but it's possible to reuse some code between them.

It is possible to convert Ed25519 public keys to Curve25519, but the other way round misses a sign bit. i.e. two Ed25519 public keys correspond to a single Curve25519 public key. Private keys are very similar as well.

---

Concerning implementations it's important to distinguish between the actual implementation, and libraries that package them in usable form.

Actual implementations

djb's implementations in SUPERCOP

• Ref written in c, very slow
• djb's Ref10 written in c, decent performance
• djb's amd64-64-24k and amd64-51-30k, written in assembly, about twice as fast as Ref10

He also wrote an earlier, incompatible, prototype in NaCl, don't use that one

Floodyberry's donna implementation

Contains several variants, both assembly and c. Some optimized for 64 bit, some optimized for 32 bit.

Libraries

• LibSodium

  C library, currently uses Ref10 implementation

  Has bindings for many programming languages. It's probably the most popular version and what I recommend to most people.

  Contains a bunch of other crypto functions from NaCl, such authenticated encryption (XSalsa20Poly1305), hashes, Curve25519 key-exchange.

• Nightcracker's Ed25519

  C library, uses Ref10 implementation.

  Most interesting feature of this library is that it supports key-exchange using Ed25519 public keys. But it doesn't hash the shared key, so it doesn't produce the same shared secret as Curve25519.

  Contains pre-built binaries for Win32 and Win64.

• My C# port

  Pure managed code and works unchanged on 32 and 64 bit platforms. Based on Ref10. A bit slower than c implementations, but the difference is surprisingly small.

  Supports key-exchange compatible with NaCl using both Curve25519 and Ed25519 key and contains a bunch of other crypto functions from NaCl. I'm aiming for a similar feature set as LibSodium.

  The Ed25519 signature functions work and have seen a reasonable amount of tests, but other parts of the library are a bit rough.

• Directly using an implementation from SUPERCOP or Floodyberry's code.

  Probably requires a bit more work for building, but you'll get higher performance (~2x) and don't need to carry around code you don't need.

---

I recommend going with LibSodium for now. It's relatively popular and well maintained. Performance is decent, should only cause performance issues in really signature heavy applications.

Storebought

You say my implementation does not hash shared secrets, and doesn't produce the same results as Curve25519. However, I'm not aware of any Curve25519 implementation that hashes, nor is there a default hash function defined for Curve25519 output AFAIK, so I'm not sure whether I should add the hashing. – Courser

1) crypto_box_beforenm uses one specific hash 2) The Curve25519 paper describes a different hash. 3) You can skip the hashing if you only use the output of scalarmult as input for a KDF, which obviously does hash. – Storebought

In that case I'll keep it how it is right now - without hashing. That way you can be interoperable with all the other schemes as well as skip hashing when not needed. – Courser

@Codesinchaos Is there a nuget package for your C# port? – Epoch

@Epoch Not yet. I'll only create one once I finalize the API. – Storebought

Any chance that I could get a generalized ETA? – Epoch

@Epoch Unfortunately I have no clue. API design is hard and I don't know when I'll find the time refactor it. – Storebought

Is there any official source code repository where I can get the source for djb's Ref10 ? – Gazzo

Answer 2

Adding to CodesInChaos' answer:

Libraries

• My Java port

  Based on Ref 10, and provides the standard JCA APIs so it can be added to a crypto Provider.

Island

Hi, str4d Any hints or tips to port REF10 to JavaCard? – Rupe

Answer 3

By far the most mature and performant one is the one written by Daniel Bernstein himself. It can be found within SUPERCOP.

However, the API of it is quite awkward, and it takes quite some digging/extracting to get what you want. To save other people work I have done this myself and put my code on Github.

Beware your exact terms though, Ed25519 and Curve25519 are related, but different things. What you should know is that Ed25519 is a public/private key signature system and Curve25519 is a key exchange. Ed25519 keypairs can be converted to Curve25519 keypairs, the other way around I'm not so sure about. What my library on Github does is keep everything in Ed25519 keypairs and convert to Curve25519 for key exchanging.

Courser

If I understand the web site correctly the key exchange is not relevant for sqlr, so Ed25519 is what is required. And it's based on ecliptic curve =) – Melanymelaphyre

Answer 4

Rust has the ed25519 crate, which implements Edwards Digital Signature Algorithm (EdDSA) over Curve25519 as specified in RFC 8032. Another Rust crate is ed25519_dalek, which features a Rust implementation of ed25519 key generation, signing, and verification. There are some implications for hierachical key derivation on ed255190-dalek, this post has a few nice pointers and a solution.

Magallanes

Answer 5

Embedded implementations

• http://www.dlbeer.co.nz/oss/c25519.html
• μNaCl, and a research paper describing its performance

Georgeannageorgeanne

The c25519 library is considered potentially unsafe, see : github.com/MystenLabs/ed25519-unsafe-libs – Moira

Answer 6

Go 1.17 (Q3 2021) will come with a new and faster implementation, done by Filo Sottile.

See golang commit b0c49ae:

This change replaces the crypto/ed25519/internal/edwards25519 package with code from filippo.io/edwards25519, a significantly faster, safer, well tested (over 1600 lines of new tests, 99% test coverage), and better documented (600 lines of new comments) implementation.

Some highlights:

• an unsaturated 51-bit limb field implementation optimized for 64-bit architectures and math/bits.Mul64 intrinsics
• more efficient variable time scalar multiplication using multi-width non-adjacent form with a larger lookup table for fixed-base
• a safe math/big.Int-like API for the Scalar, Point, and field.Element types with fully abstracted reduction invariants
• a test suite including a testing/quick fuzzer that explores edge case values that would be impossible to hit randomly, and systematic tests for arguments and receiver aliasing
• point decoding rules that strictly match the original logic of crypto/ed25519/internal/edwards25519, to avoid consensus issues
• AssemblyPolicy-compliant assembly cores for arm64 and amd64, the former under 20 lines, and the latter generated by a program based on github.com/mmcloughlin/avo that can be reviewed line-by-line against the generic implementation

Big