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