dh.c revision 162852
1162852Sdes/* $OpenBSD: dh.c,v 1.42 2006/08/03 03:34:42 deraadt Exp $ */ 269587Sgreen/* 369587Sgreen * Copyright (c) 2000 Niels Provos. All rights reserved. 469587Sgreen * 569587Sgreen * Redistribution and use in source and binary forms, with or without 669587Sgreen * modification, are permitted provided that the following conditions 769587Sgreen * are met: 869587Sgreen * 1. Redistributions of source code must retain the above copyright 969587Sgreen * notice, this list of conditions and the following disclaimer. 1069587Sgreen * 2. Redistributions in binary form must reproduce the above copyright 1169587Sgreen * notice, this list of conditions and the following disclaimer in the 1269587Sgreen * documentation and/or other materials provided with the distribution. 1369587Sgreen * 1469587Sgreen * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR 1569587Sgreen * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES 1669587Sgreen * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. 1769587Sgreen * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT, 1869587Sgreen * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT 1969587Sgreen * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 2069587Sgreen * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 2169587Sgreen * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 2269587Sgreen * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF 2369587Sgreen * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 2469587Sgreen */ 2569587Sgreen 2669587Sgreen#include "includes.h" 2769587Sgreen 28162852Sdes#include <sys/param.h> 2969587Sgreen 3069587Sgreen#include <openssl/bn.h> 3169587Sgreen#include <openssl/dh.h> 3269587Sgreen 33162852Sdes#include <stdarg.h> 34162852Sdes#include <stdio.h> 35162852Sdes#include <stdlib.h> 36162852Sdes#include <string.h> 37162852Sdes 3869587Sgreen#include "dh.h" 3976259Sgreen#include "pathnames.h" 4076259Sgreen#include "log.h" 4176259Sgreen#include "misc.h" 4269587Sgreen 4392555Sdesstatic int 4469587Sgreenparse_prime(int linenum, char *line, struct dhgroup *dhg) 4569587Sgreen{ 4669587Sgreen char *cp, *arg; 4769587Sgreen char *strsize, *gen, *prime; 48162852Sdes const char *errstr = NULL; 4969587Sgreen 5069587Sgreen cp = line; 51162852Sdes if ((arg = strdelim(&cp)) == NULL) 52162852Sdes return 0; 5369587Sgreen /* Ignore leading whitespace */ 5469587Sgreen if (*arg == '\0') 5569587Sgreen arg = strdelim(&cp); 56106121Sdes if (!arg || !*arg || *arg == '#') 5769587Sgreen return 0; 5869587Sgreen 5969587Sgreen /* time */ 6069587Sgreen if (cp == NULL || *arg == '\0') 6169587Sgreen goto fail; 6269587Sgreen arg = strsep(&cp, " "); /* type */ 6369587Sgreen if (cp == NULL || *arg == '\0') 6469587Sgreen goto fail; 6569587Sgreen arg = strsep(&cp, " "); /* tests */ 6669587Sgreen if (cp == NULL || *arg == '\0') 6769587Sgreen goto fail; 6869587Sgreen arg = strsep(&cp, " "); /* tries */ 6969587Sgreen if (cp == NULL || *arg == '\0') 7069587Sgreen goto fail; 7169587Sgreen strsize = strsep(&cp, " "); /* size */ 7269587Sgreen if (cp == NULL || *strsize == '\0' || 73162852Sdes (dhg->size = (u_int)strtonum(strsize, 0, 64*1024, &errstr)) == 0 || 74162852Sdes errstr) 7569587Sgreen goto fail; 7676259Sgreen /* The whole group is one bit larger */ 7776259Sgreen dhg->size++; 7869587Sgreen gen = strsep(&cp, " "); /* gen */ 7969587Sgreen if (cp == NULL || *gen == '\0') 8069587Sgreen goto fail; 8169587Sgreen prime = strsep(&cp, " "); /* prime */ 8269587Sgreen if (cp != NULL || *prime == '\0') 8369587Sgreen goto fail; 8469587Sgreen 8592555Sdes if ((dhg->g = BN_new()) == NULL) 8692555Sdes fatal("parse_prime: BN_new failed"); 8792555Sdes if ((dhg->p = BN_new()) == NULL) 8892555Sdes fatal("parse_prime: BN_new failed"); 8976259Sgreen if (BN_hex2bn(&dhg->g, gen) == 0) 9076259Sgreen goto failclean; 9169587Sgreen 9276259Sgreen if (BN_hex2bn(&dhg->p, prime) == 0) 9376259Sgreen goto failclean; 9476259Sgreen 9576259Sgreen if (BN_num_bits(dhg->p) != dhg->size) 9676259Sgreen goto failclean; 9776259Sgreen 98128456Sdes if (BN_is_zero(dhg->g) || BN_is_one(dhg->g)) 99128456Sdes goto failclean; 100128456Sdes 10169587Sgreen return (1); 10276259Sgreen 10376259Sgreen failclean: 10492555Sdes BN_clear_free(dhg->g); 10592555Sdes BN_clear_free(dhg->p); 10669587Sgreen fail: 10776259Sgreen error("Bad prime description in line %d", linenum); 10869587Sgreen return (0); 10969587Sgreen} 11069587Sgreen 11169587SgreenDH * 11276259Sgreenchoose_dh(int min, int wantbits, int max) 11369587Sgreen{ 11469587Sgreen FILE *f; 115128456Sdes char line[4096]; 11669587Sgreen int best, bestcount, which; 11769587Sgreen int linenum; 11869587Sgreen struct dhgroup dhg; 11969587Sgreen 12092555Sdes if ((f = fopen(_PATH_DH_MODULI, "r")) == NULL && 12192555Sdes (f = fopen(_PATH_DH_PRIMES, "r")) == NULL) { 122137015Sdes logit("WARNING: %s does not exist, using fixed modulus", 123137015Sdes _PATH_DH_MODULI); 124137015Sdes return (dh_new_group14()); 12569587Sgreen } 12669587Sgreen 12769587Sgreen linenum = 0; 12869587Sgreen best = bestcount = 0; 12969587Sgreen while (fgets(line, sizeof(line), f)) { 13069587Sgreen linenum++; 13169587Sgreen if (!parse_prime(linenum, line, &dhg)) 13269587Sgreen continue; 13392555Sdes BN_clear_free(dhg.g); 13492555Sdes BN_clear_free(dhg.p); 13569587Sgreen 13676259Sgreen if (dhg.size > max || dhg.size < min) 13776259Sgreen continue; 13876259Sgreen 13976259Sgreen if ((dhg.size > wantbits && dhg.size < best) || 14076259Sgreen (dhg.size > best && best < wantbits)) { 14169587Sgreen best = dhg.size; 14269587Sgreen bestcount = 0; 14369587Sgreen } 14469587Sgreen if (dhg.size == best) 14569587Sgreen bestcount++; 14669587Sgreen } 14792555Sdes rewind(f); 14869587Sgreen 14969587Sgreen if (bestcount == 0) { 15092555Sdes fclose(f); 151124208Sdes logit("WARNING: no suitable primes in %s", _PATH_DH_PRIMES); 152137015Sdes return (dh_new_group14()); 15369587Sgreen } 15469587Sgreen 15569587Sgreen linenum = 0; 15669587Sgreen which = arc4random() % bestcount; 15769587Sgreen while (fgets(line, sizeof(line), f)) { 15869587Sgreen if (!parse_prime(linenum, line, &dhg)) 15969587Sgreen continue; 16076259Sgreen if ((dhg.size > max || dhg.size < min) || 16176259Sgreen dhg.size != best || 16276259Sgreen linenum++ != which) { 16392555Sdes BN_clear_free(dhg.g); 16492555Sdes BN_clear_free(dhg.p); 16569587Sgreen continue; 16669587Sgreen } 16769587Sgreen break; 16869587Sgreen } 16969587Sgreen fclose(f); 17076259Sgreen if (linenum != which+1) 17176259Sgreen fatal("WARNING: line %d disappeared in %s, giving up", 17276259Sgreen which, _PATH_DH_PRIMES); 17369587Sgreen 17469587Sgreen return (dh_new_group(dhg.g, dhg.p)); 17569587Sgreen} 17676259Sgreen 177137015Sdes/* diffie-hellman-groupN-sha1 */ 17876259Sgreen 17976259Sgreenint 18076259Sgreendh_pub_is_valid(DH *dh, BIGNUM *dh_pub) 18176259Sgreen{ 18276259Sgreen int i; 18376259Sgreen int n = BN_num_bits(dh_pub); 18476259Sgreen int bits_set = 0; 185162852Sdes BIGNUM *tmp; 18676259Sgreen 18776259Sgreen if (dh_pub->neg) { 188124208Sdes logit("invalid public DH value: negativ"); 18976259Sgreen return 0; 19076259Sgreen } 191162852Sdes if (BN_cmp(dh_pub, BN_value_one()) != 1) { /* pub_exp <= 1 */ 192162852Sdes logit("invalid public DH value: <= 1"); 193162852Sdes return 0; 194162852Sdes } 195162852Sdes 196162852Sdes if ((tmp = BN_new()) == NULL) 197162852Sdes return (-1); 198162852Sdes if (!BN_sub(tmp, dh->p, BN_value_one()) || 199162852Sdes BN_cmp(dh_pub, tmp) != -1) { /* pub_exp > p-2 */ 200162852Sdes BN_clear_free(tmp); 201162852Sdes logit("invalid public DH value: >= p-1"); 202162852Sdes return 0; 203162852Sdes } 204162852Sdes BN_clear_free(tmp); 205162852Sdes 20676259Sgreen for (i = 0; i <= n; i++) 20776259Sgreen if (BN_is_bit_set(dh_pub, i)) 20876259Sgreen bits_set++; 209113908Sdes debug2("bits set: %d/%d", bits_set, BN_num_bits(dh->p)); 21076259Sgreen 21176259Sgreen /* if g==2 and bits_set==1 then computing log_g(dh_pub) is trivial */ 212162852Sdes if (bits_set > 1) 21376259Sgreen return 1; 214162852Sdes 215124208Sdes logit("invalid public DH value (%d/%d)", bits_set, BN_num_bits(dh->p)); 21676259Sgreen return 0; 21776259Sgreen} 21876259Sgreen 21976259Sgreenvoid 22076259Sgreendh_gen_key(DH *dh, int need) 22176259Sgreen{ 222128456Sdes int i, bits_set, tries = 0; 22376259Sgreen 22476259Sgreen if (dh->p == NULL) 22576259Sgreen fatal("dh_gen_key: dh->p == NULL"); 226126274Sdes if (need > INT_MAX / 2 || 2 * need >= BN_num_bits(dh->p)) 22776259Sgreen fatal("dh_gen_key: group too small: %d (2*need %d)", 22876259Sgreen BN_num_bits(dh->p), 2*need); 22976259Sgreen do { 23076259Sgreen if (dh->priv_key != NULL) 23192555Sdes BN_clear_free(dh->priv_key); 23292555Sdes if ((dh->priv_key = BN_new()) == NULL) 23376259Sgreen fatal("dh_gen_key: BN_new failed"); 23476259Sgreen /* generate a 2*need bits random private exponent */ 23576259Sgreen if (!BN_rand(dh->priv_key, 2*need, 0, 0)) 23676259Sgreen fatal("dh_gen_key: BN_rand failed"); 23776259Sgreen if (DH_generate_key(dh) == 0) 23876259Sgreen fatal("DH_generate_key"); 239128456Sdes for (i = 0, bits_set = 0; i <= BN_num_bits(dh->priv_key); i++) 24076259Sgreen if (BN_is_bit_set(dh->priv_key, i)) 24176259Sgreen bits_set++; 242113908Sdes debug2("dh_gen_key: priv key bits set: %d/%d", 24376259Sgreen bits_set, BN_num_bits(dh->priv_key)); 24476259Sgreen if (tries++ > 10) 24576259Sgreen fatal("dh_gen_key: too many bad keys: giving up"); 24676259Sgreen } while (!dh_pub_is_valid(dh, dh->pub_key)); 24776259Sgreen} 24876259Sgreen 24976259SgreenDH * 25076259Sgreendh_new_group_asc(const char *gen, const char *modulus) 25176259Sgreen{ 25276259Sgreen DH *dh; 25376259Sgreen 25492555Sdes if ((dh = DH_new()) == NULL) 25592555Sdes fatal("dh_new_group_asc: DH_new"); 25676259Sgreen 25776259Sgreen if (BN_hex2bn(&dh->p, modulus) == 0) 25876259Sgreen fatal("BN_hex2bn p"); 25976259Sgreen if (BN_hex2bn(&dh->g, gen) == 0) 26076259Sgreen fatal("BN_hex2bn g"); 26176259Sgreen 26276259Sgreen return (dh); 26376259Sgreen} 26476259Sgreen 26576259Sgreen/* 26676259Sgreen * This just returns the group, we still need to generate the exchange 26776259Sgreen * value. 26876259Sgreen */ 26976259Sgreen 27076259SgreenDH * 27176259Sgreendh_new_group(BIGNUM *gen, BIGNUM *modulus) 27276259Sgreen{ 27376259Sgreen DH *dh; 27476259Sgreen 27592555Sdes if ((dh = DH_new()) == NULL) 27692555Sdes fatal("dh_new_group: DH_new"); 27776259Sgreen dh->p = modulus; 27876259Sgreen dh->g = gen; 27976259Sgreen 28076259Sgreen return (dh); 28176259Sgreen} 28276259Sgreen 28376259SgreenDH * 28476259Sgreendh_new_group1(void) 28576259Sgreen{ 28676259Sgreen static char *gen = "2", *group1 = 28776259Sgreen "FFFFFFFF" "FFFFFFFF" "C90FDAA2" "2168C234" "C4C6628B" "80DC1CD1" 28876259Sgreen "29024E08" "8A67CC74" "020BBEA6" "3B139B22" "514A0879" "8E3404DD" 28976259Sgreen "EF9519B3" "CD3A431B" "302B0A6D" "F25F1437" "4FE1356D" "6D51C245" 29076259Sgreen "E485B576" "625E7EC6" "F44C42E9" "A637ED6B" "0BFF5CB6" "F406B7ED" 29176259Sgreen "EE386BFB" "5A899FA5" "AE9F2411" "7C4B1FE6" "49286651" "ECE65381" 29276259Sgreen "FFFFFFFF" "FFFFFFFF"; 29376259Sgreen 29476259Sgreen return (dh_new_group_asc(gen, group1)); 29576259Sgreen} 29676259Sgreen 297137015SdesDH * 298137015Sdesdh_new_group14(void) 299137015Sdes{ 300137015Sdes static char *gen = "2", *group14 = 301137015Sdes "FFFFFFFF" "FFFFFFFF" "C90FDAA2" "2168C234" "C4C6628B" "80DC1CD1" 302137015Sdes "29024E08" "8A67CC74" "020BBEA6" "3B139B22" "514A0879" "8E3404DD" 303137015Sdes "EF9519B3" "CD3A431B" "302B0A6D" "F25F1437" "4FE1356D" "6D51C245" 304137015Sdes "E485B576" "625E7EC6" "F44C42E9" "A637ED6B" "0BFF5CB6" "F406B7ED" 305137015Sdes "EE386BFB" "5A899FA5" "AE9F2411" "7C4B1FE6" "49286651" "ECE45B3D" 306137015Sdes "C2007CB8" "A163BF05" "98DA4836" "1C55D39A" "69163FA8" "FD24CF5F" 307137015Sdes "83655D23" "DCA3AD96" "1C62F356" "208552BB" "9ED52907" "7096966D" 308137015Sdes "670C354E" "4ABC9804" "F1746C08" "CA18217C" "32905E46" "2E36CE3B" 309137015Sdes "E39E772C" "180E8603" "9B2783A2" "EC07A28F" "B5C55DF0" "6F4C52C9" 310137015Sdes "DE2BCBF6" "95581718" "3995497C" "EA956AE5" "15D22618" "98FA0510" 311137015Sdes "15728E5A" "8AACAA68" "FFFFFFFF" "FFFFFFFF"; 312137015Sdes 313137015Sdes return (dh_new_group_asc(gen, group14)); 314137015Sdes} 315137015Sdes 31676259Sgreen/* 31776259Sgreen * Estimates the group order for a Diffie-Hellman group that has an 31876259Sgreen * attack complexity approximately the same as O(2**bits). Estimate 31976259Sgreen * with: O(exp(1.9223 * (ln q)^(1/3) (ln ln q)^(2/3))) 32076259Sgreen */ 32176259Sgreen 32276259Sgreenint 32376259Sgreendh_estimate(int bits) 32476259Sgreen{ 32576259Sgreen 326126274Sdes if (bits <= 128) 32776259Sgreen return (1024); /* O(2**86) */ 328126274Sdes if (bits <= 192) 32976259Sgreen return (2048); /* O(2**116) */ 33076259Sgreen return (4096); /* O(2**156) */ 33176259Sgreen} 332