Skip to contentSkip to conversation

ecc: make l_ecc_point_from_data const time (for compressed points)

PATCH Applied James Prestwood 2 participants 2 messages Jan 12, 2022 – Feb 3, 2022

lore
Share & tools
lore

James Prestwood

author
#0 lore raw

PATCH 1/1 ecc: make l_ecc_point_from_data const time (for compressed points)

This only alters the two compressed point types as there isn't a security reason to make the function const time for compliant/full point data as these are never used in conjunction with compressed points.

The timing difference came down mainly to the conditional _vli_mod_sub call which was only called depending on the first bit of p->y. More subtly the check differered between BIT0 and BIT1 by a '!' operation which would result in an additional instruction.

This patch addresses the '!' operation by checking if the subtraction is needed and considering both compressed types in that logic.

For the subtraction, it is now done unconditionally and the result is stored in a temporary variable. Then l_secure_select is used to copy the data to p->y, or back into the temporary variable depending on if 'need_sub' evaluated to true.

---
 ell/ecc.c | 20 ++++++++++----------
 1 file changed, 10 insertions(+), 10 deletions(-)
ell/ecc.c +10 -10
index 24b7cff..5830e01 100644
@@ -535,6 +535,8 @@ LIB_EXPORT struct l_ecc_point *l_ecc_point_from_data(
 {
 	struct l_ecc_point *p;
 	size_t bytes = curve->ndigits * 8;
+	uint64_t tmp[L_ECC_MAX_DIGITS];
+	bool sub;
 
 	if (!data)
 		return NULL;
@@ -554,20 +556,18 @@ LIB_EXPORT struct l_ecc_point *l_ecc_point_from_data(
 
 		break;
 	case L_ECC_POINT_TYPE_COMPRESSED_BIT0:
-		if (!_ecc_compute_y(curve, p->y, p->x))
-			goto failed;
-
-		if (!(p->y[0] & 1))
-			_vli_mod_sub(p->y, curve->p, p->y, curve->p,
-						curve->ndigits);
-		break;
 	case L_ECC_POINT_TYPE_COMPRESSED_BIT1:
 		if (!_ecc_compute_y(curve, p->y, p->x))
 			goto failed;
 
-		if (p->y[0] & 1)
-			_vli_mod_sub(p->y, curve->p, p->y, curve->p,
-						curve->ndigits);
+		sub = ((type == L_ECC_POINT_TYPE_COMPRESSED_BIT0 &&
+				!(p->y[0] & 1)) ||
+				(type == L_ECC_POINT_TYPE_COMPRESSED_BIT1 &&
+				(p->y[0] & 1)));
+
+		_vli_mod_sub(tmp, curve->p, p->y, curve->p, curve->ndigits);
+
+		l_secure_select(sub, tmp, p->y, p->y, curve->ndigits * 8);
 
 		break;
 	case L_ECC_POINT_TYPE_FULL:
Signature · 1 line
2.31.1
Applied
#1 lore raw

Hi James,

Quoted 12 lines · James Prestwood

This only alters the two compressed point types as there isn't a security reason to make the function const time for compliant/full point data as these are never used in conjunction with compressed points.

The timing difference came down mainly to the conditional _vli_mod_sub call which was only called depending on the first bit of p->y. More subtly the check differered between BIT0 and BIT1 by a '!' operation which would result in an additional instruction.

This patch addresses the '!' operation by checking if the subtraction is needed and considering both compressed types in that logic.

Quoted 8 lines

For the subtraction, it is now done unconditionally and the result is stored in a temporary variable. Then l_secure_select is used to copy the data to p->y, or back into the temporary variable depending on if 'need_sub' evaluated to true.

---
  ell/ecc.c | 20 ++++++++++----------
  1 file changed, 10 insertions(+), 10 deletions(-)

Applied, thanks.

Regards,
-Denis