1*0Sstevel@tonic-gate /* 2*0Sstevel@tonic-gate * Copyright (c) 2000 Niels Provos. All rights reserved. 3*0Sstevel@tonic-gate * 4*0Sstevel@tonic-gate * Redistribution and use in source and binary forms, with or without 5*0Sstevel@tonic-gate * modification, are permitted provided that the following conditions 6*0Sstevel@tonic-gate * are met: 7*0Sstevel@tonic-gate * 1. Redistributions of source code must retain the above copyright 8*0Sstevel@tonic-gate * notice, this list of conditions and the following disclaimer. 9*0Sstevel@tonic-gate * 2. Redistributions in binary form must reproduce the above copyright 10*0Sstevel@tonic-gate * notice, this list of conditions and the following disclaimer in the 11*0Sstevel@tonic-gate * documentation and/or other materials provided with the distribution. 12*0Sstevel@tonic-gate * 13*0Sstevel@tonic-gate * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR 14*0Sstevel@tonic-gate * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES 15*0Sstevel@tonic-gate * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. 16*0Sstevel@tonic-gate * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT, 17*0Sstevel@tonic-gate * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT 18*0Sstevel@tonic-gate * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 19*0Sstevel@tonic-gate * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 20*0Sstevel@tonic-gate * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 21*0Sstevel@tonic-gate * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF 22*0Sstevel@tonic-gate * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 23*0Sstevel@tonic-gate */ 24*0Sstevel@tonic-gate 25*0Sstevel@tonic-gate #include "includes.h" 26*0Sstevel@tonic-gate RCSID("$OpenBSD: dh.c,v 1.22 2002/06/27 08:49:44 markus Exp $"); 27*0Sstevel@tonic-gate 28*0Sstevel@tonic-gate #pragma ident "%Z%%M% %I% %E% SMI" 29*0Sstevel@tonic-gate 30*0Sstevel@tonic-gate #include "xmalloc.h" 31*0Sstevel@tonic-gate 32*0Sstevel@tonic-gate #include <openssl/bn.h> 33*0Sstevel@tonic-gate #include <openssl/dh.h> 34*0Sstevel@tonic-gate #include <openssl/evp.h> 35*0Sstevel@tonic-gate 36*0Sstevel@tonic-gate #include "buffer.h" 37*0Sstevel@tonic-gate #include "cipher.h" 38*0Sstevel@tonic-gate #include "kex.h" 39*0Sstevel@tonic-gate #include "dh.h" 40*0Sstevel@tonic-gate #include "pathnames.h" 41*0Sstevel@tonic-gate #include "log.h" 42*0Sstevel@tonic-gate #include "misc.h" 43*0Sstevel@tonic-gate 44*0Sstevel@tonic-gate static int 45*0Sstevel@tonic-gate parse_prime(int linenum, char *line, struct dhgroup *dhg) 46*0Sstevel@tonic-gate { 47*0Sstevel@tonic-gate char *cp, *arg; 48*0Sstevel@tonic-gate char *strsize, *gen, *prime; 49*0Sstevel@tonic-gate 50*0Sstevel@tonic-gate cp = line; 51*0Sstevel@tonic-gate arg = strdelim(&cp); 52*0Sstevel@tonic-gate /* Ignore leading whitespace */ 53*0Sstevel@tonic-gate if (*arg == '\0') 54*0Sstevel@tonic-gate arg = strdelim(&cp); 55*0Sstevel@tonic-gate if (!arg || !*arg || *arg == '#') 56*0Sstevel@tonic-gate return 0; 57*0Sstevel@tonic-gate 58*0Sstevel@tonic-gate /* time */ 59*0Sstevel@tonic-gate if (cp == NULL || *arg == '\0') 60*0Sstevel@tonic-gate goto fail; 61*0Sstevel@tonic-gate arg = strsep(&cp, " "); /* type */ 62*0Sstevel@tonic-gate if (cp == NULL || *arg == '\0') 63*0Sstevel@tonic-gate goto fail; 64*0Sstevel@tonic-gate arg = strsep(&cp, " "); /* tests */ 65*0Sstevel@tonic-gate if (cp == NULL || *arg == '\0') 66*0Sstevel@tonic-gate goto fail; 67*0Sstevel@tonic-gate arg = strsep(&cp, " "); /* tries */ 68*0Sstevel@tonic-gate if (cp == NULL || *arg == '\0') 69*0Sstevel@tonic-gate goto fail; 70*0Sstevel@tonic-gate strsize = strsep(&cp, " "); /* size */ 71*0Sstevel@tonic-gate if (cp == NULL || *strsize == '\0' || 72*0Sstevel@tonic-gate (dhg->size = atoi(strsize)) == 0) 73*0Sstevel@tonic-gate goto fail; 74*0Sstevel@tonic-gate /* The whole group is one bit larger */ 75*0Sstevel@tonic-gate dhg->size++; 76*0Sstevel@tonic-gate gen = strsep(&cp, " "); /* gen */ 77*0Sstevel@tonic-gate if (cp == NULL || *gen == '\0') 78*0Sstevel@tonic-gate goto fail; 79*0Sstevel@tonic-gate prime = strsep(&cp, " "); /* prime */ 80*0Sstevel@tonic-gate if (cp != NULL || *prime == '\0') 81*0Sstevel@tonic-gate goto fail; 82*0Sstevel@tonic-gate 83*0Sstevel@tonic-gate if ((dhg->g = BN_new()) == NULL) 84*0Sstevel@tonic-gate fatal("parse_prime: BN_new failed"); 85*0Sstevel@tonic-gate if ((dhg->p = BN_new()) == NULL) 86*0Sstevel@tonic-gate fatal("parse_prime: BN_new failed"); 87*0Sstevel@tonic-gate if (BN_hex2bn(&dhg->g, gen) == 0) 88*0Sstevel@tonic-gate goto failclean; 89*0Sstevel@tonic-gate 90*0Sstevel@tonic-gate if (BN_hex2bn(&dhg->p, prime) == 0) 91*0Sstevel@tonic-gate goto failclean; 92*0Sstevel@tonic-gate 93*0Sstevel@tonic-gate if (BN_num_bits(dhg->p) != dhg->size) 94*0Sstevel@tonic-gate goto failclean; 95*0Sstevel@tonic-gate 96*0Sstevel@tonic-gate return (1); 97*0Sstevel@tonic-gate 98*0Sstevel@tonic-gate failclean: 99*0Sstevel@tonic-gate BN_clear_free(dhg->g); 100*0Sstevel@tonic-gate BN_clear_free(dhg->p); 101*0Sstevel@tonic-gate fail: 102*0Sstevel@tonic-gate error("Bad prime description in line %d", linenum); 103*0Sstevel@tonic-gate return (0); 104*0Sstevel@tonic-gate } 105*0Sstevel@tonic-gate 106*0Sstevel@tonic-gate DH * 107*0Sstevel@tonic-gate choose_dh(int min, int wantbits, int max) 108*0Sstevel@tonic-gate { 109*0Sstevel@tonic-gate FILE *f; 110*0Sstevel@tonic-gate char line[2048]; 111*0Sstevel@tonic-gate int best, bestcount, which; 112*0Sstevel@tonic-gate int linenum; 113*0Sstevel@tonic-gate struct dhgroup dhg; 114*0Sstevel@tonic-gate 115*0Sstevel@tonic-gate if ((f = fopen(_PATH_DH_MODULI, "r")) == NULL && 116*0Sstevel@tonic-gate (f = fopen(_PATH_DH_PRIMES, "r")) == NULL) { 117*0Sstevel@tonic-gate log("WARNING: %s does not exist, using old modulus", _PATH_DH_MODULI); 118*0Sstevel@tonic-gate return (dh_new_group1()); 119*0Sstevel@tonic-gate } 120*0Sstevel@tonic-gate 121*0Sstevel@tonic-gate linenum = 0; 122*0Sstevel@tonic-gate best = bestcount = 0; 123*0Sstevel@tonic-gate while (fgets(line, sizeof(line), f)) { 124*0Sstevel@tonic-gate linenum++; 125*0Sstevel@tonic-gate if (!parse_prime(linenum, line, &dhg)) 126*0Sstevel@tonic-gate continue; 127*0Sstevel@tonic-gate BN_clear_free(dhg.g); 128*0Sstevel@tonic-gate BN_clear_free(dhg.p); 129*0Sstevel@tonic-gate 130*0Sstevel@tonic-gate if (dhg.size > max || dhg.size < min) 131*0Sstevel@tonic-gate continue; 132*0Sstevel@tonic-gate 133*0Sstevel@tonic-gate if ((dhg.size > wantbits && dhg.size < best) || 134*0Sstevel@tonic-gate (dhg.size > best && best < wantbits)) { 135*0Sstevel@tonic-gate best = dhg.size; 136*0Sstevel@tonic-gate bestcount = 0; 137*0Sstevel@tonic-gate } 138*0Sstevel@tonic-gate if (dhg.size == best) 139*0Sstevel@tonic-gate bestcount++; 140*0Sstevel@tonic-gate } 141*0Sstevel@tonic-gate rewind(f); 142*0Sstevel@tonic-gate 143*0Sstevel@tonic-gate if (bestcount == 0) { 144*0Sstevel@tonic-gate fclose(f); 145*0Sstevel@tonic-gate log("WARNING: no suitable primes in %s", _PATH_DH_PRIMES); 146*0Sstevel@tonic-gate return (NULL); 147*0Sstevel@tonic-gate } 148*0Sstevel@tonic-gate 149*0Sstevel@tonic-gate linenum = 0; 150*0Sstevel@tonic-gate which = arc4random() % bestcount; 151*0Sstevel@tonic-gate while (fgets(line, sizeof(line), f)) { 152*0Sstevel@tonic-gate if (!parse_prime(linenum, line, &dhg)) 153*0Sstevel@tonic-gate continue; 154*0Sstevel@tonic-gate if ((dhg.size > max || dhg.size < min) || 155*0Sstevel@tonic-gate dhg.size != best || 156*0Sstevel@tonic-gate linenum++ != which) { 157*0Sstevel@tonic-gate BN_clear_free(dhg.g); 158*0Sstevel@tonic-gate BN_clear_free(dhg.p); 159*0Sstevel@tonic-gate continue; 160*0Sstevel@tonic-gate } 161*0Sstevel@tonic-gate break; 162*0Sstevel@tonic-gate } 163*0Sstevel@tonic-gate fclose(f); 164*0Sstevel@tonic-gate if (linenum != which+1) 165*0Sstevel@tonic-gate fatal("WARNING: line %d disappeared in %s, giving up", 166*0Sstevel@tonic-gate which, _PATH_DH_PRIMES); 167*0Sstevel@tonic-gate 168*0Sstevel@tonic-gate return (dh_new_group(dhg.g, dhg.p)); 169*0Sstevel@tonic-gate } 170*0Sstevel@tonic-gate 171*0Sstevel@tonic-gate /* diffie-hellman-group1-sha1 */ 172*0Sstevel@tonic-gate 173*0Sstevel@tonic-gate int 174*0Sstevel@tonic-gate dh_pub_is_valid(DH *dh, BIGNUM *dh_pub) 175*0Sstevel@tonic-gate { 176*0Sstevel@tonic-gate int i; 177*0Sstevel@tonic-gate int n = BN_num_bits(dh_pub); 178*0Sstevel@tonic-gate int bits_set = 0; 179*0Sstevel@tonic-gate 180*0Sstevel@tonic-gate if (dh_pub->neg) { 181*0Sstevel@tonic-gate log("invalid public DH value: negativ"); 182*0Sstevel@tonic-gate return 0; 183*0Sstevel@tonic-gate } 184*0Sstevel@tonic-gate for (i = 0; i <= n; i++) 185*0Sstevel@tonic-gate if (BN_is_bit_set(dh_pub, i)) 186*0Sstevel@tonic-gate bits_set++; 187*0Sstevel@tonic-gate debug("bits set: %d/%d", bits_set, BN_num_bits(dh->p)); 188*0Sstevel@tonic-gate 189*0Sstevel@tonic-gate /* if g==2 and bits_set==1 then computing log_g(dh_pub) is trivial */ 190*0Sstevel@tonic-gate if (bits_set > 1 && (BN_cmp(dh_pub, dh->p) == -1)) 191*0Sstevel@tonic-gate return 1; 192*0Sstevel@tonic-gate log("invalid public DH value (%d/%d)", bits_set, BN_num_bits(dh->p)); 193*0Sstevel@tonic-gate return 0; 194*0Sstevel@tonic-gate } 195*0Sstevel@tonic-gate 196*0Sstevel@tonic-gate void 197*0Sstevel@tonic-gate dh_gen_key(DH *dh, int need) 198*0Sstevel@tonic-gate { 199*0Sstevel@tonic-gate int i, bits_set = 0, tries = 0; 200*0Sstevel@tonic-gate 201*0Sstevel@tonic-gate if (dh->p == NULL) 202*0Sstevel@tonic-gate fatal("dh_gen_key: dh->p == NULL"); 203*0Sstevel@tonic-gate if (2*need >= BN_num_bits(dh->p)) 204*0Sstevel@tonic-gate fatal("dh_gen_key: group too small: %d (2*need %d)", 205*0Sstevel@tonic-gate BN_num_bits(dh->p), 2*need); 206*0Sstevel@tonic-gate do { 207*0Sstevel@tonic-gate if (dh->priv_key != NULL) 208*0Sstevel@tonic-gate BN_clear_free(dh->priv_key); 209*0Sstevel@tonic-gate if ((dh->priv_key = BN_new()) == NULL) 210*0Sstevel@tonic-gate fatal("dh_gen_key: BN_new failed"); 211*0Sstevel@tonic-gate /* generate a 2*need bits random private exponent */ 212*0Sstevel@tonic-gate if (!BN_rand(dh->priv_key, 2*need, 0, 0)) 213*0Sstevel@tonic-gate fatal("dh_gen_key: BN_rand failed"); 214*0Sstevel@tonic-gate if (DH_generate_key(dh) == 0) 215*0Sstevel@tonic-gate fatal("DH_generate_key"); 216*0Sstevel@tonic-gate for (i = 0; i <= BN_num_bits(dh->priv_key); i++) 217*0Sstevel@tonic-gate if (BN_is_bit_set(dh->priv_key, i)) 218*0Sstevel@tonic-gate bits_set++; 219*0Sstevel@tonic-gate debug("dh_gen_key: priv key bits set: %d/%d", 220*0Sstevel@tonic-gate bits_set, BN_num_bits(dh->priv_key)); 221*0Sstevel@tonic-gate if (tries++ > 10) 222*0Sstevel@tonic-gate fatal("dh_gen_key: too many bad keys: giving up"); 223*0Sstevel@tonic-gate } while (!dh_pub_is_valid(dh, dh->pub_key)); 224*0Sstevel@tonic-gate } 225*0Sstevel@tonic-gate 226*0Sstevel@tonic-gate DH * 227*0Sstevel@tonic-gate dh_new_group_asc(const char *gen, const char *modulus) 228*0Sstevel@tonic-gate { 229*0Sstevel@tonic-gate DH *dh; 230*0Sstevel@tonic-gate 231*0Sstevel@tonic-gate if ((dh = DH_new()) == NULL) 232*0Sstevel@tonic-gate fatal("dh_new_group_asc: DH_new"); 233*0Sstevel@tonic-gate 234*0Sstevel@tonic-gate if (BN_hex2bn(&dh->p, modulus) == 0) 235*0Sstevel@tonic-gate fatal("BN_hex2bn p"); 236*0Sstevel@tonic-gate if (BN_hex2bn(&dh->g, gen) == 0) 237*0Sstevel@tonic-gate fatal("BN_hex2bn g"); 238*0Sstevel@tonic-gate 239*0Sstevel@tonic-gate return (dh); 240*0Sstevel@tonic-gate } 241*0Sstevel@tonic-gate 242*0Sstevel@tonic-gate /* 243*0Sstevel@tonic-gate * This just returns the group, we still need to generate the exchange 244*0Sstevel@tonic-gate * value. 245*0Sstevel@tonic-gate */ 246*0Sstevel@tonic-gate 247*0Sstevel@tonic-gate DH * 248*0Sstevel@tonic-gate dh_new_group(BIGNUM *gen, BIGNUM *modulus) 249*0Sstevel@tonic-gate { 250*0Sstevel@tonic-gate DH *dh; 251*0Sstevel@tonic-gate 252*0Sstevel@tonic-gate if ((dh = DH_new()) == NULL) 253*0Sstevel@tonic-gate fatal("dh_new_group: DH_new"); 254*0Sstevel@tonic-gate dh->p = modulus; 255*0Sstevel@tonic-gate dh->g = gen; 256*0Sstevel@tonic-gate 257*0Sstevel@tonic-gate return (dh); 258*0Sstevel@tonic-gate } 259*0Sstevel@tonic-gate 260*0Sstevel@tonic-gate DH * 261*0Sstevel@tonic-gate dh_new_group1(void) 262*0Sstevel@tonic-gate { 263*0Sstevel@tonic-gate static char *gen = "2", *group1 = 264*0Sstevel@tonic-gate "FFFFFFFF" "FFFFFFFF" "C90FDAA2" "2168C234" "C4C6628B" "80DC1CD1" 265*0Sstevel@tonic-gate "29024E08" "8A67CC74" "020BBEA6" "3B139B22" "514A0879" "8E3404DD" 266*0Sstevel@tonic-gate "EF9519B3" "CD3A431B" "302B0A6D" "F25F1437" "4FE1356D" "6D51C245" 267*0Sstevel@tonic-gate "E485B576" "625E7EC6" "F44C42E9" "A637ED6B" "0BFF5CB6" "F406B7ED" 268*0Sstevel@tonic-gate "EE386BFB" "5A899FA5" "AE9F2411" "7C4B1FE6" "49286651" "ECE65381" 269*0Sstevel@tonic-gate "FFFFFFFF" "FFFFFFFF"; 270*0Sstevel@tonic-gate 271*0Sstevel@tonic-gate return (dh_new_group_asc(gen, group1)); 272*0Sstevel@tonic-gate } 273*0Sstevel@tonic-gate 274*0Sstevel@tonic-gate /* 275*0Sstevel@tonic-gate * Estimates the group order for a Diffie-Hellman group that has an 276*0Sstevel@tonic-gate * attack complexity approximately the same as O(2**bits). Estimate 277*0Sstevel@tonic-gate * with: O(exp(1.9223 * (ln q)^(1/3) (ln ln q)^(2/3))) 278*0Sstevel@tonic-gate */ 279*0Sstevel@tonic-gate 280*0Sstevel@tonic-gate int 281*0Sstevel@tonic-gate dh_estimate(int bits) 282*0Sstevel@tonic-gate { 283*0Sstevel@tonic-gate 284*0Sstevel@tonic-gate if (bits < 64) 285*0Sstevel@tonic-gate return (512); /* O(2**63) */ 286*0Sstevel@tonic-gate if (bits < 128) 287*0Sstevel@tonic-gate return (1024); /* O(2**86) */ 288*0Sstevel@tonic-gate if (bits < 192) 289*0Sstevel@tonic-gate return (2048); /* O(2**116) */ 290*0Sstevel@tonic-gate return (4096); /* O(2**156) */ 291*0Sstevel@tonic-gate } 292