1// Copyright 1995-2016 The OpenSSL Project Authors. All Rights Reserved.
2//
3// Licensed under the Apache License, Version 2.0 (the "License");
4// you may not use this file except in compliance with the License.
5// You may obtain a copy of the License at
6//
7//     https://www.apache.org/licenses/LICENSE-2.0
8//
9// Unless required by applicable law or agreed to in writing, software
10// distributed under the License is distributed on an "AS IS" BASIS,
11// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
12// See the License for the specific language governing permissions and
13// limitations under the License.
14
15#include <openssl/dh.h>
16
17#include <openssl/bn.h>
18#include <openssl/err.h>
19
20#include "../bn/internal.h"
21#include "internal.h"
22
23
24static_assert(OPENSSL_DH_MAX_MODULUS_BITS <=
25                  BN_MONTGOMERY_MAX_WORDS * BN_BITS2,
26              "Max DH size too big for Montgomery arithmetic");
27
28int dh_check_params_fast(const DH *dh) {
29  // Most operations scale with p and q.
30  if (BN_is_negative(dh->p) || !BN_is_odd(dh->p) ||
31      BN_num_bits(dh->p) > OPENSSL_DH_MAX_MODULUS_BITS) {
32    OPENSSL_PUT_ERROR(DH, DH_R_INVALID_PARAMETERS);
33    return 0;
34  }
35
36  // q must be bounded by p.
37  if (dh->q != NULL && (BN_is_negative(dh->q) || BN_ucmp(dh->q, dh->p) > 0)) {
38    OPENSSL_PUT_ERROR(DH, DH_R_INVALID_PARAMETERS);
39    return 0;
40  }
41
42  // g must be an element of p's multiplicative group.
43  if (BN_is_negative(dh->g) || BN_is_zero(dh->g) ||
44      BN_ucmp(dh->g, dh->p) >= 0) {
45    OPENSSL_PUT_ERROR(DH, DH_R_INVALID_PARAMETERS);
46    return 0;
47  }
48
49  return 1;
50}
51
52int DH_check_pub_key(const DH *dh, const BIGNUM *pub_key, int *out_flags) {
53  *out_flags = 0;
54  if (!dh_check_params_fast(dh)) {
55    return 0;
56  }
57
58  bssl::UniquePtr<BN_CTX> ctx(BN_CTX_new());
59  if (ctx == NULL) {
60    return 0;
61  }
62  bssl::BN_CTXScope scope(ctx.get());
63
64  // Check |pub_key| is greater than 1.
65  if (BN_cmp(pub_key, BN_value_one()) <= 0) {
66    *out_flags |= DH_CHECK_PUBKEY_TOO_SMALL;
67  }
68
69  // Check |pub_key| is less than |dh->p| - 1.
70  BIGNUM *tmp = BN_CTX_get(ctx.get());
71  if (tmp == NULL ||
72      !BN_copy(tmp, dh->p) ||
73      !BN_sub_word(tmp, 1)) {
74    return 0;
75  }
76  if (BN_cmp(pub_key, tmp) >= 0) {
77    *out_flags |= DH_CHECK_PUBKEY_TOO_LARGE;
78  }
79
80  if (dh->q != NULL) {
81    // Check |pub_key|^|dh->q| is 1 mod |dh->p|. This is necessary for RFC 5114
82    // groups which are not safe primes but pick a generator on a prime-order
83    // subgroup of size |dh->q|.
84    if (!BN_mod_exp_mont(tmp, pub_key, dh->q, dh->p, ctx.get(), NULL)) {
85      return 0;
86    }
87    if (!BN_is_one(tmp)) {
88      *out_flags |= DH_CHECK_PUBKEY_INVALID;
89    }
90  }
91
92  return 1;
93}
94
95int DH_check(const DH *dh, int *out_flags) {
96  *out_flags = 0;
97  if (!dh_check_params_fast(dh)) {
98    return 0;
99  }
100
101  // Check that p is a safe prime and if g is 2, 3 or 5, check that it is a
102  // suitable generator where:
103  //   for 2, p mod 24 == 11
104  //   for 3, p mod 12 == 5
105  //   for 5, p mod 10 == 3 or 7
106  // should hold.
107  bssl::UniquePtr<BN_CTX> ctx(BN_CTX_new());
108  if (ctx == nullptr) {
109    return 0;
110  }
111  bssl::BN_CTXScope scope(ctx.get());
112  BIGNUM *t1 = BN_CTX_get(ctx.get());
113  if (t1 == nullptr) {
114    return 0;
115  }
116  BIGNUM *t2 = BN_CTX_get(ctx.get());
117  if (t2 == nullptr) {
118    return 0;
119  }
120
121  if (dh->q) {
122    if (BN_cmp(dh->g, BN_value_one()) <= 0) {
123      *out_flags |= DH_CHECK_NOT_SUITABLE_GENERATOR;
124    } else if (BN_cmp(dh->g, dh->p) >= 0) {
125      *out_flags |= DH_CHECK_NOT_SUITABLE_GENERATOR;
126    } else {
127      // Check g^q == 1 mod p
128      if (!BN_mod_exp_mont(t1, dh->g, dh->q, dh->p, ctx.get(), nullptr)) {
129        return 0;
130      }
131      if (!BN_is_one(t1)) {
132        *out_flags |= DH_CHECK_NOT_SUITABLE_GENERATOR;
133      }
134    }
135    int r = BN_is_prime_ex(dh->q, BN_prime_checks_for_validation, ctx.get(),
136                           nullptr);
137    if (r < 0) {
138      return 0;
139    }
140    if (!r) {
141      *out_flags |= DH_CHECK_Q_NOT_PRIME;
142    }
143    // Check p == 1 mod q  i.e. q divides p - 1
144    if (!BN_div(t1, t2, dh->p, dh->q, ctx.get())) {
145      return 0;
146    }
147    if (!BN_is_one(t2)) {
148      *out_flags |= DH_CHECK_INVALID_Q_VALUE;
149    }
150  } else if (BN_is_word(dh->g, DH_GENERATOR_2)) {
151    BN_ULONG l = BN_mod_word(dh->p, 24);
152    if (l == (BN_ULONG)-1) {
153      return 0;
154    }
155    if (l != 11) {
156      *out_flags |= DH_CHECK_NOT_SUITABLE_GENERATOR;
157    }
158  } else if (BN_is_word(dh->g, DH_GENERATOR_5)) {
159    BN_ULONG l = BN_mod_word(dh->p, 10);
160    if (l == (BN_ULONG)-1) {
161      return 0;
162    }
163    if (l != 3 && l != 7) {
164      *out_flags |= DH_CHECK_NOT_SUITABLE_GENERATOR;
165    }
166  } else {
167    *out_flags |= DH_CHECK_UNABLE_TO_CHECK_GENERATOR;
168  }
169
170  int r =
171      BN_is_prime_ex(dh->p, BN_prime_checks_for_validation, ctx.get(), nullptr);
172  if (r < 0) {
173    return 0;
174  }
175  if (!r) {
176    *out_flags |= DH_CHECK_P_NOT_PRIME;
177  } else if (!dh->q) {
178    if (!BN_rshift1(t1, dh->p)) {
179      return 0;
180    }
181    r = BN_is_prime_ex(t1, BN_prime_checks_for_validation, ctx.get(), nullptr);
182    if (r < 0) {
183      return 0;
184    }
185    if (!r) {
186      *out_flags |= DH_CHECK_P_NOT_SAFE_PRIME;
187    }
188  }
189  return 1;
190}
191