/*
* Copyright 1995-2018 The OpenSSL Project Authors. All Rights Reserved.
*
- * Licensed under the OpenSSL license (the "License"). You may not use
+ * Licensed under the Apache License 2.0 (the "License"). You may not use
* this file except in compliance with the License. You can obtain a copy
* in the file LICENSE in the source distribution or at
* https://www.openssl.org/source/license.html
#include <assert.h>
#include <limits.h>
#include "internal/cryptlib.h"
-#include "bn_lcl.h"
+#include "bn_local.h"
#include <openssl/opensslconf.h>
+#include "internal/constant_time.h"
/* This stuff appears to be completely unused, so is deprecated */
-#if OPENSSL_API_COMPAT < 0x00908000L
+#ifndef OPENSSL_NO_DEPRECATED_0_9_8
/*-
* For a 32 bit machine
* 2 - 4 == 128
return bits;
}
+/*
+ * This function still leaks `a->dmax`: it's caller's responsibility to
+ * expand the input `a` in advance to a public length.
+ */
+static ossl_inline
+int bn_num_bits_consttime(const BIGNUM *a)
+{
+ int j, ret;
+ unsigned int mask, past_i;
+ int i = a->top - 1;
+ bn_check_top(a);
+
+ for (j = 0, past_i = 0, ret = 0; j < a->dmax; j++) {
+ mask = constant_time_eq_int(i, j); /* 0xff..ff if i==j, 0x0 otherwise */
+
+ ret += BN_BITS2 & (~mask & ~past_i);
+ ret += BN_num_bits_word(a->d[j]) & mask;
+
+ past_i |= mask; /* past_i will become 0xff..ff after i==j */
+ }
+
+ /*
+ * if BN_is_zero(a) => i is -1 and ret contains garbage, so we mask the
+ * final result.
+ */
+ mask = ~(constant_time_eq_int(i, ((int)-1)));
+
+ return ret & mask;
+}
+
int BN_num_bits(const BIGNUM *a)
{
int i = a->top - 1;
bn_check_top(a);
+ if (a->flags & BN_FLG_CONSTTIME) {
+ /*
+ * We assume that BIGNUMs flagged as CONSTTIME have also been expanded
+ * so that a->dmax is not leaking secret information.
+ *
+ * In other words, it's the caller's responsibility to ensure `a` has
+ * been preallocated in advance to a public length if we hit this
+ * branch.
+ *
+ */
+ return bn_num_bits_consttime(a);
+ }
+
if (BN_is_zero(a))
return 0;
+
return ((i * BN_BITS2) + BN_num_bits_word(a->d[i]));
}
-static void bn_free_d(BIGNUM *a)
+static void bn_free_d(BIGNUM *a, int clear)
{
if (BN_get_flags(a, BN_FLG_SECURE))
- OPENSSL_secure_free(a->d);
+ OPENSSL_secure_clear_free(a->d, a->dmax * sizeof(a->d[0]));
+ else if (clear != 0)
+ OPENSSL_clear_free(a->d, a->dmax * sizeof(a->d[0]));
else
OPENSSL_free(a->d);
}
{
if (a == NULL)
return;
- if (a->d != NULL && !BN_get_flags(a, BN_FLG_STATIC_DATA)) {
- OPENSSL_cleanse(a->d, a->dmax * sizeof(a->d[0]));
- bn_free_d(a);
- }
+ if (a->d != NULL && !BN_get_flags(a, BN_FLG_STATIC_DATA))
+ bn_free_d(a, 1);
if (BN_get_flags(a, BN_FLG_MALLOCED)) {
OPENSSL_cleanse(a, sizeof(*a));
OPENSSL_free(a);
if (a == NULL)
return;
if (!BN_get_flags(a, BN_FLG_STATIC_DATA))
- bn_free_d(a);
+ bn_free_d(a, 0);
if (a->flags & BN_FLG_MALLOCED)
OPENSSL_free(a);
}
{
BN_ULONG *a = NULL;
- bn_check_top(b);
-
if (words > (INT_MAX / (4 * BN_BITS2))) {
BNerr(BN_F_BN_EXPAND_INTERNAL, BN_R_BIGNUM_TOO_LONG);
return NULL;
BIGNUM *bn_expand2(BIGNUM *b, int words)
{
- bn_check_top(b);
-
if (words > b->dmax) {
BN_ULONG *a = bn_expand_internal(b, words);
if (!a)
return NULL;
- if (b->d) {
- OPENSSL_cleanse(b->d, b->dmax * sizeof(b->d[0]));
- bn_free_d(b);
- }
+ if (b->d != NULL)
+ bn_free_d(b, 1);
b->d = a;
b->dmax = words;
}
- bn_check_top(b);
return b;
}
BIGNUM *BN_copy(BIGNUM *a, const BIGNUM *b)
{
+ int bn_words;
+
bn_check_top(b);
+ bn_words = BN_get_flags(b, BN_FLG_CONSTTIME) ? b->dmax : b->top;
+
if (a == b)
return a;
- if (bn_wexpand(a, b->top) == NULL)
+ if (bn_wexpand(a, bn_words) == NULL)
return NULL;
if (b->top > 0)
- memcpy(a->d, b->d, sizeof(b->d[0]) * b->top);
+ memcpy(a->d, b->d, sizeof(b->d[0]) * bn_words);
- a->top = b->top;
a->neg = b->neg;
+ a->top = b->top;
+ a->flags |= b->flags & BN_FLG_FIXED_TOP;
bn_check_top(a);
return a;
}
+#define FLAGS_DATA(flags) ((flags) & (BN_FLG_STATIC_DATA \
+ | BN_FLG_CONSTTIME \
+ | BN_FLG_SECURE \
+ | BN_FLG_FIXED_TOP))
+#define FLAGS_STRUCT(flags) ((flags) & (BN_FLG_MALLOCED))
+
void BN_swap(BIGNUM *a, BIGNUM *b)
{
int flags_old_a, flags_old_b;
b->dmax = tmp_dmax;
b->neg = tmp_neg;
- a->flags =
- (flags_old_a & BN_FLG_MALLOCED) | (flags_old_b & BN_FLG_STATIC_DATA);
- b->flags =
- (flags_old_b & BN_FLG_MALLOCED) | (flags_old_a & BN_FLG_STATIC_DATA);
+ a->flags = FLAGS_STRUCT(flags_old_a) | FLAGS_DATA(flags_old_b);
+ b->flags = FLAGS_STRUCT(flags_old_b) | FLAGS_DATA(flags_old_a);
bn_check_top(a);
bn_check_top(b);
}
void BN_clear(BIGNUM *a)
{
+ if (a == NULL)
+ return;
bn_check_top(a);
if (a->d != NULL)
OPENSSL_cleanse(a->d, sizeof(*a->d) * a->dmax);
- a->top = 0;
a->neg = 0;
+ a->top = 0;
+ a->flags &= ~BN_FLG_FIXED_TOP;
}
BN_ULONG BN_get_word(const BIGNUM *a)
a->neg = 0;
a->d[0] = w;
a->top = (w ? 1 : 0);
+ a->flags &= ~BN_FLG_FIXED_TOP;
bn_check_top(a);
return 1;
}
return ret;
}
+typedef enum {big, little} endianess_t;
+
/* ignore negative */
-static int bn2binpad(const BIGNUM *a, unsigned char *to, int tolen)
+static
+int bn2binpad(const BIGNUM *a, unsigned char *to, int tolen, endianess_t endianess)
{
- int i;
+ int n;
+ size_t i, lasti, j, atop, mask;
BN_ULONG l;
- bn_check_top(a);
- i = BN_num_bytes(a);
- if (tolen == -1)
- tolen = i;
- else if (tolen < i)
- return -1;
- /* Add leading zeroes if necessary */
- if (tolen > i) {
- memset(to, 0, tolen - i);
- to += tolen - i;
+ /*
+ * In case |a| is fixed-top, BN_num_bytes can return bogus length,
+ * but it's assumed that fixed-top inputs ought to be "nominated"
+ * even for padded output, so it works out...
+ */
+ n = BN_num_bytes(a);
+ if (tolen == -1) {
+ tolen = n;
+ } else if (tolen < n) { /* uncommon/unlike case */
+ BIGNUM temp = *a;
+
+ bn_correct_top(&temp);
+ n = BN_num_bytes(&temp);
+ if (tolen < n)
+ return -1;
+ }
+
+ /* Swipe through whole available data and don't give away padded zero. */
+ atop = a->dmax * BN_BYTES;
+ if (atop == 0) {
+ OPENSSL_cleanse(to, tolen);
+ return tolen;
}
- while (i--) {
+
+ lasti = atop - 1;
+ atop = a->top * BN_BYTES;
+ if (endianess == big)
+ to += tolen; /* start from the end of the buffer */
+ for (i = 0, j = 0; j < (size_t)tolen; j++) {
+ unsigned char val;
l = a->d[i / BN_BYTES];
- *(to++) = (unsigned char)(l >> (8 * (i % BN_BYTES))) & 0xff;
+ mask = 0 - ((j - atop) >> (8 * sizeof(i) - 1));
+ val = (unsigned char)(l >> (8 * (i % BN_BYTES)) & mask);
+ if (endianess == big)
+ *--to = val;
+ else
+ *to++ = val;
+ i += (i - lasti) >> (8 * sizeof(i) - 1); /* stay on last limb */
}
+
return tolen;
}
{
if (tolen < 0)
return -1;
- return bn2binpad(a, to, tolen);
+ return bn2binpad(a, to, tolen, big);
}
int BN_bn2bin(const BIGNUM *a, unsigned char *to)
{
- return bn2binpad(a, to, -1);
+ return bn2binpad(a, to, -1, big);
}
BIGNUM *BN_lebin2bn(const unsigned char *s, int len, BIGNUM *ret)
int BN_bn2lebinpad(const BIGNUM *a, unsigned char *to, int tolen)
{
- int i;
- BN_ULONG l;
- bn_check_top(a);
- i = BN_num_bytes(a);
- if (tolen < i)
+ if (tolen < 0)
return -1;
- /* Add trailing zeroes if necessary */
- if (tolen > i)
- memset(to + i, 0, tolen - i);
- to += i;
- while (i--) {
- l = a->d[i / BN_BYTES];
- to--;
- *to = (unsigned char)(l >> (8 * (i % BN_BYTES))) & 0xff;
- }
- return tolen;
+ return bn2binpad(a, to, tolen, little);
+}
+
+BIGNUM *BN_native2bn(const unsigned char *s, int len, BIGNUM *ret)
+{
+#ifdef B_ENDIAN
+ return BN_bin2bn(s, len, ret);
+#else
+ return BN_lebin2bn(s, len, ret);
+#endif
+}
+
+int BN_bn2nativepad(const BIGNUM *a, unsigned char *to, int tolen)
+{
+#ifdef B_ENDIAN
+ return BN_bn2binpad(a, to, tolen);
+#else
+ return BN_bn2lebinpad(a, to, tolen);
+#endif
}
int BN_ucmp(const BIGNUM *a, const BIGNUM *b)
for (k = a->top; k < i + 1; k++)
a->d[k] = 0;
a->top = i + 1;
+ a->flags &= ~BN_FLG_FIXED_TOP;
}
a->d[i] |= (((BN_ULONG)1) << j);
int i;
BN_ULONG aa, bb;
+ if (n == 0)
+ return 0;
+
aa = a[n - 1];
bb = b[n - 1];
if (aa != bb)
return bn_cmp_words(a, b, cl);
}
-/*
+/*-
* Constant-time conditional swap of a and b.
- * a and b are swapped if condition is not 0. The code assumes that at most one bit of condition is set.
- * nwords is the number of words to swap. The code assumes that at least nwords are allocated in both a and b,
- * and that no more than nwords are used by either a or b.
- * a and b cannot be the same number
+ * a and b are swapped if condition is not 0.
+ * nwords is the number of words to swap.
+ * Assumes that at least nwords are allocated in both a and b.
+ * Assumes that no more than nwords are used by either a or b.
*/
void BN_consttime_swap(BN_ULONG condition, BIGNUM *a, BIGNUM *b, int nwords)
{
BN_ULONG t;
int i;
+ if (a == b)
+ return;
+
bn_wcheck_size(a, nwords);
bn_wcheck_size(b, nwords);
- assert(a != b);
- assert((condition & (condition - 1)) == 0);
- assert(sizeof(BN_ULONG) >= sizeof(int));
-
- condition = ((condition - 1) >> (BN_BITS2 - 1)) - 1;
+ condition = ((~condition & ((condition - 1))) >> (BN_BITS2 - 1)) - 1;
t = (a->top ^ b->top) & condition;
a->top ^= t;
a->neg ^= t;
b->neg ^= t;
- /*
- * cannot just arbitrarily swap flags.
- * The way a->d is allocated etc.
- * BN_FLG_MALLOCED, BN_FLG_STATIC_DATA, ...
+ /*-
+ * BN_FLG_STATIC_DATA: indicates that data may not be written to. Intention
+ * is actually to treat it as it's read-only data, and some (if not most)
+ * of it does reside in read-only segment. In other words observation of
+ * BN_FLG_STATIC_DATA in BN_consttime_swap should be treated as fatal
+ * condition. It would either cause SEGV or effectively cause data
+ * corruption.
+ *
+ * BN_FLG_MALLOCED: refers to BN structure itself, and hence must be
+ * preserved.
+ *
+ * BN_FLG_SECURE: must be preserved, because it determines how x->d was
+ * allocated and hence how to free it.
+ *
+ * BN_FLG_CONSTTIME: sufficient to mask and swap
+ *
+ * BN_FLG_FIXED_TOP: indicates that we haven't called bn_correct_top() on
+ * the data, so the d array may be padded with additional 0 values (i.e.
+ * top could be greater than the minimal value that it could be). We should
+ * be swapping it
*/
- t = (a->flags ^ b->flags) & condition & BN_FLG_CONSTTIME;
+
+#define BN_CONSTTIME_SWAP_FLAGS (BN_FLG_CONSTTIME | BN_FLG_FIXED_TOP)
+
+ t = ((a->flags ^ b->flags) & BN_CONSTTIME_SWAP_FLAGS) & condition;
a->flags ^= t;
b->flags ^= t;
-#define BN_CONSTTIME_SWAP(ind) \
- do { \
- t = (a->d[ind] ^ b->d[ind]) & condition; \
- a->d[ind] ^= t; \
- b->d[ind] ^= t; \
- } while (0)
-
- switch (nwords) {
- default:
- for (i = 10; i < nwords; i++)
- BN_CONSTTIME_SWAP(i);
- /* Fallthrough */
- case 10:
- BN_CONSTTIME_SWAP(9); /* Fallthrough */
- case 9:
- BN_CONSTTIME_SWAP(8); /* Fallthrough */
- case 8:
- BN_CONSTTIME_SWAP(7); /* Fallthrough */
- case 7:
- BN_CONSTTIME_SWAP(6); /* Fallthrough */
- case 6:
- BN_CONSTTIME_SWAP(5); /* Fallthrough */
- case 5:
- BN_CONSTTIME_SWAP(4); /* Fallthrough */
- case 4:
- BN_CONSTTIME_SWAP(3); /* Fallthrough */
- case 3:
- BN_CONSTTIME_SWAP(2); /* Fallthrough */
- case 2:
- BN_CONSTTIME_SWAP(1); /* Fallthrough */
- case 1:
- BN_CONSTTIME_SWAP(0);
- }
-#undef BN_CONSTTIME_SWAP
+ /* conditionally swap the data */
+ for (i = 0; i < nwords; i++) {
+ t = (a->d[i] ^ b->d[i]) & condition;
+ a->d[i] ^= t;
+ b->d[i] ^= t;
+ }
}
+#undef BN_CONSTTIME_SWAP_FLAGS
+
/* Bits of security, see SP800-57 */
int BN_security_bits(int L, int N)
void BN_zero_ex(BIGNUM *a)
{
- a->top = 0;
a->neg = 0;
+ a->top = 0;
+ a->flags &= ~BN_FLG_FIXED_TOP;
}
int BN_abs_is_word(const BIGNUM *a, const BN_ULONG w)
}
if (a->top == 0)
a->neg = 0;
+ a->flags &= ~BN_FLG_FIXED_TOP;
bn_pollute(a);
}
projects / openssl.git / blobdiff