Coverage Report

Created: 2024-11-25 06:31

/src/nettle/rsa-sign-tr.c
Line
Count
Source (jump to first uncovered line)
1
/* rsa-sign-tr.c
2
3
   Creating RSA signatures, with some additional checks.
4
5
   Copyright (C) 2001, 2015 Niels Möller
6
   Copyright (C) 2012 Nikos Mavrogiannopoulos
7
   Copyright (C) 2018 Red Hat Inc.
8
9
   This file is part of GNU Nettle.
10
11
   GNU Nettle is free software: you can redistribute it and/or
12
   modify it under the terms of either:
13
14
     * the GNU Lesser General Public License as published by the Free
15
       Software Foundation; either version 3 of the License, or (at your
16
       option) any later version.
17
18
   or
19
20
     * the GNU General Public License as published by the Free
21
       Software Foundation; either version 2 of the License, or (at your
22
       option) any later version.
23
24
   or both in parallel, as here.
25
26
   GNU Nettle is distributed in the hope that it will be useful,
27
   but WITHOUT ANY WARRANTY; without even the implied warranty of
28
   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
29
   General Public License for more details.
30
31
   You should have received copies of the GNU General Public License and
32
   the GNU Lesser General Public License along with this program.  If
33
   not, see http://www.gnu.org/licenses/.
34
*/
35
36
#if HAVE_CONFIG_H
37
# include "config.h"
38
#endif
39
40
#include <assert.h>
41
42
#include "gmp-glue.h"
43
#include "rsa.h"
44
#include "rsa-internal.h"
45
46
96.4k
#define MAX(a, b) ((a) > (b) ? (a) : (b))
47
48
#if NETTLE_USE_MINI_GMP
49
/* Blinds m, by computing c = m r^e (mod n), for a random r. Also
50
   returns the inverse (ri), for use by rsa_unblind. */
51
static void
52
rsa_blind (const struct rsa_public_key *pub,
53
     void *random_ctx, nettle_random_func *random,
54
     mpz_t c, mpz_t ri, const mpz_t m)
55
{
56
  mpz_t r;
57
58
  mpz_init(r);
59
60
  /* c = m*(r^e)
61
   * ri = r^(-1)
62
   */
63
  do
64
    {
65
      nettle_mpz_random(r, random_ctx, random, pub->n);
66
      /* invert r */
67
    }
68
  while (!mpz_invert (ri, r, pub->n));
69
70
  /* c = c*(r^e) mod n */
71
  mpz_powm_sec(r, r, pub->e, pub->n);
72
  mpz_mul(c, m, r);
73
  mpz_fdiv_r(c, c, pub->n);
74
75
  mpz_clear(r);
76
}
77
78
/* m = c ri mod n */
79
static void
80
rsa_unblind (const struct rsa_public_key *pub,
81
       mpz_t m, const mpz_t ri, const mpz_t c)
82
{
83
  mpz_mul(m, c, ri);
84
  mpz_fdiv_r(m, m, pub->n);
85
}
86
87
/* Checks for any errors done in the RSA computation. That avoids
88
 * attacks which rely on faults on hardware, or even software MPI
89
 * implementation. */
90
int
91
rsa_compute_root_tr(const struct rsa_public_key *pub,
92
        const struct rsa_private_key *key,
93
        void *random_ctx, nettle_random_func *random,
94
        mpz_t x, const mpz_t m)
