From b5aa971d26113b67975492c5e8e8476b3c5e81b6 Mon Sep 17 00:00:00 2001 From: jsing Date: Wed, 21 Jun 2023 07:41:55 +0000 Subject: [PATCH] Make BN_num_bits() independent of bn->top. Provide bn_bitsize(), which performs a constant time scan of a BN in order to determine the bit size of the BN value. Use this for BN_num_bits() such that it is no longer dependent on the bn->top value. ok tb@ --- lib/libcrypto/Makefile | 3 +- lib/libcrypto/bn/bn_internal.h | 6 ++- lib/libcrypto/bn/bn_lib.c | 31 ++-------------- lib/libcrypto/bn/bn_local.h | 4 +- lib/libcrypto/bn/bn_primitives.c | 63 ++++++++++++++++++++++++++++++++ 5 files changed, 74 insertions(+), 33 deletions(-) create mode 100644 lib/libcrypto/bn/bn_primitives.c diff --git a/lib/libcrypto/Makefile b/lib/libcrypto/Makefile index 89bd94d79ae..6fe129bcdd3 100644 --- a/lib/libcrypto/Makefile +++ b/lib/libcrypto/Makefile @@ -1,4 +1,4 @@ -# $OpenBSD: Makefile,v 1.130 2023/06/11 05:35:43 tb Exp $ +# $OpenBSD: Makefile,v 1.131 2023/06/21 07:41:55 jsing Exp $ LIB= crypto LIBREBUILD=y @@ -195,6 +195,7 @@ SRCS+= bn_mod_sqrt.c SRCS+= bn_mont.c SRCS+= bn_mul.c SRCS+= bn_prime.c +SRCS+= bn_primitives.c SRCS+= bn_rand.c SRCS+= bn_recp.c SRCS+= bn_shift.c diff --git a/lib/libcrypto/bn/bn_internal.h b/lib/libcrypto/bn/bn_internal.h index 5f86e21330b..f5c69c5d77c 100644 --- a/lib/libcrypto/bn/bn_internal.h +++ b/lib/libcrypto/bn/bn_internal.h @@ -1,4 +1,4 @@ -/* $OpenBSD: bn_internal.h,v 1.12 2023/06/12 16:17:24 jsing Exp $ */ +/* $OpenBSD: bn_internal.h,v 1.13 2023/06/21 07:41:55 jsing Exp $ */ /* * Copyright (c) 2023 Joel Sing * @@ -22,6 +22,10 @@ #ifndef HEADER_BN_INTERNAL_H #define HEADER_BN_INTERNAL_H +int bn_word_clz(BN_ULONG w); + +int bn_bitsize(const BIGNUM *bn); + #ifndef HAVE_BN_CT_NE_ZERO static inline int bn_ct_ne_zero(BN_ULONG w) diff --git a/lib/libcrypto/bn/bn_lib.c b/lib/libcrypto/bn/bn_lib.c index 389dd3ff3ea..b8eb5654971 100644 --- a/lib/libcrypto/bn/bn_lib.c +++ b/lib/libcrypto/bn/bn_lib.c @@ -1,4 +1,4 @@ -/* $OpenBSD: bn_lib.c,v 1.86 2023/04/30 19:15:48 tb Exp $ */ +/* $OpenBSD: bn_lib.c,v 1.87 2023/06/21 07:41:55 jsing Exp $ */ /* Copyright (C) 1995-1998 Eric Young (eay@cryptsoft.com) * All rights reserved. * @@ -159,27 +159,6 @@ BN_value_one(void) return &bn_value_one; } -#ifndef HAVE_BN_WORD_CLZ -int -bn_word_clz(BN_ULONG w) -{ - BN_ULONG bits, mask, shift; - - bits = shift = BN_BITS2; - mask = 0; - - while ((shift >>= 1) != 0) { - bits += (shift & mask) - (shift & ~mask); - mask = bn_ct_ne_zero_mask(w >> bits); - } - bits += 1 & mask; - - bits -= bn_ct_eq_zero(w); - - return BN_BITS2 - bits; -} -#endif - int BN_num_bits_word(BN_ULONG w) { @@ -187,13 +166,9 @@ BN_num_bits_word(BN_ULONG w) } int -BN_num_bits(const BIGNUM *a) +BN_num_bits(const BIGNUM *bn) { - int i = a->top - 1; - - if (BN_is_zero(a)) - return 0; - return ((i * BN_BITS2) + BN_num_bits_word(a->d[i])); + return bn_bitsize(bn); } void diff --git a/lib/libcrypto/bn/bn_local.h b/lib/libcrypto/bn/bn_local.h index 78b4157d127..c86e4d032bb 100644 --- a/lib/libcrypto/bn/bn_local.h +++ b/lib/libcrypto/bn/bn_local.h @@ -1,4 +1,4 @@ -/* $OpenBSD: bn_local.h,v 1.22 2023/05/10 12:21:55 tb Exp $ */ +/* $OpenBSD: bn_local.h,v 1.23 2023/06/21 07:41:55 jsing Exp $ */ /* Copyright (C) 1995-1998 Eric Young (eay@cryptsoft.com) * All rights reserved. * @@ -259,8 +259,6 @@ void bn_sqr_comba8(BN_ULONG *r, const BN_ULONG *a); int bn_mul_mont(BN_ULONG *rp, const BN_ULONG *ap, const BN_ULONG *bp, const BN_ULONG *np, const BN_ULONG *n0, int num); -int bn_word_clz(BN_ULONG w); - void bn_correct_top(BIGNUM *a); int bn_expand(BIGNUM *a, int bits); int bn_wexpand(BIGNUM *a, int words); diff --git a/lib/libcrypto/bn/bn_primitives.c b/lib/libcrypto/bn/bn_primitives.c new file mode 100644 index 00000000000..e9caec48184 --- /dev/null +++ b/lib/libcrypto/bn/bn_primitives.c @@ -0,0 +1,63 @@ +/* $OpenBSD: bn_primitives.c,v 1.1 2023/06/21 07:41:55 jsing Exp $ */ +/* + * Copyright (c) 2023 Joel Sing + * + * Permission to use, copy, modify, and distribute this software for any + * purpose with or without fee is hereby granted, provided that the above + * copyright notice and this permission notice appear in all copies. + * + * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES + * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF + * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR + * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES + * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN + * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF + * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE. + */ + +#include + +#include "bn_arch.h" +#include "bn_internal.h" +#include "bn_local.h" + +#ifndef HAVE_BN_WORD_CLZ +int +bn_word_clz(BN_ULONG w) +{ + BN_ULONG bits, mask, shift; + + bits = shift = BN_BITS2; + mask = 0; + + while ((shift >>= 1) != 0) { + bits += (shift & mask) - (shift & ~mask); + mask = bn_ct_ne_zero_mask(w >> bits); + } + bits += 1 & mask; + + bits -= bn_ct_eq_zero(w); + + return BN_BITS2 - bits; +} +#endif + +#ifndef HAVE_BN_BITSIZE +int +bn_bitsize(const BIGNUM *bn) +{ + BN_ULONG n = 0, x = 0; + BN_ULONG mask, w; + int i = 0; + + while (i < bn->top) { + w = bn->d[i]; + mask = bn_ct_ne_zero_mask(w); + n = ((BN_ULONG)i & mask) | (n & ~mask); + x = (w & mask) | (x & ~mask); + i++; + } + + return (n + 1) * BN_BITS2 - bn_word_clz(x); +} +#endif -- 2.20.1