Yesterday @burdges mentioned some ideas about how to try to erase secret data from memory, and some things about zero-on-drop behaviour in Rust. It would be good to have a reliable way to clear secret data.

If I understand correctly, just implementing the Drop trait to zero memory may not be sufficient, for two reasons:

1. the write may be optimized away (see also);

2. drop() may never be called, because Rust's memory model allows memory leaks: "memory unsafety is doing something with invalid data, a memory leak is not doing something with valid data"

Other notes that may be of interest: this morning at RWC 2017, Laurent Simon (@lmrs2 ?) presented secretgrind.

It could be quite convenient if Rust had a #[secret_stack] function annotation that guaranteed stack erasure, but this would require a language change.

I noticed the upcoming 4.0 release has removed the u32_backend and u64_backend features in favor of checking the target pointer size, which seems very sensible.* We know the u32_backend can be drastically faster than the u64_backend in some configurations:

On my Xperia 10 with SailfishOS (armv7hl user space on aarch64 kernel, yes I know, rustflags = "-C target-feature=+v7,+neon"):

• u32_backend + std: [644.25 us 646.59 us 649.28 us]
• u64_backend + std: [6.4522 ms 6.4685 ms 6.4880 ms]

…but not all:

On a Cortex-M3 (Texas Instruments CC2538):

• u32_backend without alloc: 470507 cycles
• u32_backend with alloc (wut): 878507 cycles
• u64_backend without alloc: 494078 cycles
• u64_backend with alloc: 470502 cycles (the fastest)

