[PATCH 1/3] crypto: ecc - Fix carry overflow in vli multiplication

[Ahmad Fatoum <a.fatoum@barebox.org>]

This is an adoption of the corresponding Linux commit:

| commit 27b536a2ec8e2f85a0380c2d13c9ecbc7aaab406
|
|     crypto: ecc - Fix carry overflow in vli multiplication
|
|     The carry flag calculation fails when r01.m_high is saturated
|     (0xFFFFFFFFFFFFFFFF) and addition of lower bits overflows.
|
|     The condition (r01.m_high < product.m_high) doesn't handle the case
|     where r01.m_high == product.m_high and an additional carry exists
|     from lower-bit overflow.
|
|     When commit 3c4b23901a0c ("crypto: ecdh - Add ECDH software support")
|     introduced crypto/ecc.c, it split the muladd() function in the
|     micro-ecc library into separate mul_64_64() and add_128_128() helpers.
|     It seems the check got lost in translation.
|
|     Add proper handling for this boundary by accounting for the carry
|     from the lower addition.
|
|     Fixes: 3c4b23901a0c ("crypto: ecdh - Add ECDH software support")
|     Signed-off-by: Anastasia Tishchenko <sv3iry@gmail.com>
|     Cc: stable@vger.kernel.org # v4.8+
|     Reviewed-by: Lukas Wunner <lukas@wunner.de>
|     Signed-off-by: Herbert Xu <herbert@gondor.apana.org.au>

Fixes: d2cc4152f483 ("Add elliptic curve cryptography (ECC) helper functions")
Reported-by: Lukas Wunner <lukas@wunner.de>
Closes: https://lore.kernel.org/barebox/agS_XfdyvX_1q9dt@wunner.de/
Signed-off-by: Ahmad Fatoum <a.fatoum@barebox.org>
---
 crypto/ecc.c | 33 +++++++++++++++++++++------------
 1 file changed, 21 insertions(+), 12 deletions(-)

diff --git a/crypto/ecc.c b/crypto/ecc.c
index b6abdbee67be..67faae0a68f9 100644
--- a/crypto/ecc.c
+++ b/crypto/ecc.c
@@ -1,4 +1,4 @@
-// SPDX-Comment: Origin-URL: https://git.kernel.org/pub/scm/linux/kernel/git/torvalds/linux.git/tree/crypto/ecc.c?id=d6ea871d73abbb6a1e00e71ed5762e394d06cb2b
+// SPDX-Comment: Origin-URL: https://git.kernel.org/pub/scm/linux/kernel/git/torvalds/linux.git/tree/crypto/ecc.c?id=27b536a2ec8e2f85a0380c2d13c9ecbc7aaab406
 /*
  * Copyright (c) 2013, 2014 Kenneth MacKay. All rights reserved.
  * Copyright (c) 2019 Vitaly Chikunov <vt@altlinux.org>
@@ -381,14 +381,26 @@ static uint128_t mul_64_64(u64 left, u64 right)
 	return result;
 }
 
-static uint128_t add_128_128(uint128_t a, uint128_t b)
+/* Calculate addition with overflow checking. Returns true on wrap-around,
+ * false otherwise.
+ */
+static bool check_add_128_128_overflow(uint128_t *result, uint128_t a,
+				       uint128_t b)
 {
-	uint128_t result;
+	bool carry;
 
-	result.m_low = a.m_low + b.m_low;
-	result.m_high = a.m_high + b.m_high + (result.m_low < a.m_low);
+	result->m_low = a.m_low + b.m_low;
+	carry = (result->m_low < a.m_low);
 
-	return result;
+	result->m_high = a.m_high + b.m_high + carry;
+
+	/* Using constant-time bitwise arithmetic to prevent timing
+	 * side-channels.
+	 */
+	carry = (result->m_high < a.m_high) |
+		((result->m_high == a.m_high) & carry);
+
+	return carry;
 }
 
 static void vli_mult(u64 *result, const u64 *left, const u64 *right,
@@ -413,9 +425,7 @@ static void vli_mult(u64 *result, const u64 *left, const u64 *right,
 			uint128_t product;
 
 			product = mul_64_64(left[i], right[k - i]);
-
-			r01 = add_128_128(r01, product);
-			r2 += (r01.m_high < product.m_high);
+			r2 += check_add_128_128_overflow(&r01, r01, product);
 		}
 
 		result[k] = r01.m_low;
@@ -438,7 +448,7 @@ static void vli_umult(u64 *result, const u64 *left, u32 right,
 		uint128_t product;
 
 		product = mul_64_64(left[k], right);
-		r01 = add_128_128(r01, product);
+		check_add_128_128_overflow(&r01, r01, product);
 		/* no carry */
 		result[k] = r01.m_low;
 		r01.m_low = r01.m_high;
@@ -475,8 +485,7 @@ static void vli_square(u64 *result, const u64 *left, unsigned int ndigits)
 				product.m_low <<= 1;
 			}
 
-			r01 = add_128_128(r01, product);
-			r2 += (r01.m_high < product.m_high);
+			r2 += check_add_128_128_overflow(&r01, r01, product);
 		}
 
 		result[k] = r01.m_low;
-- 
2.47.3