Coverage Report

Created: 2024-11-21 07:03

/src/nss-nspr/nss/lib/freebl/dh.c
Line
Count
Source (jump to first uncovered line)
1
/* This Source Code Form is subject to the terms of the Mozilla Public
2
 * License, v. 2.0. If a copy of the MPL was not distributed with this
3
 * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
4
5
/*
6
 * Diffie-Hellman parameter generation, key generation, and secret derivation.
7
 * KEA secret generation and verification.
8
 */
9
#ifdef FREEBL_NO_DEPEND
10
#include "stubs.h"
11
#endif
12
13
#include "prerr.h"
14
#include "secerr.h"
15
16
#include "blapi.h"
17
#include "blapii.h"
18
#include "secitem.h"
19
#include "mpi.h"
20
#include "secmpi.h"
21
22
0
#define KEA_DERIVED_SECRET_LEN 128
23
24
/* Lengths are in bytes. */
25
static unsigned int
26
dh_GetSecretKeyLen(unsigned int primeLen)
27
0
{
28
    /* Based on Table 2 in NIST SP 800-57. */
29
0
    if (primeLen >= 1920) { /* 15360 bits */
30
0
        return 64;          /* 512 bits */
31
0
    }
32
0
    if (primeLen >= 960) { /* 7680 bits */
33
0
        return 48;         /* 384 bits */
34
0
    }
35
0
    if (primeLen >= 384) { /* 3072 bits */
36
0
        return 32;         /* 256 bits */
37
0
    }
38
0
    if (primeLen >= 256) { /* 2048 bits */
39
0
        return 28;         /* 224 bits */
40
0
    }
41
0
    return 20; /* 160 bits */
42
0
}
43
44
SECStatus
45
DH_GenParam(int primeLen, DHParams **params)
46
0
{
47
0
    PLArenaPool *arena;
48
0
    DHParams *dhparams;
49
0
    unsigned char *ab = NULL;
50
0
    mp_int p, q, a, h, psub1, test;
51
0
    mp_err err = MP_OKAY;
52
0
    SECStatus rv = SECSuccess;
53
0
    if (!params || primeLen < 0) {
54
0
        PORT_SetError(SEC_ERROR_INVALID_ARGS);
55
0
        return SECFailure;
56
0
    }
57
0
    arena = PORT_NewArena(NSS_FREEBL_DEFAULT_CHUNKSIZE);
58
0
    if (!arena) {
59
0
        PORT_SetError(SEC_ERROR_NO_MEMORY);
60
0
        return SECFailure;
61
0
    }
62
0
    dhparams = (DHParams *)PORT_ArenaZAlloc(arena, sizeof(DHParams));
63
0
    if (!dhparams) {
64
0
        PORT_SetError(SEC_ERROR_NO_MEMORY);
65
0
        PORT_FreeArena(arena, PR_TRUE);
66
0
        return SECFailure;
67
0
    }
68
0
    dhparams->arena = arena;
69
0
    MP_DIGITS(&p) = 0;
70
0
    MP_DIGITS(&q) = 0;
71
0
    MP_DIGITS(&a) = 0;
72
0
    MP_DIGITS(&h) = 0;
73
0
    MP_DIGITS(&psub1) = 0;
74
0
    MP_DIGITS(&test) = 0;
75
0
    CHECK_MPI_OK(mp_init(&p));
76
0
    CHECK_MPI_OK(mp_init(&q));
77
0
    CHECK_MPI_OK(mp_init(&a));
78
0
    CHECK_MPI_OK(mp_init(&h));
79
0
    CHECK_MPI_OK(mp_init(&psub1));
80
0
    CHECK_MPI_OK(mp_init(&test));
81
    /* generate prime with MPI, uses Miller-Rabin to generate safe prime. */
82
0
    CHECK_SEC_OK(generate_prime(&p, primeLen));
83
    /* construct Sophie-Germain prime q = (p-1)/2. */
84
0
    CHECK_MPI_OK(mp_sub_d(&p, 1, &psub1));
85
0
    CHECK_MPI_OK(mp_div_2(&psub1, &q));
86
    /* construct a generator from the prime. */
87
0
    ab = PORT_Alloc(primeLen);
88
0
    if (!ab) {
89
0
        PORT_SetError(SEC_ERROR_NO_MEMORY);
90
0
        rv = SECFailure;
91
0
        goto cleanup;
92
0
    }
93
    /* generate a candidate number a in p's field */
94
0
    CHECK_SEC_OK(RNG_GenerateGlobalRandomBytes(ab, primeLen));
95
0
    CHECK_MPI_OK(mp_read_unsigned_octets(&a, ab, primeLen));
96
    /* force a < p (note that quot(a/p) <= 1) */
97
0
    if (mp_cmp(&a, &p) > 0)
98
0
        CHECK_MPI_OK(mp_sub(&a, &p, &a));
99
0
    do {
100
        /* check that a is in the range [2..p-1] */
101
0
        if (mp_cmp_d(&a, 2) < 0 || mp_cmp(&a, &psub1) >= 0) {
102
            /* a is outside of the allowed range.  Set a=3 and keep going. */
103
0
            mp_set(&a, 3);
104
0
        }
105
        /* if a**q mod p != 1 then a is a generator */
106
0
        CHECK_MPI_OK(mp_exptmod(&a, &q, &p, &test));
107
0
        if (mp_cmp_d(&test, 1) != 0)
108
0
            break;
109
        /* increment the candidate and try again. */
110
0
        CHECK_MPI_OK(mp_add_d(&a, 1, &a));
111
0
    } while (PR_TRUE);
112
0
    MPINT_TO_SECITEM(&p, &dhparams->prime, arena);
113
0
    MPINT_TO_SECITEM(&a, &dhparams->base, arena);
114
0
    *params = dhparams;
115
0
cleanup:
116
0
    mp_clear(&p);
117
0
    mp_clear(&q);
118
0
    mp_clear(&a);
119
0
    mp_clear(&h);
120
0
    mp_clear(&psub1);
121
0
    mp_clear(&test);
122
0
    if (ab) {
123
0
        PORT_ZFree(ab, primeLen);
124
0
    }
125
0
    if (err) {
126
0
        MP_TO_SEC_ERROR(err);
127
0
        rv = SECFailure;
128
0
    }
129
0
    if (rv != SECSuccess) {
130
0
        PORT_FreeArena(arena, PR_TRUE);
131
0
    }
132
0
    return rv;
133
0
}
134
135
SECStatus
136
DH_NewKey(DHParams *params, DHPrivateKey **privKey)
137
0
{
138
0
    PLArenaPool *arena;
139
0
    DHPrivateKey *key;
140
0
    mp_int g, xa, p, Ya;
141
0
    mp_err err = MP_OKAY;
142
0
    SECStatus rv = SECSuccess;
143
0
    if (!params || !privKey) {
144
0
        PORT_SetError(SEC_ERROR_INVALID_ARGS);
145
0
        return SECFailure;
146
0
    }
147
0
    arena = PORT_NewArena(NSS_FREEBL_DEFAULT_CHUNKSIZE);
148
0
    if (!arena) {
149
0
        PORT_SetError(SEC_ERROR_NO_MEMORY);
150
0
        return SECFailure;
151
0
    }
152
0
    key = (DHPrivateKey *)PORT_ArenaZAlloc(arena, sizeof(DHPrivateKey));
153
0
    if (!key) {
154
0
        PORT_SetError(SEC_ERROR_NO_MEMORY);
155
0
        PORT_FreeArena(arena, PR_TRUE);
156
0
        return SECFailure;
157
0
    }
158
0
    key->arena = arena;
159
0
    MP_DIGITS(&g) = 0;
160
0
    MP_DIGITS(&xa) = 0;
161
0
    MP_DIGITS(&p) = 0;
162
0
    MP_DIGITS(&Ya) = 0;
163
0
    CHECK_MPI_OK(mp_init(&g));
164
0
    CHECK_MPI_OK(mp_init(&xa));
165
0
    CHECK_MPI_OK(mp_init(&p));
166
0
    CHECK_MPI_OK(mp_init(&Ya));
167
    /* Set private key's p */
168
0
    CHECK_SEC_OK(SECITEM_CopyItem(arena, &key->prime, &params->prime));
169
0
    SECITEM_TO_MPINT(key->prime, &p);
170
    /* Set private key's g */
171
0
    CHECK_SEC_OK(SECITEM_CopyItem(arena, &key->base, &params->base));
172
0
    SECITEM_TO_MPINT(key->base, &g);
173
    /* Generate private key xa */
174
0
    SECITEM_AllocItem(arena, &key->privateValue,
175
0
                      dh_GetSecretKeyLen(params->prime.len));
176
0
    CHECK_SEC_OK(RNG_GenerateGlobalRandomBytes(key->privateValue.data,
177
0
                                               key->privateValue.len));
178
0
    SECITEM_TO_MPINT(key->privateValue, &xa);
179
    /* xa < p */
180
0
    CHECK_MPI_OK(mp_mod(&xa, &p, &xa));
181
    /* Compute public key Ya = g ** xa mod p */
182
0
    CHECK_MPI_OK(mp_exptmod(&g, &xa, &p, &Ya));
183
0
    MPINT_TO_SECITEM(&Ya, &key->publicValue, key->arena);
184
0
    *privKey = key;
185
0
cleanup:
186
0
    mp_clear(&g);
187
0
    mp_clear(&xa);
188
0
    mp_clear(&p);
189
0
    mp_clear(&Ya);
190
0
    if (err) {
191
0
        MP_TO_SEC_ERROR(err);
192
0
        rv = SECFailure;
193
0
    }
194
0
    if (rv) {
195
0
        *privKey = NULL;
196
0
        PORT_FreeArena(arena, PR_TRUE);
197
0
    }
198
0
    return rv;
199
0
}
200
201
SECStatus
202
DH_Derive(SECItem *publicValue,
203
          SECItem *prime,
204
          SECItem *privateValue,
205
          SECItem *derivedSecret,
206
          unsigned int outBytes)
