dh.c revision 76259
169587Sgreen/* 269587Sgreen * Copyright (c) 2000 Niels Provos. All rights reserved. 369587Sgreen * 469587Sgreen * Redistribution and use in source and binary forms, with or without 569587Sgreen * modification, are permitted provided that the following conditions 669587Sgreen * are met: 769587Sgreen * 1. Redistributions of source code must retain the above copyright 869587Sgreen * notice, this list of conditions and the following disclaimer. 969587Sgreen * 2. Redistributions in binary form must reproduce the above copyright 1069587Sgreen * notice, this list of conditions and the following disclaimer in the 1169587Sgreen * documentation and/or other materials provided with the distribution. 1269587Sgreen * 1369587Sgreen * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR 1469587Sgreen * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES 1569587Sgreen * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. 1669587Sgreen * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT, 1769587Sgreen * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT 1869587Sgreen * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 1969587Sgreen * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 2069587Sgreen * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 2169587Sgreen * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF 2269587Sgreen * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 2369587Sgreen */ 2469587Sgreen 2569587Sgreen#include "includes.h" 2676259SgreenRCSID("$OpenBSD: dh.c,v 1.14 2001/04/15 08:43:45 markus Exp $"); 2769587Sgreen 2869587Sgreen#include "xmalloc.h" 2969587Sgreen 3069587Sgreen#include <openssl/bn.h> 3169587Sgreen#include <openssl/dh.h> 3269587Sgreen#include <openssl/evp.h> 3369587Sgreen 3469587Sgreen#include "buffer.h" 3576259Sgreen#include "cipher.h" 3669587Sgreen#include "kex.h" 3769587Sgreen#include "dh.h" 3876259Sgreen#include "pathnames.h" 3976259Sgreen#include "log.h" 4076259Sgreen#include "misc.h" 4169587Sgreen 4269587Sgreenint 4369587Sgreenparse_prime(int linenum, char *line, struct dhgroup *dhg) 4469587Sgreen{ 4569587Sgreen char *cp, *arg; 4669587Sgreen char *strsize, *gen, *prime; 4769587Sgreen 4869587Sgreen cp = line; 4969587Sgreen arg = strdelim(&cp); 5069587Sgreen /* Ignore leading whitespace */ 5169587Sgreen if (*arg == '\0') 5269587Sgreen arg = strdelim(&cp); 5369587Sgreen if (!*arg || *arg == '#') 5469587Sgreen return 0; 5569587Sgreen 5669587Sgreen /* time */ 5769587Sgreen if (cp == NULL || *arg == '\0') 5869587Sgreen goto fail; 5969587Sgreen arg = strsep(&cp, " "); /* type */ 6069587Sgreen if (cp == NULL || *arg == '\0') 6169587Sgreen goto fail; 6269587Sgreen arg = strsep(&cp, " "); /* tests */ 6369587Sgreen if (cp == NULL || *arg == '\0') 6469587Sgreen goto fail; 6569587Sgreen arg = strsep(&cp, " "); /* tries */ 6669587Sgreen if (cp == NULL || *arg == '\0') 6769587Sgreen goto fail; 6869587Sgreen strsize = strsep(&cp, " "); /* size */ 6969587Sgreen if (cp == NULL || *strsize == '\0' || 7069587Sgreen (dhg->size = atoi(strsize)) == 0) 7169587Sgreen goto fail; 7276259Sgreen /* The whole group is one bit larger */ 7376259Sgreen dhg->size++; 7469587Sgreen gen = strsep(&cp, " "); /* gen */ 7569587Sgreen if (cp == NULL || *gen == '\0') 7669587Sgreen goto fail; 7769587Sgreen prime = strsep(&cp, " "); /* prime */ 7869587Sgreen if (cp != NULL || *prime == '\0') 7969587Sgreen goto fail; 8069587Sgreen 8169587Sgreen dhg->g = BN_new(); 8269587Sgreen dhg->p = BN_new(); 8376259Sgreen if (BN_hex2bn(&dhg->g, gen) == 0) 8476259Sgreen goto failclean; 8569587Sgreen 8676259Sgreen if (BN_hex2bn(&dhg->p, prime) == 0) 8776259Sgreen goto failclean; 8876259Sgreen 8976259Sgreen if (BN_num_bits(dhg->p) != dhg->size) 9076259Sgreen goto failclean; 9176259Sgreen 9269587Sgreen return (1); 9376259Sgreen 9476259Sgreen failclean: 9576259Sgreen BN_free(dhg->g); 9676259Sgreen BN_free(dhg->p); 9769587Sgreen fail: 9876259Sgreen error("Bad prime description in line %d", linenum); 9969587Sgreen return (0); 10069587Sgreen} 10169587Sgreen 10269587SgreenDH * 10376259Sgreenchoose_dh(int min, int wantbits, int max) 10469587Sgreen{ 10569587Sgreen FILE *f; 10669587Sgreen char line[1024]; 10769587Sgreen int best, bestcount, which; 10869587Sgreen int linenum; 10969587Sgreen struct dhgroup dhg; 11069587Sgreen 11176259Sgreen f = fopen(_PATH_DH_PRIMES, "r"); 11269587Sgreen if (!f) { 11376259Sgreen log("WARNING: %s does not exist, using old prime", _PATH_DH_PRIMES); 11469587Sgreen return (dh_new_group1()); 11569587Sgreen } 11669587Sgreen 11769587Sgreen linenum = 0; 11869587Sgreen best = bestcount = 0; 11969587Sgreen while (fgets(line, sizeof(line), f)) { 12069587Sgreen linenum++; 12169587Sgreen if (!parse_prime(linenum, line, &dhg)) 12269587Sgreen continue; 12369587Sgreen BN_free(dhg.g); 12469587Sgreen BN_free(dhg.p); 12569587Sgreen 12676259Sgreen if (dhg.size > max || dhg.size < min) 12776259Sgreen continue; 12876259Sgreen 12976259Sgreen if ((dhg.size > wantbits && dhg.size < best) || 13076259Sgreen (dhg.size > best && best < wantbits)) { 13169587Sgreen best = dhg.size; 13269587Sgreen bestcount = 0; 13369587Sgreen } 13469587Sgreen if (dhg.size == best) 13569587Sgreen bestcount++; 13669587Sgreen } 13769587Sgreen fclose (f); 13869587Sgreen 13969587Sgreen if (bestcount == 0) { 14076259Sgreen log("WARNING: no suitable primes in %s", _PATH_DH_PRIMES); 14176259Sgreen return (NULL); 14269587Sgreen } 14369587Sgreen 14476259Sgreen f = fopen(_PATH_DH_PRIMES, "r"); 14569587Sgreen if (!f) { 14676259Sgreen fatal("WARNING: %s disappeared, giving up", _PATH_DH_PRIMES); 14769587Sgreen } 14869587Sgreen 14969587Sgreen linenum = 0; 15069587Sgreen which = arc4random() % bestcount; 15169587Sgreen while (fgets(line, sizeof(line), f)) { 15269587Sgreen if (!parse_prime(linenum, line, &dhg)) 15369587Sgreen continue; 15476259Sgreen if ((dhg.size > max || dhg.size < min) || 15576259Sgreen dhg.size != best || 15676259Sgreen linenum++ != which) { 15769587Sgreen BN_free(dhg.g); 15869587Sgreen BN_free(dhg.p); 15969587Sgreen continue; 16069587Sgreen } 16169587Sgreen break; 16269587Sgreen } 16369587Sgreen fclose(f); 16476259Sgreen if (linenum != which+1) 16576259Sgreen fatal("WARNING: line %d disappeared in %s, giving up", 16676259Sgreen which, _PATH_DH_PRIMES); 16769587Sgreen 16869587Sgreen return (dh_new_group(dhg.g, dhg.p)); 16969587Sgreen} 17076259Sgreen 17176259Sgreen/* diffie-hellman-group1-sha1 */ 17276259Sgreen 17376259Sgreenint 17476259Sgreendh_pub_is_valid(DH *dh, BIGNUM *dh_pub) 17576259Sgreen{ 17676259Sgreen int i; 17776259Sgreen int n = BN_num_bits(dh_pub); 17876259Sgreen int bits_set = 0; 17976259Sgreen 18076259Sgreen if (dh_pub->neg) { 18176259Sgreen log("invalid public DH value: negativ"); 18276259Sgreen return 0; 18376259Sgreen } 18476259Sgreen for (i = 0; i <= n; i++) 18576259Sgreen if (BN_is_bit_set(dh_pub, i)) 18676259Sgreen bits_set++; 18776259Sgreen debug("bits set: %d/%d", bits_set, BN_num_bits(dh->p)); 18876259Sgreen 18976259Sgreen /* if g==2 and bits_set==1 then computing log_g(dh_pub) is trivial */ 19076259Sgreen if (bits_set > 1 && (BN_cmp(dh_pub, dh->p) == -1)) 19176259Sgreen return 1; 19276259Sgreen log("invalid public DH value (%d/%d)", bits_set, BN_num_bits(dh->p)); 19376259Sgreen return 0; 19476259Sgreen} 19576259Sgreen 19676259Sgreenvoid 19776259Sgreendh_gen_key(DH *dh, int need) 19876259Sgreen{ 19976259Sgreen int i, bits_set = 0, tries = 0; 20076259Sgreen 20176259Sgreen if (dh->p == NULL) 20276259Sgreen fatal("dh_gen_key: dh->p == NULL"); 20376259Sgreen if (2*need >= BN_num_bits(dh->p)) 20476259Sgreen fatal("dh_gen_key: group too small: %d (2*need %d)", 20576259Sgreen BN_num_bits(dh->p), 2*need); 20676259Sgreen do { 20776259Sgreen if (dh->priv_key != NULL) 20876259Sgreen BN_free(dh->priv_key); 20976259Sgreen dh->priv_key = BN_new(); 21076259Sgreen if (dh->priv_key == NULL) 21176259Sgreen fatal("dh_gen_key: BN_new failed"); 21276259Sgreen /* generate a 2*need bits random private exponent */ 21376259Sgreen if (!BN_rand(dh->priv_key, 2*need, 0, 0)) 21476259Sgreen fatal("dh_gen_key: BN_rand failed"); 21576259Sgreen if (DH_generate_key(dh) == 0) 21676259Sgreen fatal("DH_generate_key"); 21776259Sgreen for (i = 0; i <= BN_num_bits(dh->priv_key); i++) 21876259Sgreen if (BN_is_bit_set(dh->priv_key, i)) 21976259Sgreen bits_set++; 22076259Sgreen debug("dh_gen_key: priv key bits set: %d/%d", 22176259Sgreen bits_set, BN_num_bits(dh->priv_key)); 22276259Sgreen if (tries++ > 10) 22376259Sgreen fatal("dh_gen_key: too many bad keys: giving up"); 22476259Sgreen } while (!dh_pub_is_valid(dh, dh->pub_key)); 22576259Sgreen} 22676259Sgreen 22776259SgreenDH * 22876259Sgreendh_new_group_asc(const char *gen, const char *modulus) 22976259Sgreen{ 23076259Sgreen DH *dh; 23176259Sgreen 23276259Sgreen dh = DH_new(); 23376259Sgreen if (dh == NULL) 23476259Sgreen fatal("DH_new"); 23576259Sgreen 23676259Sgreen if (BN_hex2bn(&dh->p, modulus) == 0) 23776259Sgreen fatal("BN_hex2bn p"); 23876259Sgreen if (BN_hex2bn(&dh->g, gen) == 0) 23976259Sgreen fatal("BN_hex2bn g"); 24076259Sgreen 24176259Sgreen return (dh); 24276259Sgreen} 24376259Sgreen 24476259Sgreen/* 24576259Sgreen * This just returns the group, we still need to generate the exchange 24676259Sgreen * value. 24776259Sgreen */ 24876259Sgreen 24976259SgreenDH * 25076259Sgreendh_new_group(BIGNUM *gen, BIGNUM *modulus) 25176259Sgreen{ 25276259Sgreen DH *dh; 25376259Sgreen 25476259Sgreen dh = DH_new(); 25576259Sgreen if (dh == NULL) 25676259Sgreen fatal("DH_new"); 25776259Sgreen dh->p = modulus; 25876259Sgreen dh->g = gen; 25976259Sgreen 26076259Sgreen return (dh); 26176259Sgreen} 26276259Sgreen 26376259SgreenDH * 26476259Sgreendh_new_group1(void) 26576259Sgreen{ 26676259Sgreen static char *gen = "2", *group1 = 26776259Sgreen "FFFFFFFF" "FFFFFFFF" "C90FDAA2" "2168C234" "C4C6628B" "80DC1CD1" 26876259Sgreen "29024E08" "8A67CC74" "020BBEA6" "3B139B22" "514A0879" "8E3404DD" 26976259Sgreen "EF9519B3" "CD3A431B" "302B0A6D" "F25F1437" "4FE1356D" "6D51C245" 27076259Sgreen "E485B576" "625E7EC6" "F44C42E9" "A637ED6B" "0BFF5CB6" "F406B7ED" 27176259Sgreen "EE386BFB" "5A899FA5" "AE9F2411" "7C4B1FE6" "49286651" "ECE65381" 27276259Sgreen "FFFFFFFF" "FFFFFFFF"; 27376259Sgreen 27476259Sgreen return (dh_new_group_asc(gen, group1)); 27576259Sgreen} 27676259Sgreen 27776259Sgreen/* 27876259Sgreen * Estimates the group order for a Diffie-Hellman group that has an 27976259Sgreen * attack complexity approximately the same as O(2**bits). Estimate 28076259Sgreen * with: O(exp(1.9223 * (ln q)^(1/3) (ln ln q)^(2/3))) 28176259Sgreen */ 28276259Sgreen 28376259Sgreenint 28476259Sgreendh_estimate(int bits) 28576259Sgreen{ 28676259Sgreen 28776259Sgreen if (bits < 64) 28876259Sgreen return (512); /* O(2**63) */ 28976259Sgreen if (bits < 128) 29076259Sgreen return (1024); /* O(2**86) */ 29176259Sgreen if (bits < 192) 29276259Sgreen return (2048); /* O(2**116) */ 29376259Sgreen return (4096); /* O(2**156) */ 29476259Sgreen} 295