95
{
96
  int res;
97
  mpz_t t, mb, xb, ri;
98
99
  /* mpz_powm_sec handles only odd moduli. If p, q or n is even, the
100
     key is invalid and rejected by rsa_private_key_prepare. However,
101
     some applications, notably gnutls, don't use this function, and
102
     we don't want an invalid key to lead to a crash down inside
103
     mpz_powm_sec. So do an additional check here. */
104
  if (mpz_even_p (pub->n) || mpz_even_p (key->p) || mpz_even_p (key->q))
105
    return 0;
106
107
  mpz_init (mb);
108
  mpz_init (xb);
109
  mpz_init (ri);
110
  mpz_init (t);
111
112
  rsa_blind (pub, random_ctx, random, mb, ri, m);
113
114
  rsa_compute_root (key, xb, mb);
115
116
  mpz_powm_sec(t, xb, pub->e, pub->n);
117
  res = (mpz_cmp(mb, t) == 0);
118
119
  if (res)
120
    rsa_unblind (pub, x, ri, xb);
121
122
  mpz_clear (mb);
123
  mpz_clear (xb);
124
  mpz_clear (ri);
125
  mpz_clear (t);
126
127
  return res;
128
}
129
130
int
131
_rsa_sec_compute_root_tr(const struct rsa_public_key *pub,
132
       const struct rsa_private_key *key,
133
       void *random_ctx, nettle_random_func *random,
134
       mp_limb_t *x, const mp_limb_t *m)
135
{
136
  mp_size_t nn;
137
  mpz_t mz;
138
  mpz_t xz;
139
  int res;
140
141
  mpz_init(xz);
142
143
  nn = mpz_size (pub->n);
144
145
  res = rsa_compute_root_tr(pub, key, random_ctx, random, xz,
146
          mpz_roinit_n(mz, m, nn));
147
148
  if (res)
149
    mpz_limbs_copy(x, xz, nn);
150
151
  mpz_clear(xz);
152
  return res;
153
}
154
#else
155
/* Blinds m, by computing c = m r^e (mod n), for a random r. Also
156
   returns the inverse (ri), for use by rsa_unblind. Must have c != m,
157
   no in-place operation.*/
158
static void
159
rsa_sec_blind (const struct rsa_public_key *pub,
160
               void *random_ctx, nettle_random_func *random,
161
               mp_limb_t *c, mp_limb_t *ri, const mp_limb_t *m)
162
24.1k
{
163
24.1k
  const mp_limb_t *ep = mpz_limbs_read (pub->e);
164
24.1k
  const mp_limb_t *np = mpz_limbs_read (pub->n);
165
24.1k
  mp_bitcnt_t ebn = mpz_sizeinbase (pub->e, 2);
166
24.1k
  mp_size_t nn = mpz_size (pub->n);
167
24.1k
  size_t itch;
168
24.1k
  size_t i2;
169
24.1k
  mp_limb_t *scratch;
170
24.1k
  TMP_GMP_DECL (tp, mp_limb_t);
171
24.1k
  TMP_GMP_DECL (rp, mp_limb_t);
172
24.1k
  TMP_GMP_DECL (r, uint8_t);
173
174
24.1k
  TMP_GMP_ALLOC (rp, nn);
175
24.1k
  TMP_GMP_ALLOC (r, nn * sizeof(mp_limb_t));
176
177
  /* c = m*(r^e) mod n */
178
24.1k
  itch = mpn_sec_powm_itch(nn, ebn, nn);
179
24.1k
  i2 = mpn_sec_mul_itch(nn, nn);
180
24.1k
  itch = MAX(itch, i2);
181
24.1k
  i2 = mpn_sec_div_r_itch(2*nn, nn);
182
24.1k
  itch = MAX(itch, i2);
183
24.1k
  i2 = mpn_sec_invert_itch(nn);
184
24.1k
  itch = MAX(itch, i2);
185
186
24.1k
  TMP_GMP_ALLOC (tp, 2*nn  + itch);
187
24.1k
  scratch = tp + 2*nn;
188
189
  /* ri = r^(-1) */
190
24.1k
  do
191
24.1k
    {
192
24.1k
      random(random_ctx, nn * sizeof(mp_limb_t), (uint8_t *)r);
193
24.1k
      mpn_set_base256(rp, nn, r, nn * sizeof(mp_limb_t));
194
24.1k
      mpn_copyi(tp, rp, nn);
195
      /* invert r */
196
24.1k
    }
197
24.1k
  while (!mpn_sec_invert (ri, tp, np, nn, 2 * nn * GMP_NUMB_BITS, scratch));
198
199
24.1k
  mpn_sec_powm (c, rp, nn, ep, ebn, np, nn, scratch);
200
24.1k
  mpn_sec_mul (tp, c, nn, m, nn, scratch);
201
24.1k
  mpn_sec_div_r (tp, 2*nn, np, nn, scratch);
202
24.1k
  mpn_copyi(c, tp, nn);
203
204
24.1k
  TMP_GMP_FREE (r);
205
24.1k
  TMP_GMP_FREE (rp);
206
24.1k
  TMP_GMP_FREE (tp);
207
24.1k
}
208
209
/* m = c ri mod n. Allows x == c. */
210
static void
211
rsa_sec_unblind (const struct rsa_public_key *pub,
212
                 mp_limb_t *x, mp_limb_t *ri, const mp_limb_t *c)
