1 /* Copyright (C) 1995-1998 Eric Young (eay (at) cryptsoft.com) 2 * All rights reserved. 3 * 4 * This package is an SSL implementation written 5 * by Eric Young (eay (at) cryptsoft.com). 6 * The implementation was written so as to conform with Netscapes SSL. 7 * 8 * This library is free for commercial and non-commercial use as long as 9 * the following conditions are aheared to. The following conditions 10 * apply to all code found in this distribution, be it the RC4, RSA, 11 * lhash, DES, etc., code; not just the SSL code. The SSL documentation 12 * included with this distribution is covered by the same copyright terms 13 * except that the holder is Tim Hudson (tjh (at) cryptsoft.com). 14 * 15 * Copyright remains Eric Young's, and as such any Copyright notices in 16 * the code are not to be removed. 17 * If this package is used in a product, Eric Young should be given attribution 18 * as the author of the parts of the library used. 19 * This can be in the form of a textual message at program startup or 20 * in documentation (online or textual) provided with the package. 21 * 22 * Redistribution and use in source and binary forms, with or without 23 * modification, are permitted provided that the following conditions 24 * are met: 25 * 1. Redistributions of source code must retain the copyright 26 * notice, this list of conditions and the following disclaimer. 27 * 2. Redistributions in binary form must reproduce the above copyright 28 * notice, this list of conditions and the following disclaimer in the 29 * documentation and/or other materials provided with the distribution. 30 * 3. All advertising materials mentioning features or use of this software 31 * must display the following acknowledgement: 32 * "This product includes cryptographic software written by 33 * Eric Young (eay (at) cryptsoft.com)" 34 * The word 'cryptographic' can be left out if the rouines from the library 35 * being used are not cryptographic related :-). 36 * 4. If you include any Windows specific code (or a derivative thereof) from 37 * the apps directory (application code) you must include an acknowledgement: 38 * "This product includes software written by Tim Hudson (tjh (at) cryptsoft.com)" 39 * 40 * THIS SOFTWARE IS PROVIDED BY ERIC YOUNG ``AS IS'' AND 41 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 42 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 43 * ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE 44 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 45 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 46 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 47 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 48 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 49 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 50 * SUCH DAMAGE. 51 * 52 * The licence and distribution terms for any publically available version or 53 * derivative of this code cannot be changed. i.e. this code cannot simply be 54 * copied and put under another distribution licence 55 * [including the GNU Public Licence.] */ 56 57 #include <openssl/bn.h> 58 59 #include <assert.h> 60 #include <limits.h> 61 62 #include "internal.h" 63 64 65 BIGNUM *BN_bin2bn(const uint8_t *in, size_t len, BIGNUM *ret) { 66 size_t num_words; 67 unsigned m; 68 BN_ULONG word = 0; 69 BIGNUM *bn = NULL; 70 71 if (ret == NULL) { 72 ret = bn = BN_new(); 73 } 74 75 if (ret == NULL) { 76 return NULL; 77 } 78 79 if (len == 0) { 80 ret->top = 0; 81 return ret; 82 } 83 84 num_words = ((len - 1) / BN_BYTES) + 1; 85 m = (len - 1) % BN_BYTES; 86 if (!bn_wexpand(ret, num_words)) { 87 if (bn) { 88 BN_free(bn); 89 } 90 return NULL; 91 } 92 93 /* |bn_wexpand| must check bounds on |num_words| to write it into 94 * |ret->dmax|. */ 95 assert(num_words <= INT_MAX); 96 ret->top = (int)num_words; 97 ret->neg = 0; 98 99 while (len--) { 100 word = (word << 8) | *(in++); 101 if (m-- == 0) { 102 ret->d[--num_words] = word; 103 word = 0; 104 m = BN_BYTES - 1; 105 } 106 } 107 108 /* need to call this due to clear byte at top if avoiding having the top bit 109 * set (-ve number) */ 110 bn_correct_top(ret); 111 return ret; 112 } 113 114 BIGNUM *BN_le2bn(const uint8_t *in, size_t len, BIGNUM *ret) { 115 BIGNUM *bn = NULL; 116 if (ret == NULL) { 117 bn = BN_new(); 118 ret = bn; 119 } 120 121 if (ret == NULL) { 122 return NULL; 123 } 124 125 if (len == 0) { 126 ret->top = 0; 127 ret->neg = 0; 128 return ret; 129 } 130 131 /* Reserve enough space in |ret|. */ 132 size_t num_words = ((len - 1) / BN_BYTES) + 1; 133 if (!bn_wexpand(ret, num_words)) { 134 BN_free(bn); 135 return NULL; 136 } 137 ret->top = num_words; 138 139 /* Make sure the top bytes will be zeroed. */ 140 ret->d[num_words - 1] = 0; 141 142 /* We only support little-endian platforms, so we can simply memcpy the 143 * internal representation. */ 144 OPENSSL_memcpy(ret->d, in, len); 145 146 bn_correct_top(ret); 147 return ret; 148 } 149 150 size_t BN_bn2bin(const BIGNUM *in, uint8_t *out) { 151 size_t n, i; 152 BN_ULONG l; 153 154 n = i = BN_num_bytes(in); 155 while (i--) { 156 l = in->d[i / BN_BYTES]; 157 *(out++) = (unsigned char)(l >> (8 * (i % BN_BYTES))) & 0xff; 158 } 159 return n; 160 } 161 162 int BN_bn2le_padded(uint8_t *out, size_t len, const BIGNUM *in) { 163 /* If we don't have enough space, fail out. */ 164 size_t num_bytes = BN_num_bytes(in); 165 if (len < num_bytes) { 166 return 0; 167 } 168 169 /* We only support little-endian platforms, so we can simply memcpy into the 170 * internal representation. */ 171 OPENSSL_memcpy(out, in->d, num_bytes); 172 173 /* Pad out the rest of the buffer with zeroes. */ 174 OPENSSL_memset(out + num_bytes, 0, len - num_bytes); 175 176 return 1; 177 } 178 179 /* constant_time_select_ulong returns |x| if |v| is 1 and |y| if |v| is 0. Its 180 * behavior is undefined if |v| takes any other value. */ 181 static BN_ULONG constant_time_select_ulong(int v, BN_ULONG x, BN_ULONG y) { 182 BN_ULONG mask = v; 183 mask--; 184 185 return (~mask & x) | (mask & y); 186 } 187 188 /* constant_time_le_size_t returns 1 if |x| <= |y| and 0 otherwise. |x| and |y| 189 * must not have their MSBs set. */ 190 static int constant_time_le_size_t(size_t x, size_t y) { 191 return ((x - y - 1) >> (sizeof(size_t) * 8 - 1)) & 1; 192 } 193 194 /* read_word_padded returns the |i|'th word of |in|, if it is not out of 195 * bounds. Otherwise, it returns 0. It does so without branches on the size of 196 * |in|, however it necessarily does not have the same memory access pattern. If 197 * the access would be out of bounds, it reads the last word of |in|. |in| must 198 * not be zero. */ 199 static BN_ULONG read_word_padded(const BIGNUM *in, size_t i) { 200 /* Read |in->d[i]| if valid. Otherwise, read the last word. */ 201 BN_ULONG l = in->d[constant_time_select_ulong( 202 constant_time_le_size_t(in->dmax, i), in->dmax - 1, i)]; 203 204 /* Clamp to zero if above |d->top|. */ 205 return constant_time_select_ulong(constant_time_le_size_t(in->top, i), 0, l); 206 } 207 208 int BN_bn2bin_padded(uint8_t *out, size_t len, const BIGNUM *in) { 209 /* Special case for |in| = 0. Just branch as the probability is negligible. */ 210 if (BN_is_zero(in)) { 211 OPENSSL_memset(out, 0, len); 212 return 1; 213 } 214 215 /* Check if the integer is too big. This case can exit early in non-constant 216 * time. */ 217 if ((size_t)in->top > (len + (BN_BYTES - 1)) / BN_BYTES) { 218 return 0; 219 } 220 if ((len % BN_BYTES) != 0) { 221 BN_ULONG l = read_word_padded(in, len / BN_BYTES); 222 if (l >> (8 * (len % BN_BYTES)) != 0) { 223 return 0; 224 } 225 } 226 227 /* Write the bytes out one by one. Serialization is done without branching on 228 * the bits of |in| or on |in->top|, but if the routine would otherwise read 229 * out of bounds, the memory access pattern can't be fixed. However, for an 230 * RSA key of size a multiple of the word size, the probability of BN_BYTES 231 * leading zero octets is low. 232 * 233 * See Falko Stenzke, "Manger's Attack revisited", ICICS 2010. */ 234 size_t i = len; 235 while (i--) { 236 BN_ULONG l = read_word_padded(in, i / BN_BYTES); 237 *(out++) = (uint8_t)(l >> (8 * (i % BN_BYTES))) & 0xff; 238 } 239 return 1; 240 } 241 242 BN_ULONG BN_get_word(const BIGNUM *bn) { 243 switch (bn->top) { 244 case 0: 245 return 0; 246 case 1: 247 return bn->d[0]; 248 default: 249 return BN_MASK2; 250 } 251 } 252 253 int BN_get_u64(const BIGNUM *bn, uint64_t *out) { 254 switch (bn->top) { 255 case 0: 256 *out = 0; 257 return 1; 258 case 1: 259 *out = bn->d[0]; 260 return 1; 261 #if defined(OPENSSL_32_BIT) 262 case 2: 263 *out = (uint64_t) bn->d[0] | (((uint64_t) bn->d[1]) << 32); 264 return 1; 265 #endif 266 default: 267 return 0; 268 } 269 } 270
