Coverage Report

Created: 2024-11-21 07:03

/src/boringssl/crypto/fipsmodule/ec/wnaf.c.inc
Line
Count
Source (jump to first uncovered line)
1
/* Originally written by Bodo Moeller for the OpenSSL project.
2
 * ====================================================================
3
 * Copyright (c) 1998-2005 The OpenSSL Project.  All rights reserved.
4
 *
5
 * Redistribution and use in source and binary forms, with or without
6
 * modification, are permitted provided that the following conditions
7
 * are met:
8
 *
9
 * 1. Redistributions of source code must retain the above copyright
10
 *    notice, this list of conditions and the following disclaimer.
11
 *
12
 * 2. Redistributions in binary form must reproduce the above copyright
13
 *    notice, this list of conditions and the following disclaimer in
14
 *    the documentation and/or other materials provided with the
15
 *    distribution.
16
 *
17
 * 3. All advertising materials mentioning features or use of this
18
 *    software must display the following acknowledgment:
19
 *    "This product includes software developed by the OpenSSL Project
20
 *    for use in the OpenSSL Toolkit. (http://www.openssl.org/)"
21
 *
22
 * 4. The names "OpenSSL Toolkit" and "OpenSSL Project" must not be used to
23
 *    endorse or promote products derived from this software without
24
 *    prior written permission. For written permission, please contact
25
 *    openssl-core@openssl.org.
26
 *
27
 * 5. Products derived from this software may not be called "OpenSSL"
28
 *    nor may "OpenSSL" appear in their names without prior written
29
 *    permission of the OpenSSL Project.
30
 *
31
 * 6. Redistributions of any form whatsoever must retain the following
32
 *    acknowledgment:
33
 *    "This product includes software developed by the OpenSSL Project
34
 *    for use in the OpenSSL Toolkit (http://www.openssl.org/)"
35
 *
36
 * THIS SOFTWARE IS PROVIDED BY THE OpenSSL PROJECT ``AS IS'' AND ANY
37
 * EXPRESSED OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
38
 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
39
 * PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL THE OpenSSL PROJECT OR
40
 * ITS CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
41
 * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
42
 * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
43
 * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
44
 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT,
45
 * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
46
 * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED
47
 * OF THE POSSIBILITY OF SUCH DAMAGE.
48
 * ====================================================================
49
 *
50
 * This product includes cryptographic software written by Eric Young
51
 * (eay@cryptsoft.com).  This product includes software written by Tim
52
 * Hudson (tjh@cryptsoft.com).
53
 *
54
 */
55
/* ====================================================================
56
 * Copyright 2002 Sun Microsystems, Inc. ALL RIGHTS RESERVED.
57
 *
58
 * Portions of the attached software ("Contribution") are developed by
59
 * SUN MICROSYSTEMS, INC., and are contributed to the OpenSSL project.
60
 *
61
 * The Contribution is licensed pursuant to the OpenSSL open source
62
 * license provided above.
63
 *
64
 * The elliptic curve binary polynomial software is originally written by
65
 * Sheueling Chang Shantz and Douglas Stebila of Sun Microsystems
66
 * Laboratories. */
