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 a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox