Coverage Report

Created: 2021-05-04 09:02

/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
52.2k
   {
19
52.2k
   return (group_order.bits() + 1) / 2;
20
52.2k
   }
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
1.46k
   {
37
1.46k
   std::vector<BigInt> ws(PointGFp::WORKSPACE_SIZE);
38
39
1.46k
   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
1.46k
   const size_t T_bits = round_up(p_bits + blinding_size(mod_order.get_modulus()) + 1, WINDOW_BITS) / WINDOW_BITS;
47
48
1.46k
   std::vector<PointGFp> T(WINDOW_SIZE*T_bits);
49
50
1.46k
   PointGFp g = base;
51
1.46k
   PointGFp g2, g4;
52
53
204k
   for(size_t i = 0; i != T_bits; i++)
54
203k
      {
55
203k
      g2 = g;
56
203k
      g2.mult2(ws);
57
203k
      g4 = g2;
58
203k
      g4.mult2(ws);
59
60
203k
      T[7*i+0] = g;
61
203k
      T[7*i+1] = std::move(g2);
62
203k
      T[7*i+2] = T[7*i+1].plus(T[7*i+0], ws); // g2+g
63
203k
      T[7*i+3] = g4;
64
203k
      T[7*i+4] = T[7*i+3].plus(T[7*i+0], ws); // g4+g
65
203k
      T[7*i+5] = T[7*i+3].plus(T[7*i+1], ws); // g4+g2
66
203k
      T[7*i+6] = T[7*i+3].plus(T[7*i+2], ws); // g4+g2+g
67
68
203k
      g.swap(g4);
69
203k
      g.mult2(ws);
70
203k
      }
71
72
1.46k
   PointGFp::force_all_affine(T, ws[0].get_word_vector());
73
74
1.46k
   m_W.resize(T.size() * 2 * m_p_words);
75
76
1.46k
   word* p = &m_W[0];
77
1.40M
   for(size_t i = 0; i != T.size(); ++i)
78
1.40M
      {
79
1.40M
      T[i].get_x().encode_words(p, m_p_words);
80
1.40M
      p += m_p_words;
81
1.40M
      T[i].get_y().encode_words(p, m_p_words);
82
1.40M
      p += m_p_words;
83
1.40M
      }
84
1.46k
   }
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
31.6k
   {
91
31.6k
   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
31.6k
   BigInt scalar = m_mod_order.reduce(k);
96
97
31.6k
   if(rng.is_seeded())
98
31.6k
      {
99
      // Choose a small mask m and use k' = k + m*order (Coron's 1st countermeasure)
100
31.6k
      const BigInt mask(rng, blinding_size(group_order));
101
31.6k
      scalar += group_order * mask;
102
31.6k
      }
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
31.6k
   const size_t windows = round_up(scalar.bits(), WINDOW_BITS) / WINDOW_BITS;
118
119
31.6k
   const size_t elem_size = 2*m_p_words;
120
121
31.6k
   BOTAN_ASSERT(windows <= m_W.size() / (3*elem_size),
122
31.6k
                "Precomputed sufficient values for scalar mult");
123
124
31.6k
   PointGFp R = m_base_point.zero();
125
126
31.6k
   if(ws.size() < PointGFp::WORKSPACE_SIZE)
127
21.0k
      ws.resize(PointGFp::WORKSPACE_SIZE);
128
129
   // the precomputed multiples are not secret so use std::vector
130
31.6k
   std::vector<word> Wt(elem_size);
131
132
6.84M
   for(size_t i = 0; i != windows; ++i)
133
6.81M
      {
134
6.81M
      const size_t window = windows - i - 1;
135
6.81M
      const size_t base_addr = (WINDOW_SIZE*window)*elem_size;
136
137
6.81M
      const word w = scalar.get_substring(WINDOW_BITS*window, WINDOW_BITS);
138
139
6.81M
      const auto w_is_1 = CT::Mask<word>::is_equal(w, 1);
140
6.81M
      const auto w_is_2 = CT::Mask<word>::is_equal(w, 2);
141
6.81M
      const auto w_is_3 = CT::Mask<word>::is_equal(w, 3);
142
6.81M
      const auto w_is_4 = CT::Mask<word>::is_equal(w, 4);
143
6.81M
      const auto w_is_5 = CT::Mask<word>::is_equal(w, 5);
144
6.81M
      const auto w_is_6 = CT::Mask<word>::is_equal(w, 6);
145
6.81M
      const auto w_is_7 = CT::Mask<word>::is_equal(w, 7);
146
147
110M
      for(size_t j = 0; j != elem_size; ++j)
148
103M
         {
149
103M
         const word w1 = w_is_1.if_set_return(m_W[base_addr + 0*elem_size + j]);
150
103M
         const word w2 = w_is_2.if_set_return(m_W[base_addr + 1*elem_size + j]);
151
103M
         const word w3 = w_is_3.if_set_return(m_W[base_addr + 2*elem_size + j]);
152
103M
         const word w4 = w_is_4.if_set_return(m_W[base_addr + 3*elem_size + j]);
153
103M
         const word w5 = w_is_5.if_set_return(m_W[base_addr + 4*elem_size + j]);
154
103M
         const word w6 = w_is_6.if_set_return(m_W[base_addr + 5*elem_size + j]);
155
103M
         const word w7 = w_is_7.if_set_return(m_W[base_addr + 6*elem_size + j]);
156
157
103M
         Wt[j] = w1 | w2 | w3 | w4 | w5 | w6 | w7;
158
103M
         }
159
160
6.81M
      R.add_affine(&Wt[0], m_p_words, &Wt[m_p_words], m_p_words, ws);
161
162
6.81M
      if(i == 0 && rng.is_seeded())
163
31.6k
         {
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
31.6k
         BOTAN_DEBUG_ASSERT(w != 0);
170
31.6k
         R.randomize_repr(rng, ws[0].get_word_vector());
171
31.6k
         }
172
6.81M
      }
173
174
31.6k
   BOTAN_DEBUG_ASSERT(R.on_the_curve());
175
176
31.6k
   return R;
177
31.6k
   }
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
19.1k
   {
186
19.1k
   if(ws.size() < PointGFp::WORKSPACE_SIZE)
187
6.67k
      ws.resize(PointGFp::WORKSPACE_SIZE);
188
189
19.1k
   std::vector<PointGFp> U(static_cast<size_t>(1) << m_window_bits);
190
19.1k
   U[0] = point.zero();
191
19.1k
   U[1] = point;
192
193
153k
   for(size_t i = 2; i < U.size(); i += 2)
194
134k
      {
195
134k
      U[i] = U[i/2].double_of(ws);
196
134k
      U[i+1] = U[i].plus(point, ws);
197
134k
      }
198
199
   // Hack to handle Blinded_Point_Multiply
200
19.1k
   if(rng.is_seeded())
201
19.1k
      {
202
19.1k
      BigInt& mask = ws[0];
203
19.1k
      BigInt& mask2 = ws[1];
204
19.1k
      BigInt& mask3 = ws[2];
205
19.1k
      BigInt& new_x = ws[3];
206
19.1k
      BigInt& new_y = ws[4];
207
19.1k
      BigInt& new_z = ws[5];
208
19.1k
      secure_vector<word>& tmp = ws[6].get_word_vector();
209
210
19.1k
      const CurveGFp& curve = U[0].get_curve();
211
212
19.1k
      const size_t p_bits = curve.get_p().bits();
213
214
      // Skipping zero point since it can't be randomized
215
306k
      for(size_t i = 1; i != U.size(); ++i)
216
287k
         {
217
287k
         mask.randomize(rng, p_bits - 1, false);
218
         // Easy way of ensuring mask != 0
219
287k
         mask.set_bit(0);
220
221
287k
         curve.sqr(mask2, mask, tmp);
222
287k
         curve.mul(mask3, mask, mask2, tmp);
223
224
287k
         curve.mul(new_x, U[i].get_x(), mask2, tmp);
225
287k
         curve.mul(new_y, U[i].get_y(), mask3, tmp);
226
287k
         curve.mul(new_z, U[i].get_z(), mask, tmp);
227
228
287k
         U[i].swap_coords(new_x, new_y, new_z);
229
287k
         }
230
19.1k
      }
231
232
19.1k
   m_T.resize(U.size() * 3 * m_p_words);
233
234
19.1k
   word* p = &m_T[0];
235
325k
   for(size_t i = 0; i != U.size(); ++i)
236
306k
      {
237
306k
      U[i].get_x().encode_words(p              , m_p_words);
238
306k
      U[i].get_y().encode_words(p +   m_p_words, m_p_words);
239
306k
      U[i].get_z().encode_words(p + 2*m_p_words, m_p_words);
240
306k
      p += 3*m_p_words;
241
306k
      }
242
19.1k
   }
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
19.1k
   {
249
19.1k
   if(k.is_negative())
250
0
      throw Invalid_Argument("PointGFp_Var_Point_Precompute scalar must be positive");
251
19.1k
   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
19.1k
   const BigInt mask(rng, blinding_size(group_order), false);
256
19.1k
   const BigInt scalar = k + group_order * mask;
257
258
19.1k
   const size_t elem_size = 3*m_p_words;
259
19.1k
   const size_t window_elems = static_cast<size_t>(1) << m_window_bits;
260
261
19.1k
   size_t windows = round_up(scalar.bits(), m_window_bits) / m_window_bits;
262
19.1k
   PointGFp R(m_curve);
263
19.1k
   secure_vector<word> e(elem_size);
264
265
19.1k
   if(windows > 0)
266
19.1k
      {
267
19.1k
      windows--;
268
269
19.1k
      const uint32_t w = scalar.get_substring(windows*m_window_bits, m_window_bits);
270
271
19.1k
      clear_mem(e.data(), e.size());
272
306k
      for(size_t i = 1; i != window_elems; ++i)
273
287k
         {
274
287k
         const auto wmask = CT::Mask<word>::is_equal(w, i);
275
276
5.78M
         for(size_t j = 0; j != elem_size; ++j)
277
5.49M
            {
278
5.49M
            e[j] |= wmask.if_set_return(m_T[i * elem_size + j]);
279
5.49M
            }
280
287k
         }
281
282
19.1k
      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
19.1k
      R.randomize_repr(rng, ws[0].get_word_vector());
290
19.1k
      }
291
292
2.83M
   while(windows)
293
2.81M
      {
294
2.81M
      R.mult2i(m_window_bits, ws);
295
296
2.81M
      const uint32_t w = scalar.get_substring((windows-1)*m_window_bits, m_window_bits);
297
298
2.81M
      clear_mem(e.data(), e.size());
299
45.0M
      for(size_t i = 1; i != window_elems; ++i)
300
42.2M
         {
301
42.2M
         const auto wmask = CT::Mask<word>::is_equal(w, i);
302
303
925M
         for(size_t j = 0; j != elem_size; ++j)
304
883M
            {
305
883M
            e[j] |= wmask.if_set_return(m_T[i * elem_size + j]);
306
883M
            }
307
42.2M
         }
308
309
2.81M
      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
2.81M
      windows--;
312
2.81M
      }
313
314
19.1k
   BOTAN_DEBUG_ASSERT(R.on_the_curve());
315
316
19.1k
   return R;
317
19.1k
   }
