Bug Summary

File:src/lib/libcrypto/ec/ecp_smpl.c
Warning:line 1175, column 16
Access to field 'Z_is_one' results in a dereference of a null pointer (loaded from variable 'p')

Annotated Source Code

Press '?' to see keyboard shortcuts

clang -cc1 -cc1 -triple amd64-unknown-openbsd7.4 -analyze -disable-free -clear-ast-before-backend -disable-llvm-verifier -discard-value-names -main-file-name ecp_smpl.c -analyzer-checker=core -analyzer-checker=apiModeling -analyzer-checker=unix -analyzer-checker=deadcode -analyzer-checker=security.insecureAPI.UncheckedReturn -analyzer-checker=security.insecureAPI.getpw -analyzer-checker=security.insecureAPI.gets -analyzer-checker=security.insecureAPI.mktemp -analyzer-checker=security.insecureAPI.mkstemp -analyzer-checker=security.insecureAPI.vfork -analyzer-checker=nullability.NullPassedToNonnull -analyzer-checker=nullability.NullReturnedFromNonnull -analyzer-output plist -w -setup-static-analyzer -mrelocation-model pic -pic-level 1 -pic-is-pie -mframe-pointer=all -relaxed-aliasing -ffp-contract=on -fno-rounding-math -mconstructor-aliases -funwind-tables=2 -target-cpu x86-64 -target-feature +retpoline-indirect-calls -target-feature +retpoline-indirect-branches -tune-cpu generic -debugger-tuning=gdb -fcoverage-compilation-dir=/usr/src/lib/libcrypto/obj -resource-dir /usr/local/llvm16/lib/clang/16 -D LIBRESSL_INTERNAL -D HAVE_FUNOPEN -I /usr/src/lib/libcrypto -I /usr/src/lib/libcrypto/arch/amd64 -I /usr/src/lib/libcrypto/asn1 -I /usr/src/lib/libcrypto/bio -I /usr/src/lib/libcrypto/bn -I /usr/src/lib/libcrypto/bn/arch/amd64 -I /usr/src/lib/libcrypto/bytestring -I /usr/src/lib/libcrypto/curve25519 -I /usr/src/lib/libcrypto/dh -I /usr/src/lib/libcrypto/dsa -I /usr/src/lib/libcrypto/ec -I /usr/src/lib/libcrypto/ecdsa -I /usr/src/lib/libcrypto/evp -I /usr/src/lib/libcrypto/hidden -I /usr/src/lib/libcrypto/hmac -I /usr/src/lib/libcrypto/kdf -I /usr/src/lib/libcrypto/modes -I /usr/src/lib/libcrypto/ocsp -I /usr/src/lib/libcrypto/pkcs12 -I /usr/src/lib/libcrypto/rsa -I /usr/src/lib/libcrypto/sha -I /usr/src/lib/libcrypto/ts -I /usr/src/lib/libcrypto/x509 -I /usr/src/lib/libcrypto/obj -D AES_ASM -D BSAES_ASM -D VPAES_ASM -D OPENSSL_IA32_SSE2 -D RSA_ASM -D OPENSSL_BN_ASM_MONT -D OPENSSL_BN_ASM_MONT5 -D MD5_ASM -D GHASH_ASM -D RC4_MD5_ASM -D SHA1_ASM -D SHA256_ASM -D SHA512_ASM -D WHIRLPOOL_ASM -D OPENSSL_CPUID_OBJ -internal-isystem /usr/local/llvm16/lib/clang/16/include -internal-externc-isystem /usr/include -O2 -fdebug-compilation-dir=/usr/src/lib/libcrypto/obj -ferror-limit 19 -fwrapv -D_RET_PROTECTOR -ret-protector -fcf-protection=branch -fno-jump-tables -fgnuc-version=4.2.1 -vectorize-loops -vectorize-slp -fno-builtin-malloc -fno-builtin-calloc -fno-builtin-realloc -fno-builtin-valloc -fno-builtin-free -fno-builtin-strdup -fno-builtin-strndup -analyzer-output=html -faddrsig -D__GCC_HAVE_DWARF2_CFI_ASM=1 -o /home/ben/Projects/scan/2024-01-11-140451-98009-1 -x c /usr/src/lib/libcrypto/ec/ecp_smpl.c
1/* $OpenBSD: ecp_smpl.c,v 1.56 2023/08/03 18:53:56 tb Exp $ */
2/* Includes code written by Lenka Fibikova <fibikova@exp-math.uni-essen.de>
3 * for the OpenSSL project.
4 * Includes code written by Bodo Moeller for the OpenSSL project.
5*/
6/* ====================================================================
7 * Copyright (c) 1998-2002 The OpenSSL Project. All rights reserved.
8 *
9 * Redistribution and use in source and binary forms, with or without
10 * modification, are permitted provided that the following conditions
11 * are met:
12 *
13 * 1. Redistributions of source code must retain the above copyright
14 * notice, this list of conditions and the following disclaimer.
15 *
16 * 2. Redistributions in binary form must reproduce the above copyright
17 * notice, this list of conditions and the following disclaimer in
18 * the documentation and/or other materials provided with the
19 * distribution.
20 *
21 * 3. All advertising materials mentioning features or use of this
22 * software must display the following acknowledgment:
23 * "This product includes software developed by the OpenSSL Project
24 * for use in the OpenSSL Toolkit. (http://www.openssl.org/)"
25 *
26 * 4. The names "OpenSSL Toolkit" and "OpenSSL Project" must not be used to
27 * endorse or promote products derived from this software without
28 * prior written permission. For written permission, please contact
29 * openssl-core@openssl.org.
30 *
31 * 5. Products derived from this software may not be called "OpenSSL"
32 * nor may "OpenSSL" appear in their names without prior written
33 * permission of the OpenSSL Project.
34 *
35 * 6. Redistributions of any form whatsoever must retain the following
36 * acknowledgment:
37 * "This product includes software developed by the OpenSSL Project
38 * for use in the OpenSSL Toolkit (http://www.openssl.org/)"
39 *
40 * THIS SOFTWARE IS PROVIDED BY THE OpenSSL PROJECT ``AS IS'' AND ANY
41 * EXPRESSED OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
42 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
43 * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE OpenSSL PROJECT OR
44 * ITS CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
45 * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
46 * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
47 * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
48 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT,
49 * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
50 * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED
51 * OF THE POSSIBILITY OF SUCH DAMAGE.
52 * ====================================================================
53 *
54 * This product includes cryptographic software written by Eric Young
55 * (eay@cryptsoft.com). This product includes software written by Tim
56 * Hudson (tjh@cryptsoft.com).
57 *
58 */
59/* ====================================================================
60 * Copyright 2002 Sun Microsystems, Inc. ALL RIGHTS RESERVED.
61 * Portions of this software developed by SUN MICROSYSTEMS, INC.,
62 * and contributed to the OpenSSL project.
63 */
64
65#include <openssl/err.h>
66
67#include "bn_local.h"
68#include "ec_local.h"
69
70/*
71 * Most method functions in this file are designed to work with
72 * non-trivial representations of field elements if necessary
73 * (see ecp_mont.c): while standard modular addition and subtraction
74 * are used, the field_mul and field_sqr methods will be used for
75 * multiplication, and field_encode and field_decode (if defined)
76 * will be used for converting between representations.
77 *
78 * Functions ec_GFp_simple_points_make_affine() and
79 * ec_GFp_simple_point_get_affine_coordinates() specifically assume
80 * that if a non-trivial representation is used, it is a Montgomery
81 * representation (i.e. 'encoding' means multiplying by some factor R).
82 */
83
84int
85ec_GFp_simple_group_init(EC_GROUP *group)
86{
87 BN_init(&group->field);
88 BN_init(&group->a);
89 BN_init(&group->b);
90 group->a_is_minus3 = 0;
91 return 1;
92}
93
94void
95ec_GFp_simple_group_finish(EC_GROUP *group)
96{
97 BN_free(&group->field);
98 BN_free(&group->a);
99 BN_free(&group->b);
100}
101
102int
103ec_GFp_simple_group_copy(EC_GROUP *dest, const EC_GROUP *src)
104{
105 if (!bn_copy(&dest->field, &src->field))
106 return 0;
107 if (!bn_copy(&dest->a, &src->a))
108 return 0;
109 if (!bn_copy(&dest->b, &src->b))
110 return 0;
111
112 dest->a_is_minus3 = src->a_is_minus3;
113
114 return 1;
115}
116
117static int
118ec_decode_scalar(const EC_GROUP *group, BIGNUM *bn, const BIGNUM *x, BN_CTX *ctx)
119{
120 if (bn == NULL((void *)0))
121 return 1;
122
123 if (group->meth->field_decode != NULL((void *)0))
124 return group->meth->field_decode(group, bn, x, ctx);
125
126 return bn_copy(bn, x);
127}
128
129static int
130ec_encode_scalar(const EC_GROUP *group, BIGNUM *bn, const BIGNUM *x, BN_CTX *ctx)
131{
132 if (!BN_nnmod(bn, x, &group->field, ctx))
133 return 0;
134
135 if (group->meth->field_encode != NULL((void *)0))
136 return group->meth->field_encode(group, bn, bn, ctx);
137
138 return 1;
139}
140
141static int
142ec_encode_z_coordinate(const EC_GROUP *group, BIGNUM *bn, int *is_one,
143 const BIGNUM *z, BN_CTX *ctx)
144{
145 if (!BN_nnmod(bn, z, &group->field, ctx))
146 return 0;
147
148 *is_one = BN_is_one(bn);
149 if (*is_one && group->meth->field_set_to_one != NULL((void *)0))
150 return group->meth->field_set_to_one(group, bn, ctx);
151
152 if (group->meth->field_encode != NULL((void *)0))
153 return group->meth->field_encode(group, bn, bn, ctx);
154
155 return 1;
156}
157
158int
159ec_GFp_simple_group_set_curve(EC_GROUP *group,
160 const BIGNUM *p, const BIGNUM *a, const BIGNUM *b, BN_CTX *ctx)
161{
162 BIGNUM *a_plus_3;
163 int ret = 0;
164
165 /* p must be a prime > 3 */
166 if (BN_num_bits(p) <= 2 || !BN_is_odd(p)) {
167 ECerror(EC_R_INVALID_FIELD)ERR_put_error(16,(0xfff),(103),"/usr/src/lib/libcrypto/ec/ecp_smpl.c"
,167);
168 return 0;
169 }
170
171 BN_CTX_start(ctx);
172
173 if ((a_plus_3 = BN_CTX_get(ctx)) == NULL((void *)0))
174 goto err;
175
176 if (!bn_copy(&group->field, p))
177 goto err;
178 BN_set_negative(&group->field, 0);
179
180 if (!ec_encode_scalar(group, &group->a, a, ctx))
181 goto err;
182 if (!ec_encode_scalar(group, &group->b, b, ctx))
183 goto err;
184
185 if (!BN_set_word(a_plus_3, 3))
186 goto err;
187 if (!BN_mod_add(a_plus_3, a_plus_3, a, &group->field, ctx))
188 goto err;
189
190 group->a_is_minus3 = BN_is_zero(a_plus_3);
191
192 ret = 1;
193
194 err:
195 BN_CTX_end(ctx);
196
197 return ret;
198}
199
200int
201ec_GFp_simple_group_get_curve(const EC_GROUP *group, BIGNUM *p, BIGNUM *a,
202 BIGNUM *b, BN_CTX *ctx)
203{
204 if (p != NULL((void *)0)) {
205 if (!bn_copy(p, &group->field))
206 return 0;
207 }
208 if (!ec_decode_scalar(group, a, &group->a, ctx))
209 return 0;
210 if (!ec_decode_scalar(group, b, &group->b, ctx))
211 return 0;
212
213 return 1;
214}
215
216int
217ec_GFp_simple_group_get_degree(const EC_GROUP *group)
218{
219 return BN_num_bits(&group->field);
220}
221
222int
223ec_GFp_simple_group_check_discriminant(const EC_GROUP *group, BN_CTX *ctx)
224{
225 BIGNUM *p, *a, *b, *discriminant;
226 int ret = 0;
227
228 BN_CTX_start(ctx);
229
230 if ((p = BN_CTX_get(ctx)) == NULL((void *)0))
231 goto err;
232 if ((a = BN_CTX_get(ctx)) == NULL((void *)0))
233 goto err;
234 if ((b = BN_CTX_get(ctx)) == NULL((void *)0))
235 goto err;
236 if ((discriminant = BN_CTX_get(ctx)) == NULL((void *)0))
237 goto err;
238
239 if (!EC_GROUP_get_curve(group, p, a, b, ctx))
240 goto err;
241
242 /*
243 * Check that the discriminant 4a^3 + 27b^2 is non-zero modulo p.
244 */
245
246 if (BN_is_zero(a) && BN_is_zero(b))
247 goto err;
248 if (BN_is_zero(a) || BN_is_zero(b))
249 goto done;
250
251 /* Compute the discriminant: first 4a^3, then 27b^2, then their sum. */
252 if (!BN_mod_sqr(discriminant, a, p, ctx))
253 goto err;
254 if (!BN_mod_mul(discriminant, discriminant, a, p, ctx))
255 goto err;
256 if (!BN_lshift(discriminant, discriminant, 2))
257 goto err;
258
259 if (!BN_mod_sqr(b, b, p, ctx))
260 goto err;
261 if (!BN_mul_word(b, 27))
262 goto err;
263
264 if (!BN_mod_add(discriminant, discriminant, b, p, ctx))
265 goto err;
266
267 if (BN_is_zero(discriminant))
268 goto err;
269
270 done:
271 ret = 1;
272
273 err:
274 BN_CTX_end(ctx);
275
276 return ret;
277}
278
279int
280ec_GFp_simple_point_init(EC_POINT * point)
281{
282 BN_init(&point->X);
283 BN_init(&point->Y);
284 BN_init(&point->Z);
285 point->Z_is_one = 0;
286
287 return 1;
288}
289
290void
291ec_GFp_simple_point_finish(EC_POINT *point)
292{
293 BN_free(&point->X);
294 BN_free(&point->Y);
295 BN_free(&point->Z);
296 point->Z_is_one = 0;
297}
298
299int
300ec_GFp_simple_point_copy(EC_POINT *dest, const EC_POINT *src)
301{
302 if (!bn_copy(&dest->X, &src->X))
303 return 0;
304 if (!bn_copy(&dest->Y, &src->Y))
305 return 0;
306 if (!bn_copy(&dest->Z, &src->Z))
307 return 0;
308 dest->Z_is_one = src->Z_is_one;
309
310 return 1;
311}
312
313int
314ec_GFp_simple_point_set_to_infinity(const EC_GROUP *group, EC_POINT *point)
315{
316 point->Z_is_one = 0;
317 BN_zero(&point->Z);
318 return 1;
319}
320
321int
322ec_GFp_simple_set_Jprojective_coordinates(const EC_GROUP *group,
323 EC_POINT *point, const BIGNUM *x, const BIGNUM *y, const BIGNUM *z,
324 BN_CTX *ctx)
325{
326 int ret = 0;
327
328 /*
329 * Setting individual coordinates allows the creation of bad points.
330 * EC_POINT_set_Jprojective_coordinates() checks at the API boundary.
331 */
332
333 if (x != NULL((void *)0)) {
334 if (!ec_encode_scalar(group, &point->X, x, ctx))
335 goto err;
336 }
337 if (y != NULL((void *)0)) {
338 if (!ec_encode_scalar(group, &point->Y, y, ctx))
339 goto err;
340 }
341 if (z != NULL((void *)0)) {
342 if (!ec_encode_z_coordinate(group, &point->Z, &point->Z_is_one,
343 z, ctx))
344 goto err;
345 }
346
347 ret = 1;
348
349 err:
350 return ret;
351}
352
353int
354ec_GFp_simple_get_Jprojective_coordinates(const EC_GROUP *group,
355 const EC_POINT *point, BIGNUM *x, BIGNUM *y, BIGNUM *z, BN_CTX *ctx)
356{
357 int ret = 0;
358
359 if (!ec_decode_scalar(group, x, &point->X, ctx))
360 goto err;
361 if (!ec_decode_scalar(group, y, &point->Y, ctx))
362 goto err;
363 if (!ec_decode_scalar(group, z, &point->Z, ctx))
364 goto err;
365
366 ret = 1;
367
368 err:
369 return ret;
370}
371
372int
373ec_GFp_simple_point_set_affine_coordinates(const EC_GROUP *group, EC_POINT *point,
374 const BIGNUM *x, const BIGNUM *y, BN_CTX *ctx)
375{
376 if (x == NULL((void *)0) || y == NULL((void *)0)) {
377 /* unlike for projective coordinates, we do not tolerate this */
378 ECerror(ERR_R_PASSED_NULL_PARAMETER)ERR_put_error(16,(0xfff),((3|64)),"/usr/src/lib/libcrypto/ec/ecp_smpl.c"
,378);
379 return 0;
380 }
381 return EC_POINT_set_Jprojective_coordinates(group, point, x, y,
382 BN_value_one(), ctx);
383}
384
385int
386ec_GFp_simple_point_get_affine_coordinates(const EC_GROUP *group,
387 const EC_POINT *point, BIGNUM *x, BIGNUM *y, BN_CTX *ctx)
388{
389 BIGNUM *z, *Z, *Z_1, *Z_2, *Z_3;
390 int ret = 0;
391
392 if (EC_POINT_is_at_infinity(group, point) > 0) {
393 ECerror(EC_R_POINT_AT_INFINITY)ERR_put_error(16,(0xfff),(106),"/usr/src/lib/libcrypto/ec/ecp_smpl.c"
,393);
394 return 0;
395 }
396
397 BN_CTX_start(ctx);
398
399 if ((z = BN_CTX_get(ctx)) == NULL((void *)0))
400 goto err;
401 if ((Z = BN_CTX_get(ctx)) == NULL((void *)0))
402 goto err;
403 if ((Z_1 = BN_CTX_get(ctx)) == NULL((void *)0))
404 goto err;
405 if ((Z_2 = BN_CTX_get(ctx)) == NULL((void *)0))
406 goto err;
407 if ((Z_3 = BN_CTX_get(ctx)) == NULL((void *)0))
408 goto err;
409
410 /* Convert from projective coordinates (X, Y, Z) into (X/Z^2, Y/Z^3). */
411
412 if (!ec_decode_scalar(group, z, &point->Z, ctx))
413 goto err;
414
415 if (BN_is_one(z)) {
416 if (!ec_decode_scalar(group, x, &point->X, ctx))
417 goto err;
418 if (!ec_decode_scalar(group, y, &point->Y, ctx))
419 goto err;
420 goto done;
421 }
422
423 if (BN_mod_inverse_ct(Z_1, z, &group->field, ctx) == NULL((void *)0)) {
424 ECerror(ERR_R_BN_LIB)ERR_put_error(16,(0xfff),(3),"/usr/src/lib/libcrypto/ec/ecp_smpl.c"
,424);
425 goto err;
426 }
427 if (group->meth->field_encode == NULL((void *)0)) {
428 /* field_sqr works on standard representation */
429 if (!group->meth->field_sqr(group, Z_2, Z_1, ctx))
430 goto err;
431 } else {
432 if (!BN_mod_sqr(Z_2, Z_1, &group->field, ctx))
433 goto err;
434 }
435
436 if (x != NULL((void *)0)) {
437 /*
438 * in the Montgomery case, field_mul will cancel out
439 * Montgomery factor in X:
440 */
441 if (!group->meth->field_mul(group, x, &point->X, Z_2, ctx))
442 goto err;
443 }
444 if (y != NULL((void *)0)) {
445 if (group->meth->field_encode == NULL((void *)0)) {
446 /* field_mul works on standard representation */
447 if (!group->meth->field_mul(group, Z_3, Z_2, Z_1, ctx))
448 goto err;
449 } else {
450 if (!BN_mod_mul(Z_3, Z_2, Z_1, &group->field, ctx))
451 goto err;
452 }
453
454 /*
455 * in the Montgomery case, field_mul will cancel out
456 * Montgomery factor in Y:
457 */
458 if (!group->meth->field_mul(group, y, &point->Y, Z_3, ctx))
459 goto err;
460 }
461
462 done:
463 ret = 1;
464
465 err:
466 BN_CTX_end(ctx);
467
468 return ret;
469}
470
471int
472ec_GFp_simple_add(const EC_GROUP *group, EC_POINT *r, const EC_POINT *a, const EC_POINT *b, BN_CTX *ctx)
473{
474 int (*field_mul) (const EC_GROUP *, BIGNUM *, const BIGNUM *, const BIGNUM *, BN_CTX *);
475 int (*field_sqr) (const EC_GROUP *, BIGNUM *, const BIGNUM *, BN_CTX *);
476 BIGNUM *n0, *n1, *n2, *n3, *n4, *n5, *n6;
477 const BIGNUM *p;
478 int ret = 0;
479
480 if (a == b)
481 return EC_POINT_dbl(group, r, a, ctx);
482 if (EC_POINT_is_at_infinity(group, a) > 0)
483 return EC_POINT_copy(r, b);
484 if (EC_POINT_is_at_infinity(group, b) > 0)
485 return EC_POINT_copy(r, a);
486
487 field_mul = group->meth->field_mul;
488 field_sqr = group->meth->field_sqr;
489 p = &group->field;
490
491 BN_CTX_start(ctx);
492
493 if ((n0 = BN_CTX_get(ctx)) == NULL((void *)0))
494 goto end;
495 if ((n1 = BN_CTX_get(ctx)) == NULL((void *)0))
496 goto end;
497 if ((n2 = BN_CTX_get(ctx)) == NULL((void *)0))
498 goto end;
499 if ((n3 = BN_CTX_get(ctx)) == NULL((void *)0))
500 goto end;
501 if ((n4 = BN_CTX_get(ctx)) == NULL((void *)0))
502 goto end;
503 if ((n5 = BN_CTX_get(ctx)) == NULL((void *)0))
504 goto end;
505 if ((n6 = BN_CTX_get(ctx)) == NULL((void *)0))
506 goto end;
507
508 /*
509 * Note that in this function we must not read components of 'a' or
510 * 'b' once we have written the corresponding components of 'r'. ('r'
511 * might be one of 'a' or 'b'.)
512 */
513
514 /* n1, n2 */
515 if (b->Z_is_one) {
516 if (!bn_copy(n1, &a->X))
517 goto end;
518 if (!bn_copy(n2, &a->Y))
519 goto end;
520 /* n1 = X_a */
521 /* n2 = Y_a */
522 } else {
523 if (!field_sqr(group, n0, &b->Z, ctx))
524 goto end;
525 if (!field_mul(group, n1, &a->X, n0, ctx))
526 goto end;
527 /* n1 = X_a * Z_b^2 */
528
529 if (!field_mul(group, n0, n0, &b->Z, ctx))
530 goto end;
531 if (!field_mul(group, n2, &a->Y, n0, ctx))
532 goto end;
533 /* n2 = Y_a * Z_b^3 */
534 }
535
536 /* n3, n4 */
537 if (a->Z_is_one) {
538 if (!bn_copy(n3, &b->X))
539 goto end;
540 if (!bn_copy(n4, &b->Y))
541 goto end;
542 /* n3 = X_b */
543 /* n4 = Y_b */
544 } else {
545 if (!field_sqr(group, n0, &a->Z, ctx))
546 goto end;
547 if (!field_mul(group, n3, &b->X, n0, ctx))
548 goto end;
549 /* n3 = X_b * Z_a^2 */
550
551 if (!field_mul(group, n0, n0, &a->Z, ctx))
552 goto end;
553 if (!field_mul(group, n4, &b->Y, n0, ctx))
554 goto end;
555 /* n4 = Y_b * Z_a^3 */
556 }
557
558 /* n5, n6 */
559 if (!BN_mod_sub_quick(n5, n1, n3, p))
560 goto end;
561 if (!BN_mod_sub_quick(n6, n2, n4, p))
562 goto end;
563 /* n5 = n1 - n3 */
564 /* n6 = n2 - n4 */
565
566 if (BN_is_zero(n5)) {
567 if (BN_is_zero(n6)) {
568 /* a is the same point as b */
569 BN_CTX_end(ctx);
570 ret = EC_POINT_dbl(group, r, a, ctx);
571 ctx = NULL((void *)0);
572 goto end;
573 } else {
574 /* a is the inverse of b */
575 BN_zero(&r->Z);
576 r->Z_is_one = 0;
577 ret = 1;
578 goto end;
579 }
580 }
581 /* 'n7', 'n8' */
582 if (!BN_mod_add_quick(n1, n1, n3, p))
583 goto end;
584 if (!BN_mod_add_quick(n2, n2, n4, p))
585 goto end;
586 /* 'n7' = n1 + n3 */
587 /* 'n8' = n2 + n4 */
588
589 /* Z_r */
590 if (a->Z_is_one && b->Z_is_one) {
591 if (!bn_copy(&r->Z, n5))
592 goto end;
593 } else {
594 if (a->Z_is_one) {
595 if (!bn_copy(n0, &b->Z))
596 goto end;
597 } else if (b->Z_is_one) {
598 if (!bn_copy(n0, &a->Z))
599 goto end;
600 } else {
601 if (!field_mul(group, n0, &a->Z, &b->Z, ctx))
602 goto end;
603 }
604 if (!field_mul(group, &r->Z, n0, n5, ctx))
605 goto end;
606 }
607 r->Z_is_one = 0;
608 /* Z_r = Z_a * Z_b * n5 */
609
610 /* X_r */
611 if (!field_sqr(group, n0, n6, ctx))
612 goto end;
613 if (!field_sqr(group, n4, n5, ctx))
614 goto end;
615 if (!field_mul(group, n3, n1, n4, ctx))
616 goto end;
617 if (!BN_mod_sub_quick(&r->X, n0, n3, p))
618 goto end;
619 /* X_r = n6^2 - n5^2 * 'n7' */
620
621 /* 'n9' */
622 if (!BN_mod_lshift1_quick(n0, &r->X, p))
623 goto end;
624 if (!BN_mod_sub_quick(n0, n3, n0, p))
625 goto end;
626 /* n9 = n5^2 * 'n7' - 2 * X_r */
627
628 /* Y_r */
629 if (!field_mul(group, n0, n0, n6, ctx))
630 goto end;
631 if (!field_mul(group, n5, n4, n5, ctx))
632 goto end; /* now n5 is n5^3 */
633 if (!field_mul(group, n1, n2, n5, ctx))
634 goto end;
635 if (!BN_mod_sub_quick(n0, n0, n1, p))
636 goto end;
637 if (BN_is_odd(n0))
638 if (!BN_add(n0, n0, p))
639 goto end;
640 /* now 0 <= n0 < 2*p, and n0 is even */
641 if (!BN_rshift1(&r->Y, n0))
642 goto end;
643 /* Y_r = (n6 * 'n9' - 'n8' * 'n5^3') / 2 */
644
645 ret = 1;
646
647 end:
648 BN_CTX_end(ctx);
649
650 return ret;
651}
652
653int
654ec_GFp_simple_dbl(const EC_GROUP *group, EC_POINT *r, const EC_POINT *a, BN_CTX *ctx)
655{
656 int (*field_mul) (const EC_GROUP *, BIGNUM *, const BIGNUM *, const BIGNUM *, BN_CTX *);
657 int (*field_sqr) (const EC_GROUP *, BIGNUM *, const BIGNUM *, BN_CTX *);
658 const BIGNUM *p;
659 BIGNUM *n0, *n1, *n2, *n3;
660 int ret = 0;
661
662 if (EC_POINT_is_at_infinity(group, a) > 0)
663 return EC_POINT_set_to_infinity(group, r);
664
665 field_mul = group->meth->field_mul;
666 field_sqr = group->meth->field_sqr;
667 p = &group->field;
668
669 BN_CTX_start(ctx);
670
671 if ((n0 = BN_CTX_get(ctx)) == NULL((void *)0))
672 goto err;
673 if ((n1 = BN_CTX_get(ctx)) == NULL((void *)0))
674 goto err;
675 if ((n2 = BN_CTX_get(ctx)) == NULL((void *)0))
676 goto err;
677 if ((n3 = BN_CTX_get(ctx)) == NULL((void *)0))
678 goto err;
679
680 /*
681 * Note that in this function we must not read components of 'a' once
682 * we have written the corresponding components of 'r'. ('r' might
683 * the same as 'a'.)
684 */
685
686 /* n1 */
687 if (a->Z_is_one) {
688 if (!field_sqr(group, n0, &a->X, ctx))
689 goto err;
690 if (!BN_mod_lshift1_quick(n1, n0, p))
691 goto err;
692 if (!BN_mod_add_quick(n0, n0, n1, p))
693 goto err;
694 if (!BN_mod_add_quick(n1, n0, &group->a, p))
695 goto err;
696 /* n1 = 3 * X_a^2 + a_curve */
697 } else if (group->a_is_minus3) {
698 if (!field_sqr(group, n1, &a->Z, ctx))
699 goto err;
700 if (!BN_mod_add_quick(n0, &a->X, n1, p))
701 goto err;
702 if (!BN_mod_sub_quick(n2, &a->X, n1, p))
703 goto err;
704 if (!field_mul(group, n1, n0, n2, ctx))
705 goto err;
706 if (!BN_mod_lshift1_quick(n0, n1, p))
707 goto err;
708 if (!BN_mod_add_quick(n1, n0, n1, p))
709 goto err;
710 /*
711 * n1 = 3 * (X_a + Z_a^2) * (X_a - Z_a^2) = 3 * X_a^2 - 3 *
712 * Z_a^4
713 */
714 } else {
715 if (!field_sqr(group, n0, &a->X, ctx))
716 goto err;
717 if (!BN_mod_lshift1_quick(n1, n0, p))
718 goto err;
719 if (!BN_mod_add_quick(n0, n0, n1, p))
720 goto err;
721 if (!field_sqr(group, n1, &a->Z, ctx))
722 goto err;
723 if (!field_sqr(group, n1, n1, ctx))
724 goto err;
725 if (!field_mul(group, n1, n1, &group->a, ctx))
726 goto err;
727 if (!BN_mod_add_quick(n1, n1, n0, p))
728 goto err;
729 /* n1 = 3 * X_a^2 + a_curve * Z_a^4 */
730 }
731
732 /* Z_r */
733 if (a->Z_is_one) {
734 if (!bn_copy(n0, &a->Y))
735 goto err;
736 } else {
737 if (!field_mul(group, n0, &a->Y, &a->Z, ctx))
738 goto err;
739 }
740 if (!BN_mod_lshift1_quick(&r->Z, n0, p))
741 goto err;
742 r->Z_is_one = 0;
743 /* Z_r = 2 * Y_a * Z_a */
744
745 /* n2 */
746 if (!field_sqr(group, n3, &a->Y, ctx))
747 goto err;
748 if (!field_mul(group, n2, &a->X, n3, ctx))
749 goto err;
750 if (!BN_mod_lshift_quick(n2, n2, 2, p))
751 goto err;
752 /* n2 = 4 * X_a * Y_a^2 */
753
754 /* X_r */
755 if (!BN_mod_lshift1_quick(n0, n2, p))
756 goto err;
757 if (!field_sqr(group, &r->X, n1, ctx))
758 goto err;
759 if (!BN_mod_sub_quick(&r->X, &r->X, n0, p))
760 goto err;
761 /* X_r = n1^2 - 2 * n2 */
762
763 /* n3 */
764 if (!field_sqr(group, n0, n3, ctx))
765 goto err;
766 if (!BN_mod_lshift_quick(n3, n0, 3, p))
767 goto err;
768 /* n3 = 8 * Y_a^4 */
769
770 /* Y_r */
771 if (!BN_mod_sub_quick(n0, n2, &r->X, p))
772 goto err;
773 if (!field_mul(group, n0, n1, n0, ctx))
774 goto err;
775 if (!BN_mod_sub_quick(&r->Y, n0, n3, p))
776 goto err;
777 /* Y_r = n1 * (n2 - X_r) - n3 */
778
779 ret = 1;
780
781 err:
782 BN_CTX_end(ctx);
783
784 return ret;
785}
786
787int
788ec_GFp_simple_invert(const EC_GROUP *group, EC_POINT *point, BN_CTX *ctx)
789{
790 if (EC_POINT_is_at_infinity(group, point) > 0 || BN_is_zero(&point->Y))
791 /* point is its own inverse */
792 return 1;
793
794 return BN_usub(&point->Y, &group->field, &point->Y);
795}
796
797int
798ec_GFp_simple_is_at_infinity(const EC_GROUP *group, const EC_POINT *point)
799{
800 return BN_is_zero(&point->Z);
801}
802
803int
804ec_GFp_simple_is_on_curve(const EC_GROUP *group, const EC_POINT *point, BN_CTX *ctx)
805{
806 int (*field_mul) (const EC_GROUP *, BIGNUM *, const BIGNUM *, const BIGNUM *, BN_CTX *);
807 int (*field_sqr) (const EC_GROUP *, BIGNUM *, const BIGNUM *, BN_CTX *);
808 const BIGNUM *p;
809 BIGNUM *rh, *tmp, *Z4, *Z6;
810 int ret = -1;
811
812 if (EC_POINT_is_at_infinity(group, point) > 0)
813 return 1;
814
815 field_mul = group->meth->field_mul;
816 field_sqr = group->meth->field_sqr;
817 p = &group->field;
818
819 BN_CTX_start(ctx);
820
821 if ((rh = BN_CTX_get(ctx)) == NULL((void *)0))
822 goto err;
823 if ((tmp = BN_CTX_get(ctx)) == NULL((void *)0))
824 goto err;
825 if ((Z4 = BN_CTX_get(ctx)) == NULL((void *)0))
826 goto err;
827 if ((Z6 = BN_CTX_get(ctx)) == NULL((void *)0))
828 goto err;
829
830 /*
831 * We have a curve defined by a Weierstrass equation y^2 = x^3 + a*x
832 * + b. The point to consider is given in Jacobian projective
833 * coordinates where (X, Y, Z) represents (x, y) = (X/Z^2, Y/Z^3).
834 * Substituting this and multiplying by Z^6 transforms the above
835 * equation into Y^2 = X^3 + a*X*Z^4 + b*Z^6. To test this, we add up
836 * the right-hand side in 'rh'.
837 */
838
839 /* rh := X^2 */
840 if (!field_sqr(group, rh, &point->X, ctx))
841 goto err;
842
843 if (!point->Z_is_one) {
844 if (!field_sqr(group, tmp, &point->Z, ctx))
845 goto err;
846 if (!field_sqr(group, Z4, tmp, ctx))
847 goto err;
848 if (!field_mul(group, Z6, Z4, tmp, ctx))
849 goto err;
850
851 /* rh := (rh + a*Z^4)*X */
852 if (group->a_is_minus3) {
853 if (!BN_mod_lshift1_quick(tmp, Z4, p))
854 goto err;
855 if (!BN_mod_add_quick(tmp, tmp, Z4, p))
856 goto err;
857 if (!BN_mod_sub_quick(rh, rh, tmp, p))
858 goto err;
859 if (!field_mul(group, rh, rh, &point->X, ctx))
860 goto err;
861 } else {
862 if (!field_mul(group, tmp, Z4, &group->a, ctx))
863 goto err;
864 if (!BN_mod_add_quick(rh, rh, tmp, p))
865 goto err;
866 if (!field_mul(group, rh, rh, &point->X, ctx))
867 goto err;
868 }
869
870 /* rh := rh + b*Z^6 */
871 if (!field_mul(group, tmp, &group->b, Z6, ctx))
872 goto err;
873 if (!BN_mod_add_quick(rh, rh, tmp, p))
874 goto err;
875 } else {
876 /* point->Z_is_one */
877
878 /* rh := (rh + a)*X */
879 if (!BN_mod_add_quick(rh, rh, &group->a, p))
880 goto err;
881 if (!field_mul(group, rh, rh, &point->X, ctx))
882 goto err;
883 /* rh := rh + b */
884 if (!BN_mod_add_quick(rh, rh, &group->b, p))
885 goto err;
886 }
887
888 /* 'lh' := Y^2 */
889 if (!field_sqr(group, tmp, &point->Y, ctx))
890 goto err;
891
892 ret = (0 == BN_ucmp(tmp, rh));
893
894 err:
895 BN_CTX_end(ctx);
896
897 return ret;
898}
899
900int
901ec_GFp_simple_cmp(const EC_GROUP *group, const EC_POINT *a, const EC_POINT *b, BN_CTX *ctx)
902{
903 /*
904 * return values: -1 error 0 equal (in affine coordinates) 1
905 * not equal
906 */
907
908 int (*field_mul) (const EC_GROUP *, BIGNUM *, const BIGNUM *, const BIGNUM *, BN_CTX *);
909 int (*field_sqr) (const EC_GROUP *, BIGNUM *, const BIGNUM *, BN_CTX *);
910 BIGNUM *tmp1, *tmp2, *Za23, *Zb23;
911 const BIGNUM *tmp1_, *tmp2_;
912 int ret = -1;
913
914 if (EC_POINT_is_at_infinity(group, a) > 0)
915 return EC_POINT_is_at_infinity(group, b) > 0 ? 0 : 1;
916
917 if (EC_POINT_is_at_infinity(group, b) > 0)
918 return 1;
919
920 if (a->Z_is_one && b->Z_is_one)
921 return ((BN_cmp(&a->X, &b->X) == 0) && BN_cmp(&a->Y, &b->Y) == 0) ? 0 : 1;
922
923 field_mul = group->meth->field_mul;
924 field_sqr = group->meth->field_sqr;
925
926 BN_CTX_start(ctx);
927
928 if ((tmp1 = BN_CTX_get(ctx)) == NULL((void *)0))
929 goto end;
930 if ((tmp2 = BN_CTX_get(ctx)) == NULL((void *)0))
931 goto end;
932 if ((Za23 = BN_CTX_get(ctx)) == NULL((void *)0))
933 goto end;
934 if ((Zb23 = BN_CTX_get(ctx)) == NULL((void *)0))
935 goto end;
936
937 /*
938 * We have to decide whether (X_a/Z_a^2, Y_a/Z_a^3) = (X_b/Z_b^2,
939 * Y_b/Z_b^3), or equivalently, whether (X_a*Z_b^2, Y_a*Z_b^3) =
940 * (X_b*Z_a^2, Y_b*Z_a^3).
941 */
942
943 if (!b->Z_is_one) {
944 if (!field_sqr(group, Zb23, &b->Z, ctx))
945 goto end;
946 if (!field_mul(group, tmp1, &a->X, Zb23, ctx))
947 goto end;
948 tmp1_ = tmp1;
949 } else
950 tmp1_ = &a->X;
951 if (!a->Z_is_one) {
952 if (!field_sqr(group, Za23, &a->Z, ctx))
953 goto end;
954 if (!field_mul(group, tmp2, &b->X, Za23, ctx))
955 goto end;
956 tmp2_ = tmp2;
957 } else
958 tmp2_ = &b->X;
959
960 /* compare X_a*Z_b^2 with X_b*Z_a^2 */
961 if (BN_cmp(tmp1_, tmp2_) != 0) {
962 ret = 1; /* points differ */
963 goto end;
964 }
965 if (!b->Z_is_one) {
966 if (!field_mul(group, Zb23, Zb23, &b->Z, ctx))
967 goto end;
968 if (!field_mul(group, tmp1, &a->Y, Zb23, ctx))
969 goto end;
970 /* tmp1_ = tmp1 */
971 } else
972 tmp1_ = &a->Y;
973 if (!a->Z_is_one) {
974 if (!field_mul(group, Za23, Za23, &a->Z, ctx))
975 goto end;
976 if (!field_mul(group, tmp2, &b->Y, Za23, ctx))
977 goto end;
978 /* tmp2_ = tmp2 */
979 } else
980 tmp2_ = &b->Y;
981
982 /* compare Y_a*Z_b^3 with Y_b*Z_a^3 */
983 if (BN_cmp(tmp1_, tmp2_) != 0) {
984 ret = 1; /* points differ */
985 goto end;
986 }
987 /* points are equal */
988 ret = 0;
989
990 end:
991 BN_CTX_end(ctx);
992
993 return ret;
994}
995
996int
997ec_GFp_simple_make_affine(const EC_GROUP *group, EC_POINT *point, BN_CTX *ctx)
998{
999 BIGNUM *x, *y;
1000 int ret = 0;
1001
1002 if (point->Z_is_one || EC_POINT_is_at_infinity(group, point) > 0)
1003 return 1;
1004
1005 BN_CTX_start(ctx);
1006
1007 if ((x = BN_CTX_get(ctx)) == NULL((void *)0))
1008 goto err;
1009 if ((y = BN_CTX_get(ctx)) == NULL((void *)0))
1010 goto err;
1011
1012 if (!EC_POINT_get_affine_coordinates(group, point, x, y, ctx))
1013 goto err;
1014 if (!EC_POINT_set_affine_coordinates(group, point, x, y, ctx))
1015 goto err;
1016 if (!point->Z_is_one) {
1017 ECerror(ERR_R_INTERNAL_ERROR)ERR_put_error(16,(0xfff),((4|64)),"/usr/src/lib/libcrypto/ec/ecp_smpl.c"
,1017);
1018 goto err;
1019 }
1020 ret = 1;
1021
1022 err:
1023 BN_CTX_end(ctx);
1024
1025 return ret;
1026}
1027
1028int
1029ec_GFp_simple_points_make_affine(const EC_GROUP *group, size_t num, EC_POINT *points[], BN_CTX *ctx)
1030{
1031 BIGNUM *tmp0, *tmp1;
1032 size_t pow2 = 0;
1033 BIGNUM **heap = NULL((void *)0);
1034 size_t i;
1035 int ret = 0;
1036
1037 if (num == 0)
1
Assuming 'num' is not equal to 0
→
2
←
Taking false branch
→
1038 return 1;
1039
1040 BN_CTX_start(ctx);
1041
1042 if ((tmp0 = BN_CTX_get(ctx)) == NULL((void *)0))
3
←
Assuming the condition is false
→
4
←
Taking false branch
→
1043 goto err;
1044 if ((tmp1 = BN_CTX_get(ctx)) == NULL((void *)0))
5
←
Assuming the condition is false
→
6
←
Taking false branch
→
1045 goto err;
1046
1047 /*
1048 * Before converting the individual points, compute inverses of all Z
1049 * values. Modular inversion is rather slow, but luckily we can do
1050 * with a single explicit inversion, plus about 3 multiplications per
1051 * input value.
1052 */
1053
1054 pow2 = 1;
1055 while (num > pow2)
7
←
Assuming 'num' is > 'pow2'
→
8
←
Loop condition is true. Entering loop body
→
9
←
Assuming 'num' is <= 'pow2'
→
10
←
Loop condition is false. Execution continues on line 1061
→
1056 pow2 <<= 1;
1057 /*
1058 * Now pow2 is the smallest power of 2 satifsying pow2 >= num. We
1059 * need twice that.
1060 */
1061 pow2 <<= 1;
1062
1063 heap = reallocarray(NULL((void *)0), pow2, sizeof heap[0]);
1064 if (heap == NULL((void *)0))
11
←
Assuming 'heap' is not equal to NULL
→
12
←
Taking false branch
→
1065 goto err;
1066
1067 /*
1068 * The array is used as a binary tree, exactly as in heapsort:
1069 *
1070 * heap[1] heap[2] heap[3] heap[4] heap[5]
1071 * heap[6] heap[7] heap[8]heap[9] heap[10]heap[11]
1072 * heap[12]heap[13] heap[14] heap[15]
1073 *
1074 * We put the Z's in the last line; then we set each other node to the
1075 * product of its two child-nodes (where empty or 0 entries are
1076 * treated as ones); then we invert heap[1]; then we invert each
1077 * other node by replacing it by the product of its parent (after
1078 * inversion) and its sibling (before inversion).
1079 */
1080 heap[0] = NULL((void *)0);
1081 for (i = pow2 / 2 - 1; i > 0; i--)
13
←
Loop condition is true. Entering loop body
→
14
←
Loop condition is false. Execution continues on line 1083
→
1082 heap[i] = NULL((void *)0);
1083 for (i = 0; i < num; i++)
15
←
Loop condition is true. Entering loop body
→
16
←
Loop condition is true. Entering loop body
→
17
←
Loop condition is false. Execution continues on line 1085
→
1084 heap[pow2 / 2 + i] = &points[i]->Z;
1085 for (i = pow2 / 2 + num; i < pow2; i++)
18
←
Loop condition is false. Execution continues on line 1089
→
1086 heap[i] = NULL((void *)0);
1087
1088 /* set each node to the product of its children */
1089 for (i = pow2 / 2 - 1; i > 0; i--) {
19
←
Loop condition is true. Entering loop body
→
24
←
Loop condition is false. Execution continues on line 1112
→
1090 heap[i] = BN_new();
1091 if (heap[i] == NULL((void *)0))
20
←
Assuming the condition is false
→
21
←
Taking false branch
→
1092 goto err;
1093
1094 if (heap[2 * i] != NULL((void *)0)) {
22
←
Assuming pointer value is null
→
23
←
Taking false branch
→
1095 if ((heap[2 * i + 1] == NULL((void *)0)) || BN_is_zero(heap[2 * i + 1])) {
1096 if (!bn_copy(heap[i], heap[2 * i]))
1097 goto err;
1098 } else {
1099 if (BN_is_zero(heap[2 * i])) {
1100 if (!bn_copy(heap[i], heap[2 * i + 1]))
1101 goto err;
1102 } else {
1103 if (!group->meth->field_mul(group, heap[i],
1104 heap[2 * i], heap[2 * i + 1], ctx))
1105 goto err;
1106 }
1107 }
1108 }
1109 }
1110
1111 /* invert heap[1] */
1112 if (!BN_is_zero(heap[1])) {
25
←
Assuming the condition is false
→
26
←
Taking false branch
→
1113 if (BN_mod_inverse_ct(heap[1], heap[1], &group->field, ctx) == NULL((void *)0)) {
1114 ECerror(ERR_R_BN_LIB)ERR_put_error(16,(0xfff),(3),"/usr/src/lib/libcrypto/ec/ecp_smpl.c"
,1114);
1115 goto err;
1116 }
1117 }
1118 if (group->meth->field_encode != NULL((void *)0)) {
27
←
Assuming field 'field_encode' is equal to NULL
→
28
←
Taking false branch
→
1119 /*
1120 * in the Montgomery case, we just turned R*H (representing
1121 * H) into 1/(R*H), but we need R*(1/H) (representing
1122 * 1/H); i.e. we have need to multiply by the Montgomery
1123 * factor twice
1124 */
1125 if (!group->meth->field_encode(group, heap[1], heap[1], ctx))
1126 goto err;
1127 if (!group->meth->field_encode(group, heap[1], heap[1], ctx))
1128 goto err;
1129 }
1130 /* set other heap[i]'s to their inverses */
1131 for (i = 2; i < pow2 / 2 + num; i += 2) {
32
←
Loop condition is false. Execution continues on line 1152
→
1132 /* i is even */
1133 if ((heap[i + 1] != NULL((void *)0)) && !BN_is_zero(heap[i + 1])) {
29
←
Assuming the condition is false
→
1134 if (!group->meth->field_mul(group, tmp0, heap[i / 2], heap[i + 1], ctx))
1135 goto err;
1136 if (!group->meth->field_mul(group, tmp1, heap[i / 2], heap[i], ctx))
1137 goto err;
1138 if (!bn_copy(heap[i], tmp0))
1139 goto err;
1140 if (!bn_copy(heap[i + 1], tmp1))
1141 goto err;
1142 } else {
1143 if (!bn_copy(heap[i], heap[i / 2]))
30
←
Assuming the condition is false
→
31
←
Taking false branch
→
1144 goto err;
1145 }
1146 }
1147
1148 /*
1149 * we have replaced all non-zero Z's by their inverses, now fix up
1150 * all the points
1151 */
1152 for (i = 0; i < num; i++) {
33
←
The value 0 is assigned to 'i'
→
34
←
Loop condition is true. Entering loop body
→
1153 EC_POINT *p = points[i];
35
←
'p' initialized to a null pointer value
→
1154
1155 if (!BN_is_zero(&p->Z)) {
36
←
Assuming the condition is true
→
37
←
Taking true branch
→
1156 /* turn (X, Y, 1/Z) into (X/Z^2, Y/Z^3, 1) */
1157
1158 if (!group->meth->field_sqr(group, tmp1, &p->Z, ctx))
38
←
Assuming the condition is false
→
39
←
Taking false branch
→
1159 goto err;
1160 if (!group->meth->field_mul(group, &p->X, &p->X, tmp1, ctx))
40
←
Assuming the condition is false
→
41
←
Taking false branch
→
1161 goto err;
1162
1163 if (!group->meth->field_mul(group, tmp1, tmp1, &p->Z, ctx))
42
←
Assuming the condition is false
→
43
←
Taking false branch
→
1164 goto err;
1165 if (!group->meth->field_mul(group, &p->Y, &p->Y, tmp1, ctx))
44
←
Assuming the condition is false
→
45
←
Taking false branch
→
1166 goto err;
1167
1168 if (group->meth->field_set_to_one != NULL((void *)0)) {
46
←
Assuming field 'field_set_to_one' is equal to NULL
→
47
←
Taking false branch
→
1169 if (!group->meth->field_set_to_one(group, &p->Z, ctx))
1170 goto err;
1171 } else {
1172 if (!BN_one(&p->Z))
48
←
Assuming the condition is false
→
49
←
Taking false branch
→
1173 goto err;
1174 }
1175 p->Z_is_one = 1;
50
←
Access to field 'Z_is_one' results in a dereference of a null pointer (loaded from variable 'p')
1176 }
1177 }
1178
1179 ret = 1;
1180
1181 err:
1182 BN_CTX_end(ctx);
1183
1184 if (heap != NULL((void *)0)) {
1185 /*
1186 * heap[pow2/2] .. heap[pow2-1] have not been allocated
1187 * locally!
1188 */
1189 for (i = pow2 / 2 - 1; i > 0; i--) {
1190 BN_free(heap[i]);
1191 }
1192 free(heap);
1193 }
1194 return ret;
1195}
1196
1197int
1198ec_GFp_simple_field_mul(const EC_GROUP *group, BIGNUM *r, const BIGNUM *a, const BIGNUM *b, BN_CTX *ctx)
1199{
1200 return BN_mod_mul(r, a, b, &group->field, ctx);
1201}
1202
1203int
1204ec_GFp_simple_field_sqr(const EC_GROUP *group, BIGNUM *r, const BIGNUM *a, BN_CTX *ctx)
1205{
1206 return BN_mod_sqr(r, a, &group->field, ctx);
1207}
1208
1209/*
1210 * Apply randomization of EC point projective coordinates:
1211 *
1212 * (X, Y, Z) = (lambda^2 * X, lambda^3 * Y, lambda * Z)
1213 *
1214 * where lambda is in the interval [1, group->field).
1215 */
1216int
1217ec_GFp_simple_blind_coordinates(const EC_GROUP *group, EC_POINT *p, BN_CTX *ctx)
1218{
1219 BIGNUM *lambda = NULL((void *)0);
1220 BIGNUM *tmp = NULL((void *)0);
1221 int ret = 0;
1222
1223 BN_CTX_start(ctx);
1224 if ((lambda = BN_CTX_get(ctx)) == NULL((void *)0))
1225 goto err;
1226 if ((tmp = BN_CTX_get(ctx)) == NULL((void *)0))
1227 goto err;
1228
1229 /* Generate lambda in [1, group->field). */
1230 if (!bn_rand_interval(lambda, 1, &group->field))
1231 goto err;
1232
1233 if (group->meth->field_encode != NULL((void *)0) &&
1234 !group->meth->field_encode(group, lambda, lambda, ctx))
1235 goto err;
1236
1237 /* Z = lambda * Z */
1238 if (!group->meth->field_mul(group, &p->Z, lambda, &p->Z, ctx))
1239 goto err;
1240
1241 /* tmp = lambda^2 */
1242 if (!group->meth->field_sqr(group, tmp, lambda, ctx))
1243 goto err;
1244
1245 /* X = lambda^2 * X */
1246 if (!group->meth->field_mul(group, &p->X, tmp, &p->X, ctx))
1247 goto err;
1248
1249 /* tmp = lambda^3 */
1250 if (!group->meth->field_mul(group, tmp, tmp, lambda, ctx))
1251 goto err;
1252
1253 /* Y = lambda^3 * Y */
1254 if (!group->meth->field_mul(group, &p->Y, tmp, &p->Y, ctx))
1255 goto err;
1256
1257 /* Disable optimized arithmetics after replacing Z by lambda * Z. */
1258 p->Z_is_one = 0;
1259
1260 ret = 1;
1261
1262 err:
1263 BN_CTX_end(ctx);
1264 return ret;
1265}
1266
1267#define EC_POINT_BN_set_flags(P, flags) do { \
1268 BN_set_flags(&(P)->X, (flags)); \
1269 BN_set_flags(&(P)->Y, (flags)); \
1270 BN_set_flags(&(P)->Z, (flags)); \
1271} while(0)
1272
1273#define EC_POINT_CSWAP(c, a, b, w, t) do { \
1274 if (!BN_swap_ct(c, &(a)->X, &(b)->X, w) || \
1275 !BN_swap_ct(c, &(a)->Y, &(b)->Y, w) || \
1276 !BN_swap_ct(c, &(a)->Z, &(b)->Z, w)) \
1277 goto err; \
1278 t = ((a)->Z_is_one ^ (b)->Z_is_one) & (c); \
1279 (a)->Z_is_one ^= (t); \
1280 (b)->Z_is_one ^= (t); \
1281} while(0)
1282
1283/*
1284 * This function computes (in constant time) a point multiplication over the
1285 * EC group.
1286 *
1287 * At a high level, it is Montgomery ladder with conditional swaps.
1288 *
1289 * It performs either a fixed point multiplication
1290 * (scalar * generator)
1291 * when point is NULL, or a variable point multiplication
1292 * (scalar * point)
1293 * when point is not NULL.
1294 *
1295 * scalar should be in the range [0,n) otherwise all constant time bets are off.
1296 *
1297 * NB: This says nothing about EC_POINT_add and EC_POINT_dbl,
1298 * which of course are not constant time themselves.
1299 *
1300 * The product is stored in r.
1301 *
1302 * Returns 1 on success, 0 otherwise.
1303 */
1304static int
1305ec_GFp_simple_mul_ct(const EC_GROUP *group, EC_POINT *r, const BIGNUM *scalar,
1306 const EC_POINT *point, BN_CTX *ctx)
1307{
1308 int i, cardinality_bits, group_top, kbit, pbit, Z_is_one;
1309 EC_POINT *s = NULL((void *)0);
1310 BIGNUM *k = NULL((void *)0);
1311 BIGNUM *lambda = NULL((void *)0);
1312 BIGNUM *cardinality = NULL((void *)0);
1313 int ret = 0;
1314
1315 BN_CTX_start(ctx);
1316
1317 if ((s = EC_POINT_new(group)) == NULL((void *)0))
1318 goto err;
1319
1320 if (point == NULL((void *)0)) {
1321 if (!EC_POINT_copy(s, group->generator))
1322 goto err;
1323 } else {
1324 if (!EC_POINT_copy(s, point))
1325 goto err;
1326 }
1327
1328 EC_POINT_BN_set_flags(s, BN_FLG_CONSTTIME0x04);
1329
1330 if ((cardinality = BN_CTX_get(ctx)) == NULL((void *)0))
1331 goto err;
1332 if ((lambda = BN_CTX_get(ctx)) == NULL((void *)0))
1333 goto err;
1334 if ((k = BN_CTX_get(ctx)) == NULL((void *)0))
1335 goto err;
1336 if (!BN_mul(cardinality, &group->order, &group->cofactor, ctx))
1337 goto err;
1338
1339 /*
1340 * Group cardinalities are often on a word boundary.
1341 * So when we pad the scalar, some timing diff might
1342 * pop if it needs to be expanded due to carries.
1343 * So expand ahead of time.
1344 */
1345 cardinality_bits = BN_num_bits(cardinality);
1346 group_top = cardinality->top;
1347 if (!bn_wexpand(k, group_top + 2) ||
1348 !bn_wexpand(lambda, group_top + 2))
1349 goto err;
1350
1351 if (!bn_copy(k, scalar))
1352 goto err;
1353
1354 BN_set_flags(k, BN_FLG_CONSTTIME0x04);
1355
1356 if (BN_num_bits(k) > cardinality_bits || BN_is_negative(k)) {
1357 /*
1358 * This is an unusual input, and we don't guarantee
1359 * constant-timeness
1360 */
1361 if (!BN_nnmod(k, k, cardinality, ctx))
1362 goto err;
1363 }
1364
1365 if (!BN_add(lambda, k, cardinality))
1366 goto err;
1367 BN_set_flags(lambda, BN_FLG_CONSTTIME0x04);
1368 if (!BN_add(k, lambda, cardinality))
1369 goto err;
1370 /*
1371 * lambda := scalar + cardinality
1372 * k := scalar + 2*cardinality
1373 */
1374 kbit = BN_is_bit_set(lambda, cardinality_bits);
1375 if (!BN_swap_ct(kbit, k, lambda, group_top + 2))
1376 goto err;
1377
1378 group_top = group->field.top;
1379 if (!bn_wexpand(&s->X, group_top) ||
1380 !bn_wexpand(&s->Y, group_top) ||
1381 !bn_wexpand(&s->Z, group_top) ||
1382 !bn_wexpand(&r->X, group_top) ||
1383 !bn_wexpand(&r->Y, group_top) ||
1384 !bn_wexpand(&r->Z, group_top))
1385 goto err;
1386
1387 /*
1388 * Apply coordinate blinding for EC_POINT if the underlying EC_METHOD
1389 * implements it.
1390 */
1391 if (!ec_point_blind_coordinates(group, s, ctx))
1392 goto err;
1393
1394 /* top bit is a 1, in a fixed pos */
1395 if (!EC_POINT_copy(r, s))
1396 goto err;
1397
1398 EC_POINT_BN_set_flags(r, BN_FLG_CONSTTIME0x04);
1399
1400 if (!EC_POINT_dbl(group, s, s, ctx))
1401 goto err;
1402
1403 pbit = 0;
1404
1405 /*
1406 * The ladder step, with branches, is
1407 *
1408 * k[i] == 0: S = add(R, S), R = dbl(R)
1409 * k[i] == 1: R = add(S, R), S = dbl(S)
1410 *
1411 * Swapping R, S conditionally on k[i] leaves you with state
1412 *
1413 * k[i] == 0: T, U = R, S
1414 * k[i] == 1: T, U = S, R
1415 *
1416 * Then perform the ECC ops.
1417 *
1418 * U = add(T, U)
1419 * T = dbl(T)
1420 *
1421 * Which leaves you with state
1422 *
1423 * k[i] == 0: U = add(R, S), T = dbl(R)
1424 * k[i] == 1: U = add(S, R), T = dbl(S)
1425 *
1426 * Swapping T, U conditionally on k[i] leaves you with state
1427 *
1428 * k[i] == 0: R, S = T, U
1429 * k[i] == 1: R, S = U, T
1430 *
1431 * Which leaves you with state
1432 *
1433 * k[i] == 0: S = add(R, S), R = dbl(R)
1434 * k[i] == 1: R = add(S, R), S = dbl(S)
1435 *
1436 * So we get the same logic, but instead of a branch it's a
1437 * conditional swap, followed by ECC ops, then another conditional swap.
1438 *
1439 * Optimization: The end of iteration i and start of i-1 looks like
1440 *
1441 * ...
1442 * CSWAP(k[i], R, S)
1443 * ECC
1444 * CSWAP(k[i], R, S)
1445 * (next iteration)
1446 * CSWAP(k[i-1], R, S)
1447 * ECC
1448 * CSWAP(k[i-1], R, S)
1449 * ...
1450 *
1451 * So instead of two contiguous swaps, you can merge the condition
1452 * bits and do a single swap.
1453 *
1454 * k[i] k[i-1] Outcome
1455 * 0 0 No Swap
1456 * 0 1 Swap
1457 * 1 0 Swap
1458 * 1 1 No Swap
1459 *
1460 * This is XOR. pbit tracks the previous bit of k.
1461 */
1462
1463 for (i = cardinality_bits - 1; i >= 0; i--) {
1464 kbit = BN_is_bit_set(k, i) ^ pbit;
1465 EC_POINT_CSWAP(kbit, r, s, group_top, Z_is_one);
1466 if (!EC_POINT_add(group, s, r, s, ctx))
1467 goto err;
1468 if (!EC_POINT_dbl(group, r, r, ctx))
1469 goto err;
1470 /*
1471 * pbit logic merges this cswap with that of the
1472 * next iteration
1473 */
1474 pbit ^= kbit;
1475 }
1476 /* one final cswap to move the right value into r */
1477 EC_POINT_CSWAP(pbit, r, s, group_top, Z_is_one);
1478
1479 ret = 1;
1480
1481 err:
1482 EC_POINT_free(s);
1483 BN_CTX_end(ctx);
1484
1485 return ret;
1486}
1487
1488#undef EC_POINT_BN_set_flags
1489#undef EC_POINT_CSWAP
1490
1491int
1492ec_GFp_simple_mul_generator_ct(const EC_GROUP *group, EC_POINT *r,
1493 const BIGNUM *scalar, BN_CTX *ctx)
1494{
1495 return ec_GFp_simple_mul_ct(group, r, scalar, NULL((void *)0), ctx);
1496}
1497
1498int
1499ec_GFp_simple_mul_single_ct(const EC_GROUP *group, EC_POINT *r,
1500 const BIGNUM *scalar, const EC_POINT *point, BN_CTX *ctx)
1501{
1502 return ec_GFp_simple_mul_ct(group, r, scalar, point, ctx);
1503}
1504
1505int
1506ec_GFp_simple_mul_double_nonct(const EC_GROUP *group, EC_POINT *r,
1507 const BIGNUM *g_scalar, const BIGNUM *p_scalar, const EC_POINT *point,
1508 BN_CTX *ctx)
1509{
1510 return ec_wNAF_mul(group, r, g_scalar, 1, &point, &p_scalar, ctx);
1511}
1512
1513static const EC_METHOD ec_GFp_simple_method = {
1514 .field_type = NID_X9_62_prime_field406,
1515 .group_init = ec_GFp_simple_group_init,
1516 .group_finish = ec_GFp_simple_group_finish,
1517 .group_copy = ec_GFp_simple_group_copy,
1518 .group_set_curve = ec_GFp_simple_group_set_curve,
1519 .group_get_curve = ec_GFp_simple_group_get_curve,
1520 .group_get_degree = ec_GFp_simple_group_get_degree,
1521 .group_order_bits = ec_group_simple_order_bits,
1522 .group_check_discriminant = ec_GFp_simple_group_check_discriminant,
1523 .point_init = ec_GFp_simple_point_init,
1524 .point_finish = ec_GFp_simple_point_finish,
1525 .point_copy = ec_GFp_simple_point_copy,
1526 .point_set_to_infinity = ec_GFp_simple_point_set_to_infinity,
1527 .point_set_Jprojective_coordinates =
1528 ec_GFp_simple_set_Jprojective_coordinates,
1529 .point_get_Jprojective_coordinates =
1530 ec_GFp_simple_get_Jprojective_coordinates,
1531 .point_set_affine_coordinates =
1532 ec_GFp_simple_point_set_affine_coordinates,
1533 .point_get_affine_coordinates =
1534 ec_GFp_simple_point_get_affine_coordinates,
1535 .point_set_compressed_coordinates =
1536 ec_GFp_simple_set_compressed_coordinates,
1537 .point2oct = ec_GFp_simple_point2oct,
1538 .oct2point = ec_GFp_simple_oct2point,
1539 .add = ec_GFp_simple_add,
1540 .dbl = ec_GFp_simple_dbl,
1541 .invert = ec_GFp_simple_invert,
1542 .is_at_infinity = ec_GFp_simple_is_at_infinity,
1543 .is_on_curve = ec_GFp_simple_is_on_curve,
1544 .point_cmp = ec_GFp_simple_cmp,
1545 .make_affine = ec_GFp_simple_make_affine,
1546 .points_make_affine = ec_GFp_simple_points_make_affine,
1547 .mul_generator_ct = ec_GFp_simple_mul_generator_ct,
1548 .mul_single_ct = ec_GFp_simple_mul_single_ct,
1549 .mul_double_nonct = ec_GFp_simple_mul_double_nonct,
1550 .field_mul = ec_GFp_simple_field_mul,
1551 .field_sqr = ec_GFp_simple_field_sqr,
1552 .blind_coordinates = ec_GFp_simple_blind_coordinates,
1553};
1554
1555const EC_METHOD *
1556EC_GFp_simple_method(void)
1557{
1558 return &ec_GFp_simple_method;
1559}
1560LCRYPTO_ALIAS(EC_GFp_simple_method)asm("");