207
0
{
208
0
    mp_int p, Xa, Yb, ZZ, psub1;
209
0
    mp_err err = MP_OKAY;
210
0
    unsigned int len = 0;
211
0
    unsigned int nb;
212
0
    unsigned char *secret = NULL;
213
0
    if (!publicValue || !publicValue->len || !prime || !prime->len ||
214
0
        !privateValue || !privateValue->len || !derivedSecret) {
215
0
        PORT_SetError(SEC_ERROR_INVALID_ARGS);
216
0
        return SECFailure;
217
0
    }
218
0
    memset(derivedSecret, 0, sizeof *derivedSecret);
219
0
    MP_DIGITS(&p) = 0;
220
0
    MP_DIGITS(&Xa) = 0;
221
0
    MP_DIGITS(&Yb) = 0;
222
0
    MP_DIGITS(&ZZ) = 0;
223
0
    MP_DIGITS(&psub1) = 0;
224
0
    CHECK_MPI_OK(mp_init(&p));
225
0
    CHECK_MPI_OK(mp_init(&Xa));
226
0
    CHECK_MPI_OK(mp_init(&Yb));
227
0
    CHECK_MPI_OK(mp_init(&ZZ));
228
0
    CHECK_MPI_OK(mp_init(&psub1));
229
0
    SECITEM_TO_MPINT(*publicValue, &Yb);
230
0
    SECITEM_TO_MPINT(*privateValue, &Xa);
231
0
    SECITEM_TO_MPINT(*prime, &p);
232
0
    CHECK_MPI_OK(mp_sub_d(&p, 1, &psub1));
233
234
    /* We assume that the modulus, p, is a safe prime. That is, p = 2q+1 where
235
     * q is also a prime. Thus the orders of the subgroups are factors of 2q:
236
     * namely 1, 2, q and 2q.
237
     *
238
     * We check that the peer's public value isn't zero (which isn't in the
239
     * group), one (subgroup of order one) or p-1 (subgroup of order 2). We
240
     * also check that the public value is less than p, to avoid being fooled
241
     * by values like p+1 or 2*p-1.
242
     *
243
     * Thus we must be operating in the subgroup of size q or 2q. */
244
0
    if (mp_cmp_d(&Yb, 1) <= 0 ||
245
0
        mp_cmp(&Yb, &psub1) >= 0) {
246
0
        err = MP_BADARG;
247
0
        goto cleanup;
248
0
    }
249
250
    /* ZZ = (Yb)**Xa mod p */
251
0
    CHECK_MPI_OK(mp_exptmod(&Yb, &Xa, &p, &ZZ));
252
    /* number of bytes in the derived secret */
253
0
    len = mp_unsigned_octet_size(&ZZ);
254
0
    if (len <= 0) {
255
0
        err = MP_BADARG;
256
0
        goto cleanup;
257
0
    }
258
259
    /*
260
     * We check to make sure that ZZ is not equal to 0, 1 or -1 mod p.
261
     * This helps guard against small subgroup attacks, since an attacker
262
     * using a subgroup of size N will produce 0, 1 or -1 with probability 1/N.
263
     * When the protocol is executed within a properly large subgroup, the
264
     * probability of this result will be negligibly small.  For example,
265
     * with a safe prime of the form 2q+1, the probability will be 1/q.
266
     *
267
     * We return MP_BADARG because this is probably the result of a bad
268
     * public value or a bad prime having been provided.
269
     */
270
0
    if (mp_cmp_d(&ZZ, 0) == 0 || mp_cmp_d(&ZZ, 1) == 0 ||
271
0
        mp_cmp(&ZZ, &psub1) == 0) {
272
0
        err = MP_BADARG;
273
0
        goto cleanup;
274
0
    }
275
276
    /* allocate a buffer which can hold the entire derived secret. */
277
0
    secret = PORT_Alloc(len);
278
0
    if (secret == NULL) {
279
0
        err = MP_MEM;
280
0
        goto cleanup;
281
0
    }
282
    /* grab the derived secret */
283
0
    err = mp_to_unsigned_octets(&ZZ, secret, len);
284
0
    if (err >= 0)
285
0
        err = MP_OKAY;
286
    /*
287
    ** if outBytes is 0 take all of the bytes from the derived secret.
288
    ** if outBytes is not 0 take exactly outBytes from the derived secret, zero
289
    ** pad at the beginning if necessary, and truncate beginning bytes
290
    ** if necessary.
291
    */
292
0
    if (outBytes > 0)
293
0
        nb = outBytes;
294
0
    else
295
0
        nb = len;
296
0
    if (SECITEM_AllocItem(NULL, derivedSecret, nb) == NULL) {
297
0
        err = MP_MEM;
298
0
        goto cleanup;
299
0
    }
300
0
    if (len < nb) {
301
0
        unsigned int offset = nb - len;
302
0
        memset(derivedSecret->data, 0, offset);
303
0
        memcpy(derivedSecret->data + offset, secret, len);
304
0
    } else {
305
0
        memcpy(derivedSecret->data, secret + len - nb, nb);
306
0
    }
307
0
cleanup:
308
0
    mp_clear(&p);
309
0
    mp_clear(&Xa);
310
0
    mp_clear(&Yb);
311
0
    mp_clear(&ZZ);
312
0
    mp_clear(&psub1);
313
0
    if (secret) {
314
        /* free the buffer allocated for the full secret. */
315
0
        PORT_ZFree(secret, len);
316
0
    }
317
0
    if (err) {
318
0
        MP_TO_SEC_ERROR(err);
319
0
        if (derivedSecret->data)
320
0
            PORT_ZFree(derivedSecret->data, derivedSecret->len);
321
0
        return SECFailure;
322
0
    }
323
0
    return SECSuccess;
324
0
}
325
326
SECStatus
327
KEA_Derive(SECItem *prime,
328
           SECItem *public1,
329
           SECItem *public2,
330
           SECItem *private1,
331
           SECItem *private2,
332
           SECItem *derivedSecret)
