Coverage Report

Created: 2022-06-23 06:44

/src/botan/src/lib/pubkey/ec_group/point_mul.cpp
Line
Count
Source (jump to first uncovered line)
1
/*
2
* (C) 2015,2018 Jack Lloyd
3
*
4
* Botan is released under the Simplified BSD License (see license.txt)
5
*/
6
7
#include <botan/internal/point_mul.h>
8
#include <botan/rng.h>
9
#include <botan/reducer.h>
10
#include <botan/internal/rounding.h>
11
#include <botan/internal/ct_utils.h>
12
13
namespace Botan {
14
15
namespace {
16
17
size_t blinding_size(const BigInt& group_order)
18
60.8k
   {
19
60.8k
   return (group_order.bits() + 1) / 2;
20
60.8k
   }
21
22
}
23
24
PointGFp multi_exponentiate(const PointGFp& x, const BigInt& z1,
25
                            const PointGFp& y, const BigInt& z2)
26
0
   {
27
0
   PointGFp_Multi_Point_Precompute xy_mul(x, y);
28
0
   return xy_mul.multi_exp(z1, z2);
29
0
   }
30
31
PointGFp_Base_Point_Precompute::PointGFp_Base_Point_Precompute(const PointGFp& base,
32
                                                               const Modular_Reducer& mod_order) :
33
   m_base_point(base),
34
   m_mod_order(mod_order),
35
   m_p_words(base.get_curve().get_p().sig_words())
36
2.15k
   {
37
2.15k
   std::vector<BigInt> ws(PointGFp::WORKSPACE_SIZE);
38
39
2.15k
   const size_t p_bits = base.get_curve().get_p().bits();
40
41
   /*
42
   * Some of the curves (eg secp160k1) have an order slightly larger than
43
   * the size of the prime modulus. In all cases they are at most 1 bit
44
   * longer. The +1 compensates for this.
45
   */
46
2.15k
   const size_t T_bits = round_up(p_bits + blinding_size(mod_order.get_modulus()) + 1, WINDOW_BITS) / WINDOW_BITS;
47
48
2.15k
   std::vector<PointGFp> T(WINDOW_SIZE*T_bits);
49
50
2.15k
   PointGFp g = base;
51
2.15k
   PointGFp g2, g4;
52
53
313k
   for(size_t i = 0; i != T_bits; i++)
54
311k
      {
55
311k
      g2 = g;
56
311k
      g2.mult2(ws);
57
311k
      g4 = g2;
58
311k
      g4.mult2(ws);
59
60
311k
      T[7*i+0] = g;
61
311k
      T[7*i+1] = std::move(g2);
62
311k
      T[7*i+2] = T[7*i+1].plus(T[7*i+0], ws); // g2+g
63
311k
      T[7*i+3] = g4;
64
311k
      T[7*i+4] = T[7*i+3].plus(T[7*i+0], ws); // g4+g
65
311k
      T[7*i+5] = T[7*i+3].plus(T[7*i+1], ws); // g4+g2
66
311k
      T[7*i+6] = T[7*i+3].plus(T[7*i+2], ws); // g4+g2+g
67
68
311k
      g.swap(g4);
69
311k
      g.mult2(ws);
70
311k
      }
71
72
2.15k
   PointGFp::force_all_affine(T, ws[0].get_word_vector());
73
74
2.15k
   m_W.resize(T.size() * 2 * m_p_words);
75
76
2.15k
   word* p = &m_W[0];
77
2.15M
   for(size_t i = 0; i != T.size(); ++i)
78
2.15M
      {
79
2.15M
      T[i].get_x().encode_words(p, m_p_words);
80
2.15M
      p += m_p_words;
81
2.15M
      T[i].get_y().encode_words(p, m_p_words);
82
2.15M
      p += m_p_words;
83
2.15M
      }
84
2.15k
   }
85
86
PointGFp PointGFp_Base_Point_Precompute::mul(const BigInt& k,
87
                                             RandomNumberGenerator& rng,
88
                                             const BigInt& group_order,
89
                                             std::vector<BigInt>& ws) const
90
32.9k
   {
91
32.9k
   if(k.is_negative())
92
0
      throw Invalid_Argument("PointGFp_Base_Point_Precompute scalar must be positive");
93
94
   // Instead of reducing k mod group order should we alter the mask size??
95
32.9k
   BigInt scalar = m_mod_order.reduce(k);
96
97
32.9k
   if(rng.is_seeded())
98
32.9k
      {
99
      // Choose a small mask m and use k' = k + m*order (Coron's 1st countermeasure)
100
32.9k
      const BigInt mask(rng, blinding_size(group_order));
101
32.9k
      scalar += group_order * mask;
102
32.9k
      }
103
0
   else
104
0
      {
105
      /*
106
      When we don't have an RNG we cannot do scalar blinding. Instead use the
107
      same trick as OpenSSL and add one or two copies of the order to normalize
108
      the length of the scalar at order.bits()+1. This at least ensures the loop
109
      bound does not leak information about the high bits of the scalar.
110
      */
111
0
      scalar += group_order;
112
0
      if(scalar.bits() == group_order.bits())
113
0
         scalar += group_order;
114
0
      BOTAN_DEBUG_ASSERT(scalar.bits() == group_order.bits() + 1);
115
0
      }
116
117
32.9k
   const size_t windows = round_up(scalar.bits(), WINDOW_BITS) / WINDOW_BITS;
118
119
32.9k
   const size_t elem_size = 2*m_p_words;
120
121
32.9k
   BOTAN_ASSERT(windows <= m_W.size() / (3*elem_size),
122
32.9k
                "Precomputed sufficient values for scalar mult");
123
124
32.9k
   PointGFp R = m_base_point.zero();
125
126
32.9k
   if(ws.size() < PointGFp::WORKSPACE_SIZE)
127
18.2k
      ws.resize(PointGFp::WORKSPACE_SIZE);
128
129
   // the precomputed multiples are not secret so use std::vector
130
32.9k
   std::vector<word> Wt(elem_size);
131
132
6.63M
   for(size_t i = 0; i != windows; ++i)
133
6.60M
      {
134
6.60M
      const size_t window = windows - i - 1;
135
6.60M
      const size_t base_addr = (WINDOW_SIZE*window)*elem_size;
136
137
6.60M
      const word w = scalar.get_substring(WINDOW_BITS*window, WINDOW_BITS);
138
139
6.60M
      const auto w_is_1 = CT::Mask<word>::is_equal(w, 1);
140
6.60M
      const auto w_is_2 = CT::Mask<word>::is_equal(w, 2);
141
6.60M
      const auto w_is_3 = CT::Mask<word>::is_equal(w, 3);
142
6.60M
      const auto w_is_4 = CT::Mask<word>::is_equal(w, 4);
143
6.60M
      const auto w_is_5 = CT::Mask<word>::is_equal(w, 5);
144
6.60M
      const auto w_is_6 = CT::Mask<word>::is_equal(w, 6);
145
6.60M
      const auto w_is_7 = CT::Mask<word>::is_equal(w, 7);
146
147
99.4M
      for(size_t j = 0; j != elem_size; ++j)
148
92.8M
         {
149
92.8M
         const word w1 = w_is_1.if_set_return(m_W[base_addr + 0*elem_size + j]);
150
92.8M
         const word w2 = w_is_2.if_set_return(m_W[base_addr + 1*elem_size + j]);
151
92.8M
         const word w3 = w_is_3.if_set_return(m_W[base_addr + 2*elem_size + j]);
152
92.8M
         const word w4 = w_is_4.if_set_return(m_W[base_addr + 3*elem_size + j]);
153
92.8M
         const word w5 = w_is_5.if_set_return(m_W[base_addr + 4*elem_size + j]);
154
92.8M
         const word w6 = w_is_6.if_set_return(m_W[base_addr + 5*elem_size + j]);
155
92.8M
         const word w7 = w_is_7.if_set_return(m_W[base_addr + 6*elem_size + j]);
156
157
92.8M
         Wt[j] = w1 | w2 | w3 | w4 | w5 | w6 | w7;
158
92.8M
         }
159
160
6.60M
      R.add_affine(&Wt[0], m_p_words, &Wt[m_p_words], m_p_words, ws);
161
162
6.60M
      if(i == 0 && rng.is_seeded())
163
32.9k
         {
164
         /*
165
         * Since we start with the top bit of the exponent we know the
166
         * first window must have a non-zero element, and thus R is
167
         * now a point other than the point at infinity.
168
         */
169
32.9k
         BOTAN_DEBUG_ASSERT(w != 0);
170
32.9k
         R.randomize_repr(rng, ws[0].get_word_vector());
171
32.9k
         }
172
6.60M
      }
173
174
32.9k
   BOTAN_DEBUG_ASSERT(R.on_the_curve());
175
176
32.9k
   return R;
177
32.9k
   }
178
179
PointGFp_Var_Point_Precompute::PointGFp_Var_Point_Precompute(const PointGFp& point,
180
                                                             RandomNumberGenerator& rng,
181
                                                             std::vector<BigInt>& ws) :
182
   m_curve(point.get_curve()),
183
   m_p_words(m_curve.get_p().sig_words()),
184
   m_window_bits(4)
185
25.7k
   {
186
25.7k
   if(ws.size() < PointGFp::WORKSPACE_SIZE)
187
8.11k
      ws.resize(PointGFp::WORKSPACE_SIZE);
188
189
25.7k
   std::vector<PointGFp> U(static_cast<size_t>(1) << m_window_bits);
190
25.7k
   U[0] = point.zero();
191
25.7k
   U[1] = point;
192
193
205k
   for(size_t i = 2; i < U.size(); i += 2)
194
179k
      {
195
179k
      U[i] = U[i/2].double_of(ws);
196
179k
      U[i+1] = U[i].plus(point, ws);
197
179k
      }
198
199
   // Hack to handle Blinded_Point_Multiply
200
25.7k
   if(rng.is_seeded())
201
25.7k
      {
202
25.7k
      BigInt& mask = ws[0];
203
25.7k
      BigInt& mask2 = ws[1];
204
25.7k
      BigInt& mask3 = ws[2];
205
25.7k
      BigInt& new_x = ws[3];
206
25.7k
      BigInt& new_y = ws[4];
207
25.7k
      BigInt& new_z = ws[5];
208
25.7k
      secure_vector<word>& tmp = ws[6].get_word_vector();
209
210
25.7k
      const CurveGFp& curve = U[0].get_curve();
211
212
25.7k
      const size_t p_bits = curve.get_p().bits();
213
214
      // Skipping zero point since it can't be randomized
215
411k
      for(size_t i = 1; i != U.size(); ++i)
216
385k
         {
217
385k
         mask.randomize(rng, p_bits - 1, false);
218
         // Easy way of ensuring mask != 0
219
385k
         mask.set_bit(0);
220
221
385k
         curve.sqr(mask2, mask, tmp);
222
385k
         curve.mul(mask3, mask, mask2, tmp);
223
224
385k
         curve.mul(new_x, U[i].get_x(), mask2, tmp);
225
385k
         curve.mul(new_y, U[i].get_y(), mask3, tmp);
226
385k
         curve.mul(new_z, U[i].get_z(), mask, tmp);
227
228
385k
         U[i].swap_coords(new_x, new_y, new_z);
229
385k
         }
230
25.7k
      }
231
232
25.7k
   m_T.resize(U.size() * 3 * m_p_words);
233
234
25.7k
   word* p = &m_T[0];
235
437k
   for(size_t i = 0; i != U.size(); ++i)
236
411k
      {
237
411k
      U[i].get_x().encode_words(p              , m_p_words);
238
411k
      U[i].get_y().encode_words(p +   m_p_words, m_p_words);
239
411k
      U[i].get_z().encode_words(p + 2*m_p_words, m_p_words);
240
411k
      p += 3*m_p_words;
241
411k
      }
242
25.7k
   }
243
244
PointGFp PointGFp_Var_Point_Precompute::mul(const BigInt& k,
245
                                            RandomNumberGenerator& rng,
246
                                            const BigInt& group_order,
247
                                            std::vector<BigInt>& ws) const
248
25.7k
   {
249
25.7k
   if(k.is_negative())
250
0
      throw Invalid_Argument("PointGFp_Var_Point_Precompute scalar must be positive");
251
25.7k
   if(ws.size() < PointGFp::WORKSPACE_SIZE)
252
0
      ws.resize(PointGFp::WORKSPACE_SIZE);
253
254
   // Choose a small mask m and use k' = k + m*order (Coron's 1st countermeasure)
255
25.7k
   const BigInt mask(rng, blinding_size(group_order), false);
256
25.7k
   const BigInt scalar = k + group_order * mask;
257
258
25.7k
   const size_t elem_size = 3*m_p_words;
259
25.7k
   const size_t window_elems = static_cast<size_t>(1) << m_window_bits;
260
261
25.7k
   size_t windows = round_up(scalar.bits(), m_window_bits) / m_window_bits;
262
25.7k
   PointGFp R(m_curve);
263
25.7k
   secure_vector<word> e(elem_size);
264
265
25.7k
   if(windows > 0)
266
25.7k
      {
267
25.7k
      windows--;
268
269
25.7k
      const uint32_t w = scalar.get_substring(windows*m_window_bits, m_window_bits);
270
271
25.7k
      clear_mem(e.data(), e.size());
272
411k
      for(size_t i = 1; i != window_elems; ++i)
273
385k
         {
274
385k
         const auto wmask = CT::Mask<word>::is_equal(w, i);
275
276
7.70M
         for(size_t j = 0; j != elem_size; ++j)
277
7.31M
            {
278
7.31M
            e[j] |= wmask.if_set_return(m_T[i * elem_size + j]);
279
7.31M
            }
280
385k
         }
281
282
25.7k
      R.add(&e[0], m_p_words, &e[m_p_words], m_p_words, &e[2*m_p_words], m_p_words, ws);
283
284
      /*
285
      Randomize after adding the first nibble as before the addition R
286
      is zero, and we cannot effectively randomize the point
287
      representation of the zero point.
288
      */
289
25.7k
      R.randomize_repr(rng, ws[0].get_word_vector());
290
25.7k
      }
291
292
3.74M
   while(windows)
293
3.71M
      {
294
3.71M
      R.mult2i(m_window_bits, ws);
295
296
3.71M
      const uint32_t w = scalar.get_substring((windows-1)*m_window_bits, m_window_bits);
297
298
3.71M
      clear_mem(e.data(), e.size());
299
59.4M
      for(size_t i = 1; i != window_elems; ++i)
300
55.7M
         {
301
55.7M
         const auto wmask = CT::Mask<word>::is_equal(w, i);
302
303
1.21G
         for(size_t j = 0; j != elem_size; ++j)
304
1.16G
            {
305
1.16G
            e[j] |= wmask.if_set_return(m_T[i * elem_size + j]);
306
1.16G
            }
307
55.7M
         }
308
309
3.71M
      R.add(&e[0], m_p_words, &e[m_p_words], m_p_words, &e[2*m_p_words], m_p_words, ws);
310
311
3.71M
      windows--;
312
3.71M
      }
313
314
25.7k
   BOTAN_DEBUG_ASSERT(R.on_the_curve());
315
316
25.7k
   return R;
317
25.7k
   }
318
319
320
PointGFp_Multi_Point_Precompute::PointGFp_Multi_Point_Precompute(const PointGFp& x,
321
                                                                 const PointGFp& y)
322
446
   {
323
446
   if(x.on_the_curve() == false || y.on_the_curve() == false)
324
0
      {
325
0
      m_M.push_back(x.zero());
326
0
      return;
327
0
      }
328
329
446
   std::vector<BigInt> ws(PointGFp::WORKSPACE_SIZE);
330
331
446
   PointGFp x2 = x;
332
446
   x2.mult2(ws);
333
334
446
   const PointGFp x3(x2.plus(x, ws));
335
336
446
   PointGFp y2 = y;
337
446
   y2.mult2(ws);
338
339
446
   const PointGFp y3(y2.plus(y, ws));
340
341
446
   m_M.reserve(15);
342
343
446
   m_M.push_back(x);
344
446
   m_M.push_back(x2);
345
446
   m_M.push_back(x3);
346
347
446
   m_M.push_back(y);
348
446
   m_M.push_back(y.plus(x, ws));
349
446
   m_M.push_back(y.plus(x2, ws));
350
446
   m_M.push_back(y.plus(x3, ws));
351
352
446
   m_M.push_back(y2);
353
446
   m_M.push_back(y2.plus(x, ws));
354
446
   m_M.push_back(y2.plus(x2, ws));
355
446
   m_M.push_back(y2.plus(x3, ws));
356
357
446
   m_M.push_back(y3);
358
446
   m_M.push_back(y3.plus(x, ws));
359
446
   m_M.push_back(y3.plus(x2, ws));
360
446
   m_M.push_back(y3.plus(x3, ws));
361
362
446
   bool no_infinity = true;
363
446
   for(auto& pt : m_M)
364
6.69k
      {
365
6.69k
      if(pt.is_zero())
366
294
         no_infinity = false;
367
6.69k
      }
368
369
446
   if(no_infinity)
370
348
      {
371
348
      PointGFp::force_all_affine(m_M, ws[0].get_word_vector());
372
348
      }
373
374
446
   m_no_infinity = no_infinity;
375
446
   }
376
377
PointGFp PointGFp_Multi_Point_Precompute::multi_exp(const BigInt& z1,
378
                                                    const BigInt& z2) const
379
225
   {
380
225
   if(m_M.size() == 1)
381
0
      return m_M[0];
382
383
225
   std::vector<BigInt> ws(PointGFp::WORKSPACE_SIZE);
384
385
225
   const size_t z_bits = round_up(std::max(z1.bits(), z2.bits()), 2);
386
387
225
   PointGFp H = m_M[0].zero();
388
389
38.2k
   for(size_t i = 0; i != z_bits; i += 2)
390
38.0k
      {
391
38.0k
      if(i > 0)
392
37.8k
         {
393
37.8k
         H.mult2i(2, ws);
394
37.8k
         }
395
396
38.0k
      const uint32_t z1_b = z1.get_substring(z_bits - i - 2, 2);
397
38.0k
      const uint32_t z2_b = z2.get_substring(z_bits - i - 2, 2);
398
399
38.0k
      const uint32_t z12 = (4*z2_b) + z1_b;
400
401
      // This function is not intended to be const time
402
38.0k
      if(z12)
403
31.9k
         {
404
31.9k
         if(m_no_infinity)
405
18.0k
            H.add_affine(m_M[z12-1], ws);
406
13.8k
         else
407
13.8k
            H.add(m_M[z12-1], ws);
408
31.9k
         }
409
38.0k
      }
410
411
225
   if(z1.is_negative() != z2.is_negative())
412
0
      H.negate();
413
414
225
   return H;
415
225
   }
416
417
}