ed25519-dalek

Fast and efficient Rust implementation of ed25519 key generation, signing, and verification.

Use

To import ed25519-dalek, add the following to the dependencies section of your project's Cargo.toml:

ed25519-dalek = "2"

Feature Flags

This crate is #[no_std] compatible with default-features = false.

Major Changes

See CHANGELOG.md for a list of changes made in past version of this crate.

Breaking Changes in 2.0.0

• Bump MSRV from 1.41 to 1.60.0
• Bump Rust edition
• Bump signature dependency to 2.0
• Make digest an optional dependency
• Make zeroize an optional dependency
• Make rand_core an optional dependency
• Adopt curve25519-backend selection over features
• Make all batch verification deterministic remove batch_deterministic (#256)
• Remove ExpandedSecretKey API (#205)
• Rename Keypair → SigningKey and PublicKey → VerifyingKey
• Make hazmat feature to expose, ExpandedSecretKey, raw_sign(), raw_sign_prehashed(), raw_verify(), and raw_verify_prehashed()

Documentation

Documentation is available here.

Compatibility Policies

All on-by-default features of this library are covered by semantic versioning (SemVer). SemVer exemptions are outlined below for MSRV and public API.

Minimum Supported Rust Version

From 2.x and on, MSRV changes will be accompanied by a minor version bump.

Public API SemVer Exemptions

Breaking changes to SemVer-exempted components affecting the public API will be accompanied by some version bump.

Below are the specific policies:

Safety

ed25519-dalek is designed to prevent misuse. Signing is constant-time, all signing keys are zeroed when they go out of scope (unless zeroize is disabled), detached public keys cannot be used for signing, and extra functions like VerifyingKey::verify_strict are made available to avoid known gotchas.

Further, this crate has no—and in fact forbids—unsafe code. You can opt in to using some highly optimized unsafe code that resides in curve25519-dalek, though. See below for more information on backend selection.

Performance

Performance is a secondary goal behind correctness, safety, and clarity, but we aim to be competitive with other implementations.

Benchmarks

Benchmarks are run using criterion.rs:

cargo bench --features "batch"
# Uses avx2 or ifma only if compiled for an appropriate target.
export RUSTFLAGS='-C target_cpu=native'
cargo +nightly bench --features "batch"

On an Intel 10700K running at stock comparing between the curve25519-dalek backends.

Batch Performance

If your protocol or application is able to batch signatures for verification, the verify_batch function has greatly improved performance.

As you can see, there's an optimal batch size for each machine, so you'll likely want to test the benchmarks on your target CPU to discover the best size.

(Micro)Architecture Specific Backends

A backend refers to an implementation of elliptic curve and scalar arithmetic. Different backends have different use cases. For example, if you demand formally verified code, you want to use the fiat backend (as it was generated from Fiat Crypto).

Backend selection details and instructions can be found in the curve25519-dalek docs.

Contributing

See CONTRIBUTING.md

Batch Signature Verification

The standard variants of batch signature verification (i.e. many signatures made with potentially many different public keys over potentially many different messages) is available via the batch feature. It uses deterministic randomness, i.e., it hashes the inputs (using merlin, which handles transcript item separation) and uses the result to generate random coefficients. Batch verification requires allocation, so this won't function in heapless settings.

Validation Criteria

The validation criteria of a signature scheme are the criteria that signatures and public keys must satisfy in order to be accepted. Unfortunately, Ed25519 has some underspecified parts, leading to different validation criteria across implementations. For a very good overview of this, see Henry's post.

In this section, we mention some specific details about our validation criteria, and how to navigate them.

Malleability and the legacy_compatibility Feature

A signature scheme is considered to produce malleable signatures if a passive attacker with knowledge of a public key A, message m, and valid signature σ' can produce a distinct σ' such that σ' is a valid signature of m with respect to A. A scheme is only malleable if the attacker can do this without knowledge of the private key corresponding to A.

ed25519-dalek is not a malleable signature scheme.

Some other Ed25519 implementations are malleable, though, such as libsodium with ED25519_COMPAT enabled, ed25519-donna, NaCl's ref10 impl, and probably a lot more. If you need to interoperate with such implementations and accept otherwise invalid signatures, you can enable the legacy_compatibility flag. Do not enable legacy_compatibility if you don't have to, because it will make your signatures malleable.

Note: CIRCL has no scalar range check at all. We do not have a feature flag for interoperating with the larger set of RFC-disallowed signatures that CIRCL accepts.

Weak key Forgery and verify_strict()

A signature forgery is what it sounds like: it's when an attacker, given a public key A, creates a signature σ and message m such that σ is a valid signature of m with respect to A. Since this is the core security definition of any signature scheme, Ed25519 signatures cannot be forged.

However, there's a much looser kind of forgery that Ed25519 permits, which we call weak key forgery. An attacker can produce a special public key A (which we call a weak public key) and a signature σ such that σ is a valid signature of any message m, with respect to A, with high probability. This attack is acknowledged in the Ed25519 paper, and caused an exploitable bug in the Scuttlebutt protocol (paper, section 7.1). The VerifyingKey::verify() function permits weak keys.

We provide VerifyingKey::verify_strict (and verify_strict_prehashed) to help users avoid these scenarios. These functions perform an extra check on A, ensuring it's not a weak public key. In addition, we provide the VerifyingKey::is_weak to allow users to perform this check before attempting signature verification.

Batch verification

As mentioned above, weak public keys can be used to produce signatures for unknown messages with high probability. This means that sometimes a weak forgery attempt will fail. In fact, it can fail up to 7/8 of the time. If you call verify() twice on the same failed forgery, it will return an error both times, as expected. However, if you call verify_batch() twice on two distinct otherwise-valid batches, both of which contain the failed forgery, there's a 21% chance that one fails and the other succeeds.

Why is this? It's because verify_batch() does not do the weak key testing of verify_strict(), and it multiplies each verification equation by some random coefficient. If the failed forgery gets multiplied by 8, then the weak key (which is a low-order point) becomes 0, and the verification equation on the attempted forgery will succeed.

Since verify_batch() is intended to be high-throughput, we think it's best not to put weak key checks in it. If you want to prevent weird behavior due to weak public keys in your batches, you should call VerifyingKey::is_weak on the inputs in advance.