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 <[email protected]>
| Cc: [email protected] # v4.8+
| Reviewed-by: Lukas Wunner <[email protected]>
| Signed-off-by: Herbert Xu <[email protected]>
Fixes: d2cc4152f483 ("Add elliptic curve cryptography (ECC) helper functions")
Reported-by: Lukas Wunner <[email protected]>
Closes: https://lore.kernel.org/barebox/[email protected]/
Signed-off-by: Ahmad Fatoum <[email protected]>
---
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 <[email protected]>
@@ -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
