From 1f60c1c788559ef69ee39ad490ba89b13733e1ca Mon Sep 17 00:00:00 2001 From: Nicola Tuveri Date: Sat, 8 Jun 2019 12:48:47 +0300 Subject: [PATCH] Fix potential SCA vulnerability in some EC_METHODs This commit addresses a potential side-channel vulnerability in the internals of some elliptic curve low level operations. The side-channel leakage appears to be tiny, so the severity of this issue is rather low. The issue was reported by David Schrammel and Samuel Weiser. Reviewed-by: Matt Caswell Reviewed-by: Bernd Edlinger (Merged from https://github.com/openssl/openssl/pull/9239) (cherry picked from commit 3cb914c463ed1c9e32cfb773d816139a61b6ad5f) --- crypto/ec/ecp_nistp224.c | 35 +++++++++++++++++++++++++++++++---- crypto/ec/ecp_nistp256.c | 22 +++++++++++++++++++++- crypto/ec/ecp_nistp521.c | 20 +++++++++++++++++++- 3 files changed, 71 insertions(+), 6 deletions(-) diff --git a/crypto/ec/ecp_nistp224.c b/crypto/ec/ecp_nistp224.c index 36edcd5130..5a3812d04e 100644 --- a/crypto/ec/ecp_nistp224.c +++ b/crypto/ec/ecp_nistp224.c @@ -907,6 +907,7 @@ static void point_add(felem x3, felem y3, felem z3, felem ftmp, ftmp2, ftmp3, ftmp4, ftmp5, x_out, y_out, z_out; widefelem tmp, tmp2; limb z1_is_zero, z2_is_zero, x_equal, y_equal; + limb points_equal; if (!mixed) { /* ftmp2 = z2^2 */ @@ -963,15 +964,41 @@ static void point_add(felem x3, felem y3, felem z3, felem_reduce(ftmp, tmp); /* - * the formulae are incorrect if the points are equal so we check for - * this and do doubling if this happens + * The formulae are incorrect if the points are equal, in affine coordinates + * (X_1, Y_1) == (X_2, Y_2), so we check for this and do doubling if this + * happens. + * + * We use bitwise operations to avoid potential side-channels introduced by + * the short-circuiting behaviour of boolean operators. */ x_equal = felem_is_zero(ftmp); y_equal = felem_is_zero(ftmp3); + /* + * The special case of either point being the point at infinity (z1 and/or + * z2 are zero), is handled separately later on in this function, so we + * avoid jumping to point_double here in those special cases. + */ z1_is_zero = felem_is_zero(z1); z2_is_zero = felem_is_zero(z2); - /* In affine coordinates, (X_1, Y_1) == (X_2, Y_2) */ - if (x_equal && y_equal && !z1_is_zero && !z2_is_zero) { + + /* + * Compared to `ecp_nistp256.c` and `ecp_nistp521.c`, in this + * specific implementation `felem_is_zero()` returns truth as `0x1` + * (rather than `0xff..ff`). + * + * This implies that `~true` in this implementation becomes + * `0xff..fe` (rather than `0x0`): for this reason, to be used in + * the if expression, we mask out only the last bit in the next + * line. + */ + points_equal = (x_equal & y_equal & (~z1_is_zero) & (~z2_is_zero)) & 1; + + if (points_equal) { + /* + * This is obviously not constant-time but, as mentioned before, this + * case never happens during single point multiplication, so there is no + * timing leak for ECDH or ECDSA signing. + */ point_double(x3, y3, z3, x1, y1, z1); return; } diff --git a/crypto/ec/ecp_nistp256.c b/crypto/ec/ecp_nistp256.c index 8265d574de..3c3769873e 100644 --- a/crypto/ec/ecp_nistp256.c +++ b/crypto/ec/ecp_nistp256.c @@ -1241,6 +1241,7 @@ static void point_add(felem x3, felem y3, felem z3, longfelem tmp, tmp2; smallfelem small1, small2, small3, small4, small5; limb x_equal, y_equal, z1_is_zero, z2_is_zero; + limb points_equal; felem_shrink(small3, z1); @@ -1340,7 +1341,26 @@ static void point_add(felem x3, felem y3, felem z3, felem_shrink(small1, ftmp5); y_equal = smallfelem_is_zero(small1); - if (x_equal && y_equal && !z1_is_zero && !z2_is_zero) { + /* + * The formulae are incorrect if the points are equal, in affine coordinates + * (X_1, Y_1) == (X_2, Y_2), so we check for this and do doubling if this + * happens. + * + * We use bitwise operations to avoid potential side-channels introduced by + * the short-circuiting behaviour of boolean operators. + * + * The special case of either point being the point at infinity (z1 and/or + * z2 are zero), is handled separately later on in this function, so we + * avoid jumping to point_double here in those special cases. + */ + points_equal = (x_equal & y_equal & (~z1_is_zero) & (~z2_is_zero)); + + if (points_equal) { + /* + * This is obviously not constant-time but, as mentioned before, this + * case never happens during single point multiplication, so there is no + * timing leak for ECDH or ECDSA signing. + */ point_double(x3, y3, z3, x1, y1, z1); return; } diff --git a/crypto/ec/ecp_nistp521.c b/crypto/ec/ecp_nistp521.c index 14cd409162..b10f4c8672 100644 --- a/crypto/ec/ecp_nistp521.c +++ b/crypto/ec/ecp_nistp521.c @@ -1158,6 +1158,7 @@ static void point_add(felem x3, felem y3, felem z3, felem ftmp, ftmp2, ftmp3, ftmp4, ftmp5, ftmp6, x_out, y_out, z_out; largefelem tmp, tmp2; limb x_equal, y_equal, z1_is_zero, z2_is_zero; + limb points_equal; z1_is_zero = felem_is_zero(z1); z2_is_zero = felem_is_zero(z2); @@ -1242,7 +1243,24 @@ static void point_add(felem x3, felem y3, felem z3, felem_scalar64(ftmp5, 2); /* ftmp5[i] < 2^61 */ - if (x_equal && y_equal && !z1_is_zero && !z2_is_zero) { + /* + * The formulae are incorrect if the points are equal, in affine coordinates + * (X_1, Y_1) == (X_2, Y_2), so we check for this and do doubling if this + * happens. + * + * We use bitwise operations to avoid potential side-channels introduced by + * the short-circuiting behaviour of boolean operators. + * + * The special case of either point being the point at infinity (z1 and/or + * z2 are zero), is handled separately later on in this function, so we + * avoid jumping to point_double here in those special cases. + * + * Notice the comment below on the implications of this branching for timing + * leaks and why it is considered practically irrelevant. + */ + points_equal = (x_equal & y_equal & (~z1_is_zero) & (~z2_is_zero)); + + if (points_equal) { /* * This is obviously not constant-time but it will almost-never happen * for ECDH / ECDSA. The case where it can happen is during scalar-mult -- 2.25.1