318
319
320
PointGFp_Multi_Point_Precompute::PointGFp_Multi_Point_Precompute(const PointGFp& x,
321
                                                                 const PointGFp& y)
322
260
   {
323
260
   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
260
   std::vector<BigInt> ws(PointGFp::WORKSPACE_SIZE);
330
331
260
   PointGFp x2 = x;
332
260
   x2.mult2(ws);
333
334
260
   const PointGFp x3(x2.plus(x, ws));
335
336
260
   PointGFp y2 = y;
337
260
   y2.mult2(ws);
338
339
260
   const PointGFp y3(y2.plus(y, ws));
340
341
260
   m_M.reserve(15);
342
343
260
   m_M.push_back(x);
344
260
   m_M.push_back(x2);
345
260
   m_M.push_back(x3);
346
347
260
   m_M.push_back(y);
348
260
   m_M.push_back(y.plus(x, ws));
349
260
   m_M.push_back(y.plus(x2, ws));
350
260
   m_M.push_back(y.plus(x3, ws));
351
352
260
   m_M.push_back(y2);
353
260
   m_M.push_back(y2.plus(x, ws));
354
260
   m_M.push_back(y2.plus(x2, ws));
355
260
   m_M.push_back(y2.plus(x3, ws));
356
357
260
   m_M.push_back(y3);
358
260
   m_M.push_back(y3.plus(x, ws));
359
260
   m_M.push_back(y3.plus(x2, ws));
360
260
   m_M.push_back(y3.plus(x3, ws));
361
362
260
   bool no_infinity = true;
363
260
   for(auto& pt : m_M)
364
3.90k
      {
365
3.90k
      if(pt.is_zero())
366
219
         no_infinity = false;
367
3.90k
      }
368
369
260
   if(no_infinity)
370
187
      {
371
187
      PointGFp::force_all_affine(m_M, ws[0].get_word_vector());
372
187
      }
373
374
260
   m_no_infinity = no_infinity;
375
260
   }
