1255767Sdes/* $OpenBSD: dh.c,v 1.51 2013/07/02 12:31:43 markus 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 51255767Sdes dhg->p = dhg->g = NULL; 5269587Sgreen cp = line; 53162852Sdes if ((arg = strdelim(&cp)) == NULL) 54162852Sdes return 0; 5569587Sgreen /* Ignore leading whitespace */ 5669587Sgreen if (*arg == '\0') 5769587Sgreen arg = strdelim(&cp); 58106121Sdes if (!arg || !*arg || *arg == '#') 5969587Sgreen return 0; 6069587Sgreen 6169587Sgreen /* time */ 6269587Sgreen if (cp == NULL || *arg == '\0') 63255767Sdes goto truncated; 6469587Sgreen arg = strsep(&cp, " "); /* type */ 6569587Sgreen if (cp == NULL || *arg == '\0') 66255767Sdes goto truncated; 67181111Sdes /* Ensure this is a safe prime */ 68181111Sdes n = strtonum(arg, 0, 5, &errstr); 69255767Sdes if (errstr != NULL || n != MODULI_TYPE_SAFE) { 70255767Sdes error("moduli:%d: type is not %d", linenum, MODULI_TYPE_SAFE); 71181111Sdes goto fail; 72255767Sdes } 7369587Sgreen arg = strsep(&cp, " "); /* tests */ 7469587Sgreen if (cp == NULL || *arg == '\0') 75255767Sdes goto truncated; 76181111Sdes /* Ensure prime has been tested and is not composite */ 77181111Sdes n = strtonum(arg, 0, 0x1f, &errstr); 78181111Sdes if (errstr != NULL || 79255767Sdes (n & MODULI_TESTS_COMPOSITE) || !(n & ~MODULI_TESTS_COMPOSITE)) { 80255767Sdes error("moduli:%d: invalid moduli tests flag", linenum); 81181111Sdes goto fail; 82255767Sdes } 8369587Sgreen arg = strsep(&cp, " "); /* tries */ 8469587Sgreen if (cp == NULL || *arg == '\0') 85255767Sdes goto truncated; 86181111Sdes n = strtonum(arg, 0, 1<<30, &errstr); 87255767Sdes if (errstr != NULL || n == 0) { 88255767Sdes error("moduli:%d: invalid primality trial count", linenum); 89181111Sdes goto fail; 90255767Sdes } 9169587Sgreen strsize = strsep(&cp, " "); /* size */ 9269587Sgreen if (cp == NULL || *strsize == '\0' || 93204917Sdes (dhg->size = (int)strtonum(strsize, 0, 64*1024, &errstr)) == 0 || 94255767Sdes errstr) { 95255767Sdes error("moduli:%d: invalid prime length", linenum); 9669587Sgreen goto fail; 97255767Sdes } 9876259Sgreen /* The whole group is one bit larger */ 9976259Sgreen dhg->size++; 10069587Sgreen gen = strsep(&cp, " "); /* gen */ 10169587Sgreen if (cp == NULL || *gen == '\0') 102255767Sdes goto truncated; 10369587Sgreen prime = strsep(&cp, " "); /* prime */ 104255767Sdes if (cp != NULL || *prime == '\0') { 105255767Sdes truncated: 106255767Sdes error("moduli:%d: truncated", linenum); 10769587Sgreen goto fail; 108255767Sdes } 10969587Sgreen 11092555Sdes if ((dhg->g = BN_new()) == NULL) 11192555Sdes fatal("parse_prime: BN_new failed"); 11292555Sdes if ((dhg->p = BN_new()) == NULL) 11392555Sdes fatal("parse_prime: BN_new failed"); 114255767Sdes if (BN_hex2bn(&dhg->g, gen) == 0) { 115255767Sdes error("moduli:%d: could not parse generator value", linenum); 116255767Sdes goto fail; 117255767Sdes } 118255767Sdes if (BN_hex2bn(&dhg->p, prime) == 0) { 119255767Sdes error("moduli:%d: could not parse prime value", linenum); 120255767Sdes goto fail; 121255767Sdes } 122255767Sdes if (BN_num_bits(dhg->p) != dhg->size) { 123255767Sdes error("moduli:%d: prime has wrong size: actual %d listed %d", 124255767Sdes linenum, BN_num_bits(dhg->p), dhg->size - 1); 125255767Sdes goto fail; 126255767Sdes } 127255767Sdes if (BN_cmp(dhg->g, BN_value_one()) <= 0) { 128255767Sdes error("moduli:%d: generator is invalid", linenum); 129255767Sdes goto fail; 130255767Sdes } 13169587Sgreen 132255767Sdes return 1; 13376259Sgreen 13469587Sgreen fail: 135255767Sdes if (dhg->g != NULL) 136255767Sdes BN_clear_free(dhg->g); 137255767Sdes if (dhg->p != NULL) 138255767Sdes BN_clear_free(dhg->p); 139255767Sdes dhg->g = dhg->p = NULL; 14076259Sgreen error("Bad prime description in line %d", linenum); 141255767Sdes return 0; 14269587Sgreen} 14369587Sgreen 14469587SgreenDH * 14576259Sgreenchoose_dh(int min, int wantbits, int max) 14669587Sgreen{ 14769587Sgreen FILE *f; 148128456Sdes char line[4096]; 14969587Sgreen int best, bestcount, which; 15069587Sgreen int linenum; 15169587Sgreen struct dhgroup dhg; 15269587Sgreen 15392555Sdes if ((f = fopen(_PATH_DH_MODULI, "r")) == NULL && 15492555Sdes (f = fopen(_PATH_DH_PRIMES, "r")) == NULL) { 155137015Sdes logit("WARNING: %s does not exist, using fixed modulus", 156137015Sdes _PATH_DH_MODULI); 157137015Sdes return (dh_new_group14()); 15869587Sgreen } 15969587Sgreen 16069587Sgreen linenum = 0; 16169587Sgreen best = bestcount = 0; 16269587Sgreen while (fgets(line, sizeof(line), f)) { 16369587Sgreen linenum++; 16469587Sgreen if (!parse_prime(linenum, line, &dhg)) 16569587Sgreen continue; 16692555Sdes BN_clear_free(dhg.g); 16792555Sdes BN_clear_free(dhg.p); 16869587Sgreen 16976259Sgreen if (dhg.size > max || dhg.size < min) 17076259Sgreen continue; 17176259Sgreen 17276259Sgreen if ((dhg.size > wantbits && dhg.size < best) || 17376259Sgreen (dhg.size > best && best < wantbits)) { 17469587Sgreen best = dhg.size; 17569587Sgreen bestcount = 0; 17669587Sgreen } 17769587Sgreen if (dhg.size == best) 17869587Sgreen bestcount++; 17969587Sgreen } 18092555Sdes rewind(f); 18169587Sgreen 18269587Sgreen if (bestcount == 0) { 18392555Sdes fclose(f); 184124208Sdes logit("WARNING: no suitable primes in %s", _PATH_DH_PRIMES); 185137015Sdes return (dh_new_group14()); 18669587Sgreen } 18769587Sgreen 18869587Sgreen linenum = 0; 189181111Sdes which = arc4random_uniform(bestcount); 19069587Sgreen while (fgets(line, sizeof(line), f)) { 19169587Sgreen if (!parse_prime(linenum, line, &dhg)) 19269587Sgreen continue; 19376259Sgreen if ((dhg.size > max || dhg.size < min) || 19476259Sgreen dhg.size != best || 19576259Sgreen linenum++ != which) { 19692555Sdes BN_clear_free(dhg.g); 19792555Sdes BN_clear_free(dhg.p); 19869587Sgreen continue; 19969587Sgreen } 20069587Sgreen break; 20169587Sgreen } 20269587Sgreen fclose(f); 20376259Sgreen if (linenum != which+1) 20476259Sgreen fatal("WARNING: line %d disappeared in %s, giving up", 20576259Sgreen which, _PATH_DH_PRIMES); 20669587Sgreen 20769587Sgreen return (dh_new_group(dhg.g, dhg.p)); 20869587Sgreen} 20976259Sgreen 210137015Sdes/* diffie-hellman-groupN-sha1 */ 21176259Sgreen 21276259Sgreenint 21376259Sgreendh_pub_is_valid(DH *dh, BIGNUM *dh_pub) 21476259Sgreen{ 21576259Sgreen int i; 21676259Sgreen int n = BN_num_bits(dh_pub); 21776259Sgreen int bits_set = 0; 218162852Sdes BIGNUM *tmp; 21976259Sgreen 22076259Sgreen if (dh_pub->neg) { 221181111Sdes logit("invalid public DH value: negative"); 22276259Sgreen return 0; 22376259Sgreen } 224162852Sdes if (BN_cmp(dh_pub, BN_value_one()) != 1) { /* pub_exp <= 1 */ 225162852Sdes logit("invalid public DH value: <= 1"); 226162852Sdes return 0; 227162852Sdes } 228162852Sdes 229181111Sdes if ((tmp = BN_new()) == NULL) { 230181111Sdes error("%s: BN_new failed", __func__); 231181111Sdes return 0; 232181111Sdes } 233162852Sdes if (!BN_sub(tmp, dh->p, BN_value_one()) || 234162852Sdes BN_cmp(dh_pub, tmp) != -1) { /* pub_exp > p-2 */ 235162852Sdes BN_clear_free(tmp); 236162852Sdes logit("invalid public DH value: >= p-1"); 237162852Sdes return 0; 238162852Sdes } 239162852Sdes BN_clear_free(tmp); 240162852Sdes 24176259Sgreen for (i = 0; i <= n; i++) 24276259Sgreen if (BN_is_bit_set(dh_pub, i)) 24376259Sgreen bits_set++; 244113908Sdes debug2("bits set: %d/%d", bits_set, BN_num_bits(dh->p)); 24576259Sgreen 24676259Sgreen /* if g==2 and bits_set==1 then computing log_g(dh_pub) is trivial */ 247162852Sdes if (bits_set > 1) 24876259Sgreen return 1; 249162852Sdes 250124208Sdes logit("invalid public DH value (%d/%d)", bits_set, BN_num_bits(dh->p)); 25176259Sgreen return 0; 25276259Sgreen} 25376259Sgreen 25476259Sgreenvoid 25576259Sgreendh_gen_key(DH *dh, int need) 25676259Sgreen{ 257128456Sdes int i, bits_set, tries = 0; 25876259Sgreen 259240075Sdes if (need < 0) 260240075Sdes fatal("dh_gen_key: need < 0"); 26176259Sgreen if (dh->p == NULL) 26276259Sgreen fatal("dh_gen_key: dh->p == NULL"); 263126274Sdes if (need > INT_MAX / 2 || 2 * need >= BN_num_bits(dh->p)) 26476259Sgreen fatal("dh_gen_key: group too small: %d (2*need %d)", 26576259Sgreen BN_num_bits(dh->p), 2*need); 26676259Sgreen do { 26776259Sgreen if (dh->priv_key != NULL) 26892555Sdes BN_clear_free(dh->priv_key); 26992555Sdes if ((dh->priv_key = BN_new()) == NULL) 27076259Sgreen fatal("dh_gen_key: BN_new failed"); 27176259Sgreen /* generate a 2*need bits random private exponent */ 27276259Sgreen if (!BN_rand(dh->priv_key, 2*need, 0, 0)) 27376259Sgreen fatal("dh_gen_key: BN_rand failed"); 27476259Sgreen if (DH_generate_key(dh) == 0) 27576259Sgreen fatal("DH_generate_key"); 276128456Sdes for (i = 0, bits_set = 0; i <= BN_num_bits(dh->priv_key); i++) 27776259Sgreen if (BN_is_bit_set(dh->priv_key, i)) 27876259Sgreen bits_set++; 279113908Sdes debug2("dh_gen_key: priv key bits set: %d/%d", 28076259Sgreen bits_set, BN_num_bits(dh->priv_key)); 28176259Sgreen if (tries++ > 10) 28276259Sgreen fatal("dh_gen_key: too many bad keys: giving up"); 28376259Sgreen } while (!dh_pub_is_valid(dh, dh->pub_key)); 28476259Sgreen} 28576259Sgreen 28676259SgreenDH * 28776259Sgreendh_new_group_asc(const char *gen, const char *modulus) 28876259Sgreen{ 28976259Sgreen DH *dh; 29076259Sgreen 29192555Sdes if ((dh = DH_new()) == NULL) 29292555Sdes fatal("dh_new_group_asc: DH_new"); 29376259Sgreen 29476259Sgreen if (BN_hex2bn(&dh->p, modulus) == 0) 29576259Sgreen fatal("BN_hex2bn p"); 29676259Sgreen if (BN_hex2bn(&dh->g, gen) == 0) 29776259Sgreen fatal("BN_hex2bn g"); 29876259Sgreen 29976259Sgreen return (dh); 30076259Sgreen} 30176259Sgreen 30276259Sgreen/* 30376259Sgreen * This just returns the group, we still need to generate the exchange 30476259Sgreen * value. 30576259Sgreen */ 30676259Sgreen 30776259SgreenDH * 30876259Sgreendh_new_group(BIGNUM *gen, BIGNUM *modulus) 30976259Sgreen{ 31076259Sgreen DH *dh; 31176259Sgreen 31292555Sdes if ((dh = DH_new()) == NULL) 31392555Sdes fatal("dh_new_group: DH_new"); 31476259Sgreen dh->p = modulus; 31576259Sgreen dh->g = gen; 31676259Sgreen 31776259Sgreen return (dh); 31876259Sgreen} 31976259Sgreen 32076259SgreenDH * 32176259Sgreendh_new_group1(void) 32276259Sgreen{ 32376259Sgreen static char *gen = "2", *group1 = 32476259Sgreen "FFFFFFFF" "FFFFFFFF" "C90FDAA2" "2168C234" "C4C6628B" "80DC1CD1" 32576259Sgreen "29024E08" "8A67CC74" "020BBEA6" "3B139B22" "514A0879" "8E3404DD" 32676259Sgreen "EF9519B3" "CD3A431B" "302B0A6D" "F25F1437" "4FE1356D" "6D51C245" 32776259Sgreen "E485B576" "625E7EC6" "F44C42E9" "A637ED6B" "0BFF5CB6" "F406B7ED" 32876259Sgreen "EE386BFB" "5A899FA5" "AE9F2411" "7C4B1FE6" "49286651" "ECE65381" 32976259Sgreen "FFFFFFFF" "FFFFFFFF"; 33076259Sgreen 33176259Sgreen return (dh_new_group_asc(gen, group1)); 33276259Sgreen} 33376259Sgreen 334137015SdesDH * 335137015Sdesdh_new_group14(void) 336137015Sdes{ 337137015Sdes static char *gen = "2", *group14 = 338137015Sdes "FFFFFFFF" "FFFFFFFF" "C90FDAA2" "2168C234" "C4C6628B" "80DC1CD1" 339137015Sdes "29024E08" "8A67CC74" "020BBEA6" "3B139B22" "514A0879" "8E3404DD" 340137015Sdes "EF9519B3" "CD3A431B" "302B0A6D" "F25F1437" "4FE1356D" "6D51C245" 341137015Sdes "E485B576" "625E7EC6" "F44C42E9" "A637ED6B" "0BFF5CB6" "F406B7ED" 342137015Sdes "EE386BFB" "5A899FA5" "AE9F2411" "7C4B1FE6" "49286651" "ECE45B3D" 343137015Sdes "C2007CB8" "A163BF05" "98DA4836" "1C55D39A" "69163FA8" "FD24CF5F" 344137015Sdes "83655D23" "DCA3AD96" "1C62F356" "208552BB" "9ED52907" "7096966D" 345137015Sdes "670C354E" "4ABC9804" "F1746C08" "CA18217C" "32905E46" "2E36CE3B" 346137015Sdes "E39E772C" "180E8603" "9B2783A2" "EC07A28F" "B5C55DF0" "6F4C52C9" 347137015Sdes "DE2BCBF6" "95581718" "3995497C" "EA956AE5" "15D22618" "98FA0510" 348137015Sdes "15728E5A" "8AACAA68" "FFFFFFFF" "FFFFFFFF"; 349137015Sdes 350137015Sdes return (dh_new_group_asc(gen, group14)); 351137015Sdes} 352137015Sdes 35376259Sgreen/* 35476259Sgreen * Estimates the group order for a Diffie-Hellman group that has an 35576259Sgreen * attack complexity approximately the same as O(2**bits). Estimate 35676259Sgreen * with: O(exp(1.9223 * (ln q)^(1/3) (ln ln q)^(2/3))) 35776259Sgreen */ 35876259Sgreen 35976259Sgreenint 36076259Sgreendh_estimate(int bits) 36176259Sgreen{ 36276259Sgreen 363126274Sdes if (bits <= 128) 36476259Sgreen return (1024); /* O(2**86) */ 365126274Sdes if (bits <= 192) 36676259Sgreen return (2048); /* O(2**116) */ 36776259Sgreen return (4096); /* O(2**156) */ 36876259Sgreen} 369