Coverage Report

Created: 2025-03-06 06:58

/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
0
#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
0
{
163
0
  const mp_limb_t *ep = mpz_limbs_read (pub->e);
164
0
  const mp_limb_t *np = mpz_limbs_read (pub->n);
165
0
  mp_bitcnt_t ebn = mpz_sizeinbase (pub->e, 2);
166
0
  mp_size_t nn = mpz_size (pub->n);
167
0
  size_t itch;
168
0
  size_t i2;
169
0
  mp_limb_t *scratch;
170
0
  TMP_GMP_DECL (tp, mp_limb_t);
171
0
  TMP_GMP_DECL (rp, mp_limb_t);
172
0
  TMP_GMP_DECL (r, uint8_t);
173
174
0
  TMP_GMP_ALLOC (rp, nn);
175
0
  TMP_GMP_ALLOC (r, nn * sizeof(mp_limb_t));
176
177
  /* c = m*(r^e) mod n */
178
0
  itch = mpn_sec_powm_itch(nn, ebn, nn);
179
0
  i2 = mpn_sec_mul_itch(nn, nn);
180
0
  itch = MAX(itch, i2);
181
0
  i2 = mpn_sec_div_r_itch(2*nn, nn);
182
0
  itch = MAX(itch, i2);
183
0
  i2 = mpn_sec_invert_itch(nn);
184
0
  itch = MAX(itch, i2);
185
186
0
  TMP_GMP_ALLOC (tp, 2*nn  + itch);
187
0
  scratch = tp + 2*nn;
188
189
  /* ri = r^(-1) */
190
0
  do
191
0
    {
192
0
      random(random_ctx, nn * sizeof(mp_limb_t), (uint8_t *)r);
193
0
      mpn_set_base256(rp, nn, r, nn * sizeof(mp_limb_t));
194
0
      mpn_copyi(tp, rp, nn);
195
      /* invert r */
196
0
    }
197
0
  while (!mpn_sec_invert (ri, tp, np, nn, 2 * nn * GMP_NUMB_BITS, scratch));
198
199
0
  mpn_sec_powm (c, rp, nn, ep, ebn, np, nn, scratch);
200
0
  mpn_sec_mul (tp, c, nn, m, nn, scratch);
201
0
  mpn_sec_div_r (tp, 2*nn, np, nn, scratch);
202
0
  mpn_copyi(c, tp, nn);
203
204
0
  TMP_GMP_FREE (r);
205
0
  TMP_GMP_FREE (rp);
206
0
  TMP_GMP_FREE (tp);
207
0
}
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
0
{
214
0
  const mp_limb_t *np = mpz_limbs_read (pub->n);
215
0
  mp_size_t nn = mpz_size (pub->n);
216
217
0
  size_t itch;
218
0
  size_t i2;
219
0
  mp_limb_t *scratch;
220
0
  TMP_GMP_DECL(tp, mp_limb_t);
221
222
0
  itch = mpn_sec_mul_itch(nn, nn);
223
0
  i2 = mpn_sec_div_r_itch(nn + nn, nn);
224
0
  itch = MAX(itch, i2);
225
226
0
  TMP_GMP_ALLOC (tp, nn + nn + itch);
227
0
  scratch = tp + nn + nn;
228
229
0
  mpn_sec_mul (tp, c, nn, ri, nn, scratch);
230
0
  mpn_sec_div_r (tp, nn + nn, np, nn, scratch);
231
0
  mpn_copyi(x, tp, nn);
232
233
0
  TMP_GMP_FREE (tp);
234
0
}
235
236
static int
237
sec_equal(const mp_limb_t *a, const mp_limb_t *b, size_t limbs)
238
0
{
239
0
  volatile mp_limb_t z = 0;
240
0
  size_t i;
241
242
0
  for (i = 0; i < limbs; i++)
243
0
    {
244
0
      z |= (a[i] ^ b[i]);
245
0
    }
246
247
0
  return z == 0;
248
0
}
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
0
{
254
0
  mp_size_t nn = mpz_size (pub->n);
255
0
  mp_size_t ebn = mpz_sizeinbase (pub->e, 2);
256
0
  const mp_limb_t *np = mpz_limbs_read (pub->n);
257
0
  const mp_limb_t *ep = mpz_limbs_read (pub->e);
258
0
  int ret;
259
260
0
  mp_size_t itch;
261
262
0
  mp_limb_t *scratch;
263
0
  TMP_GMP_DECL(tp, mp_limb_t);
264
265
0
  itch = mpn_sec_powm_itch (nn, ebn, nn);
266
0
  TMP_GMP_ALLOC (tp, nn + itch);
267
0
  scratch = tp + nn;
268
269
0
  mpn_sec_powm(tp, x, nn, ep, ebn, np, nn, scratch);
270
0
  ret = sec_equal(tp, m, nn);
271
272
0
  TMP_GMP_FREE (tp);
273
0
  return ret;
274
0
}
275
276
static void
277
cnd_mpn_zero (int cnd, volatile mp_ptr rp, mp_size_t n)
278
0
{
279
0
  volatile mp_limb_t c;
280
0
  volatile mp_limb_t mask = (mp_limb_t) cnd - 1;
281
282
0
  while (--n >= 0)
283
0
    {
284
0
      c = rp[n];
285
0
      c &= mask;
286
0
      rp[n] = c;
287
0
    }
288
0
}
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
0
{
301
0
  TMP_GMP_DECL (c, mp_limb_t);
302
0
  TMP_GMP_DECL (ri, mp_limb_t);
303
0
  TMP_GMP_DECL (scratch, mp_limb_t);
304
0
  size_t key_limb_size;
305
0
  int ret;
306
307
0
  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
0
  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
0
  assert(mpz_size(pub->n) == key_limb_size);
321
322
0
  TMP_GMP_ALLOC (c, key_limb_size);
323
0
  TMP_GMP_ALLOC (ri, key_limb_size);
324
0
  TMP_GMP_ALLOC (scratch, _rsa_sec_compute_root_itch(key));
325
326
0
  rsa_sec_blind (pub, random_ctx, random, c, ri, m);
327
328
0
  _rsa_sec_compute_root(key, x, c, scratch);
329
330
0
  ret = rsa_sec_check_root(pub, x, c);
331
332
0
  rsa_sec_unblind(pub, x, ri, x);
333
334
0
  cnd_mpn_zero(1 - ret, x, key_limb_size);
335
336
0
  TMP_GMP_FREE (scratch);
337
0
  TMP_GMP_FREE (ri);
338
0
  TMP_GMP_FREE (c);
339
0
  return ret;
340
0
}
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
0
{
355
0
  TMP_GMP_DECL (l, mp_limb_t);
356
0
  mp_size_t nn = mpz_size(pub->n);
357
0
  int res;
358
359
0
  TMP_GMP_ALLOC (l, nn);
360
0
  mpz_limbs_copy(l, m, nn);
361
362
0
  res = _rsa_sec_compute_root_tr (pub, key, random_ctx, random, l, l);
363
0
  if (res) {
364
0
    mp_limb_t *xp = mpz_limbs_write (x, nn);
365
0
    mpn_copyi (xp, l, nn);
366
0
    mpz_limbs_finish (x, nn);
367
0
  }
368
369
0
  TMP_GMP_FREE (l);
370
0
  return res;
371
0
}
372
#endif