333
0
{
334
0
    mp_int p, Y, R, r, x, t, u, w;
335
0
    mp_err err;
336
0
    unsigned char *secret = NULL;
337
0
    unsigned int len = 0, offset;
338
0
    if (!prime || !public1 || !public2 || !private1 || !private2 ||
339
0
        !derivedSecret) {
340
0
        PORT_SetError(SEC_ERROR_INVALID_ARGS);
341
0
        return SECFailure;
342
0
    }
343
0
    memset(derivedSecret, 0, sizeof *derivedSecret);
344
0
    MP_DIGITS(&p) = 0;
345
0
    MP_DIGITS(&Y) = 0;
346
0
    MP_DIGITS(&R) = 0;
347
0
    MP_DIGITS(&r) = 0;
348
0
    MP_DIGITS(&x) = 0;
349
0
    MP_DIGITS(&t) = 0;
350
0
    MP_DIGITS(&u) = 0;
351
0
    MP_DIGITS(&w) = 0;
352
0
    CHECK_MPI_OK(mp_init(&p));
353
0
    CHECK_MPI_OK(mp_init(&Y));
354
0
    CHECK_MPI_OK(mp_init(&R));
355
0
    CHECK_MPI_OK(mp_init(&r));
356
0
    CHECK_MPI_OK(mp_init(&x));
357
0
    CHECK_MPI_OK(mp_init(&t));
358
0
    CHECK_MPI_OK(mp_init(&u));
359
0
    CHECK_MPI_OK(mp_init(&w));
360
0
    SECITEM_TO_MPINT(*prime, &p);
361
0
    SECITEM_TO_MPINT(*public1, &Y);
362
0
    SECITEM_TO_MPINT(*public2, &R);
363
0
    SECITEM_TO_MPINT(*private1, &r);
364
0
    SECITEM_TO_MPINT(*private2, &x);
365
    /* t = DH(Y, r, p) = Y ** r mod p */
366
0
    CHECK_MPI_OK(mp_exptmod(&Y, &r, &p, &t));
367
    /* u = DH(R, x, p) = R ** x mod p */
368
0
    CHECK_MPI_OK(mp_exptmod(&R, &x, &p, &u));
369
    /* w = (t + u) mod p */
370
0
    CHECK_MPI_OK(mp_addmod(&t, &u, &p, &w));
371
    /* allocate a buffer for the full derived secret */
372
0
    len = mp_unsigned_octet_size(&w);
373
0
    secret = PORT_Alloc(len);
374
0
    if (secret == NULL) {
375
0
        err = MP_MEM;
376
0
        goto cleanup;
377
0
    }
378
    /* grab the secret */
379
0
    err = mp_to_unsigned_octets(&w, secret, len);
380
0
    if (err > 0)
381
0
        err = MP_OKAY;
382
    /* allocate output buffer */
383
0
    if (SECITEM_AllocItem(NULL, derivedSecret, KEA_DERIVED_SECRET_LEN) == NULL) {
384
0
        err = MP_MEM;
385
0
        goto cleanup;
386
0
    }
387
0
    memset(derivedSecret->data, 0, derivedSecret->len);
388
    /* copy in the 128 lsb of the secret */
389
0
    if (len >= KEA_DERIVED_SECRET_LEN) {
390
0
        memcpy(derivedSecret->data, secret + (len - KEA_DERIVED_SECRET_LEN),
391
0
               KEA_DERIVED_SECRET_LEN);
392
0
    } else {
393
0
        offset = KEA_DERIVED_SECRET_LEN - len;
394
0
        memcpy(derivedSecret->data + offset, secret, len);
395
0
    }
396
0
cleanup:
397
0
    mp_clear(&p);
398
0
    mp_clear(&Y);
399
0
    mp_clear(&R);
400
0
    mp_clear(&r);
401
0
    mp_clear(&x);
402
0
    mp_clear(&t);
403
0
    mp_clear(&u);
404
0
    mp_clear(&w);
405
0
    if (secret)
406
0
        PORT_ZFree(secret, len);
407
0
    if (err) {
408
0
        MP_TO_SEC_ERROR(err);
409
0
        if (derivedSecret->data)
410
0
            PORT_ZFree(derivedSecret->data, derivedSecret->len);
411
0
        return SECFailure;
412
0
    }
413
0
    return SECSuccess;
414
0
}
415
416
/* Test counts based on the fact the prime and subprime
417
 * were given to us */
