Scalar-mul: Constant-Time double-and-add

[mratsim]

For curves without endomorphisms

https://eprint.iacr.org/2017/669.pdf
https://www.aimsciences.org/article/exportPdf?id=5c293be6-723e-4b97-ae1d-ff359e261cdb

Abstract

This paper presents a series of Montgomery scalar multiplication algorithms on general short Weierstrass curves over odd characteristic fields, which need only 12 field multiplications plus 12 ~ 20 field additions per scalar bit using 8 ~ 10 field registers, thus significantly outperform the binary NAF method on average. Over binary fields, the Montgomery scalar multiplication algorithm which was presented at the first CHES workshop by López and Dahab has been a favorite of ECC implementors, due to its nice properties such as high efficiency outperforming the binary NAF, natural SPA-resistance, generality coping with all ordinary curves and implementation easiness. Over odd characteristic fields, the new scalar multiplication algorithms are the first ones featuring all these properties. Building-blocks of our contribution are new efficient differential addition-and-doubling formulae and a novel conception of on-the-fly adaptive coordinates which softly represent points occurring during a scalar multiplication not only in accordance with the basepoint but also bits of the given scalar. Importantly, the new algorithms are equipped with built-in countermeasures against known side-channel attacks, while it is shown that previous Montgomery ladder algorithms with the randomized addressing countermeasure fail to thwart attacks exploiting address-dependent leakage.

paulmillr/noble-secp256k1#55

This is an algorithm for EC multiplication that emulates the Montgomery
Ladder double-and-add, but in a constant time way. An early version of
this algorithm was published in 2017, and the version implemented here
was published in 2020. The result is constant time multiply that is 85%
faster than wNAF, <10% slower than endomorphic Montgommery Ladder and
~20% faster than w/o endomorphism.

bitcoin-core/secp256k1#1099

May be combined with #35

[mratsim]

Reading the paper and the implementation in typescript

