/*
* 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_locl.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 = 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;
}
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->neg = b->neg;
a->top = b->top;
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);
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 n;
size_t i, lasti, j, atop, mask;
lasti = atop - 1;
atop = a->top * BN_BYTES;
- for (i = 0, j = 0, to += tolen; j < (size_t)tolen; j++) {
+ 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];
mask = 0 - ((j - atop) >> (8 * sizeof(i) - 1));
- *--to = (unsigned char)(l >> (8 * (i % BN_BYTES)) & mask);
+ 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 */
}
{
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)
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;
b->neg ^= t;
/*-
- * Idea behind BN_FLG_STATIC_DATA is actually to
- * indicate 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. Remaining flags are
- * BN_FLG_CONSTIME and BN_FLG_SECURE. Latter must be
- * preserved, because it determines how x->d was
- * allocated and hence how to free it. This leaves
- * BN_FLG_CONSTTIME that one can do something about.
- * To summarize it's sufficient to mask and swap
- * BN_FLG_CONSTTIME alone. BN_FLG_STATIC_DATA should
- * be treated as fatal.
+ * 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) & BN_FLG_CONSTTIME) & condition;
+
+#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)