Coverage Report

Created: 2020-06-30 13:58

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