1 /* $OpenBSD: dh.c,v 1.53 2013/11/21 00:45:44 djm Exp $ */ 2 /* 3 * Copyright (c) 2000 Niels Provos. All rights reserved. 4 * 5 * Redistribution and use in source and binary forms, with or without 6 * modification, are permitted provided that the following conditions 7 * are met: 8 * 1. Redistributions of source code must retain the above copyright 9 * notice, this list of conditions and the following disclaimer. 10 * 2. Redistributions in binary form must reproduce the above copyright 11 * notice, this list of conditions and the following disclaimer in the 12 * documentation and/or other materials provided with the distribution. 13 * 14 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR 15 * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES 16 * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. 17 * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT, 18 * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT 19 * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 20 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 21 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 22 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF 23 * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 24 */ 25 26 #include <sys/param.h> 27 28 #include <openssl/bn.h> 29 #include <openssl/dh.h> 30 31 #include <stdio.h> 32 #include <stdlib.h> 33 #include <string.h> 34 35 #include "dh.h" 36 #include "pathnames.h" 37 #include "log.h" 38 #include "misc.h" 39 40 static int 41 parse_prime(int linenum, char *line, struct dhgroup *dhg) 42 { 43 char *cp, *arg; 44 char *strsize, *gen, *prime; 45 const char *errstr = NULL; 46 long long n; 47 48 dhg->p = dhg->g = NULL; 49 cp = line; 50 if ((arg = strdelim(&cp)) == NULL) 51 return 0; 52 /* Ignore leading whitespace */ 53 if (*arg == '\0') 54 arg = strdelim(&cp); 55 if (!arg || !*arg || *arg == '#') 56 return 0; 57 58 /* time */ 59 if (cp == NULL || *arg == '\0') 60 goto truncated; 61 arg = strsep(&cp, " "); /* type */ 62 if (cp == NULL || *arg == '\0') 63 goto truncated; 64 /* Ensure this is a safe prime */ 65 n = strtonum(arg, 0, 5, &errstr); 66 if (errstr != NULL || n != MODULI_TYPE_SAFE) { 67 error("moduli:%d: type is not %d", linenum, MODULI_TYPE_SAFE); 68 goto fail; 69 } 70 arg = strsep(&cp, " "); /* tests */ 71 if (cp == NULL || *arg == '\0') 72 goto truncated; 73 /* Ensure prime has been tested and is not composite */ 74 n = strtonum(arg, 0, 0x1f, &errstr); 75 if (errstr != NULL || 76 (n & MODULI_TESTS_COMPOSITE) || !(n & ~MODULI_TESTS_COMPOSITE)) { 77 error("moduli:%d: invalid moduli tests flag", linenum); 78 goto fail; 79 } 80 arg = strsep(&cp, " "); /* tries */ 81 if (cp == NULL || *arg == '\0') 82 goto truncated; 83 n = strtonum(arg, 0, 1<<30, &errstr); 84 if (errstr != NULL || n == 0) { 85 error("moduli:%d: invalid primality trial count", linenum); 86 goto fail; 87 } 88 strsize = strsep(&cp, " "); /* size */ 89 if (cp == NULL || *strsize == '\0' || 90 (dhg->size = (int)strtonum(strsize, 0, 64*1024, &errstr)) == 0 || 91 errstr) { 92 error("moduli:%d: invalid prime length", linenum); 93 goto fail; 94 } 95 /* The whole group is one bit larger */ 96 dhg->size++; 97 gen = strsep(&cp, " "); /* gen */ 98 if (cp == NULL || *gen == '\0') 99 goto truncated; 100 prime = strsep(&cp, " "); /* prime */ 101 if (cp != NULL || *prime == '\0') { 102 truncated: 103 error("moduli:%d: truncated", linenum); 104 goto fail; 105 } 106 107 if ((dhg->g = BN_new()) == NULL) 108 fatal("parse_prime: BN_new failed"); 109 if ((dhg->p = BN_new()) == NULL) 110 fatal("parse_prime: BN_new failed"); 111 if (BN_hex2bn(&dhg->g, gen) == 0) { 112 error("moduli:%d: could not parse generator value", linenum); 113 goto fail; 114 } 115 if (BN_hex2bn(&dhg->p, prime) == 0) { 116 error("moduli:%d: could not parse prime value", linenum); 117 goto fail; 118 } 119 if (BN_num_bits(dhg->p) != dhg->size) { 120 error("moduli:%d: prime has wrong size: actual %d listed %d", 121 linenum, BN_num_bits(dhg->p), dhg->size - 1); 122 goto fail; 123 } 124 if (BN_cmp(dhg->g, BN_value_one()) <= 0) { 125 error("moduli:%d: generator is invalid", linenum); 126 goto fail; 127 } 128 129 return 1; 130 131 fail: 132 if (dhg->g != NULL) 133 BN_clear_free(dhg->g); 134 if (dhg->p != NULL) 135 BN_clear_free(dhg->p); 136 dhg->g = dhg->p = NULL; 137 error("Bad prime description in line %d", linenum); 138 return 0; 139 } 140 141 DH * 142 choose_dh(int min, int wantbits, int max) 143 { 144 FILE *f; 145 char line[4096]; 146 int best, bestcount, which; 147 int linenum; 148 struct dhgroup dhg; 149 150 if ((f = fopen(_PATH_DH_MODULI, "r")) == NULL && 151 (f = fopen(_PATH_DH_PRIMES, "r")) == NULL) { 152 logit("WARNING: %s does not exist, using fixed modulus", 153 _PATH_DH_MODULI); 154 return (dh_new_group14()); 155 } 156 157 linenum = 0; 158 best = bestcount = 0; 159 while (fgets(line, sizeof(line), f)) { 160 linenum++; 161 if (!parse_prime(linenum, line, &dhg)) 162 continue; 163 BN_clear_free(dhg.g); 164 BN_clear_free(dhg.p); 165 166 if (dhg.size > max || dhg.size < min) 167 continue; 168 169 if ((dhg.size > wantbits && dhg.size < best) || 170 (dhg.size > best && best < wantbits)) { 171 best = dhg.size; 172 bestcount = 0; 173 } 174 if (dhg.size == best) 175 bestcount++; 176 } 177 rewind(f); 178 179 if (bestcount == 0) { 180 fclose(f); 181 logit("WARNING: no suitable primes in %s", _PATH_DH_PRIMES); 182 return (dh_new_group14()); 183 } 184 185 linenum = 0; 186 which = arc4random_uniform(bestcount); 187 while (fgets(line, sizeof(line), f)) { 188 if (!parse_prime(linenum, line, &dhg)) 189 continue; 190 if ((dhg.size > max || dhg.size < min) || 191 dhg.size != best || 192 linenum++ != which) { 193 BN_clear_free(dhg.g); 194 BN_clear_free(dhg.p); 195 continue; 196 } 197 break; 198 } 199 fclose(f); 200 if (linenum != which+1) 201 fatal("WARNING: line %d disappeared in %s, giving up", 202 which, _PATH_DH_PRIMES); 203 204 return (dh_new_group(dhg.g, dhg.p)); 205 } 206 207 /* diffie-hellman-groupN-sha1 */ 208 209 int 210 dh_pub_is_valid(DH *dh, BIGNUM *dh_pub) 211 { 212 int i; 213 int n = BN_num_bits(dh_pub); 214 int bits_set = 0; 215 BIGNUM *tmp; 216 217 if (dh_pub->neg) { 218 logit("invalid public DH value: negative"); 219 return 0; 220 } 221 if (BN_cmp(dh_pub, BN_value_one()) != 1) { /* pub_exp <= 1 */ 222 logit("invalid public DH value: <= 1"); 223 return 0; 224 } 225 226 if ((tmp = BN_new()) == NULL) { 227 error("%s: BN_new failed", __func__); 228 return 0; 229 } 230 if (!BN_sub(tmp, dh->p, BN_value_one()) || 231 BN_cmp(dh_pub, tmp) != -1) { /* pub_exp > p-2 */ 232 BN_clear_free(tmp); 233 logit("invalid public DH value: >= p-1"); 234 return 0; 235 } 236 BN_clear_free(tmp); 237 238 for (i = 0; i <= n; i++) 239 if (BN_is_bit_set(dh_pub, i)) 240 bits_set++; 241 debug2("bits set: %d/%d", bits_set, BN_num_bits(dh->p)); 242 243 /* if g==2 and bits_set==1 then computing log_g(dh_pub) is trivial */ 244 if (bits_set > 1) 245 return 1; 246 247 logit("invalid public DH value (%d/%d)", bits_set, BN_num_bits(dh->p)); 248 return 0; 249 } 250 251 void 252 dh_gen_key(DH *dh, int need) 253 { 254 int pbits; 255 256 if (need <= 0) 257 fatal("%s: need <= 0", __func__); 258 if (dh->p == NULL) 259 fatal("%s: dh->p == NULL", __func__); 260 if ((pbits = BN_num_bits(dh->p)) <= 0) 261 fatal("%s: bits(p) <= 0", __func__); 262 dh->length = MIN(need * 2, pbits - 1); 263 if (DH_generate_key(dh) == 0) 264 fatal("%s: key generation failed", __func__); 265 if (!dh_pub_is_valid(dh, dh->pub_key)) 266 fatal("%s: generated invalid key", __func__); 267 } 268 269 DH * 270 dh_new_group_asc(const char *gen, const char *modulus) 271 { 272 DH *dh; 273 274 if ((dh = DH_new()) == NULL) 275 fatal("dh_new_group_asc: DH_new"); 276 277 if (BN_hex2bn(&dh->p, modulus) == 0) 278 fatal("BN_hex2bn p"); 279 if (BN_hex2bn(&dh->g, gen) == 0) 280 fatal("BN_hex2bn g"); 281 282 return (dh); 283 } 284 285 /* 286 * This just returns the group, we still need to generate the exchange 287 * value. 288 */ 289 290 DH * 291 dh_new_group(BIGNUM *gen, BIGNUM *modulus) 292 { 293 DH *dh; 294 295 if ((dh = DH_new()) == NULL) 296 fatal("dh_new_group: DH_new"); 297 dh->p = modulus; 298 dh->g = gen; 299 300 return (dh); 301 } 302 303 DH * 304 dh_new_group1(void) 305 { 306 static char *gen = "2", *group1 = 307 "FFFFFFFF" "FFFFFFFF" "C90FDAA2" "2168C234" "C4C6628B" "80DC1CD1" 308 "29024E08" "8A67CC74" "020BBEA6" "3B139B22" "514A0879" "8E3404DD" 309 "EF9519B3" "CD3A431B" "302B0A6D" "F25F1437" "4FE1356D" "6D51C245" 310 "E485B576" "625E7EC6" "F44C42E9" "A637ED6B" "0BFF5CB6" "F406B7ED" 311 "EE386BFB" "5A899FA5" "AE9F2411" "7C4B1FE6" "49286651" "ECE65381" 312 "FFFFFFFF" "FFFFFFFF"; 313 314 return (dh_new_group_asc(gen, group1)); 315 } 316 317 DH * 318 dh_new_group14(void) 319 { 320 static char *gen = "2", *group14 = 321 "FFFFFFFF" "FFFFFFFF" "C90FDAA2" "2168C234" "C4C6628B" "80DC1CD1" 322 "29024E08" "8A67CC74" "020BBEA6" "3B139B22" "514A0879" "8E3404DD" 323 "EF9519B3" "CD3A431B" "302B0A6D" "F25F1437" "4FE1356D" "6D51C245" 324 "E485B576" "625E7EC6" "F44C42E9" "A637ED6B" "0BFF5CB6" "F406B7ED" 325 "EE386BFB" "5A899FA5" "AE9F2411" "7C4B1FE6" "49286651" "ECE45B3D" 326 "C2007CB8" "A163BF05" "98DA4836" "1C55D39A" "69163FA8" "FD24CF5F" 327 "83655D23" "DCA3AD96" "1C62F356" "208552BB" "9ED52907" "7096966D" 328 "670C354E" "4ABC9804" "F1746C08" "CA18217C" "32905E46" "2E36CE3B" 329 "E39E772C" "180E8603" "9B2783A2" "EC07A28F" "B5C55DF0" "6F4C52C9" 330 "DE2BCBF6" "95581718" "3995497C" "EA956AE5" "15D22618" "98FA0510" 331 "15728E5A" "8AACAA68" "FFFFFFFF" "FFFFFFFF"; 332 333 return (dh_new_group_asc(gen, group14)); 334 } 335 336 /* 337 * Estimates the group order for a Diffie-Hellman group that has an 338 * attack complexity approximately the same as O(2**bits). 339 * Values from NIST Special Publication 800-57: Recommendation for Key 340 * Management Part 1 (rev 3) limited by the recommended maximum value 341 * from RFC4419 section 3. 342 */ 343 344 int 345 dh_estimate(int bits) 346 { 347 if (bits <= 112) 348 return 2048; 349 if (bits <= 128) 350 return 3072; 351 if (bits <= 192) 352 return 7680; 353 return 8192; 354 } 355