dh.c revision 106121
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" 26106121SdesRCSID("$OpenBSD: dh.c,v 1.22 2002/06/27 08:49:44 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 4292555Sdesstatic int 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); 53106121Sdes if (!arg || !*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 8192555Sdes if ((dhg->g = BN_new()) == NULL) 8292555Sdes fatal("parse_prime: BN_new failed"); 8392555Sdes if ((dhg->p = BN_new()) == NULL) 8492555Sdes fatal("parse_prime: BN_new failed"); 8576259Sgreen if (BN_hex2bn(&dhg->g, gen) == 0) 8676259Sgreen goto failclean; 8769587Sgreen 8876259Sgreen if (BN_hex2bn(&dhg->p, prime) == 0) 8976259Sgreen goto failclean; 9076259Sgreen 9176259Sgreen if (BN_num_bits(dhg->p) != dhg->size) 9276259Sgreen goto failclean; 9376259Sgreen 9469587Sgreen return (1); 9576259Sgreen 9676259Sgreen failclean: 9792555Sdes BN_clear_free(dhg->g); 9892555Sdes BN_clear_free(dhg->p); 9969587Sgreen fail: 10076259Sgreen error("Bad prime description in line %d", linenum); 10169587Sgreen return (0); 10269587Sgreen} 10369587Sgreen 10469587SgreenDH * 10576259Sgreenchoose_dh(int min, int wantbits, int max) 10669587Sgreen{ 10769587Sgreen FILE *f; 10892555Sdes char line[2048]; 10969587Sgreen int best, bestcount, which; 11069587Sgreen int linenum; 11169587Sgreen struct dhgroup dhg; 11269587Sgreen 11392555Sdes if ((f = fopen(_PATH_DH_MODULI, "r")) == NULL && 11492555Sdes (f = fopen(_PATH_DH_PRIMES, "r")) == NULL) { 11592555Sdes log("WARNING: %s does not exist, using old modulus", _PATH_DH_MODULI); 11669587Sgreen return (dh_new_group1()); 11769587Sgreen } 11869587Sgreen 11969587Sgreen linenum = 0; 12069587Sgreen best = bestcount = 0; 12169587Sgreen while (fgets(line, sizeof(line), f)) { 12269587Sgreen linenum++; 12369587Sgreen if (!parse_prime(linenum, line, &dhg)) 12469587Sgreen continue; 12592555Sdes BN_clear_free(dhg.g); 12692555Sdes BN_clear_free(dhg.p); 12769587Sgreen 12876259Sgreen if (dhg.size > max || dhg.size < min) 12976259Sgreen continue; 13076259Sgreen 13176259Sgreen if ((dhg.size > wantbits && dhg.size < best) || 13276259Sgreen (dhg.size > best && best < wantbits)) { 13369587Sgreen best = dhg.size; 13469587Sgreen bestcount = 0; 13569587Sgreen } 13669587Sgreen if (dhg.size == best) 13769587Sgreen bestcount++; 13869587Sgreen } 13992555Sdes rewind(f); 14069587Sgreen 14169587Sgreen if (bestcount == 0) { 14292555Sdes fclose(f); 14376259Sgreen log("WARNING: no suitable primes in %s", _PATH_DH_PRIMES); 14476259Sgreen return (NULL); 14569587Sgreen } 14669587Sgreen 14769587Sgreen linenum = 0; 14869587Sgreen which = arc4random() % bestcount; 14969587Sgreen while (fgets(line, sizeof(line), f)) { 15069587Sgreen if (!parse_prime(linenum, line, &dhg)) 15169587Sgreen continue; 15276259Sgreen if ((dhg.size > max || dhg.size < min) || 15376259Sgreen dhg.size != best || 15476259Sgreen linenum++ != which) { 15592555Sdes BN_clear_free(dhg.g); 15692555Sdes BN_clear_free(dhg.p); 15769587Sgreen continue; 15869587Sgreen } 15969587Sgreen break; 16069587Sgreen } 16169587Sgreen fclose(f); 16276259Sgreen if (linenum != which+1) 16376259Sgreen fatal("WARNING: line %d disappeared in %s, giving up", 16476259Sgreen which, _PATH_DH_PRIMES); 16569587Sgreen 16669587Sgreen return (dh_new_group(dhg.g, dhg.p)); 16769587Sgreen} 16876259Sgreen 16976259Sgreen/* diffie-hellman-group1-sha1 */ 17076259Sgreen 17176259Sgreenint 17276259Sgreendh_pub_is_valid(DH *dh, BIGNUM *dh_pub) 17376259Sgreen{ 17476259Sgreen int i; 17576259Sgreen int n = BN_num_bits(dh_pub); 17676259Sgreen int bits_set = 0; 17776259Sgreen 17876259Sgreen if (dh_pub->neg) { 17976259Sgreen log("invalid public DH value: negativ"); 18076259Sgreen return 0; 18176259Sgreen } 18276259Sgreen for (i = 0; i <= n; i++) 18376259Sgreen if (BN_is_bit_set(dh_pub, i)) 18476259Sgreen bits_set++; 18576259Sgreen debug("bits set: %d/%d", bits_set, BN_num_bits(dh->p)); 18676259Sgreen 18776259Sgreen /* if g==2 and bits_set==1 then computing log_g(dh_pub) is trivial */ 18876259Sgreen if (bits_set > 1 && (BN_cmp(dh_pub, dh->p) == -1)) 18976259Sgreen return 1; 19076259Sgreen log("invalid public DH value (%d/%d)", bits_set, BN_num_bits(dh->p)); 19176259Sgreen return 0; 19276259Sgreen} 19376259Sgreen 19476259Sgreenvoid 19576259Sgreendh_gen_key(DH *dh, int need) 19676259Sgreen{ 19776259Sgreen int i, bits_set = 0, tries = 0; 19876259Sgreen 19976259Sgreen if (dh->p == NULL) 20076259Sgreen fatal("dh_gen_key: dh->p == NULL"); 20176259Sgreen if (2*need >= BN_num_bits(dh->p)) 20276259Sgreen fatal("dh_gen_key: group too small: %d (2*need %d)", 20376259Sgreen BN_num_bits(dh->p), 2*need); 20476259Sgreen do { 20576259Sgreen if (dh->priv_key != NULL) 20692555Sdes BN_clear_free(dh->priv_key); 20792555Sdes if ((dh->priv_key = BN_new()) == NULL) 20876259Sgreen fatal("dh_gen_key: BN_new failed"); 20976259Sgreen /* generate a 2*need bits random private exponent */ 21076259Sgreen if (!BN_rand(dh->priv_key, 2*need, 0, 0)) 21176259Sgreen fatal("dh_gen_key: BN_rand failed"); 21276259Sgreen if (DH_generate_key(dh) == 0) 21376259Sgreen fatal("DH_generate_key"); 21476259Sgreen for (i = 0; i <= BN_num_bits(dh->priv_key); i++) 21576259Sgreen if (BN_is_bit_set(dh->priv_key, i)) 21676259Sgreen bits_set++; 21776259Sgreen debug("dh_gen_key: priv key bits set: %d/%d", 21876259Sgreen bits_set, BN_num_bits(dh->priv_key)); 21976259Sgreen if (tries++ > 10) 22076259Sgreen fatal("dh_gen_key: too many bad keys: giving up"); 22176259Sgreen } while (!dh_pub_is_valid(dh, dh->pub_key)); 22276259Sgreen} 22376259Sgreen 22476259SgreenDH * 22576259Sgreendh_new_group_asc(const char *gen, const char *modulus) 22676259Sgreen{ 22776259Sgreen DH *dh; 22876259Sgreen 22992555Sdes if ((dh = DH_new()) == NULL) 23092555Sdes fatal("dh_new_group_asc: DH_new"); 23176259Sgreen 23276259Sgreen if (BN_hex2bn(&dh->p, modulus) == 0) 23376259Sgreen fatal("BN_hex2bn p"); 23476259Sgreen if (BN_hex2bn(&dh->g, gen) == 0) 23576259Sgreen fatal("BN_hex2bn g"); 23676259Sgreen 23776259Sgreen return (dh); 23876259Sgreen} 23976259Sgreen 24076259Sgreen/* 24176259Sgreen * This just returns the group, we still need to generate the exchange 24276259Sgreen * value. 24376259Sgreen */ 24476259Sgreen 24576259SgreenDH * 24676259Sgreendh_new_group(BIGNUM *gen, BIGNUM *modulus) 24776259Sgreen{ 24876259Sgreen DH *dh; 24976259Sgreen 25092555Sdes if ((dh = DH_new()) == NULL) 25192555Sdes fatal("dh_new_group: DH_new"); 25276259Sgreen dh->p = modulus; 25376259Sgreen dh->g = gen; 25476259Sgreen 25576259Sgreen return (dh); 25676259Sgreen} 25776259Sgreen 25876259SgreenDH * 25976259Sgreendh_new_group1(void) 26076259Sgreen{ 26176259Sgreen static char *gen = "2", *group1 = 26276259Sgreen "FFFFFFFF" "FFFFFFFF" "C90FDAA2" "2168C234" "C4C6628B" "80DC1CD1" 26376259Sgreen "29024E08" "8A67CC74" "020BBEA6" "3B139B22" "514A0879" "8E3404DD" 26476259Sgreen "EF9519B3" "CD3A431B" "302B0A6D" "F25F1437" "4FE1356D" "6D51C245" 26576259Sgreen "E485B576" "625E7EC6" "F44C42E9" "A637ED6B" "0BFF5CB6" "F406B7ED" 26676259Sgreen "EE386BFB" "5A899FA5" "AE9F2411" "7C4B1FE6" "49286651" "ECE65381" 26776259Sgreen "FFFFFFFF" "FFFFFFFF"; 26876259Sgreen 26976259Sgreen return (dh_new_group_asc(gen, group1)); 27076259Sgreen} 27176259Sgreen 27276259Sgreen/* 27376259Sgreen * Estimates the group order for a Diffie-Hellman group that has an 27476259Sgreen * attack complexity approximately the same as O(2**bits). Estimate 27576259Sgreen * with: O(exp(1.9223 * (ln q)^(1/3) (ln ln q)^(2/3))) 27676259Sgreen */ 27776259Sgreen 27876259Sgreenint 27976259Sgreendh_estimate(int bits) 28076259Sgreen{ 28176259Sgreen 28276259Sgreen if (bits < 64) 28376259Sgreen return (512); /* O(2**63) */ 28476259Sgreen if (bits < 128) 28576259Sgreen return (1024); /* O(2**86) */ 28676259Sgreen if (bits < 192) 28776259Sgreen return (2048); /* O(2**116) */ 28876259Sgreen return (4096); /* O(2**156) */ 28976259Sgreen} 290