Use fewer primes for the trial division
[openssl.git] / crypto / dh / dh_check.c
1 /*
2  * Copyright 1995-2019 The OpenSSL Project Authors. All Rights Reserved.
3  *
4  * Licensed under the Apache License 2.0 (the "License").  You may not use
5  * this file except in compliance with the License.  You can obtain a copy
6  * in the file LICENSE in the source distribution or at
7  * https://www.openssl.org/source/license.html
8  */
9
10 #include <stdio.h>
11 #include "internal/cryptlib.h"
12 #include <openssl/bn.h>
13 #include "dh_local.h"
14
15 # define DH_NUMBER_ITERATIONS_FOR_PRIME 64
16
17 /*-
18  * Check that p and g are suitable enough
19  *
20  * p is odd
21  * 1 < g < p - 1
22  */
23 int DH_check_params_ex(const DH *dh)
24 {
25     int errflags = 0;
26
27     if (!DH_check_params(dh, &errflags))
28         return 0;
29
30     if ((errflags & DH_CHECK_P_NOT_PRIME) != 0)
31         DHerr(DH_F_DH_CHECK_PARAMS_EX, DH_R_CHECK_P_NOT_PRIME);
32     if ((errflags & DH_NOT_SUITABLE_GENERATOR) != 0)
33         DHerr(DH_F_DH_CHECK_PARAMS_EX, DH_R_NOT_SUITABLE_GENERATOR);
34     if ((errflags & DH_MODULUS_TOO_SMALL) != 0)
35         DHerr(DH_F_DH_CHECK_PARAMS_EX, DH_R_MODULUS_TOO_SMALL);
36     if ((errflags & DH_MODULUS_TOO_LARGE) != 0)
37         DHerr(DH_F_DH_CHECK_PARAMS_EX, DH_R_MODULUS_TOO_LARGE);
38
39     return errflags == 0;
40 }
41
42 int DH_check_params(const DH *dh, int *ret)
43 {
44     int ok = 0;
45     BIGNUM *tmp = NULL;
46     BN_CTX *ctx = NULL;
47
48     *ret = 0;
49     ctx = BN_CTX_new();
50     if (ctx == NULL)
51         goto err;
52     BN_CTX_start(ctx);
53     tmp = BN_CTX_get(ctx);
54     if (tmp == NULL)
55         goto err;
56
57     if (!BN_is_odd(dh->p))
58         *ret |= DH_CHECK_P_NOT_PRIME;
59     if (BN_is_negative(dh->g) || BN_is_zero(dh->g) || BN_is_one(dh->g))
60         *ret |= DH_NOT_SUITABLE_GENERATOR;
61     if (BN_copy(tmp, dh->p) == NULL || !BN_sub_word(tmp, 1))
62         goto err;
63     if (BN_cmp(dh->g, tmp) >= 0)
64         *ret |= DH_NOT_SUITABLE_GENERATOR;
65     if (BN_num_bits(dh->p) < DH_MIN_MODULUS_BITS)
66         *ret |= DH_MODULUS_TOO_SMALL;
67     if (BN_num_bits(dh->p) > OPENSSL_DH_MAX_MODULUS_BITS)
68         *ret |= DH_MODULUS_TOO_LARGE;
69
70     ok = 1;
71  err:
72     BN_CTX_end(ctx);
73     BN_CTX_free(ctx);
74     return ok;
75 }
76
77 /*-
78  * Check that p is a safe prime and
79  * g is a suitable generator.
80  */
81 int DH_check_ex(const DH *dh)
82 {
83     int errflags = 0;
84
85     if (!DH_check(dh, &errflags))
86         return 0;
87
88     if ((errflags & DH_NOT_SUITABLE_GENERATOR) != 0)
89         DHerr(DH_F_DH_CHECK_EX, DH_R_NOT_SUITABLE_GENERATOR);
90     if ((errflags & DH_CHECK_Q_NOT_PRIME) != 0)
91         DHerr(DH_F_DH_CHECK_EX, DH_R_CHECK_Q_NOT_PRIME);
92     if ((errflags & DH_CHECK_INVALID_Q_VALUE) != 0)
93         DHerr(DH_F_DH_CHECK_EX, DH_R_CHECK_INVALID_Q_VALUE);
94     if ((errflags & DH_CHECK_INVALID_J_VALUE) != 0)
95         DHerr(DH_F_DH_CHECK_EX, DH_R_CHECK_INVALID_J_VALUE);
96     if ((errflags & DH_UNABLE_TO_CHECK_GENERATOR) != 0)
97         DHerr(DH_F_DH_CHECK_EX, DH_R_UNABLE_TO_CHECK_GENERATOR);
98     if ((errflags & DH_CHECK_P_NOT_PRIME) != 0)
99         DHerr(DH_F_DH_CHECK_EX, DH_R_CHECK_P_NOT_PRIME);
100     if ((errflags & DH_CHECK_P_NOT_SAFE_PRIME) != 0)
101         DHerr(DH_F_DH_CHECK_EX, DH_R_CHECK_P_NOT_SAFE_PRIME);
102     if ((errflags & DH_MODULUS_TOO_SMALL) != 0)
103         DHerr(DH_F_DH_CHECK_EX, DH_R_MODULUS_TOO_SMALL);
104     if ((errflags & DH_MODULUS_TOO_LARGE) != 0)
105         DHerr(DH_F_DH_CHECK_EX, DH_R_MODULUS_TOO_LARGE);
106
107     return errflags == 0;
108 }
109
110 int DH_check(const DH *dh, int *ret)
111 {
112     int ok = 0, r;
113     BN_CTX *ctx = NULL;
114     BIGNUM *t1 = NULL, *t2 = NULL;
115
116     if (!DH_check_params(dh, ret))
117         return 0;
118
119     ctx = BN_CTX_new();
120     if (ctx == NULL)
121         goto err;
122     BN_CTX_start(ctx);
123     t1 = BN_CTX_get(ctx);
124     t2 = BN_CTX_get(ctx);
125     if (t2 == NULL)
126         goto err;
127
128     if (dh->q) {
129         if (BN_cmp(dh->g, BN_value_one()) <= 0)
130             *ret |= DH_NOT_SUITABLE_GENERATOR;
131         else if (BN_cmp(dh->g, dh->p) >= 0)
132             *ret |= DH_NOT_SUITABLE_GENERATOR;
133         else {
134             /* Check g^q == 1 mod p */
135             if (!BN_mod_exp(t1, dh->g, dh->q, dh->p, ctx))
136                 goto err;
137             if (!BN_is_one(t1))
138                 *ret |= DH_NOT_SUITABLE_GENERATOR;
139         }
140         r = BN_is_prime_ex(dh->q, DH_NUMBER_ITERATIONS_FOR_PRIME, ctx, NULL);
141         if (r < 0)
142             goto err;
143         if (!r)
144             *ret |= DH_CHECK_Q_NOT_PRIME;
145         /* Check p == 1 mod q  i.e. q divides p - 1 */
146         if (!BN_div(t1, t2, dh->p, dh->q, ctx))
147             goto err;
148         if (!BN_is_one(t2))
149             *ret |= DH_CHECK_INVALID_Q_VALUE;
150         if (dh->j && BN_cmp(dh->j, t1))
151             *ret |= DH_CHECK_INVALID_J_VALUE;
152     }
153
154     r = BN_is_prime_ex(dh->p, DH_NUMBER_ITERATIONS_FOR_PRIME, ctx, NULL);
155     if (r < 0)
156         goto err;
157     if (!r)
158         *ret |= DH_CHECK_P_NOT_PRIME;
159     else if (!dh->q) {
160         if (!BN_rshift1(t1, dh->p))
161             goto err;
162         r = BN_is_prime_ex(t1, DH_NUMBER_ITERATIONS_FOR_PRIME, ctx, NULL);
163         if (r < 0)
164             goto err;
165         if (!r)
166             *ret |= DH_CHECK_P_NOT_SAFE_PRIME;
167     }
168     ok = 1;
169  err:
170     BN_CTX_end(ctx);
171     BN_CTX_free(ctx);
172     return ok;
173 }
174
175 int DH_check_pub_key_ex(const DH *dh, const BIGNUM *pub_key)
176 {
177     int errflags = 0;
178
179     if (!DH_check_pub_key(dh, pub_key, &errflags))
180         return 0;
181
182     if ((errflags & DH_CHECK_PUBKEY_TOO_SMALL) != 0)
183         DHerr(DH_F_DH_CHECK_PUB_KEY_EX, DH_R_CHECK_PUBKEY_TOO_SMALL);
184     if ((errflags & DH_CHECK_PUBKEY_TOO_LARGE) != 0)
185         DHerr(DH_F_DH_CHECK_PUB_KEY_EX, DH_R_CHECK_PUBKEY_TOO_LARGE);
186     if ((errflags & DH_CHECK_PUBKEY_INVALID) != 0)
187         DHerr(DH_F_DH_CHECK_PUB_KEY_EX, DH_R_CHECK_PUBKEY_INVALID);
188
189     return errflags == 0;
190 }
191
192 int DH_check_pub_key(const DH *dh, const BIGNUM *pub_key, int *ret)
193 {
194     int ok = 0;
195     BIGNUM *tmp = NULL;
196     BN_CTX *ctx = NULL;
197
198     *ret = 0;
199     ctx = BN_CTX_new();
200     if (ctx == NULL)
201         goto err;
202     BN_CTX_start(ctx);
203     tmp = BN_CTX_get(ctx);
204     if (tmp == NULL || !BN_set_word(tmp, 1))
205         goto err;
206     if (BN_cmp(pub_key, tmp) <= 0)
207         *ret |= DH_CHECK_PUBKEY_TOO_SMALL;
208     if (BN_copy(tmp, dh->p) == NULL || !BN_sub_word(tmp, 1))
209         goto err;
210     if (BN_cmp(pub_key, tmp) >= 0)
211         *ret |= DH_CHECK_PUBKEY_TOO_LARGE;
212
213     if (dh->q != NULL) {
214         /* Check pub_key^q == 1 mod p */
215         if (!BN_mod_exp(tmp, pub_key, dh->q, dh->p, ctx))
216             goto err;
217         if (!BN_is_one(tmp))
218             *ret |= DH_CHECK_PUBKEY_INVALID;
219     }
220
221     ok = 1;
222  err:
223     BN_CTX_end(ctx);
224     BN_CTX_free(ctx);
225     return ok;
226 }