67
68
#include <openssl/ec.h>
69
70
#include <assert.h>
71
#include <string.h>
72
73
#include <openssl/bn.h>
74
#include <openssl/err.h>
75
#include <openssl/mem.h>
76
#include <openssl/thread.h>
77
78
#include "internal.h"
79
#include "../bn/internal.h"
80
#include "../../internal.h"
81
82
83
// This file implements the wNAF-based interleaving multi-exponentiation method
84
// at:
85
//   http://link.springer.com/chapter/10.1007%2F3-540-45537-X_13
86
//   http://www.bmoeller.de/pdf/TI-01-08.multiexp.pdf
87
88
void ec_compute_wNAF(const EC_GROUP *group, int8_t *out,
89
8
                     const EC_SCALAR *scalar, size_t bits, int w) {
90
  // 'int8_t' can represent integers with absolute values less than 2^7.
91
8
  assert(0 < w && w <= 7);
92
8
  assert(bits != 0);
93
8
  int bit = 1 << w;         // 2^w, at most 128
94
8
  int next_bit = bit << 1;  // 2^(w+1), at most 256
95
8
  int mask = next_bit - 1;  // at most 255
96
97
8
  int window_val = scalar->words[0] & mask;
98
3.63k
  for (size_t j = 0; j < bits + 1; j++) {
99
3.62k
    assert(0 <= window_val && window_val <= next_bit);
100
3.62k
    int digit = 0;
101
3.62k
    if (window_val & 1) {
102
622
      assert(0 < window_val && window_val < next_bit);
103
622
      if (window_val & bit) {
104
302
        digit = window_val - next_bit;
105
        // We know -next_bit < digit < 0 and window_val - digit = next_bit.
106
107
        // modified wNAF
108
302
        if (j + w + 1 >= bits) {
109
          // special case for generating modified wNAFs:
110
          // no new bits will be added into window_val,
111
          // so using a positive digit here will decrease
112
          // the total length of the representation
113
114
1
          digit = window_val & (mask >> 1);
115
          // We know 0 < digit < bit and window_val - digit = bit.
116
1
        }
117
320
      } else {
118
320
        digit = window_val;
119
        // We know 0 < digit < bit and window_val - digit = 0.
120
320
      }
121
122
622
      window_val -= digit;
123
124
      // Now window_val is 0 or 2^(w+1) in standard wNAF generation.
125
      // For modified window NAFs, it may also be 2^w.
126
      //
127
      // See the comments above for the derivation of each of these bounds.
128
622
      assert(window_val == 0 || window_val == next_bit || window_val == bit);
129
622
      assert(-bit < digit && digit < bit);
130
131
      // window_val was odd, so digit is also odd.
132
622
      assert(digit & 1);
133
622
    }
134
135
3.62k
    out[j] = digit;
136
137
    // Incorporate the next bit. Previously, |window_val| <= |next_bit|, so if
138
    // we shift and add at most one copy of |bit|, this will continue to hold
139
    // afterwards.
140
3.62k
    window_val >>= 1;
141
3.62k
    window_val += bit * bn_is_bit_set_words(scalar->words, group->order.N.width,
142
3.62k
                                            j + w + 1);
143
3.62k
    assert(window_val <= next_bit);
144
3.62k
  }
145
146
  // bits + 1 entries should be sufficient to consume all bits.
147
8
  assert(window_val == 0);
148
8
}
149
150
// compute_precomp sets |out[i]| to (2*i+1)*p, for i from 0 to |len|.
151
static void compute_precomp(const EC_GROUP *group, EC_JACOBIAN *out,
152
8
                            const EC_JACOBIAN *p, size_t len) {
153
8
  ec_GFp_simple_point_copy(&out[0], p);
154
8
  EC_JACOBIAN two_p;
155
8
  ec_GFp_mont_dbl(group, &two_p, p);
156
64
  for (size_t i = 1; i < len; i++) {
157
56
    ec_GFp_mont_add(group, &out[i], &out[i - 1], &two_p);
158
56
  }
159
8
}
160
161
static void lookup_precomp(const EC_GROUP *group, EC_JACOBIAN *out,
162
622
                           const EC_JACOBIAN *precomp, int digit) {
163
622
  if (digit < 0) {
164
301
    digit = -digit;
165
301
    ec_GFp_simple_point_copy(out, &precomp[digit >> 1]);
166
301
    ec_GFp_simple_invert(group, out);
167
321
  } else {
168
321
    ec_GFp_simple_point_copy(out, &precomp[digit >> 1]);
169
321
  }
170
622
}
171
172
// EC_WNAF_WINDOW_BITS is the window size to use for |ec_GFp_mont_mul_public|.
173
16
#define EC_WNAF_WINDOW_BITS 4
174
175
// EC_WNAF_TABLE_SIZE is the table size to use for |ec_GFp_mont_mul_public|.
176
8
#define EC_WNAF_TABLE_SIZE (1 << (EC_WNAF_WINDOW_BITS - 1))
177
178
// EC_WNAF_STACK is the number of points worth of data to stack-allocate and
179
// avoid a malloc.
180
4
#define EC_WNAF_STACK 3
181
182
int ec_GFp_mont_mul_public_batch(const EC_GROUP *group, EC_JACOBIAN *r,
183
                                 const EC_SCALAR *g_scalar,
184
                                 const EC_JACOBIAN *points,
185
4
                                 const EC_SCALAR *scalars, size_t num) {
186
4
  size_t bits = EC_GROUP_order_bits(group);
187
4
  size_t wNAF_len = bits + 1;
188
189
4
  int ret = 0;
190
4
  int8_t wNAF_stack[EC_WNAF_STACK][EC_MAX_BYTES * 8 + 1];
191
4
  int8_t (*wNAF_alloc)[EC_MAX_BYTES * 8 + 1] = NULL;
192
4
  int8_t (*wNAF)[EC_MAX_BYTES * 8 + 1];
193
4
  EC_JACOBIAN precomp_stack[EC_WNAF_STACK][EC_WNAF_TABLE_SIZE];
194
4
  EC_JACOBIAN (*precomp_alloc)[EC_WNAF_TABLE_SIZE] = NULL;
195
4
  EC_JACOBIAN (*precomp)[EC_WNAF_TABLE_SIZE];
196
4
  if (num <= EC_WNAF_STACK) {
197
4
    wNAF = wNAF_stack;
198
4
    precomp = precomp_stack;
199
4
  } else {
200
0
    wNAF_alloc = OPENSSL_calloc(num, sizeof(wNAF_alloc[0]));
201
0
    precomp_alloc = OPENSSL_calloc(num, sizeof(precomp_alloc[0]));
202
0
    if (wNAF_alloc == NULL || precomp_alloc == NULL) {
203
0
      goto err;
204
0
    }
205
0
    wNAF = wNAF_alloc;
206
0
    precomp = precomp_alloc;
207
0
  }
208
209
4
  int8_t g_wNAF[EC_MAX_BYTES * 8 + 1];
210
4
  EC_JACOBIAN g_precomp[EC_WNAF_TABLE_SIZE];
211
4
  assert(wNAF_len <= OPENSSL_ARRAY_SIZE(g_wNAF));
212
4
  const EC_JACOBIAN *g = &group->generator.raw;
213
4
  if (g_scalar != NULL) {
214
4
    ec_compute_wNAF(group, g_wNAF, g_scalar, bits, EC_WNAF_WINDOW_BITS);
215
4
    compute_precomp(group, g_precomp, g, EC_WNAF_TABLE_SIZE);
216
4
  }
217
218
8
  for (size_t i = 0; i < num; i++) {
219
4
    assert(wNAF_len <= OPENSSL_ARRAY_SIZE(wNAF[i]));
220
4
    ec_compute_wNAF(group, wNAF[i], &scalars[i], bits, EC_WNAF_WINDOW_BITS);
221
4
    compute_precomp(group, precomp[i], &points[i], EC_WNAF_TABLE_SIZE);
222
4
  }
223
224
4
  EC_JACOBIAN tmp;
225
4
  int r_is_at_infinity = 1;
226
1.81k
  for (size_t k = wNAF_len - 1; k < wNAF_len; k--) {
227
1.81k
    if (!r_is_at_infinity) {
228
1.80k
      ec_GFp_mont_dbl(group, r, r);
229
1.80k
    }
230
231
1.81k
    if (g_scalar != NULL && g_wNAF[k] != 0) {
232
314
      lookup_precomp(group, &tmp, g_precomp, g_wNAF[k]);
233
314
      if (r_is_at_infinity) {
234
2
        ec_GFp_simple_point_copy(r, &tmp);
235
2
        r_is_at_infinity = 0;
236
312
      } else {
237
312
        ec_GFp_mont_add(group, r, r, &tmp);
238
312
      }
239
314
    }
240
241
3.62k
    for (size_t i = 0; i < num; i++) {
242
1.81k
      if (wNAF[i][k] != 0) {
243
308
        lookup_precomp(group, &tmp, precomp[i], wNAF[i][k]);
244
308
        if (r_is_at_infinity) {
245
2
          ec_GFp_simple_point_copy(r, &tmp);
246
2
          r_is_at_infinity = 0;
247
306
        } else {
248
306
          ec_GFp_mont_add(group, r, r, &tmp);
249
306
        }
250
308
      }
251
1.81k
    }
252
1.81k
  }
253
254
4
  if (r_is_at_infinity) {
255
0
    ec_GFp_simple_point_set_to_infinity(group, r);
256
0
  }
257
258
4
  ret = 1;
259
260
4
err:
261
4
  OPENSSL_free(wNAF_alloc);
262
4
  OPENSSL_free(precomp_alloc);
263
4
  return ret;
264
4
}