376
377
PointGFp PointGFp_Multi_Point_Precompute::multi_exp(const BigInt& z1,
378
                                                    const BigInt& z2) const
379
182
   {
380
182
   if(m_M.size() == 1)
381
0
      return m_M[0];
382
383
182
   std::vector<BigInt> ws(PointGFp::WORKSPACE_SIZE);
384
385
182
   const size_t z_bits = round_up(std::max(z1.bits(), z2.bits()), 2);
386
387
182
   PointGFp H = m_M[0].zero();
388
389
34.2k
   for(size_t i = 0; i != z_bits; i += 2)
390
34.0k
      {
391
34.0k
      if(i > 0)
392
33.8k
         {
393
33.8k
         H.mult2i(2, ws);
394
33.8k
         }
395
396
34.0k
      const uint32_t z1_b = z1.get_substring(z_bits - i - 2, 2);
397
34.0k
      const uint32_t z2_b = z2.get_substring(z_bits - i - 2, 2);
398
399
34.0k
      const uint32_t z12 = (4*z2_b) + z1_b;
400
401
      // This function is not intended to be const time
402
34.0k
      if(z12)
403
28.3k
         {
404
28.3k
         if(m_no_infinity)
405
17.1k
            H.add_affine(m_M[z12-1], ws);
406
11.2k
         else
407
11.2k
            H.add(m_M[z12-1], ws);
408
28.3k
         }
409
34.0k
      }
410
411
182
   if(z1.is_negative() != z2.is_negative())
412
0
      H.negate();
413
414
182
   return H;
415
182
   }
416
417
}