dh.c revision 204917
1204917Sdes/* $OpenBSD: dh.c,v 1.48 2009/10/01 11:37:33 grunk 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; 49181111Sdes long long n; 5069587Sgreen 5169587Sgreen cp = line; 52162852Sdes if ((arg = strdelim(&cp)) == NULL) 53162852Sdes return 0; 5469587Sgreen /* Ignore leading whitespace */ 5569587Sgreen if (*arg == '\0') 5669587Sgreen arg = strdelim(&cp); 57106121Sdes if (!arg || !*arg || *arg == '#') 5869587Sgreen return 0; 5969587Sgreen 6069587Sgreen /* time */ 6169587Sgreen if (cp == NULL || *arg == '\0') 6269587Sgreen goto fail; 6369587Sgreen arg = strsep(&cp, " "); /* type */ 6469587Sgreen if (cp == NULL || *arg == '\0') 6569587Sgreen goto fail; 66181111Sdes /* Ensure this is a safe prime */ 67181111Sdes n = strtonum(arg, 0, 5, &errstr); 68181111Sdes if (errstr != NULL || n != MODULI_TYPE_SAFE) 69181111Sdes goto fail; 7069587Sgreen arg = strsep(&cp, " "); /* tests */ 7169587Sgreen if (cp == NULL || *arg == '\0') 7269587Sgreen goto fail; 73181111Sdes /* Ensure prime has been tested and is not composite */ 74181111Sdes n = strtonum(arg, 0, 0x1f, &errstr); 75181111Sdes if (errstr != NULL || 76181111Sdes (n & MODULI_TESTS_COMPOSITE) || !(n & ~MODULI_TESTS_COMPOSITE)) 77181111Sdes goto fail; 7869587Sgreen arg = strsep(&cp, " "); /* tries */ 7969587Sgreen if (cp == NULL || *arg == '\0') 8069587Sgreen goto fail; 81181111Sdes n = strtonum(arg, 0, 1<<30, &errstr); 82181111Sdes if (errstr != NULL || n == 0) 83181111Sdes goto fail; 8469587Sgreen strsize = strsep(&cp, " "); /* size */ 8569587Sgreen if (cp == NULL || *strsize == '\0' || 86204917Sdes (dhg->size = (int)strtonum(strsize, 0, 64*1024, &errstr)) == 0 || 87162852Sdes errstr) 8869587Sgreen goto fail; 8976259Sgreen /* The whole group is one bit larger */ 9076259Sgreen dhg->size++; 9169587Sgreen gen = strsep(&cp, " "); /* gen */ 9269587Sgreen if (cp == NULL || *gen == '\0') 9369587Sgreen goto fail; 9469587Sgreen prime = strsep(&cp, " "); /* prime */ 9569587Sgreen if (cp != NULL || *prime == '\0') 9669587Sgreen goto fail; 9769587Sgreen 9892555Sdes if ((dhg->g = BN_new()) == NULL) 9992555Sdes fatal("parse_prime: BN_new failed"); 10092555Sdes if ((dhg->p = BN_new()) == NULL) 10192555Sdes fatal("parse_prime: BN_new failed"); 10276259Sgreen if (BN_hex2bn(&dhg->g, gen) == 0) 10376259Sgreen goto failclean; 10469587Sgreen 10576259Sgreen if (BN_hex2bn(&dhg->p, prime) == 0) 10676259Sgreen goto failclean; 10776259Sgreen 10876259Sgreen if (BN_num_bits(dhg->p) != dhg->size) 10976259Sgreen goto failclean; 11076259Sgreen 111128456Sdes if (BN_is_zero(dhg->g) || BN_is_one(dhg->g)) 112128456Sdes goto failclean; 113128456Sdes 11469587Sgreen return (1); 11576259Sgreen 11676259Sgreen failclean: 11792555Sdes BN_clear_free(dhg->g); 11892555Sdes BN_clear_free(dhg->p); 11969587Sgreen fail: 12076259Sgreen error("Bad prime description in line %d", linenum); 12169587Sgreen return (0); 12269587Sgreen} 12369587Sgreen 12469587SgreenDH * 12576259Sgreenchoose_dh(int min, int wantbits, int max) 12669587Sgreen{ 12769587Sgreen FILE *f; 128128456Sdes char line[4096]; 12969587Sgreen int best, bestcount, which; 13069587Sgreen int linenum; 13169587Sgreen struct dhgroup dhg; 13269587Sgreen 13392555Sdes if ((f = fopen(_PATH_DH_MODULI, "r")) == NULL && 13492555Sdes (f = fopen(_PATH_DH_PRIMES, "r")) == NULL) { 135137015Sdes logit("WARNING: %s does not exist, using fixed modulus", 136137015Sdes _PATH_DH_MODULI); 137137015Sdes return (dh_new_group14()); 13869587Sgreen } 13969587Sgreen 14069587Sgreen linenum = 0; 14169587Sgreen best = bestcount = 0; 14269587Sgreen while (fgets(line, sizeof(line), f)) { 14369587Sgreen linenum++; 14469587Sgreen if (!parse_prime(linenum, line, &dhg)) 14569587Sgreen continue; 14692555Sdes BN_clear_free(dhg.g); 14792555Sdes BN_clear_free(dhg.p); 14869587Sgreen 14976259Sgreen if (dhg.size > max || dhg.size < min) 15076259Sgreen continue; 15176259Sgreen 15276259Sgreen if ((dhg.size > wantbits && dhg.size < best) || 15376259Sgreen (dhg.size > best && best < wantbits)) { 15469587Sgreen best = dhg.size; 15569587Sgreen bestcount = 0; 15669587Sgreen } 15769587Sgreen if (dhg.size == best) 15869587Sgreen bestcount++; 15969587Sgreen } 16092555Sdes rewind(f); 16169587Sgreen 16269587Sgreen if (bestcount == 0) { 16392555Sdes fclose(f); 164124208Sdes logit("WARNING: no suitable primes in %s", _PATH_DH_PRIMES); 165137015Sdes return (dh_new_group14()); 16669587Sgreen } 16769587Sgreen 16869587Sgreen linenum = 0; 169181111Sdes which = arc4random_uniform(bestcount); 17069587Sgreen while (fgets(line, sizeof(line), f)) { 17169587Sgreen if (!parse_prime(linenum, line, &dhg)) 17269587Sgreen continue; 17376259Sgreen if ((dhg.size > max || dhg.size < min) || 17476259Sgreen dhg.size != best || 17576259Sgreen linenum++ != which) { 17692555Sdes BN_clear_free(dhg.g); 17792555Sdes BN_clear_free(dhg.p); 17869587Sgreen continue; 17969587Sgreen } 18069587Sgreen break; 18169587Sgreen } 18269587Sgreen fclose(f); 18376259Sgreen if (linenum != which+1) 18476259Sgreen fatal("WARNING: line %d disappeared in %s, giving up", 18576259Sgreen which, _PATH_DH_PRIMES); 18669587Sgreen 18769587Sgreen return (dh_new_group(dhg.g, dhg.p)); 18869587Sgreen} 18976259Sgreen 190137015Sdes/* diffie-hellman-groupN-sha1 */ 19176259Sgreen 19276259Sgreenint 19376259Sgreendh_pub_is_valid(DH *dh, BIGNUM *dh_pub) 19476259Sgreen{ 19576259Sgreen int i; 19676259Sgreen int n = BN_num_bits(dh_pub); 19776259Sgreen int bits_set = 0; 198162852Sdes BIGNUM *tmp; 19976259Sgreen 20076259Sgreen if (dh_pub->neg) { 201181111Sdes logit("invalid public DH value: negative"); 20276259Sgreen return 0; 20376259Sgreen } 204162852Sdes if (BN_cmp(dh_pub, BN_value_one()) != 1) { /* pub_exp <= 1 */ 205162852Sdes logit("invalid public DH value: <= 1"); 206162852Sdes return 0; 207162852Sdes } 208162852Sdes 209181111Sdes if ((tmp = BN_new()) == NULL) { 210181111Sdes error("%s: BN_new failed", __func__); 211181111Sdes return 0; 212181111Sdes } 213162852Sdes if (!BN_sub(tmp, dh->p, BN_value_one()) || 214162852Sdes BN_cmp(dh_pub, tmp) != -1) { /* pub_exp > p-2 */ 215162852Sdes BN_clear_free(tmp); 216162852Sdes logit("invalid public DH value: >= p-1"); 217162852Sdes return 0; 218162852Sdes } 219162852Sdes BN_clear_free(tmp); 220162852Sdes 22176259Sgreen for (i = 0; i <= n; i++) 22276259Sgreen if (BN_is_bit_set(dh_pub, i)) 22376259Sgreen bits_set++; 224113908Sdes debug2("bits set: %d/%d", bits_set, BN_num_bits(dh->p)); 22576259Sgreen 22676259Sgreen /* if g==2 and bits_set==1 then computing log_g(dh_pub) is trivial */ 227162852Sdes if (bits_set > 1) 22876259Sgreen return 1; 229162852Sdes 230124208Sdes logit("invalid public DH value (%d/%d)", bits_set, BN_num_bits(dh->p)); 23176259Sgreen return 0; 23276259Sgreen} 23376259Sgreen 23476259Sgreenvoid 23576259Sgreendh_gen_key(DH *dh, int need) 23676259Sgreen{ 237128456Sdes int i, bits_set, tries = 0; 23876259Sgreen 23976259Sgreen if (dh->p == NULL) 24076259Sgreen fatal("dh_gen_key: dh->p == NULL"); 241126274Sdes if (need > INT_MAX / 2 || 2 * need >= BN_num_bits(dh->p)) 24276259Sgreen fatal("dh_gen_key: group too small: %d (2*need %d)", 24376259Sgreen BN_num_bits(dh->p), 2*need); 24476259Sgreen do { 24576259Sgreen if (dh->priv_key != NULL) 24692555Sdes BN_clear_free(dh->priv_key); 24792555Sdes if ((dh->priv_key = BN_new()) == NULL) 24876259Sgreen fatal("dh_gen_key: BN_new failed"); 24976259Sgreen /* generate a 2*need bits random private exponent */ 25076259Sgreen if (!BN_rand(dh->priv_key, 2*need, 0, 0)) 25176259Sgreen fatal("dh_gen_key: BN_rand failed"); 25276259Sgreen if (DH_generate_key(dh) == 0) 25376259Sgreen fatal("DH_generate_key"); 254128456Sdes for (i = 0, bits_set = 0; i <= BN_num_bits(dh->priv_key); i++) 25576259Sgreen if (BN_is_bit_set(dh->priv_key, i)) 25676259Sgreen bits_set++; 257113908Sdes debug2("dh_gen_key: priv key bits set: %d/%d", 25876259Sgreen bits_set, BN_num_bits(dh->priv_key)); 25976259Sgreen if (tries++ > 10) 26076259Sgreen fatal("dh_gen_key: too many bad keys: giving up"); 26176259Sgreen } while (!dh_pub_is_valid(dh, dh->pub_key)); 26276259Sgreen} 26376259Sgreen 26476259SgreenDH * 26576259Sgreendh_new_group_asc(const char *gen, const char *modulus) 26676259Sgreen{ 26776259Sgreen DH *dh; 26876259Sgreen 26992555Sdes if ((dh = DH_new()) == NULL) 27092555Sdes fatal("dh_new_group_asc: DH_new"); 27176259Sgreen 27276259Sgreen if (BN_hex2bn(&dh->p, modulus) == 0) 27376259Sgreen fatal("BN_hex2bn p"); 27476259Sgreen if (BN_hex2bn(&dh->g, gen) == 0) 27576259Sgreen fatal("BN_hex2bn g"); 27676259Sgreen 27776259Sgreen return (dh); 27876259Sgreen} 27976259Sgreen 28076259Sgreen/* 28176259Sgreen * This just returns the group, we still need to generate the exchange 28276259Sgreen * value. 28376259Sgreen */ 28476259Sgreen 28576259SgreenDH * 28676259Sgreendh_new_group(BIGNUM *gen, BIGNUM *modulus) 28776259Sgreen{ 28876259Sgreen DH *dh; 28976259Sgreen 29092555Sdes if ((dh = DH_new()) == NULL) 29192555Sdes fatal("dh_new_group: DH_new"); 29276259Sgreen dh->p = modulus; 29376259Sgreen dh->g = gen; 29476259Sgreen 29576259Sgreen return (dh); 29676259Sgreen} 29776259Sgreen 29876259SgreenDH * 29976259Sgreendh_new_group1(void) 30076259Sgreen{ 30176259Sgreen static char *gen = "2", *group1 = 30276259Sgreen "FFFFFFFF" "FFFFFFFF" "C90FDAA2" "2168C234" "C4C6628B" "80DC1CD1" 30376259Sgreen "29024E08" "8A67CC74" "020BBEA6" "3B139B22" "514A0879" "8E3404DD" 30476259Sgreen "EF9519B3" "CD3A431B" "302B0A6D" "F25F1437" "4FE1356D" "6D51C245" 30576259Sgreen "E485B576" "625E7EC6" "F44C42E9" "A637ED6B" "0BFF5CB6" "F406B7ED" 30676259Sgreen "EE386BFB" "5A899FA5" "AE9F2411" "7C4B1FE6" "49286651" "ECE65381" 30776259Sgreen "FFFFFFFF" "FFFFFFFF"; 30876259Sgreen 30976259Sgreen return (dh_new_group_asc(gen, group1)); 31076259Sgreen} 31176259Sgreen 312137015SdesDH * 313137015Sdesdh_new_group14(void) 314137015Sdes{ 315137015Sdes static char *gen = "2", *group14 = 316137015Sdes "FFFFFFFF" "FFFFFFFF" "C90FDAA2" "2168C234" "C4C6628B" "80DC1CD1" 317137015Sdes "29024E08" "8A67CC74" "020BBEA6" "3B139B22" "514A0879" "8E3404DD" 318137015Sdes "EF9519B3" "CD3A431B" "302B0A6D" "F25F1437" "4FE1356D" "6D51C245" 319137015Sdes "E485B576" "625E7EC6" "F44C42E9" "A637ED6B" "0BFF5CB6" "F406B7ED" 320137015Sdes "EE386BFB" "5A899FA5" "AE9F2411" "7C4B1FE6" "49286651" "ECE45B3D" 321137015Sdes "C2007CB8" "A163BF05" "98DA4836" "1C55D39A" "69163FA8" "FD24CF5F" 322137015Sdes "83655D23" "DCA3AD96" "1C62F356" "208552BB" "9ED52907" "7096966D" 323137015Sdes "670C354E" "4ABC9804" "F1746C08" "CA18217C" "32905E46" "2E36CE3B" 324137015Sdes "E39E772C" "180E8603" "9B2783A2" "EC07A28F" "B5C55DF0" "6F4C52C9" 325137015Sdes "DE2BCBF6" "95581718" "3995497C" "EA956AE5" "15D22618" "98FA0510" 326137015Sdes "15728E5A" "8AACAA68" "FFFFFFFF" "FFFFFFFF"; 327137015Sdes 328137015Sdes return (dh_new_group_asc(gen, group14)); 329137015Sdes} 330137015Sdes 33176259Sgreen/* 33276259Sgreen * Estimates the group order for a Diffie-Hellman group that has an 33376259Sgreen * attack complexity approximately the same as O(2**bits). Estimate 33476259Sgreen * with: O(exp(1.9223 * (ln q)^(1/3) (ln ln q)^(2/3))) 33576259Sgreen */ 33676259Sgreen 33776259Sgreenint 33876259Sgreendh_estimate(int bits) 33976259Sgreen{ 34076259Sgreen 341126274Sdes if (bits <= 128) 34276259Sgreen return (1024); /* O(2**86) */ 343126274Sdes if (bits <= 192) 34476259Sgreen return (2048); /* O(2**116) */ 34576259Sgreen return (4096); /* O(2**156) */ 34676259Sgreen} 347