Coverage Report

Created: 2020-05-23 13:54

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