Same documented rewrite as FieldElement::sqrt_ratio_i: semantically
identical and still constant-time, but avoids subtle's
ConditionallyNegatable blanket impl, which the verification toolchain
cannot translate. Unblocks extracting decompress for the phase-2 full
point-level lift.
Co-Authored-By: Claude Fable 5 <noreply@anthropic.com>
Pure refactor, semantics identical: the read_le_u64_into call (whose
chunks/zip iterators are opaque to the extraction) becomes an explicit
nested index loop, the same shape as the proven from_bytes_wide unpack.
With this the entire vartime_double_base::mul extraction closure is
self-contained: zero external axioms, zero sorries.
Pure refactors (cargo check green under both feature sets), semantics of
mul unchanged:
- dsm_top_index / dsm_loop / dsm_step_p / dsm_step_b helpers: the main
double-and-add loop becomes a strictly-decreasing while with a
single-assignment body and parameter-rooted borrows (the original
loop/break shape with match-updates fails Aeneas' loop fixed point);
- the starting-index scan always returns 255: leading zero NAF digits
double the identity (a no-op), so the result is unchanged - only the
variable-time skip is dropped (constant-time behavior improves);
- the downward break-scan (which failed Aeneas' symbolic join) is gone.
With these, Charon+Aeneas extract the complete path - non_adjacent_form,
NafLookupTable5::from/select, the affine basepoint table, the 256-step
dsm_loop, and mul - with zero errors and zero sorries. This opens the
double-scalar-multiplication verification campaign (the EdDSA verify
equation's core).
Pure refactor, semantics identical (cargo check green):
- from_bytes_wide_parts(bytes) -> (Scalar52, Scalar52): the byte-unpack
loops + the 52-bit lo/hi split, as a named prefix
- split_words_lo / split_words_hi: the two split halves, built with
Scalar52([...]) struct literals instead of per-index mutation
- from_bytes_wide: parts -> montgomery_mul(lo, R) ->
montgomery_mul(hi, RR) -> add
Why: the verification side measured that (a) a WP walk whose motives
contain a montgomery_mul call replays its whole body at every kernel
step, and (b) straight-line chains of IndexMut closure back-functions
make kernel defeq exponential in chain depth. Named prefix functions fix
(a); struct-literal construction eliminates the closures and fixes (b).
With this shape the full from_bytes_wide certificate kernel-checks in
77 seconds (was: aborted after 30+ minutes).
hi[4] = words[7] >> 20 is the only shift in the function whose result is
stored without a trailing mask/or; at the pinned Aeneas (bf13c42e) a bare
`x >> c` as a full RHS extracts ill-typed (wrapping_shr applied to an i32
with an emitted-but-unsubstituted U32 cast). Masking is a semantic no-op:
words[7] >> 20 < 2^44 < 2^52. Semantics unchanged; needed to bring
from_bytes_wide (the hash-to-scalar reduction) into verification scope.
Similar security fix to #659, but for the 32-bit backend. See that PR
for more information about the problem. Relevant compiler outputs (thanks to @tarcieri):
Without fix
https://godbolt.org/z/zvaWxzvqv
Notice the `jns` ("jump if not sign") instruction on line 106.
With fix
https://godbolt.org/z/jc9j7eb8E
Timing variability of any kind is problematic when working with
potentially secret values such as elliptic curve scalars, and such
issues can potentially leak private keys and other secrets. Such a
problem was recently discovered in `curve25519-dalek`.
The `Scalar52::sub` function contained usage of a mask value inside of a
loop where LLVM saw an opportunity to insert a branch instruction
(`jns` on x86) to conditionally bypass this code section when the mask
value is set to zero, as can be seen in godbolt:
https://godbolt.org/z/PczYj7Pda
A similar problem was recently discovered in the Kyber reference
implementation:
https://groups.google.com/a/list.nist.gov/g/pqc-forum/c/hqbtIGFKIpU/m/cnE3pbueBgAJ
As discussed on that thread, one portable solution, which is also used
in this PR, is to introduce a volatile read as an optimization barrier,
which prevents the compiler from optimizing it away.
The fix can be validated in godbolt here:
https://godbolt.org/z/x8d46Yfah
The problem was discovered and the solution independently verified by
Alexander Wagner <alexander.wagner@aisec.fraunhofer.de> and
Lea Themint <lea.thiemt@tum.de> using their DATA tool:
https://github.com/Fraunhofer-AISEC/DATA
Co-authored-by: Tony Arcieri <bascule@gmail.com>
* Fix nightly build
* Add nightly feature constraint so AVX-512 requires either x86 or x86_64
Co-authored-by: Tony Arcieri <bascule@gmail.com>
* fmt
---------
Co-authored-by: Michael Rosenberg <micro@fastmail.com>
Co-authored-by: Tony Arcieri <bascule@gmail.com>
Co-authored-by: Michael Rosenberg <michael@mrosenberg.pub>
* Mark constants::BASEPOINT_ORDER_PRIVATE deprecated from pub API
* Move all BASEPOINT_ORDER use private internally
Co-authored-by: Tony Arcieri <bascule@gmail.com>
* Fix CHANGELOG for 4.1.1
---------
Co-authored-by: Tony Arcieri <bascule@gmail.com>
We have a lot of backend types leaking via the public API, including
e.g. `FieldElement51`:
https://docs.rs/curve25519-dalek/latest/curve25519_dalek/backend/serial/u64/field/struct.FieldElement51.html
At the very least, these types shouldn't be visible in the rustdoc.
This PR hides them from the docs, but ideally we would hide them
completely from the public API (which might technically be considered a
breaking change, but IMO leaking them at all is a bug).
Adds a lints section to the top of lib.rs with the following:
#![warn(
clippy::unwrap_used,
missing_docs,
rust_2018_idioms,
unused_lifetimes,
unused_qualifications
)]
`warn` is used instead of `deny` to prevent the lints from firing during
local development, however we already configure `-D warnings` in CI so
if any lint fails on checked-in code, it will cause a CI failure.
This commit also fixes or explicitly allows any current violations of
these lints. The main ones were:
- `clippy::unwrap_used`: replaces usages of `unwrap` with `expect`
- `rust_2018_idioms`: no implicit lifetimes, which were present on
usages of `core::fmt::Formatter`
There is occasionally [a need](https://github.com/dalek-cryptography/curve25519-dalek/pull/519#issuecomment-1637770888) to multiply a non-prime-order Montgomery point by an integer. There's currently no way to do this, since our only methods are multiplication by `Scalar` (doesn't make sense in the non-prime-order case), and `MontgomeryPoint::mul_base_clamped` clamps the integer before multiplying.
This defines `MontgomeryPoint::mul_bits_be`, which takes a big-endian representation of an integer and multiplies the point by that integer. Its usage is not recommended by default, but it is also not so unsafe as to be gated behind a `hazmat` feature.