213
24.1k
{
214
24.1k
  const mp_limb_t *np = mpz_limbs_read (pub->n);
215
24.1k
  mp_size_t nn = mpz_size (pub->n);
216
217
24.1k
  size_t itch;
218
24.1k
  size_t i2;
219
24.1k
  mp_limb_t *scratch;
220
24.1k
  TMP_GMP_DECL(tp, mp_limb_t);
221
222
24.1k
  itch = mpn_sec_mul_itch(nn, nn);
223
24.1k
  i2 = mpn_sec_div_r_itch(nn + nn, nn);
224
24.1k
  itch = MAX(itch, i2);
225
226
24.1k
  TMP_GMP_ALLOC (tp, nn + nn + itch);
227
24.1k
  scratch = tp + nn + nn;
228
229
24.1k
  mpn_sec_mul (tp, c, nn, ri, nn, scratch);
230
24.1k
  mpn_sec_div_r (tp, nn + nn, np, nn, scratch);
231
24.1k
  mpn_copyi(x, tp, nn);
232
233
24.1k
  TMP_GMP_FREE (tp);
234
24.1k
}
235
236
static int
237
sec_equal(const mp_limb_t *a, const mp_limb_t *b, size_t limbs)
238
24.1k
{
239
24.1k
  volatile mp_limb_t z = 0;
240
24.1k
  size_t i;
241
242
989k
  for (i = 0; i < limbs; i++)
243
965k
    {
244
965k
      z |= (a[i] ^ b[i]);
245
965k
    }
246
247
24.1k
  return z == 0;
248
24.1k
}
249
250
static int
251
rsa_sec_check_root(const struct rsa_public_key *pub,
252
                   const mp_limb_t *x, const mp_limb_t *m)
253
24.1k
{
254
24.1k
  mp_size_t nn = mpz_size (pub->n);
255
24.1k
  mp_size_t ebn = mpz_sizeinbase (pub->e, 2);
256
24.1k
  const mp_limb_t *np = mpz_limbs_read (pub->n);
257
24.1k
  const mp_limb_t *ep = mpz_limbs_read (pub->e);
258
24.1k
  int ret;
259
260
24.1k
  mp_size_t itch;
261
262
24.1k
  mp_limb_t *scratch;
263
24.1k
  TMP_GMP_DECL(tp, mp_limb_t);
264
265
24.1k
  itch = mpn_sec_powm_itch (nn, ebn, nn);
266
24.1k
  TMP_GMP_ALLOC (tp, nn + itch);
267
24.1k
  scratch = tp + nn;
268
269
24.1k
  mpn_sec_powm(tp, x, nn, ep, ebn, np, nn, scratch);
270
24.1k
  ret = sec_equal(tp, m, nn);
271
272
24.1k
  TMP_GMP_FREE (tp);
273
24.1k
  return ret;
274
24.1k
}
275
276
static void
277
cnd_mpn_zero (int cnd, volatile mp_ptr rp, mp_size_t n)
278
24.1k
{
279
24.1k
  volatile mp_limb_t c;
280
24.1k
  volatile mp_limb_t mask = (mp_limb_t) cnd - 1;
281
282
989k
  while (--n >= 0)
283
965k
    {
284
965k
      c = rp[n];
285
965k
      c &= mask;
286
965k
      rp[n] = c;
287
965k
    }
288
24.1k
}
289
290
/* Checks for any errors done in the RSA computation. That avoids
291
 * attacks which rely on faults on hardware, or even software MPI
292
 * implementation.
293
 * This version is side-channel silent even in case of error,
294
 * the destination buffer is always overwritten */
