File: | src/lib/libcrypto/ec/ec_mult.c |
Warning: | line 639, column 17 Array access results in a null pointer dereference |
Press '?' to see keyboard shortcuts
Keyboard shortcuts:
1 | /* $OpenBSD: ec_mult.c,v 1.24 2018/07/15 16:27:39 tb Exp $ */ | |||
2 | /* | |||
3 | * Originally written by Bodo Moeller and Nils Larsch for the OpenSSL project. | |||
4 | */ | |||
5 | /* ==================================================================== | |||
6 | * Copyright (c) 1998-2007 The OpenSSL Project. All rights reserved. | |||
7 | * | |||
8 | * Redistribution and use in source and binary forms, with or without | |||
9 | * modification, are permitted provided that the following conditions | |||
10 | * are met: | |||
11 | * | |||
12 | * 1. Redistributions of source code must retain the above copyright | |||
13 | * notice, this list of conditions and the following disclaimer. | |||
14 | * | |||
15 | * 2. Redistributions in binary form must reproduce the above copyright | |||
16 | * notice, this list of conditions and the following disclaimer in | |||
17 | * the documentation and/or other materials provided with the | |||
18 | * distribution. | |||
19 | * | |||
20 | * 3. All advertising materials mentioning features or use of this | |||
21 | * software must display the following acknowledgment: | |||
22 | * "This product includes software developed by the OpenSSL Project | |||
23 | * for use in the OpenSSL Toolkit. (http://www.openssl.org/)" | |||
24 | * | |||
25 | * 4. The names "OpenSSL Toolkit" and "OpenSSL Project" must not be used to | |||
26 | * endorse or promote products derived from this software without | |||
27 | * prior written permission. For written permission, please contact | |||
28 | * openssl-core@openssl.org. | |||
29 | * | |||
30 | * 5. Products derived from this software may not be called "OpenSSL" | |||
31 | * nor may "OpenSSL" appear in their names without prior written | |||
32 | * permission of the OpenSSL Project. | |||
33 | * | |||
34 | * 6. Redistributions of any form whatsoever must retain the following | |||
35 | * acknowledgment: | |||
36 | * "This product includes software developed by the OpenSSL Project | |||
37 | * for use in the OpenSSL Toolkit (http://www.openssl.org/)" | |||
38 | * | |||
39 | * THIS SOFTWARE IS PROVIDED BY THE OpenSSL PROJECT ``AS IS'' AND ANY | |||
40 | * EXPRESSED OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE | |||
41 | * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR | |||
42 | * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE OpenSSL PROJECT OR | |||
43 | * ITS CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, | |||
44 | * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT | |||
45 | * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; | |||
46 | * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) | |||
47 | * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, | |||
48 | * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) | |||
49 | * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED | |||
50 | * OF THE POSSIBILITY OF SUCH DAMAGE. | |||
51 | * ==================================================================== | |||
52 | * | |||
53 | * This product includes cryptographic software written by Eric Young | |||
54 | * (eay@cryptsoft.com). This product includes software written by Tim | |||
55 | * Hudson (tjh@cryptsoft.com). | |||
56 | * | |||
57 | */ | |||
58 | /* ==================================================================== | |||
59 | * Copyright 2002 Sun Microsystems, Inc. ALL RIGHTS RESERVED. | |||
60 | * Portions of this software developed by SUN MICROSYSTEMS, INC., | |||
61 | * and contributed to the OpenSSL project. | |||
62 | */ | |||
63 | ||||
64 | #include <string.h> | |||
65 | ||||
66 | #include <openssl/err.h> | |||
67 | ||||
68 | #include "ec_lcl.h" | |||
69 | ||||
70 | ||||
71 | /* | |||
72 | * This file implements the wNAF-based interleaving multi-exponentation method | |||
73 | * (<URL:http://www.informatik.tu-darmstadt.de/TI/Mitarbeiter/moeller.html#multiexp>); | |||
74 | * for multiplication with precomputation, we use wNAF splitting | |||
75 | * (<URL:http://www.informatik.tu-darmstadt.de/TI/Mitarbeiter/moeller.html#fastexp>). | |||
76 | */ | |||
77 | ||||
78 | ||||
79 | ||||
80 | ||||
81 | /* structure for precomputed multiples of the generator */ | |||
82 | typedef struct ec_pre_comp_st { | |||
83 | const EC_GROUP *group; /* parent EC_GROUP object */ | |||
84 | size_t blocksize; /* block size for wNAF splitting */ | |||
85 | size_t numblocks; /* max. number of blocks for which we have | |||
86 | * precomputation */ | |||
87 | size_t w; /* window size */ | |||
88 | EC_POINT **points; /* array with pre-calculated multiples of | |||
89 | * generator: 'num' pointers to EC_POINT | |||
90 | * objects followed by a NULL */ | |||
91 | size_t num; /* numblocks * 2^(w-1) */ | |||
92 | int references; | |||
93 | } EC_PRE_COMP; | |||
94 | ||||
95 | /* functions to manage EC_PRE_COMP within the EC_GROUP extra_data framework */ | |||
96 | static void *ec_pre_comp_dup(void *); | |||
97 | static void ec_pre_comp_free(void *); | |||
98 | static void ec_pre_comp_clear_free(void *); | |||
99 | ||||
100 | static EC_PRE_COMP * | |||
101 | ec_pre_comp_new(const EC_GROUP * group) | |||
102 | { | |||
103 | EC_PRE_COMP *ret = NULL((void *)0); | |||
104 | ||||
105 | if (!group) | |||
106 | return NULL((void *)0); | |||
107 | ||||
108 | ret = malloc(sizeof(EC_PRE_COMP)); | |||
109 | if (!ret) { | |||
110 | ECerror(ERR_R_MALLOC_FAILURE)ERR_put_error(16,(0xfff),((1|64)),"/usr/src/lib/libcrypto/ec/ec_mult.c" ,110); | |||
111 | return ret; | |||
112 | } | |||
113 | ret->group = group; | |||
114 | ret->blocksize = 8; /* default */ | |||
115 | ret->numblocks = 0; | |||
116 | ret->w = 4; /* default */ | |||
117 | ret->points = NULL((void *)0); | |||
118 | ret->num = 0; | |||
119 | ret->references = 1; | |||
120 | return ret; | |||
121 | } | |||
122 | ||||
123 | static void * | |||
124 | ec_pre_comp_dup(void *src_) | |||
125 | { | |||
126 | EC_PRE_COMP *src = src_; | |||
127 | ||||
128 | /* no need to actually copy, these objects never change! */ | |||
129 | ||||
130 | CRYPTO_add(&src->references, 1, CRYPTO_LOCK_EC_PRE_COMP)CRYPTO_add_lock(&src->references,1,36,((void *)0),0); | |||
131 | ||||
132 | return src_; | |||
133 | } | |||
134 | ||||
135 | static void | |||
136 | ec_pre_comp_free(void *pre_) | |||
137 | { | |||
138 | int i; | |||
139 | EC_PRE_COMP *pre = pre_; | |||
140 | ||||
141 | if (!pre) | |||
142 | return; | |||
143 | ||||
144 | i = CRYPTO_add(&pre->references, -1, CRYPTO_LOCK_EC_PRE_COMP)CRYPTO_add_lock(&pre->references,-1,36,((void *)0),0); | |||
145 | if (i > 0) | |||
146 | return; | |||
147 | ||||
148 | if (pre->points) { | |||
149 | EC_POINT **p; | |||
150 | ||||
151 | for (p = pre->points; *p != NULL((void *)0); p++) | |||
152 | EC_POINT_free(*p); | |||
153 | free(pre->points); | |||
154 | } | |||
155 | free(pre); | |||
156 | } | |||
157 | ||||
158 | static void | |||
159 | ec_pre_comp_clear_free(void *pre_) | |||
160 | { | |||
161 | int i; | |||
162 | EC_PRE_COMP *pre = pre_; | |||
163 | ||||
164 | if (!pre) | |||
165 | return; | |||
166 | ||||
167 | i = CRYPTO_add(&pre->references, -1, CRYPTO_LOCK_EC_PRE_COMP)CRYPTO_add_lock(&pre->references,-1,36,((void *)0),0); | |||
168 | if (i > 0) | |||
169 | return; | |||
170 | ||||
171 | if (pre->points) { | |||
172 | EC_POINT **p; | |||
173 | ||||
174 | for (p = pre->points; *p != NULL((void *)0); p++) { | |||
175 | EC_POINT_clear_free(*p); | |||
176 | explicit_bzero(p, sizeof *p); | |||
177 | } | |||
178 | free(pre->points); | |||
179 | } | |||
180 | freezero(pre, sizeof *pre); | |||
181 | } | |||
182 | ||||
183 | ||||
184 | ||||
185 | ||||
186 | /* Determine the modified width-(w+1) Non-Adjacent Form (wNAF) of 'scalar'. | |||
187 | * This is an array r[] of values that are either zero or odd with an | |||
188 | * absolute value less than 2^w satisfying | |||
189 | * scalar = \sum_j r[j]*2^j | |||
190 | * where at most one of any w+1 consecutive digits is non-zero | |||
191 | * with the exception that the most significant digit may be only | |||
192 | * w-1 zeros away from that next non-zero digit. | |||
193 | */ | |||
194 | static signed char * | |||
195 | compute_wNAF(const BIGNUM * scalar, int w, size_t * ret_len) | |||
196 | { | |||
197 | int window_val; | |||
198 | int ok = 0; | |||
199 | signed char *r = NULL((void *)0); | |||
200 | int sign = 1; | |||
201 | int bit, next_bit, mask; | |||
202 | size_t len = 0, j; | |||
203 | ||||
204 | if (BN_is_zero(scalar)) { | |||
205 | r = malloc(1); | |||
206 | if (!r) { | |||
207 | ECerror(ERR_R_MALLOC_FAILURE)ERR_put_error(16,(0xfff),((1|64)),"/usr/src/lib/libcrypto/ec/ec_mult.c" ,207); | |||
208 | goto err; | |||
209 | } | |||
210 | r[0] = 0; | |||
211 | *ret_len = 1; | |||
212 | return r; | |||
213 | } | |||
214 | if (w <= 0 || w > 7) { | |||
215 | /* 'signed char' can represent integers with | |||
216 | * absolute values less than 2^7 */ | |||
217 | ECerror(ERR_R_INTERNAL_ERROR)ERR_put_error(16,(0xfff),((4|64)),"/usr/src/lib/libcrypto/ec/ec_mult.c" ,217); | |||
218 | goto err; | |||
219 | } | |||
220 | bit = 1 << w; /* at most 128 */ | |||
221 | next_bit = bit << 1; /* at most 256 */ | |||
222 | mask = next_bit - 1; /* at most 255 */ | |||
223 | ||||
224 | if (BN_is_negative(scalar)) { | |||
225 | sign = -1; | |||
226 | } | |||
227 | if (scalar->d == NULL((void *)0) || scalar->top == 0) { | |||
228 | ECerror(ERR_R_INTERNAL_ERROR)ERR_put_error(16,(0xfff),((4|64)),"/usr/src/lib/libcrypto/ec/ec_mult.c" ,228); | |||
229 | goto err; | |||
230 | } | |||
231 | len = BN_num_bits(scalar); | |||
232 | r = malloc(len + 1); /* modified wNAF may be one digit longer than | |||
233 | * binary representation (*ret_len will be | |||
234 | * set to the actual length, i.e. at most | |||
235 | * BN_num_bits(scalar) + 1) */ | |||
236 | if (r == NULL((void *)0)) { | |||
237 | ECerror(ERR_R_MALLOC_FAILURE)ERR_put_error(16,(0xfff),((1|64)),"/usr/src/lib/libcrypto/ec/ec_mult.c" ,237); | |||
238 | goto err; | |||
239 | } | |||
240 | window_val = scalar->d[0] & mask; | |||
241 | j = 0; | |||
242 | while ((window_val != 0) || (j + w + 1 < len)) { | |||
243 | /* if j+w+1 >= len, window_val will not increase */ | |||
244 | int digit = 0; | |||
245 | ||||
246 | /* 0 <= window_val <= 2^(w+1) */ | |||
247 | if (window_val & 1) { | |||
248 | /* 0 < window_val < 2^(w+1) */ | |||
249 | if (window_val & bit) { | |||
250 | digit = window_val - next_bit; /* -2^w < digit < 0 */ | |||
251 | ||||
252 | #if 1 /* modified wNAF */ | |||
253 | if (j + w + 1 >= len) { | |||
254 | /* | |||
255 | * special case for generating | |||
256 | * modified wNAFs: no new bits will | |||
257 | * be added into window_val, so using | |||
258 | * a positive digit here will | |||
259 | * decrease the total length of the | |||
260 | * representation | |||
261 | */ | |||
262 | ||||
263 | digit = window_val & (mask >> 1); /* 0 < digit < 2^w */ | |||
264 | } | |||
265 | #endif | |||
266 | } else { | |||
267 | digit = window_val; /* 0 < digit < 2^w */ | |||
268 | } | |||
269 | ||||
270 | if (digit <= -bit || digit >= bit || !(digit & 1)) { | |||
271 | ECerror(ERR_R_INTERNAL_ERROR)ERR_put_error(16,(0xfff),((4|64)),"/usr/src/lib/libcrypto/ec/ec_mult.c" ,271); | |||
272 | goto err; | |||
273 | } | |||
274 | window_val -= digit; | |||
275 | ||||
276 | /* | |||
277 | * now window_val is 0 or 2^(w+1) in standard wNAF | |||
278 | * generation; for modified window NAFs, it may also | |||
279 | * be 2^w | |||
280 | */ | |||
281 | if (window_val != 0 && window_val != next_bit && window_val != bit) { | |||
282 | ECerror(ERR_R_INTERNAL_ERROR)ERR_put_error(16,(0xfff),((4|64)),"/usr/src/lib/libcrypto/ec/ec_mult.c" ,282); | |||
283 | goto err; | |||
284 | } | |||
285 | } | |||
286 | r[j++] = sign * digit; | |||
287 | ||||
288 | window_val >>= 1; | |||
289 | window_val += bit * BN_is_bit_set(scalar, j + w); | |||
290 | ||||
291 | if (window_val > next_bit) { | |||
292 | ECerror(ERR_R_INTERNAL_ERROR)ERR_put_error(16,(0xfff),((4|64)),"/usr/src/lib/libcrypto/ec/ec_mult.c" ,292); | |||
293 | goto err; | |||
294 | } | |||
295 | } | |||
296 | ||||
297 | if (j > len + 1) { | |||
298 | ECerror(ERR_R_INTERNAL_ERROR)ERR_put_error(16,(0xfff),((4|64)),"/usr/src/lib/libcrypto/ec/ec_mult.c" ,298); | |||
299 | goto err; | |||
300 | } | |||
301 | len = j; | |||
302 | ok = 1; | |||
303 | ||||
304 | err: | |||
305 | if (!ok) { | |||
306 | free(r); | |||
307 | r = NULL((void *)0); | |||
308 | } | |||
309 | if (ok) | |||
310 | *ret_len = len; | |||
311 | return r; | |||
312 | } | |||
313 | ||||
314 | ||||
315 | /* TODO: table should be optimised for the wNAF-based implementation, | |||
316 | * sometimes smaller windows will give better performance | |||
317 | * (thus the boundaries should be increased) | |||
318 | */ | |||
319 | #define EC_window_bits_for_scalar_size(b)((size_t) ((b) >= 2000 ? 6 : (b) >= 800 ? 5 : (b) >= 300 ? 4 : (b) >= 70 ? 3 : (b) >= 20 ? 2 : 1)) \ | |||
320 | ((size_t) \ | |||
321 | ((b) >= 2000 ? 6 : \ | |||
322 | (b) >= 800 ? 5 : \ | |||
323 | (b) >= 300 ? 4 : \ | |||
324 | (b) >= 70 ? 3 : \ | |||
325 | (b) >= 20 ? 2 : \ | |||
326 | 1)) | |||
327 | ||||
328 | /* Compute | |||
329 | * \sum scalars[i]*points[i], | |||
330 | * also including | |||
331 | * scalar*generator | |||
332 | * in the addition if scalar != NULL | |||
333 | */ | |||
334 | int | |||
335 | ec_wNAF_mul(const EC_GROUP * group, EC_POINT * r, const BIGNUM * scalar, | |||
336 | size_t num, const EC_POINT * points[], const BIGNUM * scalars[], BN_CTX * ctx) | |||
337 | { | |||
338 | BN_CTX *new_ctx = NULL((void *)0); | |||
339 | const EC_POINT *generator = NULL((void *)0); | |||
340 | EC_POINT *tmp = NULL((void *)0); | |||
341 | size_t totalnum; | |||
342 | size_t blocksize = 0, numblocks = 0; /* for wNAF splitting */ | |||
343 | size_t pre_points_per_block = 0; | |||
344 | size_t i, j; | |||
345 | int k; | |||
346 | int r_is_inverted = 0; | |||
347 | int r_is_at_infinity = 1; | |||
348 | size_t *wsize = NULL((void *)0); /* individual window sizes */ | |||
349 | signed char **wNAF = NULL((void *)0); /* individual wNAFs */ | |||
350 | signed char *tmp_wNAF = NULL((void *)0); | |||
351 | size_t *wNAF_len = NULL((void *)0); | |||
352 | size_t max_len = 0; | |||
353 | size_t num_val; | |||
354 | EC_POINT **val = NULL((void *)0); /* precomputation */ | |||
355 | EC_POINT **v; | |||
356 | EC_POINT ***val_sub = NULL((void *)0); /* pointers to sub-arrays of 'val' or | |||
357 | * 'pre_comp->points' */ | |||
358 | const EC_PRE_COMP *pre_comp = NULL((void *)0); | |||
359 | int num_scalar = 0; /* flag: will be set to 1 if 'scalar' must be | |||
360 | * treated like other scalars, i.e. | |||
361 | * precomputation is not available */ | |||
362 | int ret = 0; | |||
363 | ||||
364 | if (group->meth != r->meth) { | |||
| ||||
365 | ECerror(EC_R_INCOMPATIBLE_OBJECTS)ERR_put_error(16,(0xfff),(101),"/usr/src/lib/libcrypto/ec/ec_mult.c" ,365); | |||
366 | return 0; | |||
367 | } | |||
368 | if ((scalar == NULL((void *)0)) && (num == 0)) { | |||
369 | return EC_POINT_set_to_infinity(group, r); | |||
370 | } | |||
371 | for (i = 0; i < num; i++) { | |||
372 | if (group->meth != points[i]->meth) { | |||
373 | ECerror(EC_R_INCOMPATIBLE_OBJECTS)ERR_put_error(16,(0xfff),(101),"/usr/src/lib/libcrypto/ec/ec_mult.c" ,373); | |||
374 | return 0; | |||
375 | } | |||
376 | } | |||
377 | ||||
378 | if (ctx == NULL((void *)0)) { | |||
379 | ctx = new_ctx = BN_CTX_new(); | |||
380 | if (ctx == NULL((void *)0)) | |||
381 | goto err; | |||
382 | } | |||
383 | if (scalar
| |||
384 | generator = EC_GROUP_get0_generator(group); | |||
385 | if (generator == NULL((void *)0)) { | |||
386 | ECerror(EC_R_UNDEFINED_GENERATOR)ERR_put_error(16,(0xfff),(113),"/usr/src/lib/libcrypto/ec/ec_mult.c" ,386); | |||
387 | goto err; | |||
388 | } | |||
389 | /* look if we can use precomputed multiples of generator */ | |||
390 | ||||
391 | pre_comp = EC_EX_DATA_get_data(group->extra_data, ec_pre_comp_dup, ec_pre_comp_free, ec_pre_comp_clear_free); | |||
392 | ||||
393 | if (pre_comp && pre_comp->numblocks && | |||
394 | (EC_POINT_cmp(group, generator, pre_comp->points[0], ctx) == 0)) { | |||
395 | blocksize = pre_comp->blocksize; | |||
396 | ||||
397 | /* | |||
398 | * determine maximum number of blocks that wNAF | |||
399 | * splitting may yield (NB: maximum wNAF length is | |||
400 | * bit length plus one) | |||
401 | */ | |||
402 | numblocks = (BN_num_bits(scalar) / blocksize) + 1; | |||
403 | ||||
404 | /* | |||
405 | * we cannot use more blocks than we have | |||
406 | * precomputation for | |||
407 | */ | |||
408 | if (numblocks > pre_comp->numblocks) | |||
409 | numblocks = pre_comp->numblocks; | |||
410 | ||||
411 | pre_points_per_block = (size_t) 1 << (pre_comp->w - 1); | |||
412 | ||||
413 | /* check that pre_comp looks sane */ | |||
414 | if (pre_comp->num != (pre_comp->numblocks * pre_points_per_block)) { | |||
415 | ECerror(ERR_R_INTERNAL_ERROR)ERR_put_error(16,(0xfff),((4|64)),"/usr/src/lib/libcrypto/ec/ec_mult.c" ,415); | |||
416 | goto err; | |||
417 | } | |||
418 | } else { | |||
419 | /* can't use precomputation */ | |||
420 | pre_comp = NULL((void *)0); | |||
421 | numblocks = 1; | |||
422 | num_scalar = 1; /* treat 'scalar' like 'num'-th | |||
423 | * element of 'scalars' */ | |||
424 | } | |||
425 | } | |||
426 | totalnum = num + numblocks; | |||
427 | ||||
428 | /* includes space for pivot */ | |||
429 | wNAF = reallocarray(NULL((void *)0), (totalnum + 1), sizeof wNAF[0]); | |||
430 | if (wNAF == NULL((void *)0)) { | |||
431 | ECerror(ERR_R_MALLOC_FAILURE)ERR_put_error(16,(0xfff),((1|64)),"/usr/src/lib/libcrypto/ec/ec_mult.c" ,431); | |||
432 | goto err; | |||
433 | } | |||
434 | ||||
435 | wNAF[0] = NULL((void *)0); /* preliminary pivot */ | |||
436 | ||||
437 | wsize = reallocarray(NULL((void *)0), totalnum, sizeof wsize[0]); | |||
438 | wNAF_len = reallocarray(NULL((void *)0), totalnum, sizeof wNAF_len[0]); | |||
439 | val_sub = reallocarray(NULL((void *)0), totalnum, sizeof val_sub[0]); | |||
440 | ||||
441 | if (wsize == NULL((void *)0) || wNAF_len == NULL((void *)0) || val_sub == NULL((void *)0)) { | |||
442 | ECerror(ERR_R_MALLOC_FAILURE)ERR_put_error(16,(0xfff),((1|64)),"/usr/src/lib/libcrypto/ec/ec_mult.c" ,442); | |||
443 | goto err; | |||
444 | } | |||
445 | ||||
446 | /* num_val will be the total number of temporarily precomputed points */ | |||
447 | num_val = 0; | |||
448 | ||||
449 | for (i = 0; i < num + num_scalar; i++) { | |||
450 | size_t bits; | |||
451 | ||||
452 | bits = i
| |||
453 | wsize[i] = EC_window_bits_for_scalar_size(bits)((size_t) ((bits) >= 2000 ? 6 : (bits) >= 800 ? 5 : (bits ) >= 300 ? 4 : (bits) >= 70 ? 3 : (bits) >= 20 ? 2 : 1)); | |||
454 | num_val += (size_t) 1 << (wsize[i] - 1); | |||
455 | wNAF[i + 1] = NULL((void *)0); /* make sure we always have a pivot */ | |||
456 | wNAF[i] = compute_wNAF((i
| |||
457 | if (wNAF[i] == NULL((void *)0)) | |||
458 | goto err; | |||
459 | if (wNAF_len[i] > max_len) | |||
460 | max_len = wNAF_len[i]; | |||
461 | } | |||
462 | ||||
463 | if (numblocks) { | |||
464 | /* we go here iff scalar != NULL */ | |||
465 | ||||
466 | if (pre_comp == NULL((void *)0)) { | |||
467 | if (num_scalar != 1) { | |||
468 | ECerror(ERR_R_INTERNAL_ERROR)ERR_put_error(16,(0xfff),((4|64)),"/usr/src/lib/libcrypto/ec/ec_mult.c" ,468); | |||
469 | goto err; | |||
470 | } | |||
471 | /* we have already generated a wNAF for 'scalar' */ | |||
472 | } else { | |||
473 | size_t tmp_len = 0; | |||
474 | ||||
475 | if (num_scalar != 0) { | |||
476 | ECerror(ERR_R_INTERNAL_ERROR)ERR_put_error(16,(0xfff),((4|64)),"/usr/src/lib/libcrypto/ec/ec_mult.c" ,476); | |||
477 | goto err; | |||
478 | } | |||
479 | /* | |||
480 | * use the window size for which we have | |||
481 | * precomputation | |||
482 | */ | |||
483 | wsize[num] = pre_comp->w; | |||
484 | tmp_wNAF = compute_wNAF(scalar, wsize[num], &tmp_len); | |||
485 | if (tmp_wNAF == NULL((void *)0)) | |||
486 | goto err; | |||
487 | ||||
488 | if (tmp_len <= max_len) { | |||
489 | /* | |||
490 | * One of the other wNAFs is at least as long | |||
491 | * as the wNAF belonging to the generator, so | |||
492 | * wNAF splitting will not buy us anything. | |||
493 | */ | |||
494 | ||||
495 | numblocks = 1; | |||
496 | totalnum = num + 1; /* don't use wNAF | |||
497 | * splitting */ | |||
498 | wNAF[num] = tmp_wNAF; | |||
499 | tmp_wNAF = NULL((void *)0); | |||
500 | wNAF[num + 1] = NULL((void *)0); | |||
501 | wNAF_len[num] = tmp_len; | |||
502 | if (tmp_len > max_len) | |||
503 | max_len = tmp_len; | |||
504 | /* | |||
505 | * pre_comp->points starts with the points | |||
506 | * that we need here: | |||
507 | */ | |||
508 | val_sub[num] = pre_comp->points; | |||
509 | } else { | |||
510 | /* | |||
511 | * don't include tmp_wNAF directly into wNAF | |||
512 | * array - use wNAF splitting and include the | |||
513 | * blocks | |||
514 | */ | |||
515 | ||||
516 | signed char *pp; | |||
517 | EC_POINT **tmp_points; | |||
518 | ||||
519 | if (tmp_len < numblocks * blocksize) { | |||
520 | /* | |||
521 | * possibly we can do with fewer | |||
522 | * blocks than estimated | |||
523 | */ | |||
524 | numblocks = (tmp_len + blocksize - 1) / blocksize; | |||
525 | if (numblocks > pre_comp->numblocks) { | |||
526 | ECerror(ERR_R_INTERNAL_ERROR)ERR_put_error(16,(0xfff),((4|64)),"/usr/src/lib/libcrypto/ec/ec_mult.c" ,526); | |||
527 | goto err; | |||
528 | } | |||
529 | totalnum = num + numblocks; | |||
530 | } | |||
531 | /* split wNAF in 'numblocks' parts */ | |||
532 | pp = tmp_wNAF; | |||
533 | tmp_points = pre_comp->points; | |||
534 | ||||
535 | for (i = num; i < totalnum; i++) { | |||
536 | if (i < totalnum - 1) { | |||
537 | wNAF_len[i] = blocksize; | |||
538 | if (tmp_len < blocksize) { | |||
539 | ECerror(ERR_R_INTERNAL_ERROR)ERR_put_error(16,(0xfff),((4|64)),"/usr/src/lib/libcrypto/ec/ec_mult.c" ,539); | |||
540 | goto err; | |||
541 | } | |||
542 | tmp_len -= blocksize; | |||
543 | } else | |||
544 | /* | |||
545 | * last block gets whatever | |||
546 | * is left (this could be | |||
547 | * more or less than | |||
548 | * 'blocksize'!) | |||
549 | */ | |||
550 | wNAF_len[i] = tmp_len; | |||
551 | ||||
552 | wNAF[i + 1] = NULL((void *)0); | |||
553 | wNAF[i] = malloc(wNAF_len[i]); | |||
554 | if (wNAF[i] == NULL((void *)0)) { | |||
555 | ECerror(ERR_R_MALLOC_FAILURE)ERR_put_error(16,(0xfff),((1|64)),"/usr/src/lib/libcrypto/ec/ec_mult.c" ,555); | |||
556 | goto err; | |||
557 | } | |||
558 | memcpy(wNAF[i], pp, wNAF_len[i]); | |||
559 | if (wNAF_len[i] > max_len) | |||
560 | max_len = wNAF_len[i]; | |||
561 | ||||
562 | if (*tmp_points == NULL((void *)0)) { | |||
563 | ECerror(ERR_R_INTERNAL_ERROR)ERR_put_error(16,(0xfff),((4|64)),"/usr/src/lib/libcrypto/ec/ec_mult.c" ,563); | |||
564 | goto err; | |||
565 | } | |||
566 | val_sub[i] = tmp_points; | |||
567 | tmp_points += pre_points_per_block; | |||
568 | pp += blocksize; | |||
569 | } | |||
570 | } | |||
571 | } | |||
572 | } | |||
573 | /* | |||
574 | * All points we precompute now go into a single array 'val'. | |||
575 | * 'val_sub[i]' is a pointer to the subarray for the i-th point, or | |||
576 | * to a subarray of 'pre_comp->points' if we already have | |||
577 | * precomputation. | |||
578 | */ | |||
579 | val = reallocarray(NULL((void *)0), (num_val + 1), sizeof val[0]); | |||
580 | if (val == NULL((void *)0)) { | |||
581 | ECerror(ERR_R_MALLOC_FAILURE)ERR_put_error(16,(0xfff),((1|64)),"/usr/src/lib/libcrypto/ec/ec_mult.c" ,581); | |||
582 | goto err; | |||
583 | } | |||
584 | val[num_val] = NULL((void *)0); /* pivot element */ | |||
585 | ||||
586 | /* allocate points for precomputation */ | |||
587 | v = val; | |||
588 | for (i = 0; i < num + num_scalar; i++) { | |||
589 | val_sub[i] = v; | |||
590 | for (j = 0; j < ((size_t) 1 << (wsize[i] - 1)); j++) { | |||
591 | *v = EC_POINT_new(group); | |||
592 | if (*v == NULL((void *)0)) | |||
593 | goto err; | |||
594 | v++; | |||
595 | } | |||
596 | } | |||
597 | if (!(v == val + num_val)) { | |||
598 | ECerror(ERR_R_INTERNAL_ERROR)ERR_put_error(16,(0xfff),((4|64)),"/usr/src/lib/libcrypto/ec/ec_mult.c" ,598); | |||
599 | goto err; | |||
600 | } | |||
601 | if (!(tmp = EC_POINT_new(group))) | |||
602 | goto err; | |||
603 | ||||
604 | /* | |||
605 | * prepare precomputed values: val_sub[i][0] := points[i] | |||
606 | * val_sub[i][1] := 3 * points[i] val_sub[i][2] := 5 * points[i] ... | |||
607 | */ | |||
608 | for (i = 0; i < num + num_scalar; i++) { | |||
609 | if (i
| |||
610 | if (!EC_POINT_copy(val_sub[i][0], points[i])) | |||
611 | goto err; | |||
612 | } else { | |||
613 | if (!EC_POINT_copy(val_sub[i][0], generator)) | |||
614 | goto err; | |||
615 | } | |||
616 | ||||
617 | if (wsize[i] > 1) { | |||
618 | if (!EC_POINT_dbl(group, tmp, val_sub[i][0], ctx)) | |||
619 | goto err; | |||
620 | for (j = 1; j < ((size_t) 1 << (wsize[i] - 1)); j++) { | |||
621 | if (!EC_POINT_add(group, val_sub[i][j], val_sub[i][j - 1], tmp, ctx)) | |||
622 | goto err; | |||
623 | } | |||
624 | } | |||
625 | } | |||
626 | ||||
627 | if (!EC_POINTs_make_affine(group, num_val, val, ctx)) | |||
628 | goto err; | |||
629 | ||||
630 | r_is_at_infinity = 1; | |||
631 | ||||
632 | for (k = max_len - 1; k >= 0; k--) { | |||
633 | if (!r_is_at_infinity
| |||
634 | if (!EC_POINT_dbl(group, r, r, ctx)) | |||
635 | goto err; | |||
636 | } | |||
637 | for (i = 0; i < totalnum; i++) { | |||
638 | if (wNAF_len[i] > (size_t) k) { | |||
639 | int digit = wNAF[i][k]; | |||
| ||||
640 | int is_neg; | |||
641 | ||||
642 | if (digit
| |||
643 | is_neg = digit < 0; | |||
644 | ||||
645 | if (is_neg) | |||
646 | digit = -digit; | |||
647 | ||||
648 | if (is_neg != r_is_inverted) { | |||
649 | if (!r_is_at_infinity) { | |||
650 | if (!EC_POINT_invert(group, r, ctx)) | |||
651 | goto err; | |||
652 | } | |||
653 | r_is_inverted = !r_is_inverted; | |||
654 | } | |||
655 | /* digit > 0 */ | |||
656 | ||||
657 | if (r_is_at_infinity) { | |||
658 | if (!EC_POINT_copy(r, val_sub[i][digit >> 1])) | |||
659 | goto err; | |||
660 | r_is_at_infinity = 0; | |||
661 | } else { | |||
662 | if (!EC_POINT_add(group, r, r, val_sub[i][digit >> 1], ctx)) | |||
663 | goto err; | |||
664 | } | |||
665 | } | |||
666 | } | |||
667 | } | |||
668 | } | |||
669 | ||||
670 | if (r_is_at_infinity) { | |||
671 | if (!EC_POINT_set_to_infinity(group, r)) | |||
672 | goto err; | |||
673 | } else { | |||
674 | if (r_is_inverted) | |||
675 | if (!EC_POINT_invert(group, r, ctx)) | |||
676 | goto err; | |||
677 | } | |||
678 | ||||
679 | ret = 1; | |||
680 | ||||
681 | err: | |||
682 | BN_CTX_free(new_ctx); | |||
683 | EC_POINT_free(tmp); | |||
684 | free(wsize); | |||
685 | free(wNAF_len); | |||
686 | free(tmp_wNAF); | |||
687 | if (wNAF != NULL((void *)0)) { | |||
688 | signed char **w; | |||
689 | ||||
690 | for (w = wNAF; *w != NULL((void *)0); w++) | |||
691 | free(*w); | |||
692 | ||||
693 | free(wNAF); | |||
694 | } | |||
695 | if (val != NULL((void *)0)) { | |||
696 | for (v = val; *v != NULL((void *)0); v++) | |||
697 | EC_POINT_clear_free(*v); | |||
698 | free(val); | |||
699 | } | |||
700 | free(val_sub); | |||
701 | return ret; | |||
702 | } | |||
703 | ||||
704 | ||||
705 | /* ec_wNAF_precompute_mult() | |||
706 | * creates an EC_PRE_COMP object with preprecomputed multiples of the generator | |||
707 | * for use with wNAF splitting as implemented in ec_wNAF_mul(). | |||
708 | * | |||
709 | * 'pre_comp->points' is an array of multiples of the generator | |||
710 | * of the following form: | |||
711 | * points[0] = generator; | |||
712 | * points[1] = 3 * generator; | |||
713 | * ... | |||
714 | * points[2^(w-1)-1] = (2^(w-1)-1) * generator; | |||
715 | * points[2^(w-1)] = 2^blocksize * generator; | |||
716 | * points[2^(w-1)+1] = 3 * 2^blocksize * generator; | |||
717 | * ... | |||
718 | * points[2^(w-1)*(numblocks-1)-1] = (2^(w-1)) * 2^(blocksize*(numblocks-2)) * generator | |||
719 | * points[2^(w-1)*(numblocks-1)] = 2^(blocksize*(numblocks-1)) * generator | |||
720 | * ... | |||
721 | * points[2^(w-1)*numblocks-1] = (2^(w-1)) * 2^(blocksize*(numblocks-1)) * generator | |||
722 | * points[2^(w-1)*numblocks] = NULL | |||
723 | */ | |||
724 | int | |||
725 | ec_wNAF_precompute_mult(EC_GROUP * group, BN_CTX * ctx) | |||
726 | { | |||
727 | const EC_POINT *generator; | |||
728 | EC_POINT *tmp_point = NULL((void *)0), *base = NULL((void *)0), **var; | |||
729 | BN_CTX *new_ctx = NULL((void *)0); | |||
730 | BIGNUM *order; | |||
731 | size_t i, bits, w, pre_points_per_block, blocksize, numblocks, | |||
732 | num; | |||
733 | EC_POINT **points = NULL((void *)0); | |||
734 | EC_PRE_COMP *pre_comp; | |||
735 | int ret = 0; | |||
736 | ||||
737 | /* if there is an old EC_PRE_COMP object, throw it away */ | |||
738 | EC_EX_DATA_free_data(&group->extra_data, ec_pre_comp_dup, ec_pre_comp_free, ec_pre_comp_clear_free); | |||
739 | ||||
740 | if ((pre_comp = ec_pre_comp_new(group)) == NULL((void *)0)) | |||
741 | return 0; | |||
742 | ||||
743 | generator = EC_GROUP_get0_generator(group); | |||
744 | if (generator == NULL((void *)0)) { | |||
745 | ECerror(EC_R_UNDEFINED_GENERATOR)ERR_put_error(16,(0xfff),(113),"/usr/src/lib/libcrypto/ec/ec_mult.c" ,745); | |||
746 | goto err; | |||
747 | } | |||
748 | if (ctx == NULL((void *)0)) { | |||
749 | ctx = new_ctx = BN_CTX_new(); | |||
750 | if (ctx == NULL((void *)0)) | |||
751 | goto err; | |||
752 | } | |||
753 | BN_CTX_start(ctx); | |||
754 | if ((order = BN_CTX_get(ctx)) == NULL((void *)0)) | |||
755 | goto err; | |||
756 | ||||
757 | if (!EC_GROUP_get_order(group, order, ctx)) | |||
758 | goto err; | |||
759 | if (BN_is_zero(order)) { | |||
760 | ECerror(EC_R_UNKNOWN_ORDER)ERR_put_error(16,(0xfff),(114),"/usr/src/lib/libcrypto/ec/ec_mult.c" ,760); | |||
761 | goto err; | |||
762 | } | |||
763 | bits = BN_num_bits(order); | |||
764 | /* | |||
765 | * The following parameters mean we precompute (approximately) one | |||
766 | * point per bit. | |||
767 | * | |||
768 | * TBD: The combination 8, 4 is perfect for 160 bits; for other bit | |||
769 | * lengths, other parameter combinations might provide better | |||
770 | * efficiency. | |||
771 | */ | |||
772 | blocksize = 8; | |||
773 | w = 4; | |||
774 | if (EC_window_bits_for_scalar_size(bits)((size_t) ((bits) >= 2000 ? 6 : (bits) >= 800 ? 5 : (bits ) >= 300 ? 4 : (bits) >= 70 ? 3 : (bits) >= 20 ? 2 : 1)) > w) { | |||
775 | /* let's not make the window too small ... */ | |||
776 | w = EC_window_bits_for_scalar_size(bits)((size_t) ((bits) >= 2000 ? 6 : (bits) >= 800 ? 5 : (bits ) >= 300 ? 4 : (bits) >= 70 ? 3 : (bits) >= 20 ? 2 : 1)); | |||
777 | } | |||
778 | numblocks = (bits + blocksize - 1) / blocksize; /* max. number of blocks | |||
779 | * to use for wNAF | |||
780 | * splitting */ | |||
781 | ||||
782 | pre_points_per_block = (size_t) 1 << (w - 1); | |||
783 | num = pre_points_per_block * numblocks; /* number of points to | |||
784 | * compute and store */ | |||
785 | ||||
786 | points = reallocarray(NULL((void *)0), (num + 1), sizeof(EC_POINT *)); | |||
787 | if (!points) { | |||
788 | ECerror(ERR_R_MALLOC_FAILURE)ERR_put_error(16,(0xfff),((1|64)),"/usr/src/lib/libcrypto/ec/ec_mult.c" ,788); | |||
789 | goto err; | |||
790 | } | |||
791 | var = points; | |||
792 | var[num] = NULL((void *)0); /* pivot */ | |||
793 | for (i = 0; i < num; i++) { | |||
794 | if ((var[i] = EC_POINT_new(group)) == NULL((void *)0)) { | |||
795 | ECerror(ERR_R_MALLOC_FAILURE)ERR_put_error(16,(0xfff),((1|64)),"/usr/src/lib/libcrypto/ec/ec_mult.c" ,795); | |||
796 | goto err; | |||
797 | } | |||
798 | } | |||
799 | ||||
800 | if (!(tmp_point = EC_POINT_new(group)) || !(base = EC_POINT_new(group))) { | |||
801 | ECerror(ERR_R_MALLOC_FAILURE)ERR_put_error(16,(0xfff),((1|64)),"/usr/src/lib/libcrypto/ec/ec_mult.c" ,801); | |||
802 | goto err; | |||
803 | } | |||
804 | if (!EC_POINT_copy(base, generator)) | |||
805 | goto err; | |||
806 | ||||
807 | /* do the precomputation */ | |||
808 | for (i = 0; i < numblocks; i++) { | |||
809 | size_t j; | |||
810 | ||||
811 | if (!EC_POINT_dbl(group, tmp_point, base, ctx)) | |||
812 | goto err; | |||
813 | ||||
814 | if (!EC_POINT_copy(*var++, base)) | |||
815 | goto err; | |||
816 | ||||
817 | for (j = 1; j < pre_points_per_block; j++, var++) { | |||
818 | /* calculate odd multiples of the current base point */ | |||
819 | if (!EC_POINT_add(group, *var, tmp_point, *(var - 1), ctx)) | |||
820 | goto err; | |||
821 | } | |||
822 | ||||
823 | if (i < numblocks - 1) { | |||
824 | /* | |||
825 | * get the next base (multiply current one by | |||
826 | * 2^blocksize) | |||
827 | */ | |||
828 | size_t k; | |||
829 | ||||
830 | if (blocksize <= 2) { | |||
831 | ECerror(ERR_R_INTERNAL_ERROR)ERR_put_error(16,(0xfff),((4|64)),"/usr/src/lib/libcrypto/ec/ec_mult.c" ,831); | |||
832 | goto err; | |||
833 | } | |||
834 | if (!EC_POINT_dbl(group, base, tmp_point, ctx)) | |||
835 | goto err; | |||
836 | for (k = 2; k < blocksize; k++) { | |||
837 | if (!EC_POINT_dbl(group, base, base, ctx)) | |||
838 | goto err; | |||
839 | } | |||
840 | } | |||
841 | } | |||
842 | ||||
843 | if (!EC_POINTs_make_affine(group, num, points, ctx)) | |||
844 | goto err; | |||
845 | ||||
846 | pre_comp->group = group; | |||
847 | pre_comp->blocksize = blocksize; | |||
848 | pre_comp->numblocks = numblocks; | |||
849 | pre_comp->w = w; | |||
850 | pre_comp->points = points; | |||
851 | points = NULL((void *)0); | |||
852 | pre_comp->num = num; | |||
853 | ||||
854 | if (!EC_EX_DATA_set_data(&group->extra_data, pre_comp, | |||
855 | ec_pre_comp_dup, ec_pre_comp_free, ec_pre_comp_clear_free)) | |||
856 | goto err; | |||
857 | pre_comp = NULL((void *)0); | |||
858 | ||||
859 | ret = 1; | |||
860 | err: | |||
861 | if (ctx != NULL((void *)0)) | |||
862 | BN_CTX_end(ctx); | |||
863 | BN_CTX_free(new_ctx); | |||
864 | ec_pre_comp_free(pre_comp); | |||
865 | if (points) { | |||
866 | EC_POINT **p; | |||
867 | ||||
868 | for (p = points; *p != NULL((void *)0); p++) | |||
869 | EC_POINT_free(*p); | |||
870 | free(points); | |||
871 | } | |||
872 | EC_POINT_free(tmp_point); | |||
873 | EC_POINT_free(base); | |||
874 | return ret; | |||
875 | } | |||
876 | ||||
877 | ||||
878 | int | |||
879 | ec_wNAF_have_precompute_mult(const EC_GROUP * group) | |||
880 | { | |||
881 | if (EC_EX_DATA_get_data(group->extra_data, ec_pre_comp_dup, ec_pre_comp_free, ec_pre_comp_clear_free) != NULL((void *)0)) | |||
882 | return 1; | |||
883 | else | |||
884 | return 0; | |||
885 | } |