Skip to contentSkip to conversation

ecc: fix incorrect derivation of compressed points

PATCH In review James Prestwood 2 participants 4 messages Oct 10, 2023 – Oct 11, 2023

lore
Share & tools
lore
#0 lore raw

PATCH v2 1/2 ecc: fix incorrect derivation of compressed points

The logic was inversed here and was performing a subtraction if:
- Y was even and type == BIT0
- Y was odd and type == BIT1

This is not correct according to the ANSI spec. IWD relied on this API but had matching incorrect logic so things "worked" up until a compressed point needed to be parsed from an source that explicitly specified the type (e.g. an ASN1 DER in DPP). All other uses (PWD/SAE) the point type was only used to force a subtraction so since both locations used the incorrect logic the points would compute correctly.

---
 ell/ecc.c | 18 +++++++++++++++++-
 1 file changed, 17 insertions(+), 1 deletion(-)
ell/ecc.c +17 -1
index 98ef812..73ddb96 100644
@@ -562,8 +562,24 @@ LIB_EXPORT struct l_ecc_point *l_ecc_point_from_data(
 		if (!_ecc_compute_y(curve, p->y, p->x))
 			goto failed;
 
+		/*
+		 * This is determining whether or not to subtract the Y
+		 * coordinate from P. According to ANSI X9.62 an even Y should
+		 * be prefixed with 02 (BIT0) and an odd Y should be prefixed
+		 * with 03 (BIT1). If this is not the case, subtract Y from P.
+		 *
+		 * ANSI X9.62
+		 * 4.3.6 Point-to-Octet-String Conversion
+		 *
+		 * 2. If the compressed form is used, then do the following:
+		 *     2.1. Compute the bit ~Yp . (See Section 4.2.)
+		 *     2.2. Assign the value 02 to the single octet PC if ~Yp
+		 *          is 0, or the value 03 if ~Yp is 1.
+		 *     2.3. The result is the octet string PO = PC || X
+		 */
+
 		sub = secure_select(type == L_ECC_POINT_TYPE_COMPRESSED_BIT0,
-					!(p->y[0] & 1), p->y[0] & 1);
+					p->y[0] & 1, !(p->y[0] & 1));
 
 		_vli_mod_sub(tmp, curve->p, p->y, curve->p, curve->ndigits);
 
Signature · 1 line
2.25.1
#1 lore raw

PATCH v2 2/2 unit: update test-ecc with compressed point bug fix

---
 unit/test-ecc.c | 16 ++++++++--------
 1 file changed, 8 insertions(+), 8 deletions(-)
unit/test-ecc.c +8 -8
index 21f73f1..05a89ab 100644
@@ -374,28 +374,28 @@ struct compressed_point_data {
 
 static struct compressed_point_data compressed_tests[] = {
 	{
-		/* BIT1, subtraction performed */
+		/* BIT0, computed Y is odd, subtraction performed */
 		.x = "19b3fec1c000a888ee9c44272e4d7317e6e36577fc9d53e1edfb4e296b0b7ce1",
 		.exp_y = "a8f9efd0ab526cd930870779621f4e9a53d4e78887ac9f4ed45ff75ded32b158",
-		.type = L_ECC_POINT_TYPE_COMPRESSED_BIT1,
+		.type = L_ECC_POINT_TYPE_COMPRESSED_BIT0,
 	},
 	{
-		/* BIT1, no subtraction */
+		/* BIT0, computed Y is even, no subtraction */
 		.x = "958df5997362a9695ad73938c86be34a4730da877eccaaf8b189e73ff20e67c3",
 		.exp_y = "1042f37262ded34d8424c1728a1ed23a726645b71db30a38f2932001a2027f46",
-		.type = L_ECC_POINT_TYPE_COMPRESSED_BIT1,
+		.type = L_ECC_POINT_TYPE_COMPRESSED_BIT0,
 	},
 	{
-		/* BIT0, subtraction performed */
+		/* BIT1, computed Y is even, subtraction performed */
 		.x = "069bd56634454ca76e7ba434244137509141cbbf532586c6b36e9b5be8a2cc34",
 		.exp_y = "f4f34d46e4bdc1473fec4b4c8724f349375a8a602f5e83c260d6724e64ec7e99",
-		.type = L_ECC_POINT_TYPE_COMPRESSED_BIT0,
+		.type = L_ECC_POINT_TYPE_COMPRESSED_BIT1,
 	},
 	{
-		/* BIT0, no subtraction */
+		/* BIT1, computed Y is odd, no subtraction */
 		.x = "8cade296a68e0c40bcf45a049f1993263bdc8524825e2be44b14ce114e475df0",
 		.exp_y = "94ed7d09b2a0e95d8df993eaf81eb64d5ff734d01da57e53b2e0277199bc5897",
-		.type = L_ECC_POINT_TYPE_COMPRESSED_BIT0,
+		.type = L_ECC_POINT_TYPE_COMPRESSED_BIT1,
 	},
 };
 
Signature · 1 line
2.25.1
#2 lore raw

Re: [PATCH v2 2/2] unit: update test-ecc with compressed point bug fix

Hi James,

Quoted 3 lines · James Prestwood
---
  unit/test-ecc.c | 16 ++++++++--------
  1 file changed, 8 insertions(+), 8 deletions(-)

Not related to this, but unit tests for ell no longer pass:
PASS: unit/test-pem
./build-aux/test-driver: line 112: 218850 Aborted (core dumped) "$@" >> "$log_file" 2>&1
FAIL: unit/test-tls
./build-aux/test-driver: line 112: 218865 Aborted (core dumped) "$@" >> "$log_file" 2>&1
FAIL: unit/test-key
============================================================================
Testsuite summary for ell 0.59
============================================================================
# TOTAL: 44
# PASS: 42
# SKIP: 0
# XFAIL: 0
# FAIL: 2
# XPASS: 0
# ERROR: 0

[denkenz@archdev ell]$ uname -a
Linux archdev 6.5.3-arch1-1 #1 SMP PREEMPT_DYNAMIC Wed, 13 Sep 2023 08:37:40 +0000 x86_64 GNU/Linux

Regards,
-Denis

#3 lore raw
In reply to James Prestwood

Hi James,

Quoted 11 lines · James Prestwood

The logic was inversed here and was performing a subtraction if:
- Y was even and type == BIT0
- Y was odd and type == BIT1

This is not correct according to the ANSI spec. IWD relied on this API but had matching incorrect logic so things "worked" up until a compressed point needed to be parsed from an source that explicitly specified the type (e.g. an ASN1 DER in DPP). All other uses (PWD/SAE) the point type was only used to force a subtraction so since both locations used the incorrect logic the points would compute correctly.

Quoted 4 lines
---
  ell/ecc.c | 18 +++++++++++++++++-
  1 file changed, 17 insertions(+), 1 deletion(-)

Both applied, thanks.

Regards,
-Denis