295
int
296
_rsa_sec_compute_root_tr(const struct rsa_public_key *pub,
297
       const struct rsa_private_key *key,
298
       void *random_ctx, nettle_random_func *random,
299
       mp_limb_t *x, const mp_limb_t *m)
300
24.1k
{
301
24.1k
  TMP_GMP_DECL (c, mp_limb_t);
302
24.1k
  TMP_GMP_DECL (ri, mp_limb_t);
303
24.1k
  TMP_GMP_DECL (scratch, mp_limb_t);
304
24.1k
  size_t key_limb_size;
305
24.1k
  int ret;
306
307
24.1k
  key_limb_size = mpz_size(pub->n);
308
309
  /* mpz_powm_sec handles only odd moduli. If p, q or n is even, the
310
     key is invalid and rejected by rsa_private_key_prepare. However,
311
     some applications, notably gnutls, don't use this function, and
312
     we don't want an invalid key to lead to a crash down inside
313
     mpz_powm_sec. So do an additional check here. */
314
24.1k
  if (mpz_even_p (pub->n) || mpz_even_p (key->p) || mpz_even_p (key->q))
315
0
    {
316
0
      mpn_zero(x, key_limb_size);
317
0
      return 0;
318
0
    }
319
320
24.1k
  assert(mpz_size(pub->n) == key_limb_size);
321
322
24.1k
  TMP_GMP_ALLOC (c, key_limb_size);
323
24.1k
  TMP_GMP_ALLOC (ri, key_limb_size);
324
24.1k
  TMP_GMP_ALLOC (scratch, _rsa_sec_compute_root_itch(key));
325
326
24.1k
  rsa_sec_blind (pub, random_ctx, random, c, ri, m);
327
328
24.1k
  _rsa_sec_compute_root(key, x, c, scratch);
329
330
24.1k
  ret = rsa_sec_check_root(pub, x, c);
331
332
24.1k
  rsa_sec_unblind(pub, x, ri, x);
333
334
24.1k
  cnd_mpn_zero(1 - ret, x, key_limb_size);
335
336
24.1k
  TMP_GMP_FREE (scratch);
337
24.1k
  TMP_GMP_FREE (ri);
338
24.1k
  TMP_GMP_FREE (c);
339
24.1k
  return ret;
340
24.1k
}
341
342
/* Checks for any errors done in the RSA computation. That avoids
343
 * attacks which rely on faults on hardware, or even software MPI
344
 * implementation.
345
 * This version is maintained for API compatibility reasons. It
346
 * is not completely side-channel silent. There are conditionals
347
 * in buffer copying both in case of success or error.
348
 */
349
int
350
rsa_compute_root_tr(const struct rsa_public_key *pub,
351
        const struct rsa_private_key *key,
352
        void *random_ctx, nettle_random_func *random,
353
        mpz_t x, const mpz_t m)
354
24.0k
{
355
24.0k
  TMP_GMP_DECL (l, mp_limb_t);
356
24.0k
  mp_size_t nn = mpz_size(pub->n);
357
24.0k
  int res;
358
359
24.0k
  TMP_GMP_ALLOC (l, nn);
360
24.0k
  mpz_limbs_copy(l, m, nn);
361
362
24.0k
  res = _rsa_sec_compute_root_tr (pub, key, random_ctx, random, l, l);
363
24.0k
  if (res) {
364
24.0k
    mp_limb_t *xp = mpz_limbs_write (x, nn);
365
24.0k
    mpn_copyi (xp, l, nn);
366
24.0k
    mpz_limbs_finish (x, nn);
367
24.0k
  }
368
369
24.0k
  TMP_GMP_FREE (l);
370
24.0k
  return res;
371
24.0k
}
372
#endif