From 3712436071c04ed831594cf47073788417d1506b Mon Sep 17 00:00:00 2001 From: Nicola Tuveri Date: Sun, 8 Jul 2018 00:50:49 +0300 Subject: EC point multiplication: add `ladder` scaffold for specialized Montgomery ladder implementations PR #6009 and #6070 replaced the default EC point multiplication path for prime and binary curves with a unified Montgomery ladder implementation with various timing attack defenses (for the common paths when a secret scalar is feed to the point multiplication). The newly introduced default implementation directly used EC_POINT_add/dbl in the main loop. The scaffolding introduced by this commit allows EC_METHODs to define a specialized `ladder_step` function to improve performances by taking advantage of efficient formulas for differential addition-and-doubling and different coordinate systems. - `ladder_pre` is executed before the main loop of the ladder: by default it copies the input point P into S, and doubles it into R. Specialized implementations could, e.g., use this hook to transition to different coordinate systems before copying and doubling; - `ladder_step` is the core of the Montgomery ladder loop: by default it computes `S := R+S; R := 2R;`, but specific implementations could, e.g., implement a more efficient formula for differential addition-and-doubling; - `ladder_post` is executed after the Montgomery ladder loop: by default it's a noop, but specialized implementations could, e.g., use this hook to transition back from the coordinate system used for optimizing the differential addition-and-doubling or recover the y coordinate of the result point. This commit also renames `ec_mul_consttime` to `ec_scalar_mul_ladder`, as it better corresponds to what this function does: nothing can be truly said about the constant-timeness of the overall execution of this function, given that the underlying operations are not necessarily constant-time themselves. What this implementation ensures is that the same fixed sequence of operations is executed for each scalar multiplication (for a given EC_GROUP), with no dependency on the value of the input scalar. Co-authored-by: Sohaib ul Hassan Co-authored-by: Billy Brumley Reviewed-by: Andy Polyakov Reviewed-by: Matt Caswell (Merged from https://github.com/openssl/openssl/pull/6690) --- CHANGES | 7 +++++++ 1 file changed, 7 insertions(+) (limited to 'CHANGES') diff --git a/CHANGES b/CHANGES index 4765e0b14a..bfa73aeec3 100644 --- a/CHANGES +++ b/CHANGES @@ -9,6 +9,13 @@ Changes between 1.1.0h and 1.1.1 [xx XXX xxxx] + *) Add a scaffold to optionally enhance the Montgomery ladder implementation + for `ec_scalar_mul_ladder` (formerly `ec_mul_consttime`) allowing + EC_METHODs to implement their own specialized "ladder step", to take + advantage of more favorable coordinate systems or more efficient + differential addition-and-doubling algorithms. + [Billy Bob Brumley, Sohaib ul Hassan, Nicola Tuveri] + *) Modified the random device based seed sources to keep the relevant file descriptors open rather than reopening them on each access. This allows such sources to operate in a chroot() jail without -- cgit v1.2.3