Coverage Report

Created: 2021-02-21 07:20

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