From: Sasha Levin <sashal@kernel.org>
To: stable@vger.kernel.org
Cc: "Jérémy Jean" <Jeremy.Jean@oss.cyber.gouv.fr>,
"Ignat Korchagin" <ignat@linux.win>,
"Stefan Berger" <stefanb@linux.ibm.com>,
"Herbert Xu" <herbert@gondor.apana.org.au>,
"Sasha Levin" <sashal@kernel.org>
Subject: [PATCH 5.10.y] crypto: ecc - Handle exceptional points in Shamir multiplication
Date: Tue, 10 Nov 2026 11:24:06 -0500 [thread overview]
Message-ID: <20261110161933.2054228-1-sashal@kernel.org> (raw)
In-Reply-To: <20261107061814-failed-5.10-6fd70bc8bc01@kernel.org>
From: Jérémy Jean <Jeremy.Jean@oss.cyber.gouv.fr>
[ Upstream commit 6fd70bc8bc01a578c7728b7bd1cb5689c62cc5b7 ]
Shamir multiplication mishandles equal points, opposite points and the
point at infinity. This rejects valid ECDSA signatures and can accept
invalid digest/signature tuples when the public key is G or -G. The
kernel incorrectly rejects 16 valid signatures from Wycheproof.
Handle doubling, cancellation and the point at infinity in precomputation
and accumulation. Add regression tests for P-256 ECDSA and 256/512-bit
EC-RDSA. The valid vectors are Wycheproof P1363 secp256r1/SHA-256 cases
60 and 210 converted to X9.62, two constructed ECDSA signatures for
Q = +/-G with k = 2, and six constructed EC-RDSA signatures for Q = G,
-G and -2G. Also add two invalid P-256 digest/signature tuples for
Q = +/-G that must return -EKEYREJECTED.
Fixes: 0d7a78643f69 ("crypto: ecrdsa - add EC-RDSA (GOST 34.10) algorithm")
Cc: stable@vger.kernel.org
Assisted-by: LLM
Signed-off-by: Jérémy Jean <Jeremy.Jean@oss.cyber.gouv.fr>
Reviewed-by: Ignat Korchagin <ignat@linux.win>
Reviewed-by: Stefan Berger <stefanb@linux.ibm.com>
Signed-off-by: Herbert Xu <herbert@gondor.apana.org.au>
[ sashal: adapted ECC doubling calls and EC-RDSA vectors to older APIs lacking ECDSA and negative-result test support. ]
Signed-off-by: Sasha Levin <sashal@kernel.org>
---
crypto/ecc.c | 33 +++++++-
crypto/testmgr.h | 198 ++++++++++++++++++++++++++++++++++++++++++++++-
2 files changed, 228 insertions(+), 3 deletions(-)
diff --git a/crypto/ecc.c b/crypto/ecc.c
index 09067e4b320f5..506a89e90a0b4 100644
--- a/crypto/ecc.c
+++ b/crypto/ecc.c
@@ -1224,9 +1224,22 @@ static void ecc_point_add(const struct ecc_point *result,
vli_set(result->x, q->x, ndigits);
vli_set(result->y, q->y, ndigits);
vli_mod_sub(z, result->x, p->x, curve->p, ndigits);
+ if (vli_is_zero(z, ndigits)) {
+ if (vli_cmp(p->y, q->y, ndigits)) {
+ /* P + (-P) is the point at infinity. */
+ vli_clear(result->x, ndigits);
+ vli_clear(result->y, ndigits);
+ return;
+ }
+ /* The co-Z addition formula does not handle P == Q. */
+ z[0] = 1;
+ ecc_point_double_jacobian(result->x, result->y, z, curve->p, ndigits);
+ goto out;
+ }
vli_set(px, p->x, ndigits);
vli_set(py, p->y, ndigits);
xycz_add(px, py, result->x, result->y, curve->p, ndigits);
+out:
vli_mod_inv(z, z, curve->p, ndigits);
apply_z(result->x, result->y, z, curve->p, ndigits);
}
@@ -1266,21 +1279,37 @@ void ecc_point_mult_shamir(const struct ecc_point *result,
vli_set(rx, point->x, ndigits);
vli_set(ry, point->y, ndigits);
vli_clear(z + 1, ndigits - 1);
- z[0] = 1;
+ z[0] = !ecc_point_is_zero(point);
for (--i; i >= 0; i--) {
ecc_point_double_jacobian(rx, ry, z, curve->p, ndigits);
idx = (!!vli_test_bit(u1, i)) | ((!!vli_test_bit(u2, i)) << 1);
point = points[idx];
- if (point) {
+ if (point && !ecc_point_is_zero(point)) {
u64 tx[ECC_MAX_DIGITS];
u64 ty[ECC_MAX_DIGITS];
u64 tz[ECC_MAX_DIGITS];
+ if (vli_is_zero(z, ndigits)) {
+ /* Adding to infinity starts a new accumulator. */
+ vli_set(rx, point->x, ndigits);
+ vli_set(ry, point->y, ndigits);
+ z[0] = 1;
+ continue;
+ }
vli_set(tx, point->x, ndigits);
vli_set(ty, point->y, ndigits);
apply_z(tx, ty, z, curve->p, ndigits);
vli_mod_sub(tz, rx, tx, curve->p, ndigits);
+ if (vli_is_zero(tz, ndigits)) {
+ if (!vli_cmp(ry, ty, ndigits))
+ ecc_point_double_jacobian(rx, ry, z,
+ curve->p, ndigits);
+ else
+ /* Adding opposite points yields infinity. */
+ vli_clear(z, ndigits);
+ continue;
+ }
xycz_add(tx, ty, rx, ry, curve->p, ndigits);
vli_mod_mult_fast(z, z, tz, curve->p, ndigits);
}
diff --git a/crypto/testmgr.h b/crypto/testmgr.h
index 45212d077c298..103b45279764b 100644
--- a/crypto/testmgr.h
+++ b/crypto/testmgr.h
@@ -646,7 +646,8 @@ static const struct akcipher_testvec rsa_tv_template[] = {
};
/*
- * EC-RDSA test vectors are generated by gost-engine.
+ * EC-RDSA test vectors generated by gost-engine, followed by constructed
+ * exceptional-point regression vectors.
*/
static const struct akcipher_testvec ecrdsa_tv_template[] = {
{
@@ -797,6 +798,201 @@ static const struct akcipher_testvec ecrdsa_tv_template[] = {
.public_key_vec = true,
.siggen_sigver_test = true,
},
+ /*
+ * Constructed EC-RDSA exceptional-point vectors.
+ * With Q = dG, choose k = z1 + d*z2 (mod n), r = x(kG) mod n,
+ * e = -r/z2 (mod n), and s = r*d + k*e (mod n).
+ * The input digest is e, encoded little-endian.
+ */
+ /* cp256a: Q=G, z1 = 3, z2 = 1. */
+ {
+ .key =
+ "\x04\x40\x01\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00"
+ "\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00"
+ "\x00\x00\x14\x1e\x9f\x9e\x9c\xc9\xac\x22\xb1\xe3\x23\xdf\x2d\x4f"
+ "\x29\x35\x76\x2b\x3f\x45\x5a\x50\xdf\x27\xda\x9c\x98\xe0\x71\xe4"
+ "\x91\x8d",
+ .key_len = 66,
+ .params = /* OID_gostCPSignA */
+ "\x30\x13\x06\x07\x2a\x85\x03\x02\x02\x23\x01\x06\x08\x2a\x85\x03"
+ "\x07\x01\x01\x02\x02",
+ .param_len = 21,
+ .c =
+ "\x1a\xed\x44\xae\xd4\x4a\xed\x44\xae\xd4\x4a\xed\x44\xae\xd4\x49"
+ "\x32\x67\xe0\x26\x16\xfd\xb7\xaf\xa4\xd7\x3e\x61\xd4\xf9\x7b\x94"
+ "\xf7\x06\x3e\x70\x63\xe7\x06\x3e\x70\x63\xe7\x06\x3e\x70\x63\xe7"
+ "\x06\x3e\x70\x63\xe7\x06\x3e\x70\x63\xe7\x06\x3e\x70\x63\xe4\xb7",
+ .c_size = 64,
+ .m =
+ "\xdc\xd3\xfd\x46\xcb\x14\x9d\xe1\x8f\x92\x54\xb2\x0c\xa0\x22\x66"
+ "\x18\x9c\x8f\xc1\xf9\x18\x9c\x8f\xc1\xf9\x18\x9c\x8f\xc1\xf9\x08",
+ .m_size = 32,
+ .algo = OID_gost2012PKey256,
+ .public_key_vec = true,
+ .siggen_sigver_test = true,
+ },
+ /* cp256a: Q=-G, z1 = 7, z2 = 6. */
+ {
+ .key =
+ "\x04\x40\x01\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00"
+ "\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00"
+ "\x00\x00\x83\xdf\x60\x61\x63\x36\x53\xdd\x4e\x1c\xdc\x20\xd2\xb0"
+ "\xd6\xca\x89\xd4\xc0\xba\xa5\xaf\x20\xd8\x25\x63\x67\x1f\x8e\x1b"
+ "\x6e\x72",
+ .key_len = 66,
+ .params = /* OID_gostCPSignA */
+ "\x30\x13\x06\x07\x2a\x85\x03\x02\x02\x23\x01\x06\x08\x2a\x85\x03"
+ "\x07\x01\x01\x02\x02",
+ .param_len = 21,
+ .c =
+ "\x2a\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa"
+ "\x92\x10\x2d\x68\x19\x8f\x22\xd5\x60\xeb\x59\xd6\xf3\xe5\x9e\xc2"
+ "\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00"
+ "\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x01",
+ .c_size = 64,
+ .m =
+ "\xc3\x9e\xe5\xf3\xd6\x59\xeb\x60\xd5\x22\x8f\x19\x68\x2d\x10\x92"
+ "\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\x2a",
+ .m_size = 32,
+ .algo = OID_gost2012PKey256,
+ .public_key_vec = true,
+ .siggen_sigver_test = true,
+ },
+ /* cp256a: Q=-2G, z1 = 5, z2 = 2. */
+ {
+ .key =
+ "\x04\x40\x95\xfd\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff"
+ "\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff"
+ "\xff\xff\x14\x1e\x9f\x9e\x9c\xc9\xac\x22\xb1\xe3\x23\xdf\x2d\x4f"
+ "\x29\x35\x76\x2b\x3f\x45\x5a\x50\xdf\x27\xda\x9c\x98\xe0\x71\xe4"
+ "\x91\x8d",
+ .key_len = 66,
+ .params = /* OID_gostCPSignA */
+ "\x30\x13\x06\x07\x2a\x85\x03\x02\x02\x23\x01\x06\x08\x2a\x85\x03"
+ "\x07\x01\x01\x02\x02",
+ .param_len = 21,
+ .c =
+ "\x7f\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff"
+ "\xb6\x30\x88\x38\x4c\xad\x68\x80\x22\xc2\x0d\x84\xdb\xb0\xdc\x47"
+ "\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00"
+ "\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x01",
+ .c_size = 64,
+ .m =
+ "\x49\xdc\xb0\xdb\x84\x0d\xc2\x22\x80\x68\xad\x4c\x38\x88\x30\xb6"
+ "\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\x7f",
+ .m_size = 32,
+ .algo = OID_gost2012PKey256,
+ .public_key_vec = true,
+ .siggen_sigver_test = true,
+ },
+ /* tc512a: Q=G, z1 = 3, z2 = 1. */
+ {
+ .key =
+ "\x04\x81\x80\x03\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00"
+ "\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00"
+ "\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00"
+ "\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00"
+ "\x00\x00\x00\xa4\xf2\x15\x52\xcb\x89\xa5\x89\xb8\xf5\x35\xc2\x5f"
+ "\xfe\x28\x80\xe9\x41\x3a\x0e\xa5\xe6\x75\x3d\xe9\x36\xd0\x4f\xbe"
+ "\x26\x16\xdf\x21\xa9\xef\xcb\xfd\x64\x80\x77\xc1\xab\xf1\xac\x93"
+ "\x1c\x5e\xce\xe6\x50\x54\xe2\x16\x88\x1b\xa6\xe3\x6a\x83\x7a\xe8"
+ "\xcf\x03\x75",
+ .key_len = 131,
+ .params = /* OID_gostTC26Sign512A */
+ "\x30\x0b\x06\x09\x2a\x85\x03\x07\x01\x02\x01\x02\x01",
+ .param_len = 13,
+ .c =
+ "\xd8\xc0\xd7\xe3\xfb\xa6\xca\xff\x6a\xd1\xb4\xb4\x82\x1d\x15\x6f"
+ "\xa7\xc7\xbd\x63\x95\xb8\x29\x0d\xd4\xfa\xb1\x1c\x36\xbd\x32\x8d"
+ "\x1a\xba\xf1\x2e\xbc\x7b\xf2\x02\x96\xf8\xef\x2a\x5e\x72\x64\x86"
+ "\x67\x62\xfb\x62\x8e\x83\x53\x63\xb7\xe6\x78\x3c\x42\xd7\x0d\x1d"
+ "\xb7\xbf\xb8\x09\x56\xc8\x67\x00\x31\xba\x19\x19\x29\xf6\x4e\x30"
+ "\x1d\x68\x16\x34\x23\x6d\x47\xa6\x0e\x57\x1a\x4b\xed\xc0\xef\x25"
+ "\x74\x52\xef\x78\xb5\xb9\x8d\xbb\x3d\x9f\x31\x29\xd9\x34\x94\x33"
+ "\xce\x2a\x3a\x35\xcb\x51\x9c\x91\xe2\xd6\x33\xd7\xb3\x73\xae\x16",
+ .c_size = 128,
+ .m =
+ "\x5f\x04\x9d\x6b\x69\x7d\xf7\xe7\xcb\x1b\x81\x2f\x76\xfe\x20\xcd"
+ "\x2c\xcc\xd0\x74\x63\xfa\x52\x32\x56\xfb\xd3\x3e\xba\xa5\x93\xb3"
+ "\xd9\x10\x3f\x12\xb4\xe5\xa8\xf1\x59\xb8\x92\xdc\xcb\xe9\x97\xe2"
+ "\xcf\xb1\x09\xd6\xe6\xe6\x45\xce\xff\x98\x37\xa9\xf6\x47\x40\x48",
+ .m_size = 64,
+ .algo = OID_gost2012PKey512,
+ .public_key_vec = true,
+ .siggen_sigver_test = true,
+ },
+ /* tc512a: Q=-G, z1 = 7, z2 = 6. */
+ {
+ .key =
+ "\x04\x81\x80\x03\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00"
+ "\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00"
+ "\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00"
+ "\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00"
+ "\x00\x00\x00\x23\x0b\xea\xad\x34\x76\x5a\x76\x47\x0a\xca\x3d\xa0"
+ "\x01\xd7\x7f\x16\xbe\xc5\xf1\x5a\x19\x8a\xc2\x16\xc9\x2f\xb0\x41"
+ "\xd9\xe9\x20\xde\x56\x10\x34\x02\x9b\x7f\x88\x3e\x54\x0e\x53\x6c"
+ "\xe3\xa1\x31\x19\xaf\xab\x1d\xe9\x77\xe4\x59\x1c\x95\x7c\x85\x17"
+ "\x30\xfc\x8a",
+ .key_len = 131,
+ .params = /* OID_gostTC26Sign512A */
+ "\x30\x0b\x06\x09\x2a\x85\x03\x07\x01\x02\x01\x02\x01",
+ .param_len = 13,
+ .c =
+ "\x7f\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff"
+ "\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff"
+ "\x93\xf3\x4a\x99\x7a\x46\xc4\x88\xb7\xf9\x15\xc6\xa7\x02\xb0\x30"
+ "\x4d\xa5\x9c\x55\xfd\x69\x5c\x2e\xe5\x66\xd8\xa0\x8f\x88\x59\x37"
+ "\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00"
+ "\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00"
+ "\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00"
+ "\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x03",
+ .c_size = 128,
+ .m =
+ "\x3a\x59\x88\x8f\xa0\xd8\x66\xe5\x2e\x5c\x69\xfd\x55\x9c\xa5\x4d"
+ "\x30\xb0\x02\xa7\xc6\x15\xf9\xb7\x88\xc4\x46\x7a\x99\x4a\xf3\x93"
+ "\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff"
+ "\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\x7f",
+ .m_size = 64,
+ .algo = OID_gost2012PKey512,
+ .public_key_vec = true,
+ .siggen_sigver_test = true,
+ },
+ /* tc512a: Q=-2G, z1 = 5, z2 = 2. */
+ {
+ .key =
+ "\x04\x81\x80\x7c\x13\xea\xd2\xd9\xaf\x82\xb9\x1f\xb2\xfd\xe1\x8d"
+ "\xf4\x5b\x37\xe4\xf2\x04\x6a\x2a\x1d\x15\x16\x95\x2a\x5d\x40\xcd"
+ "\xbb\x34\x44\x2f\x2b\x13\x0a\x47\xb0\xf6\xe5\xa5\x58\x3a\xf4\x54"
+ "\x09\xb0\x1d\xf5\x5c\xf1\xbf\x9d\x86\xa5\x97\xab\x96\x29\x62\xfc"
+ "\xdc\x89\x3b\x76\x3d\x50\x6e\x8a\xcf\x02\x4c\x74\x0e\x6e\xe0\x1f"
+ "\x28\xab\x27\x9b\x20\x02\xc8\xc4\x12\xcb\x8a\xe3\xa4\x27\xce\x39"
+ "\x62\xdf\x35\x6d\xc1\x65\x7f\x7b\x48\x90\x11\x8f\x19\x7c\x1e\x67"
+ "\x91\x97\xeb\x90\x85\x25\xfc\x86\xb3\x88\x6e\x5c\x57\x1f\x1d\x1d"
+ "\x3b\xec\x37",
+ .key_len = 131,
+ .params = /* OID_gostTC26Sign512A */
+ "\x30\x0b\x06\x09\x2a\x85\x03\x07\x01\x02\x01\x02\x01",
+ .param_len = 13,
+ .c =
+ "\x7f\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff"
+ "\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff"
+ "\x93\xf3\x4a\x99\x7a\x46\xc4\x88\xb7\xf9\x15\xc6\xa7\x02\xb0\x30"
+ "\x4d\xa5\x9c\x55\xfd\x69\x5c\x2e\xe5\x66\xd8\xa0\x8f\x88\x59\x33"
+ "\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00"
+ "\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00"
+ "\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00"
+ "\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x03",
+ .c_size = 128,
+ .m =
+ "\x39\x59\x88\x8f\xa0\xd8\x66\xe5\x2e\x5c\x69\xfd\x55\x9c\xa5\x4d"
+ "\x30\xb0\x02\xa7\xc6\x15\xf9\xb7\x88\xc4\x46\x7a\x99\x4a\xf3\x93"
+ "\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff"
+ "\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\x7f",
+ .m_size = 64,
+ .algo = OID_gost2012PKey512,
+ .public_key_vec = true,
+ .siggen_sigver_test = true,
+ },
};
/*
--
2.53.0
prev parent reply other threads:[~2026-11-10 16:24 UTC|newest]
Thread overview: 2+ messages / expand[flat|nested] mbox.gz Atom feed top
2026-11-07 11:18 FAILED: patch "[PATCH] crypto: ecc - Handle exceptional points in Shamir multiplication" failed to apply to 5.10-stable tree Sasha Levin
2026-11-10 16:24 ` Sasha Levin [this message]
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to=20261110161933.2054228-1-sashal@kernel.org \
--to=sashal@kernel.org \
--cc=Jeremy.Jean@oss.cyber.gouv.fr \
--cc=herbert@gondor.apana.org.au \
--cc=ignat@linux.win \
--cc=stable@vger.kernel.org \
--cc=stefanb@linux.ibm.com \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
* If your mail client supports setting the In-Reply-To header
via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
This is an external index of several public inboxes,
see mirroring instructions on how to clone and mirror
all data and code used by this external index.