Skip to content

Latest commit

 

History

History
178 lines (120 loc) · 13 KB

README.md

File metadata and controls

178 lines (120 loc) · 13 KB
Raw

ed25519-dalek CI

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.

Feature Default? Description
alloc ✓ When pkcs8 is enabled, implements EncodePrivateKey/EncodePublicKey for SigningKey/VerifyingKey, respectively.
std ✓ Implements std::error::Error for SignatureError. Also enables alloc.
zeroize ✓ Implements Zeroize and ZeroizeOnDrop for SigningKey
rand_core Enables SigningKey::generate
batch Enables verify_batch for verifying many signatures quickly. Also enables rand_core.
digest Enables Context, SigningKey::{with_context, sign_prehashed} and VerifyingKey::{with_context, verify_prehashed, verify_prehashed_strict} for Ed25519ph prehashed signatures
asm Enables assembly optimizations in the SHA-512 compression functions
pkcs8 Enables PKCS#8 serialization/deserialization for SigningKey and VerifyingKey
pem Enables PEM serialization support for PKCS#8 private keys and SPKI public keys. Also enables alloc.
legacy_compatibility Unsafe: Disables certain signature checks. See below
hazmat Unsafe: Exposes the hazmat module for raw signing/verifying. Misuse of these functions will expose the private key, as in the signing oracle attack.

Major Changes

See CHANGELOG.md for a list of changes made in past versions 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

Releases MSRV
2.x 1.60
1.x 1.41

From 2.x onwards, 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:

Releases Public API Component(s) Policy
2.x Dependencies digest, pkcs8 and rand_core Minor SemVer bump

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.

Benchmark u64 simd +avx2 fiat
signing 15.017 µs 13.906 µs -7.3967% 15.877 μs +5.7268%
signature verification 40.144 µs 25.963 µs -35.603% 42.118 μs +4.9173%
strict signature verification 41.334 µs 27.874 µs -32.660% 43.985 μs +6.4136%
batch signature verification/4 109.44 µs 81.778 µs -25.079% 117.80 μs +7.6389%
batch signature verification/8 182.75 µs 138.40 µs -23.871% 195.86 μs +7.1737%
batch signature verification/16 328.67 µs 251.39 µs -23.744% 351.55 μs +6.9614%
batch signature verification/32 619.49 µs 477.36 µs -23.053% 669.41 μs +8.0582%
batch signature verification/64 1.2136 ms 936.85 µs -22.543% 1.3028 ms +7.3500%
batch signature verification/96 1.8677 ms 1.2357 ms -33.936% 2.0552 ms +10.039%
batch signature verification/128 2.3281 ms 1.5795 ms -31.996% 2.5596 ms +9.9437%
batch signature verification/256 4.1868 ms 2.8864 ms -31.061% 4.6494 μs +11.049%
keypair generation 13.973 µs 13.108 µs -6.5062% 15.099 μs +8.0584%

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.