Coverage Report

Created: 2022-11-24 06:56

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