From c1e540575c63e09e6ab25c0c7826601d77b18d97 Mon Sep 17 00:00:00 2001 From: Thomas Pornin 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