(https://github.com/signalapp/libsignal/issues/453#issuecomment-1068184262)

Today I finally got around to running some 32-bit microbenchmarks on a new Android phone (with help from a coworker), a Pixel 6a, which I feel should nonetheless still produce interesting results because, well, running armv7 code on an aarch64 device can't magically use 64-bit registers. We consistently found that the u32_backend was 5-15% slower than the u64_backend when compiling for that particular armv7.

EDIT: Later, I tested on a 32-bit Moto X and got approximately the same results.

All of this is differences of at most a tenth of a millisecond on any particular operation (we tested key agreement and signing + verifying), so it's not like it's going to make or break the crate. But it did make me think twice about "u32_backend is for 32-bit CPUs, u64_backend is for 64-bit CPUs". Is that worth restoring feature flags to override the default inference?

* Especially given that the previous config made it easy for a downstream crate to depend on u64_backend implicitly as a default feature, thus removing the chance for the final program to choose the u32_backend instead.

curve25519-dalek currently defines the following backends, modeled as crate features:

• u32_backend
• u64_backend
• fiat_u32_backend
• fiat_u64_backend
• simd_backend
• avx2_backend

First, avx2_backend can be removed: it's a deprecated legacy alias for simd_backend.

Second, I think u32_backend and u64_backend could be selected automatically by gating on e.g. cfg(target_pointer_width = "64"). If this selection were automatic, I think these features could be removed completely, with u32_backend/u64_backend selected and used by default unless another backend has been explicitly enabled.

Likewise, fiat_u64_backend and fiat_u32_backend can be collapsed down to fiat_backend using similar target_pointer_width-based gating.

If all of the above were done, the list above could be simplified down to just fiat_backend and simd_backend.

This library was previously only nostd compliant when serde was not enabled. To fix this, serde is no longer an optional dependency, but it is properly handled in both std and alloc modes. This required handling std and alloc modes separately; previously std mode included alloc. To separate these modes, it was necessary to expand a number of config checks for alloc mode to also include std.

There are suggestions for Intel-SA-00219 mitigations at https://github.com/apache/incubator-teaclave-sgx-sdk/wiki/Mitigation-of-Intel-SA-00219-in-Rust-SGX but they make no sense:

How would a u64 on only one side of secret data help, except by imposing 8 byte alignment? I'd think#[repr(align(8))] for types like Scalar suffices, except.. How does 8 byte alignment help if a cache line is 64 bytes?

It treats the stack attackable, but an enclave appears trivially exploitable if it shares stack with outside code. I think some rowhammer-like attacks perform writes with numerous reads, so afaik an enclave cannot even permit outside code read access.

Any thoughts? @tarcieri ?

As discussed in #456 ~~this sets well known defaults for:~~ ~~cfg(target_family = "wasm")~~ and ~~cfg(target_arch = "arm")~~

~~By setting the 64 bit serial arithmetric via cfg(curve25519_dalek_bits = "64")~~

EDIT: I've used platforms crate via env TARGET to determine the actual cross target and this now fixes build.rs only.

The function EdwardsPoint::hash_from_bytes() is described as "performing hashing to the group" and explicitly references draft-irtf-cfrg-hash-to-curve:

https://github.com/dalek-cryptography/curve25519-dalek/blob/8abb22bcafe30ac2dbad372d0444fdba9e63bc0e/src/edwards.rs#L529-L532

This is a rather misleading description because:

• This function does not implement the hash-to-curve process of draft-irtf-cfrg-hash-to-curve: the hash from input to a field element is different, and the handling of the sign bit is also different.
• Only a single Elligator2 map is applied, yielding something that draft-irtf-cfrg-hash-to-curve calls encode_to_curve, not hash_to_curve (the draft reserves the latter name for the construction that invokes the map twice, and adds together the two output points, to yield a quasi-uniform output distribution).

The first point is mostly about interoperability; while the map is not the same as in the draft, it is still safe (in particular, this code just uses the first 255 bits of a hash output as a field element, while the draft would generate 129 extra bits and perform a modular reduction; but in Curve25519, the field modulus is very close to 2^255, so the bias from using just 255 input bits is negligible). The second point is, arguably, more important for security, because the current hash_from_bytes() produces points with a non-uniform distribution that is easy to distinguish from a uniform random generation. Most protocols (and in particular the Signal stuff that this implementation follows) don't mind, but some of them require a uniform distribution, and the lack of uniformity can have consequences ranging from invalid security proofs to actual information leaks.

I recommend, at least, modifying the documentation to make it explicit that the implemented functionality is not compatible with draft-irtf-cfrg-hash-to-curve, and that it has a non-uniform output distribution, which may be troublesome for some (admittedly not many) protocols.

Looking at the existing pull requests, I see PR #377, which not only modifies the description of hash_from_bytes(), but also implements (in new, additional functions) the draft-irtf-hash-to-curve process. I have not looked in details at that PR, but the idea seems good.

zeroize is WASM-friendly as it has no dependencies on C compilers.

Instead uses Rust's own volatile write semantics and compiler fences to ensure zeroization is not elided by the compiler.

Related before-PR-doc (rendered): https://github.com/dalek-cryptography/curve25519-dalek/pull/453#discussion_r1042294155

Thou shall ask: https://github.com/dalek-cryptography/curve25519-dalek/issues/449#issuecomment-1340670829

Thou shall be giveth:

cfg

Test cfg matrix / expectation

All selected backends are mutually exclusive.

fiat_backend

Auto select fiat_u32 / fiat_u64 based on cfg(target_pointer_width) - default fiat_u32 on non-32/64 bits

serial (default)

Auto select u32 / u64 based on cfg(target_pointer_width) - default u32 on non-32/64 bits

fiat_backend w/ cfg(curve25519_dalek_bits = "32")

Selects fiat_u32 regardless of target_pointer on fiat_backend

fiat_backend w/ cfg(curve25519_dalek_bits = "64")

Selects fiat_u64 regardless of target_pointer

serial (default) w/ cfg(curve25519_dalek_bits = "32")

Selects u32 (serial) regardless of target_pointer

serial (default) w/ cfg(curve25519_dalek_bits = "64")

Selects u64 (serial) regardless of target_pointer

⚠️ REPLACED BY https://github.com/dalek-cryptography/curve25519-dalek/pull/249 ⚠️

Currently supported Straus algorithm does not improve performance as input size grows and saturates at ≈4x improvement over naïve multiplication. Pippenger’s algorithm takes advantage of very large amount of points (>190) by avoiding premultiplication of points and instead placing points in the buckets indexed by the multiplication factor. Then, buckets are cleverly added up to have their multipliers applied automatically. The process is repeated for each "digit" (that are 6 to 15 bits wide, depending on number of input points). As a result, the cost of multiplication grows slower than linearly with respect to the input size. For 1024 points Pippenger is >60% faster than Straus.

This patch adds:

1. An implementation of VartimeMultiscalarMul using Pippenger algorithm.
2. Dynamic switch based on input's size_hint() from Straus to Pippenger (at 190 points).
3. New DigitsBatch API to enumerate digits of scalars of arbitrary radix in a batch. Digits are produced via an iterator API on the fly, without pre-allocation: this allows us to have wider digits (i16) for more efficient computation of over 10K points.

TODO

• [ ] There is no consttime version of Pippenger. It should be pretty straightforward to add (there is only one conditional point negation that depends on the value of a scalar), but I need some help in figuring this out.
• [ ] there is no ClearOnDrop support yet.

This addresses #130.

I've noticed that operators on ExtendedPoint and the like are only implemented on &'a ExtendedPoint. Is there any reason for a PR that also implemented them for the concrete types wouldn't be accepted? The types are already copy and as far as I know the compile is better at reasoning about the code when there isn't explicit memory (i.e. a reference) involved.

~~Note: depends on #488 which should be merged first.~~

Feature-gates the inclusion of basepoint tables under a basepoint-tables feature, with the goal of reducing code size for e.g. embedded applications.

In its current for this probably isn't sufficient to address e.g. #355 but it's a start.

Proposal

TL;DR Make 5.x a "Performance release" with good defaults whilst merging to-be-tested additions behind features e.g.:

Breaking changes can be gated as optional within 4.x's first before making them defaults at 5.x.

This eases testing in the wild via these "unstable features" and elevates the confidence to adopt as default(s) in 5.x.

1. If it needs a deprecation we could always feature-gate it for 4.x as an optional additive non-breaking feature and then make it default 5.x after battletestign in the wild if so desired - like we're doing for the wasm/armv7 curve25519_dalek_bits case.

I think for 4.0.x also we could have auto-detection for backends as an optional additive non-breaking feature auto and then make it default in 5.x.

e.g. then this would make:

4.0.0 was mostly paying down the maintenance techdebt that is breaking people's builds atm and causing dependnecy duplication leading to long buildtimes :partying_face:

5.0.0 could be a performance oriented release that contains a lot of well known better defaults for performance.

Also I've proposed some feature flags which we could include this type of work via earlier perhaps:

• https://github.com/dalek-cryptography/curve25519-dalek/issues/287 (If we can get around LTO)
• https://github.com/dalek-cryptography/curve25519-dalek/pull/323
• https://github.com/dalek-cryptography/curve25519-dalek/issues/468

We should probably collect and round-up the various features here and how to incorporate them - I'll make a list here.

Reviving this thread as a separate feasibility discussion around at least:

Question 1: Should we do performance selection via features ?

This would include perhaps providing features to maybe enable something like this this -

• https://github.com/dalek-cryptography/curve25519-dalek/issues/287#issuecomment-552007045

Question 2: If we provide these features would that provide confidence to impl. crate separation for backends ?

Question 3: Is the tradeoff more around compile time for crate separation and is it relevant today ?

Some people put these things behind a feature flag e.g. regex pointed out by BurntSushi: https://docs.rs/regex/latest/regex/index.html#performance-features

There was some concern around LTO / cross-crate inlining I think around late 2019 and this may alleviate those ?

Also there is now some LTO changes in 1.65: https://www.reddit.com/r/rust/comments/ycmqml/the_rust_compiler_is_now_compiled_with_thin_lto/ And some other changes.

There was extensive chatter around #[inline] and how it works today - or a year ago?:

• https://github.com/rust-lang/hashbrown/pull/119

BurntSushi also pointed out a potential downside to these features - which are around build time:

• "If we would not add any performance features like in regex which would have a side effect - "
• "Of course, if you depend on anything that depends on hashbrown that enables the feature, then I don't think it can be turned off."

Other than doing some feature driven [cfg_attr()] - would either generic functions work as an alternative ?

Also are Rust inline docs today accurate -

There is also bunch of #[inline] discussion how it works supposedly today vs docs: https://github.com/rust-lang/hashbrown/pull/119#issuecomment-537539046

Fromn alexchrichton how #[inline] works today:

"In release mode the compiler will, by default, codegen an #[inline] function into every single referencing codegen unit , and then it will also add inlinehint . This means that if you have 16 CGUs and they all reference a hash map, every single one is getting the entire hash map implementation inlined into it."

Further from alexchrichton: https://users.rust-lang.org/t/enable-cross-crate-inlining-without-suggesting-inlining/55004/9

1. "Currently #[inline] codegens it into all referencing codegen units."
2. "For the first option we have 3 options - don't codegen into downstream crates, codegen into one CGU of any referencing downstream crate, or codegen into all CGUs. For the second we have 2 options, either apply the attribute or not."

I would recommend merging (no squash - to keep the history intact) from release/4.0 into main and keep the main as development branch for the next release what ever it will be in CHANGELOG.md in the branch.

This would greatly simplify the contributions and workflows overall leading to less errors.

This would align with the majority of the other projects contributors are used to.

Development workflow

I also would not use in-origin-repo branches and all the development should happen in fork(s) from where the PR's originate which will be consistent between maintainers and contributors.

All rendered contexes should be via remote fork feature branches also for the consistnecy.

This would also simplify the contributions and maitenance workflow and make it consistent and allows clean origin branches.

Also GitHub makes it hard to sync fork when there is a new branch in origin.

This all given if:

• develop branch is redundant
• release/x.y branches should be presented as release/x.y.z instead that get pushed into tag(s) and release
• release/x.y.z should be immutable on which release action can create the given branch
• backported fixes (non-breaking) should get release/x.y.z via release action automatically
• main branch can contain all the changes regardless of the release

As promised in #449! This is joint work with @Tarinn. In fact, @Tarinn did most of the work :-)

Fixes #147 for Aarch64, and you'll see an ARMv7 PR coming in after this.

I'm working on benchmarks across several devices now (including an unpublished very hacky armv7 version), will update here when they become available. We're seeing speedups of 20-30% in relevant benchmarks. This is the same code as in https://github.com/zkcrypto/curve25519-dalek-ng/pull/19.

I'll be cleaning up the commits in the next few minutes (trailing white space fixes, mostly), and I'll run a comparison benchmark for 343be3a, because that was only introduced for future ARMv7 support, and has not been tested under load.

TODO:

• [x] Cleanup whitespace and commits
• [x] Test shuffle! call vs vqtbx1q_u8 performance
• [x] Add Aarch64 cross build to CI
• [ ] Add NEON documentation to README Explain that ARMv7 is not yet supported