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 // TODO(davidben): This does not need to be quite so complex once the |BIGNUM|s 163 // we care about are fixed-width. |read_word_padded| is a hack to paper over 164 // parts of the |bn_correct_top| leak. Fix that, and this can be simpler. 165 166 // constant_time_select_ulong returns |x| if |v| is 1 and |y| if |v| is 0. Its 167 // behavior is undefined if |v| takes any other value. 168 static BN_ULONG constant_time_select_ulong(int v, BN_ULONG x, BN_ULONG y) { 169 BN_ULONG mask = v; 170 mask--; 171 172 return (~mask & x) | (mask & y); 173 } 174 175 // constant_time_le_size_t returns 1 if |x| <= |y| and 0 otherwise. |x| and |y| 176 // must not have their MSBs set. 177 static int constant_time_le_size_t(size_t x, size_t y) { 178 return ((x - y - 1) >> (sizeof(size_t) * 8 - 1)) & 1; 179 } 180 181 // read_word_padded returns the |i|'th word of |in|, if it is not out of 182 // bounds. Otherwise, it returns 0. It does so without branches on the size of 183 // |in|, however it necessarily does not have the same memory access pattern. If 184 // the access would be out of bounds, it reads the last word of |in|. |in| must 185 // not be zero. 186 static BN_ULONG read_word_padded(const BIGNUM *in, size_t i) { 187 if (in->dmax == 0) { 188 return 0; 189 } 190 191 // Read |in->d[i]| if valid. Otherwise, read the last word. 192 BN_ULONG l = in->d[constant_time_select_ulong( 193 constant_time_le_size_t(in->dmax, i), in->dmax - 1, i)]; 194 195 // Clamp to zero if above |d->top|. 196 return constant_time_select_ulong(constant_time_le_size_t(in->top, i), 0, l); 197 } 198 199 static int fits_in_bytes(const BIGNUM *in, size_t len) { 200 BN_ULONG mask = 0; 201 for (size_t i = (len + (BN_BYTES - 1)) / BN_BYTES; i < (size_t)in->top; i++) { 202 mask |= in->d[i]; 203 } 204 if ((len % BN_BYTES) != 0) { 205 BN_ULONG l = read_word_padded(in, len / BN_BYTES); 206 mask |= l >> (8 * (len % BN_BYTES)); 207 } 208 return mask == 0; 209 } 210 211 int BN_bn2le_padded(uint8_t *out, size_t len, const BIGNUM *in) { 212 // If we don't have enough space, fail out. 213 if (!fits_in_bytes(in, len)) { 214 return 0; 215 } 216 217 size_t todo = in->top * BN_BYTES; 218 if (todo > len) { 219 todo = len; 220 } 221 222 // We only support little-endian platforms, so we can simply memcpy into the 223 // internal representation. 224 OPENSSL_memcpy(out, in->d, todo); 225 226 // Pad out the rest of the buffer with zeroes. 227 OPENSSL_memset(out + todo, 0, len - todo); 228 229 return 1; 230 } 231 232 int BN_bn2bin_padded(uint8_t *out, size_t len, const BIGNUM *in) { 233 // Check if the integer is too big. This case can exit early in non-constant 234 // time. 235 if (!fits_in_bytes(in, len)) { 236 return 0; 237 } 238 239 // Write the bytes out one by one. Serialization is done without branching on 240 // the bits of |in| or on |in->top|, but if the routine would otherwise read 241 // out of bounds, the memory access pattern can't be fixed. However, for an 242 // RSA key of size a multiple of the word size, the probability of BN_BYTES 243 // leading zero octets is low. 244 // 245 // See Falko Stenzke, "Manger's Attack revisited", ICICS 2010. 246 size_t i = len; 247 while (i--) { 248 BN_ULONG l = read_word_padded(in, i / BN_BYTES); 249 *(out++) = (uint8_t)(l >> (8 * (i % BN_BYTES))) & 0xff; 250 } 251 return 1; 252 } 253 254 BN_ULONG BN_get_word(const BIGNUM *bn) { 255 switch (bn_minimal_width(bn)) { 256 case 0: 257 return 0; 258 case 1: 259 return bn->d[0]; 260 default: 261 return BN_MASK2; 262 } 263 } 264 265 int BN_get_u64(const BIGNUM *bn, uint64_t *out) { 266 switch (bn_minimal_width(bn)) { 267 case 0: 268 *out = 0; 269 return 1; 270 case 1: 271 *out = bn->d[0]; 272 return 1; 273 #if defined(OPENSSL_32_BIT) 274 case 2: 275 *out = (uint64_t) bn->d[0] | (((uint64_t) bn->d[1]) << 32); 276 return 1; 277 #endif 278 default: 279 return 0; 280 } 281 } 282
