Skip to content

Commit dddad95

Browse files
igus68jogme
igus68
authored and
jogme
committed
Make the ecp_sm2p256 scalar multiplication constant time
Fixes CVE-2026-54875. This fix implemets the same idea as in PR#30649 by Joshua Rogers (@MegaManSec). Assisted-by: Claude:claude-opus-4-8 Reviewed-by: Alicja Kario <hkario@redhat.com> Reviewed-by: Tomas Mraz <tomas@openssl.foundation> Merge-date: Tue Sep 29 10:41:42 2026
1 parent 197d508 commit dddad95

1 file changed

Lines changed: 161 additions & 88 deletions

File tree

‎crypto/ec/ecp_sm2p256.c‎

Lines changed: 161 additions & 88 deletions
Original file line numberDiff line numberDiff line change
@@ -171,22 +171,35 @@ static ossl_inline void ecp_sm2p256_mod_inverse(BN_ULONG *out,
171171
BN_MOD_INV(out, in, ecp_sm2p256_div_by_2, ecp_sm2p256_sub, def_p);
172172
}
173173

174-
/* Point double: R <- P + P */
175-
static void ecp_sm2p256_point_double(P256_POINT *R, const P256_POINT *P)
174+
/*
175+
* Constant-time conditional copy: r = mask ? a : r, where mask is either 0 or
176+
* all-ones. Used to select point-addition results without branching.
177+
*/
178+
static ossl_inline void ecp_sm2p256_cond_copy(P256_POINT *r,
179+
const P256_POINT *a, BN_ULONG mask)
176180
{
177181
unsigned int i;
182+
183+
for (i = 0; i < P256_LIMBS; ++i) {
184+
r->X[i] = constant_time_select_64(mask, a->X[i], r->X[i]);
185+
r->Y[i] = constant_time_select_64(mask, a->Y[i], r->Y[i]);
186+
r->Z[i] = constant_time_select_64(mask, a->Z[i], r->Z[i]);
187+
}
188+
}
189+
190+
/*
191+
* Point double: R <- P + P
192+
*
193+
* Branch-free: the doubling formula already produces Z = 0 (the point at
194+
* infinity) when the input Z is 0 (R->Z = 2*Y*Z), and the resulting X, Y are
195+
* irrelevant for a Z = 0 point, so no is_zeros(P->Z) special case is needed.
196+
*/
197+
static void ecp_sm2p256_point_double(P256_POINT *R, const P256_POINT *P)
198+
{
178199
ALIGN32 BN_ULONG tmp0[P256_LIMBS];
179200
ALIGN32 BN_ULONG tmp1[P256_LIMBS];
180201
ALIGN32 BN_ULONG tmp2[P256_LIMBS];
181202

182-
/* zero-check P->Z */
183-
if (is_zeros(P->Z)) {
184-
for (i = 0; i < P256_LIMBS; ++i)
185-
R->Z[i] = 0;
186-
187-
return;
188-
}
189-
190203
ecp_sm2p256_sqr(tmp0, P->Z);
191204
ecp_sm2p256_sub(tmp1, P->X, tmp0);
192205
ecp_sm2p256_add(tmp0, P->X, tmp0);
@@ -208,6 +221,13 @@ static void ecp_sm2p256_point_double(P256_POINT *R, const P256_POINT *P)
208221
}
209222

