From c1e540575c63e09e6ab25c0c7826601d77b18d97 Mon Sep 17 00:00:00 2001
From: Thomas Pornin <pornin@bolet.org>
Date: Wed, 2 May 2018 17:32:35 +0200
Subject: [PATCH] Fixed bug in bit length computation (implied some wrong RSA
 signatures in case of carry propagation with some specific key/factor
 lengths).

---
 src/int/i15_mulacc.c | 11 ++++++++++-
 src/int/i31_mulacc.c | 11 ++++++++++-
 test/test_crypto.c   | 40 ++++++++++++++++++++++++++++++++++++++++
 3 files changed, 60 insertions(+), 2 deletions(-)

diff --git a/src/int/i15_mulacc.c b/src/int/i15_mulacc.c
index 7bde395..69f4696 100644
--- a/src/int/i15_mulacc.c
+++ b/src/int/i15_mulacc.c
@@ -29,10 +29,19 @@ void
 br_i15_mulacc(uint16_t *d, const uint16_t *a, const uint16_t *b)
 {
 	size_t alen, blen, u;
+	unsigned dl, dh;
 
 	alen = (a[0] + 15) >> 4;
 	blen = (b[0] + 15) >> 4;
-	d[0] = a[0] + b[0];
+
+	/*
+	 * Announced bit length of d[] will be the sum of the announced
+	 * bit lengths of a[] and b[]; but the lengths are encoded.
+	 */
+	dl = (a[0] & 15) + (d[0] & 15);
+	dh = (a[0] >> 4) + (b[0] >> 4);
+	d[0] = (dh << 4) + dl + (~(uint16_t)(dl - 15) >> 15);
+
 	for (u = 0; u < blen; u ++) {
 		uint32_t f;
 		size_t v;
diff --git a/src/int/i31_mulacc.c b/src/int/i31_mulacc.c
index 04a42c7..024d095 100644
--- a/src/int/i31_mulacc.c
+++ b/src/int/i31_mulacc.c
@@ -29,10 +29,19 @@ void
 br_i31_mulacc(uint32_t *d, const uint32_t *a, const uint32_t *b)
 {
 	size_t alen, blen, u;
+	uint32_t dl, dh;
 
 	alen = (a[0] + 31) >> 5;
 	blen = (b[0] + 31) >> 5;
-	d[0] = a[0] + b[0];
+
+	/*
+	 * We want to add the two bit lengths, but these are encoded,
+	 * which requires some extra care.
+	 */
+	dl = (a[0] & 31) + (b[0] & 31);
+	dh = (a[0] >> 5) + (b[0] >> 5);
+	d[0] = (dh << 5) + dl + (~(uint32_t)(dl - 31) >> 31);
+
 	for (u = 0; u < blen; u ++) {
 		uint32_t f;
 		size_t v;
diff --git a/test/test_crypto.c b/test/test_crypto.c
index 46f208c..a8119be 100644
--- a/test/test_crypto.c
+++ b/test/test_crypto.c
@@ -4759,6 +4759,11 @@ test_RSA_sign(const char *name, br_rsa_private fpriv,
 {
 	unsigned char t1[128], t2[128];
 	unsigned char hv[20], tmp[20];
+	unsigned char rsa_n[128], rsa_e[3], rsa_p[64], rsa_q[64];
+	unsigned char rsa_dp[64], rsa_dq[64], rsa_iq[64];
+	br_rsa_public_key rsa_pk;
+	br_rsa_private_key rsa_sk;
+	unsigned char hv2[64], tmp2[64], sig[128];
 	br_sha1_context hc;
 	size_t u;
 
@@ -4812,6 +4817,41 @@ test_RSA_sign(const char *name, br_rsa_private fpriv,
 		fflush(stdout);
 	}
 
+	/*
+	 * Another KAT test, which historically showed a bug.
+	 */
+	rsa_pk.n = rsa_n;
+	rsa_pk.nlen = hextobin(rsa_n, "E65DAEF196D22C300B3DAE1CE5157EDF821BB6038E419D8D363A8B2DA84A1321042330E6F87A8BD8FE6BA1D2A17031955ED2315CC5FD2397197E238A5E0D2D0AFD25717E814EC4D2BBA887327A3C5B3A450FD8D547BDFCBB0F73B997CA13DD5E7572C4D5BAA764A349BAB2F868ACF4574AE2C7AEC94B77D2EE00A21B6CB175BB");
+	rsa_pk.e = rsa_e;
+	rsa_pk.elen = hextobin(rsa_e, "010001");
+
+	rsa_sk.n_bitlen = 1024;
+	rsa_sk.p = rsa_p;
+	rsa_sk.plen = hextobin(rsa_p, "FF58513DBA4F3F42DFDFD3E6AFB6BD62DE27E06BA3C9D9F9B542CB21228C2AAE67936514161C8FDC1A248A50195CAF22ADC50DA89BFED1B9EEFBB37304241357");
+	rsa_sk.q = rsa_q;
+	rsa_sk.qlen = hextobin(rsa_q, "E6F4F66818B7442297DDEB45E9B3D438E5B57BB5EF86EFF2462AD6B9C10F383517CDD2E7E36EAD4BEBCC57CFE8AA985F7E7B38B96D30FFBE9ED9FE21B1CFB63D");
+	rsa_sk.dp = rsa_dp;
+	rsa_sk.dplen = hextobin(rsa_dp, "6F89517B682D83919F9EF2BDBA955526A1A9C382E139A3A84AC01160B8E9871F458901C7035D988D6931FAE4C01F57350BB89E9DBEFE50F829E6F25CD43B39E3");
+	rsa_sk.dq = rsa_dq;
+	rsa_sk.dqlen = hextobin(rsa_dq, "409E08D2D7176F58BE64B88EB6F4394C31F8B4C412600E821A5FA1F416AFCB6A0F5EE6C33A3E9CFDC0DB4B3640427A9F3D23FC9AE491F0FBC435F98433DB8981");
+	rsa_sk.iq = rsa_iq;
+	rsa_sk.iqlen = hextobin(rsa_iq, "CF333D6AD66D02B4D11C8C23CA669D14D71803ADC3943BE03B1E48F52F385BCFDDFD0F85AD02A984E504FC6612549D4E7867B7D09DD13196BFC3FAA4B57393A9");
+	hextobin(sig, "CFB84D161E6DB130736FC6212EBE575571AF341CEF5757C19952A5364C90E3C47549E520E26253DAE70F645F31FA8B5DA9AE282741D3CA4B1CC365B7BD75D6D61D4CFD9AD9EDD17D23E0BA7D9775138DBABC7FF2A57587FE1EA1B51E8F3C68326E26FF89D8CF92BDD4C787D04857DFC3266E6B33B92AA08809929C72642F35C2");
+
+	hextobin(hv2, "F66C62B38E1CC69C378C0E16574AE5C6443FDFA3E85C6205C00B3231CAA3074EC1481BDC22AB575E6CF3CCD9EDA6B39F83923FC0E6475C799D257545F77233B4");
+	if (!fsign(BR_HASH_OID_SHA512, hv2, 64, &rsa_sk, t2)) {
+		fprintf(stderr, "Signature generation failed (2)\n");
+		exit(EXIT_FAILURE);
+	}
+	check_equals("Regenerated signature (2)", t2, sig, sizeof t2);
+	if (!fvrfy(t2, sizeof t2, BR_HASH_OID_SHA512,
+		sizeof tmp2, &rsa_pk, tmp2))
+	{
+		fprintf(stderr, "Signature verification failed (2)\n");
+		exit(EXIT_FAILURE);
+	}
+	check_equals("Extracted hash value (2)", hv2, tmp2, sizeof tmp2);
+
 	printf(" done.\n");
 	fflush(stdout);
 }
-- 
2.17.1