418
static int
419
dh_prime_testcount(int prime_length)
420
0
{
421
0
    if (prime_length < 1024) {
422
0
        return 50;
423
0
    } else if (prime_length < 2048) {
424
0
        return 40;
425
0
    } else if (prime_length < 3072) {
426
0
        return 56;
427
0
    }
428
0
    return 64;
429
0
}
430
431
PRBool
432
KEA_PrimeCheck(SECItem *prime)
433
0
{
434
0
    mp_int p;
435
0
    mp_err err = 0;
436
0
    MP_DIGITS(&p) = 0;
437
0
    CHECK_MPI_OK(mp_init(&p));
438
0
    SECITEM_TO_MPINT(*prime, &p);
439
0
    CHECK_MPI_OK(mpp_pprime_secure(&p, dh_prime_testcount(prime->len)));
440
0
cleanup:
441
0
    mp_clear(&p);
442
0
    return err ? PR_FALSE : PR_TRUE;
443
0
}
444
445
PRBool
446
KEA_Verify(SECItem *Y, SECItem *prime, SECItem *subPrime)
447
0
{
448
0
    mp_int p, q, y, r;
449
0
    mp_err err;
450
0
    int cmp = 1; /* default is false */
451
0
    if (!Y || !prime || !subPrime) {
452
0
        PORT_SetError(SEC_ERROR_INVALID_ARGS);
453
0
        return SECFailure;
454
0
    }
455
0
    MP_DIGITS(&p) = 0;
456
0
    MP_DIGITS(&q) = 0;
457
0
    MP_DIGITS(&y) = 0;
458
0
    MP_DIGITS(&r) = 0;
459
0
    CHECK_MPI_OK(mp_init(&p));
460
0
    CHECK_MPI_OK(mp_init(&q));
461
0
    CHECK_MPI_OK(mp_init(&y));
462
0
    CHECK_MPI_OK(mp_init(&r));
463
0
    SECITEM_TO_MPINT(*prime, &p);
464
0
    SECITEM_TO_MPINT(*subPrime, &q);
465
0
    SECITEM_TO_MPINT(*Y, &y);
466
    /* compute r = y**q mod p */
467
0
    CHECK_MPI_OK(mp_exptmod(&y, &q, &p, &r));
468
    /* compare to 1 */
469
0
    cmp = mp_cmp_d(&r, 1);
470
0
cleanup:
471
0
    mp_clear(&p);
472
0
    mp_clear(&q);
473
0
    mp_clear(&y);
474
0
    mp_clear(&r);
475
0
    if (err) {
476
0
        MP_TO_SEC_ERROR(err);
477
0
        return PR_FALSE;
478
0
    }
479
0
    return (cmp == 0) ? PR_TRUE : PR_FALSE;
480
0
}