210223
/* Point add affine: R <- P + Q */
224+
/*
225+
* NB: this function is deliberately NOT constant time. It is used only to
226+
* precompute the table of small multiples of the *public* input point (see
227+
* ecp_sm2p256_point_P_mul_by_scalar); the secret scalar never flows through
228+
* it, so its identity-dependent branches cannot leak it. Keeping the fast
229+
* branchy formula here avoids the constant-time overhead on the table build.
230+
*/
211231
static void ecp_sm2p256_point_add_affine(P256_POINT *R, const P256_POINT *P,
212232
const P256_POINT_AFFINE *Q)
213233
{
@@ -274,107 +294,164 @@ static void ecp_sm2p256_point_add_affine(P256_POINT *R, const P256_POINT *P,
274294
static void ecp_sm2p256_point_add(P256_POINT *R, const P256_POINT *P,
275295
const P256_POINT *Q)
276296
{
277-
unsigned int i;
278297
ALIGN32 BN_ULONG tmp0[P256_LIMBS] = { 0 };
279298
ALIGN32 BN_ULONG tmp1[P256_LIMBS] = { 0 };
280299
ALIGN32 BN_ULONG tmp2[P256_LIMBS] = { 0 };
281-
282-
/* zero-check P | Q ->Z */
283-
if (is_zeros(P->Z)) {
284-
for (i = 0; i < P256_LIMBS; ++i) {
285-
R->X[i] = Q->X[i];
286-
R->Y[i] = Q->Y[i];
287-
R->Z[i] = Q->Z[i];
288-
}
289-
290-
return;
291-
} else if (is_zeros(Q->Z)) {
292-
for (i = 0; i < P256_LIMBS; ++i) {
293-
R->X[i] = P->X[i];
294-
R->Y[i] = P->Y[i];
295-
R->Z[i] = P->Z[i];
296-
}
297-
298-
return;
299-
} else if (is_point_equal(P, Q)) {
300-
ecp_sm2p256_point_double(R, Q);
301-
302-
return;
303-
}
304-
300+
P256_POINT sum, dbl, res;
301+
BN_ULONG p_inf, q_inf, is_dbl;
302+
303+
p_inf = is_zeros(P->Z);
304+
q_inf = is_zeros(Q->Z);
305+
306+
/*
307+
* General P + Q addition into |sum|, valid unless P or Q is infinity or
308+
* P == +-Q. tmp0 = H and tmp1 = R are the coordinate differences: P and Q
309+
* are the same point iff both are zero; P == -Q iff only H is zero (the
310+
* formula then yields Z = 0, i.e. infinity, on its own).
311+
*/
305312
ecp_sm2p256_sqr(tmp0, P->Z);
306313
ecp_sm2p256_mul(tmp1, tmp0, P->Z);
307314
ecp_sm2p256_mul(tmp0, tmp0, Q->X);
308315
ecp_sm2p256_mul(tmp1, tmp1, Q->Y);
309-
ecp_sm2p256_mul(R->Y, P->Y, Q->Z);
310-
ecp_sm2p256_mul(R->Z, Q->Z, P->Z);
316+
ecp_sm2p256_mul(sum.Y, P->Y, Q->Z);
317+
ecp_sm2p256_mul(sum.Z, Q->Z, P->Z);
311318
ecp_sm2p256_sqr(tmp2, Q->Z);
312-
ecp_sm2p256_mul(R->Y, tmp2, R->Y);
313-
ecp_sm2p256_mul(R->X, tmp2, P->X);
314-
ecp_sm2p256_sub(tmp0, tmp0, R->X);
315-
ecp_sm2p256_mul(R->Z, tmp0, R->Z);
316-
ecp_sm2p256_sub(tmp1, tmp1, R->Y);
319+
ecp_sm2p256_mul(sum.Y, tmp2, sum.Y);
320+
ecp_sm2p256_mul(sum.X, tmp2, P->X);
321+
ecp_sm2p256_sub(tmp0, tmp0, sum.X);
322+
ecp_sm2p256_mul(sum.Z, tmp0, sum.Z);
323+
ecp_sm2p256_sub(tmp1, tmp1, sum.Y);
324+
is_dbl = is_zeros(tmp0) & is_zeros(tmp1);
317325
ecp_sm2p256_sqr(tmp2, tmp0);
318326
ecp_sm2p256_mul(tmp0, tmp0, tmp2);
319-
ecp_sm2p256_mul(tmp2, tmp2, R->X);
320-
ecp_sm2p256_sqr(R->X, tmp1);
321-
ecp_sm2p256_sub(R->X, R->X, tmp2);
322-
ecp_sm2p256_sub(R->X, R->X, tmp2);
323-
ecp_sm2p256_sub(R->X, R->X, tmp0);
324-
ecp_sm2p256_sub(tmp2, tmp2, R->X);
327+
ecp_sm2p256_mul(tmp2, tmp2, sum.X);
328+
ecp_sm2p256_sqr(sum.X, tmp1);
329+
ecp_sm2p256_sub(sum.X, sum.X, tmp2);
330+
ecp_sm2p256_sub(sum.X, sum.X, tmp2);
331+
ecp_sm2p256_sub(sum.X, sum.X, tmp0);
332+
ecp_sm2p256_sub(tmp2, tmp2, sum.X);
325333
ecp_sm2p256_mul(tmp2, tmp1, tmp2);
326-
ecp_sm2p256_mul(tmp0, tmp0, R->Y);
327-
ecp_sm2p256_sub(R->Y, tmp2, tmp0);
334+
ecp_sm2p256_mul(tmp0, tmp0, sum.Y);
335+
ecp_sm2p256_sub(sum.Y, tmp2, tmp0);
336+
337+
/* 2*P, for the P == Q case. */
338+
ecp_sm2p256_point_double(&dbl, P);
339+
340+
/*
341+
* Select the result without branching, in increasing priority:
342+
* default -> sum (distinct points; also P == -Q which gives infinity)
343+
* is_dbl -> dbl (P == Q)
344+
* q_inf -> P (Q is infinity)
345+
* p_inf -> Q (P is infinity; highest priority)
346+
* All reads of P and Q happen before R is written, so R may alias P or Q.
347+
*/
348+
memcpy(&res, &sum, sizeof(res));
349+
ecp_sm2p256_cond_copy(&res, &dbl, is_dbl);
350+
ecp_sm2p256_cond_copy(&res, P, q_inf);
351+
ecp_sm2p256_cond_copy(&res, Q, p_inf);
352+
memcpy(R, &res, sizeof(res));
328353
}
329354

330355
#if !defined(OPENSSL_NO_SM2_PRECOMP)
331356
/* Base point mul by scalar: k - scalar, G - base point */
357+
/*
358+
* Constant-time gather of the affine entry |index| from a 256-entry sub-table.
359+
* |sub| points to the sub-table for one 8-bit comb window; entry v is stored
360+
* as X[P256_LIMBS] followed by Y[P256_LIMBS] at sub + v * (2 * P256_LIMBS).
361+
* Entry 0 is not stored, so index 0 yields the all-zero (X, Y) placeholder,
362+
* which the caller turns into the point at infinity.
363+
*/
364+
static void ecp_sm2p256_select_G(P256_POINT_AFFINE *R, const BN_ULONG *sub,
365+
unsigned int index)
366+
{
367+
unsigned int v, j;
368+
369+
memset(R, 0, sizeof(*R));
370+
for (v = 1; v < 256; ++v) {
371+
BN_ULONG mask = constant_time_is_zero_64((BN_ULONG)(index ^ v));
372+
const BN_ULONG *e = sub + (size_t)v * (2 * P256_LIMBS);
373+
374+
for (j = 0; j < P256_LIMBS; ++j) {
375+
R->X[j] |= constant_time_select_64(mask, e[j], 0);
376+
R->Y[j] |= constant_time_select_64(mask, e[P256_LIMBS + j], 0);
377+
}
378+
}
379+
}
380+
381+
/*
382+
* R = k*G using the precomputed comb. Constant-time: every 8-bit window is
383+
* gathered from its full 256-entry sub-table with a mask and lifted to a
384+
* Jacobian point whose Z is 1 for a non-zero window and 0 (infinity) for a
385+
* zero window, so the unconditional, branch-free addition contributes nothing
386+
* for a zero window and no secret-dependent branch or table index remains.
387+
*/
332388
static void ecp_sm2p256_point_G_mul_by_scalar(P256_POINT *R, const BN_ULONG *k)
333389
{
334-
unsigned int i, index, mask = 0xff;
335-
P256_POINT_AFFINE Q;
390+
unsigned int i, j, index;
391+
P256_POINT_AFFINE Qaff;
392+
P256_POINT QJ;
336393

337394
memset(R, 0, sizeof(P256_POINT));
338395

339-
if (is_zeros(k))
340-
return;
396+
for (i = 0; i < 32; ++i) {
397+
index = (k[i / 8] >> (8 * (i % 8))) & 0xff;
398+
ecp_sm2p256_select_G(&Qaff,
399+
ecp_sm2p256_precomputed + (size_t)i * 256 * (2 * P256_LIMBS),
400+
index);
341401

342-
index = k[0] & mask;
343-
if (index) {
344-
index = index * 8;
345-
memcpy(R->X, ecp_sm2p256_precomputed + index, 32);
346-
memcpy(R->Y, ecp_sm2p256_precomputed + index + P256_LIMBS, 32);
347-
R->Z[0] = 1;
402+
{
403+
/* Z = 1 iff the window is non-zero, else 0 (point at infinity). */
404+
BN_ULONG nz = ~constant_time_is_zero_64((BN_ULONG)index);
405+
406+
for (j = 0; j < P256_LIMBS; ++j) {
407+
QJ.X[j] = Qaff.X[j];
408+
QJ.Y[j] = Qaff.Y[j];
409+
QJ.Z[j] = 0;
410+
}
411+
QJ.Z[0] = nz & 1;
412+
}
413+
ecp_sm2p256_point_add(R, R, &QJ);
348414
}
415+
}
416+
#endif
417+
418+
/*
419+
* Constant-time gather of |index| from a 16-entry table of Jacobian points.
420+
* Index 0 yields the all-zero point (Z = 0, i.e. the point at infinity).
421+
*/
422+
static void ecp_sm2p256_select_P(P256_POINT *R, const P256_POINT tbl[16],
423+
unsigned int index)
424+
{
425+
unsigned int i, j;
349426

350-
for (i = 1; i < 32; ++i) {
351-
index = (k[i / 8] >> (8 * (i % 8))) & mask;
427+
memset(R, 0, sizeof(*R));
428+
for (i = 1; i < 16; ++i) {
429+
BN_ULONG mask = constant_time_is_zero_64((BN_ULONG)(index ^ i));
352430

353-
if (index) {
354-
index = index + i * 256;
355-
index = index * 8;
356-
memcpy(Q.X, ecp_sm2p256_precomputed + index, 32);
357-
memcpy(Q.Y, ecp_sm2p256_precomputed + index + P256_LIMBS, 32);
358-
ecp_sm2p256_point_add_affine(R, R, &Q);
431+
for (j = 0; j < P256_LIMBS; ++j) {
432+
R->X[j] |= constant_time_select_64(mask, tbl[i].X[j], 0);
433+
R->Y[j] |= constant_time_select_64(mask, tbl[i].Y[j], 0);
434+
R->Z[j] |= constant_time_select_64(mask, tbl[i].Z[j], 0);
359435
}
360436
}
361437
}
362-
#endif
363438

364439
/*
365440
* Affine point mul by scalar: k - scalar, P - affine point
441+
*
442+
* Constant-time windowed multiplication: every 4-bit window is processed
443+
* uniformly with four doublings followed by a masked table gather and an
444+
* unconditional, branch-free addition. There is no init/skip logic and no
445+
* secret-dependent table index, so the running time and memory-access pattern
446+
* do not depend on the value of the secret scalar.
366447
*/
367448
static void ecp_sm2p256_point_P_mul_by_scalar(P256_POINT *R, const BN_ULONG *k,
368449
P256_POINT_AFFINE P)
369450
{
370-
int i, init = 0;
451+
int i;
371452
unsigned int index, mask = 0x0f;
372453
ALIGN64 P256_POINT precomputed[16];
373-
374-
memset(R, 0, sizeof(P256_POINT));
375-
376-
if (is_zeros(k))
377-
return;
454+
P256_POINT T;
378455

379456
/* The first value of the precomputed table is P. */
380457
memcpy(precomputed[1].X, P.X, 32);
@@ -391,22 +468,18 @@ static void ecp_sm2p256_point_P_mul_by_scalar(P256_POINT *R, const BN_ULONG *k,
391468
for (i = 3; i < 16; ++i)
392469
ecp_sm2p256_point_add_affine(&precomputed[i], &precomputed[i - 1], &P);
393470

471+
memset(R, 0, sizeof(*R)); /* R = point at infinity */
472+
394473
for (i = 64 - 1; i >= 0; --i) {
395474
index = (k[i / 16] >> (4 * (i % 16))) & mask;
396475

397-
if (init == 0) {
398-
if (index) {
399-
memcpy(R, &precomputed[index], sizeof(P256_POINT));
400-
init = 1;
401-
}
402-
} else {
403-
ecp_sm2p256_point_double(R, R);
404-
ecp_sm2p256_point_double(R, R);
405-
ecp_sm2p256_point_double(R, R);
406-
ecp_sm2p256_point_double(R, R);
407-
if (index)
408-
ecp_sm2p256_point_add(R, R, &precomputed[index]);
409-
}
476+
ecp_sm2p256_point_double(R, R);
477+
ecp_sm2p256_point_double(R, R);
478+
ecp_sm2p256_point_double(R, R);
479+
ecp_sm2p256_point_double(R, R);
480+
481+
ecp_sm2p256_select_P(&T, precomputed, index);
482+
ecp_sm2p256_point_add(R, R, &T);
410483
}
411484
}
412485

0 commit comments

Comments
 (0)