// Kwang Ho Kim, Junyop Choe, Song Yun Kim, Namsu Kim, Sekung Hong.
 // Speeding up regular elliptic curve scalar multiplication without precomputation.
 // Advances in Mathematics of Communications, 2020, 14 (4) : 703-726.
 // doi: 10.3934/amc.2020090
 //
 // This algorithm is similar to standard double-and-add, but the number of
 // operations is not data dependent, making it suitable for use with secret
 // keys.
 export class BPSJ8 {
   private T = [_0n, _0n, _0n, _0n, _0n];

   constructor(private readonly P: Point) {}

   multiply(scalar: bigint): Point {
     if (!isValidFieldElement(scalar)) throw new Error("Expecting valid field element");

     const scalarBits = genBits(numTo32b(scalar));
     this.setup();
     while (!scalarBits.next().value) this.ladd(0);

     this.setup();
     for (const ki of scalarBits) this.ladd(ki);
     const P = this.recover();
     if (scalar === _1n) return this.P;
     if (scalar === CURVE.P - _1n) return this.P.negate();
     return P;
   }

   private setup() {
     const t5 = mod(this.P.y ** _2n);                  //  2,3
     this.T[2] = mod(this.P.x * t5);                   //  1,4
     this.T[0] = mod(this.T[2] * BigInt(12));          //  5-7,9
     this.T[2] = mod(this.P.x ** _2n);                 //  1,8
     this.T[4] = mod(this.T[2] * BigInt(3));           // 10-11
     this.T[2] = mod(this.T[4] + CURVE.a);             // 12
     this.T[4] = mod(_2n * this.T[2]);                 // 13
     this.T[3] = mod(this.T[2] ** _2n);                // 14
     this.T[2] = mod(t5 ** _2n);                       // 15
     this.T[3] = mod(this.T[3] - this.T[0]);           // 16
     this.T[1] = mod(this.T[2] * BigInt(16));          // 17-20
     this.T[2] = _0n;                                  // 21
   }

   // 8M + 4S + 9A
   private ladd(b: 0 | 1) {
     this.T[3-b] = mod(this.T[3-b] - this.T[2+b]);     //  1
     let t5 = mod(this.T[4] * this.T[2+b]);            //  2
     t5 = mod(this.T[1] + t5);                         //  3
     let t6 = mod(t5 * this.T[3-b]);                   //  4
     const t7 = mod(t5 ** _2n);                        //  5
     t5 = mod(this.T[4] * t6);                         //  6
     t5 = mod(t7 + t5);                                //  7
     this.T[4] = mod(this.T[1] * t6);                  //  8
     this.T[1] = mod(t6 ** _2n);                       //  9
     this.T[0] = mod(this.T[0] * this.T[1]);           // 10-11
     this.T[1] = mod(this.T[4] * this.T[1]);           // 12-13
     t6 = mod(this.T[3-b] ** _2n);                     // 14
     this.T[4] = mod(this.T[2+b] * t6);                // 15
     this.T[4] = mod(this.T[4] - t7 + this.T[4] - t5); // 16-18
     this.T[3-b] = mod(t7 * t5);                       // 19
     t6 = this.T[4];                                   // 20
     t6 = ((t6 & _1n) ? (t6 + CURVE.P) : t6) / _2n;    // 20
     t6 = mod(t6 ** _2n);                              // 21
     this.T[2+b] = mod(t6 - this.T[0] - this.T[3-b]);  // 22-23
   }

   private recover(): Point {
     this.T[3] = mod(this.P.y * this.T[0]);            //  1 y_0*X_0
     let t5 = mod(this.T[3] ** _2n);                   //  2 (y_0*X_0)^2
     t5 = mod(t5 * BigInt(4));                         //  3-4 4*(y_0*X_0)^2
     const t6 = mod(t5 * this.T[2]);                   //  5 4*(y_0*X_0)^2*X_1
     this.T[0] = mod(t6 * this.T[4]);                  //  6 4*(y_0*X_0)^2*M*X_1
     const t7 = mod(this.T[0] * this.T[3]);            //  7 4*(y_0*X_0)^3*M*X_1
     this.T[0] = mod(this.P.x * this.T[1]);            //  8 x_0*Y_0
     this.T[1] = mod(this.T[0] ** _2n);                //  9 (x_0*Y_0)^2
     this.T[3] = mod(this.T[1] * this.T[0]);           // 10 (x_0*Y_0)^3
     this.T[1] = mod(this.T[3] * BigInt(27));          // 11-17 27*(x_0*Y_0)^3
     this.T[4] = invert(this.T[1]);                    // 18 1/(27*(x_0*Y_0)^3)
     this.T[1] = mod(this.T[4] * t7);                  // 19 almost y_1
     this.T[1] = mod(this.T[1] + this.P.y);            // 20 y_1
     this.T[3] = mod(this.T[4] * this.T[0]);           // 21 1/(27*(x_0*Y_0)^2)
     t5 = mod(this.T[3] * BigInt(3));                  // 22-23 1/(9*(x_0*Y_0)^2)
     this.T[0] = mod(t5 * t6);                         // 24 almost x_1
     this.T[0] = mod(this.T[0] + this.P.x);            // 25 x_1
     // x_1 = 4*(y_0*X_0)^2*X_1 / (9*(x_0*Y_0)^2) + x_0



     // y_1 = 4*(y_0*X_0)^3*M*X_1 / (27*(x_0*Y_0)^3) + y_0
     return new Point(this.T[0], this.T[1]);
   }
 }

the algorithm has variable-time table accesses in the update phase which is vulnerable to cache-timing attacks.

Thwarting this would likely cost a lot as we need to scan the full table each time (and memory is much slower than a CPU).

Furthermore, all the curves that are used without precomputations (i.e. multiplied by something different than a generator) supports endomorphism acceleration. And curves that don't support an endomorphism are used for digital signatures and so can use precomputation (of powers of the generator with the comb algorithm).

So closing.