dh.c revision 128456
1148330Snetchild/* 2148330Snetchild * Copyright (c) 2000 Niels Provos. All rights reserved. 3148330Snetchild * 4148330Snetchild * Redistribution and use in source and binary forms, with or without 5148330Snetchild * modification, are permitted provided that the following conditions 6148330Snetchild * are met: 7148330Snetchild * 1. Redistributions of source code must retain the above copyright 8148330Snetchild * notice, this list of conditions and the following disclaimer. 9148330Snetchild * 2. Redistributions in binary form must reproduce the above copyright 10148330Snetchild * notice, this list of conditions and the following disclaimer in the 11148330Snetchild * documentation and/or other materials provided with the distribution. 12148330Snetchild * 13148330Snetchild * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR 14148543Snetchild * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES 15148543Snetchild * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. 16215669Snetchild * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT, 17215669Snetchild * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT 18215669Snetchild * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 19215669Snetchild * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 20215669Snetchild * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 21215669Snetchild * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF 22215669Snetchild * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 23215669Snetchild */ 24215669Snetchild 25216179Suqs#include "includes.h" 26216179SuqsRCSID("$OpenBSD: dh.c,v 1.29 2004/02/27 22:49:27 dtucker Exp $"); 27216179Suqs 28216179Suqs#include "xmalloc.h" 29216179Suqs 30216179Suqs#include <openssl/bn.h> 31216179Suqs#include <openssl/dh.h> 32216179Suqs#include <openssl/evp.h> 33216179Suqs 34216179Suqs#include "buffer.h" 35216179Suqs#include "cipher.h" 36216179Suqs#include "kex.h" 37216179Suqs#include "dh.h" 38216179Suqs#include "pathnames.h" 39216179Suqs#include "log.h" 40148330Snetchild#include "misc.h" 41249423Sdim 42249423Sdimstatic int 43249423Sdimparse_prime(int linenum, char *line, struct dhgroup *dhg) 44249423Sdim{ 45249423Sdim char *cp, *arg; 46249423Sdim char *strsize, *gen, *prime; 47249423Sdim 48249423Sdim cp = line; 49249423Sdim arg = strdelim(&cp); 50249423Sdim /* Ignore leading whitespace */ 51249423Sdim if (*arg == '\0') 52249423Sdim arg = strdelim(&cp); 53249423Sdim if (!arg || !*arg || *arg == '#') 54249423Sdim return 0; 55249423Sdim 56249423Sdim /* time */ 57249423Sdim if (cp == NULL || *arg == '\0') 58249423Sdim goto fail; 59249423Sdim arg = strsep(&cp, " "); /* type */ 60249423Sdim if (cp == NULL || *arg == '\0') 61249423Sdim goto fail; 62249423Sdim arg = strsep(&cp, " "); /* tests */ 63249423Sdim if (cp == NULL || *arg == '\0') 64249423Sdim goto fail; 65249423Sdim arg = strsep(&cp, " "); /* tries */ 66249423Sdim if (cp == NULL || *arg == '\0') 67249423Sdim goto fail; 68249423Sdim strsize = strsep(&cp, " "); /* size */ 69249423Sdim if (cp == NULL || *strsize == '\0' || 70249423Sdim (dhg->size = atoi(strsize)) == 0) 71249423Sdim goto fail; 72249084Smav /* The whole group is one bit larger */ 73249473Santoine dhg->size++; 74249084Smav gen = strsep(&cp, " "); /* gen */ 75249084Smav if (cp == NULL || *gen == '\0') 76249084Smav goto fail; 77249084Smav prime = strsep(&cp, " "); /* prime */ 78249172Srene if (cp != NULL || *prime == '\0') 79249090Smav goto fail; 80248682Santoine 81248370Sglebius if ((dhg->g = BN_new()) == NULL) 82248682Santoine fatal("parse_prime: BN_new failed"); 83248682Santoine if ((dhg->p = BN_new()) == NULL) 84248682Santoine fatal("parse_prime: BN_new failed"); 85248151Sbapt if (BN_hex2bn(&dhg->g, gen) == 0) 86248151Sbapt goto failclean; 87248151Sbapt 88248151Sbapt if (BN_hex2bn(&dhg->p, prime) == 0) 89248139Santoine goto failclean; 90248097Sattilio 91248097Sattilio if (BN_num_bits(dhg->p) != dhg->size) 92248097Sattilio goto failclean; 93248097Sattilio 94248097Sattilio if (BN_is_zero(dhg->g) || BN_is_one(dhg->g)) 95248097Sattilio goto failclean; 96248097Sattilio 97248097Sattilio return (1); 98248097Sattilio 99248097Sattilio failclean: 100248097Sattilio BN_clear_free(dhg->g); 101248097Sattilio BN_clear_free(dhg->p); 102248097Sattilio fail: 103248097Sattilio error("Bad prime description in line %d", linenum); 104248097Sattilio return (0); 105248097Sattilio} 106248097Sattilio 107248097SattilioDH * 108248097Sattiliochoose_dh(int min, int wantbits, int max) 109248097Sattilio{ 110248097Sattilio FILE *f; 111248097Sattilio char line[4096]; 112248097Sattilio int best, bestcount, which; 113248097Sattilio int linenum; 114248097Sattilio struct dhgroup dhg; 115248097Sattilio 116248097Sattilio if ((f = fopen(_PATH_DH_MODULI, "r")) == NULL && 117248097Sattilio (f = fopen(_PATH_DH_PRIMES, "r")) == NULL) { 118248097Sattilio logit("WARNING: %s does not exist, using old modulus", _PATH_DH_MODULI); 119248097Sattilio return (dh_new_group1()); 120248097Sattilio } 121248097Sattilio 122248138Santoine linenum = 0; 123248138Santoine best = bestcount = 0; 124248139Santoine while (fgets(line, sizeof(line), f)) { 125248097Sattilio linenum++; 126248097Sattilio if (!parse_prime(linenum, line, &dhg)) 127248097Sattilio continue; 128248097Sattilio BN_clear_free(dhg.g); 129247665Sattilio BN_clear_free(dhg.p); 130247709Santoine 131247709Santoine if (dhg.size > max || dhg.size < min) 132247665Sattilio continue; 133247665Sattilio 134247665Sattilio if ((dhg.size > wantbits && dhg.size < best) || 135247665Sattilio (dhg.size > best && best < wantbits)) { 136247665Sattilio best = dhg.size; 137247665Sattilio bestcount = 0; 138247665Sattilio } 139247665Sattilio if (dhg.size == best) 140247665Sattilio bestcount++; 141247640Sattilio } 142247640Sattilio rewind(f); 143247640Sattilio 144247709Santoine if (bestcount == 0) { 145247640Sattilio fclose(f); 146247640Sattilio logit("WARNING: no suitable primes in %s", _PATH_DH_PRIMES); 147247640Sattilio return (NULL); 148247640Sattilio } 149247635Sattilio 150247635Sattilio linenum = 0; 151247631Sattilio which = arc4random() % bestcount; 152247631Sattilio while (fgets(line, sizeof(line), f)) { 153248136Santoine if (!parse_prime(linenum, line, &dhg)) 154248136Santoine continue; 155248136Santoine if ((dhg.size > max || dhg.size < min) || 156248136Santoine dhg.size != best || 157248136Santoine linenum++ != which) { 158248136Santoine BN_clear_free(dhg.g); 159245513Sbrooks BN_clear_free(dhg.p); 160245513Sbrooks continue; 161245513Sbrooks } 162245513Sbrooks break; 163245513Sbrooks } 164245513Sbrooks fclose(f); 165245513Sbrooks if (linenum != which+1) 166246591Santoine fatal("WARNING: line %d disappeared in %s, giving up", 167246591Santoine which, _PATH_DH_PRIMES); 168246591Santoine 169246591Santoine return (dh_new_group(dhg.g, dhg.p)); 170244865Snwhitehorn} 171244865Snwhitehorn 172244865Snwhitehorn/* diffie-hellman-group1-sha1 */ 173244855Sume 174244855Sumeint 175244855Sumedh_pub_is_valid(DH *dh, BIGNUM *dh_pub) 176243014Smm{ 177243014Smm int i; 178243071Seadler int n = BN_num_bits(dh_pub); 179247709Santoine int bits_set = 0; 180247709Santoine 181247709Santoine if (dh_pub->neg) { 182247709Santoine logit("invalid public DH value: negativ"); 183241896Skib return 0; 184241896Skib } 185241927Skib for (i = 0; i <= n; i++) 186241214Sjkim if (BN_is_bit_set(dh_pub, i)) 187241214Sjkim bits_set++; 188242481Santoine debug2("bits set: %d/%d", bits_set, BN_num_bits(dh->p)); 189242481Santoine 190242481Santoine /* if g==2 and bits_set==1 then computing log_g(dh_pub) is trivial */ 191243795Santoine if (bits_set > 1 && (BN_cmp(dh_pub, dh->p) == -1)) 192243795Santoine return 1; 193243795Santoine logit("invalid public DH value (%d/%d)", bits_set, BN_num_bits(dh->p)); 194240264Sglebius return 0; 195240264Sglebius} 196239462Sdim 197239747Sdimvoid 198239747Sdimdh_gen_key(DH *dh, int need) 199239462Sdim{ 200239462Sdim int i, bits_set, tries = 0; 201239462Sdim 202239462Sdim if (dh->p == NULL) 203239462Sdim fatal("dh_gen_key: dh->p == NULL"); 204239462Sdim if (need > INT_MAX / 2 || 2 * need >= BN_num_bits(dh->p)) 205239462Sdim fatal("dh_gen_key: group too small: %d (2*need %d)", 206239462Sdim BN_num_bits(dh->p), 2*need); 207239462Sdim do { 208239462Sdim if (dh->priv_key != NULL) 209239462Sdim BN_clear_free(dh->priv_key); 210239462Sdim if ((dh->priv_key = BN_new()) == NULL) 211239462Sdim fatal("dh_gen_key: BN_new failed"); 212239462Sdim /* generate a 2*need bits random private exponent */ 213239462Sdim if (!BN_rand(dh->priv_key, 2*need, 0, 0)) 214239462Sdim fatal("dh_gen_key: BN_rand failed"); 215239462Sdim if (DH_generate_key(dh) == 0) 216239462Sdim fatal("DH_generate_key"); 217239462Sdim for (i = 0, bits_set = 0; i <= BN_num_bits(dh->priv_key); i++) 218239462Sdim if (BN_is_bit_set(dh->priv_key, i)) 219239462Sdim bits_set++; 220239462Sdim debug2("dh_gen_key: priv key bits set: %d/%d", 221239462Sdim bits_set, BN_num_bits(dh->priv_key)); 222239462Sdim if (tries++ > 10) 223239747Sdim fatal("dh_gen_key: too many bad keys: giving up"); 224238405Sjkim } while (!dh_pub_is_valid(dh, dh->pub_key)); 225238412Sjkim} 226238412Sjkim 227238412SjkimDH * 228238412Sjkimdh_new_group_asc(const char *gen, const char *modulus) 229238405Sjkim{ 230238405Sjkim DH *dh; 231238405Sjkim 232238405Sjkim if ((dh = DH_new()) == NULL) 233238405Sjkim fatal("dh_new_group_asc: DH_new"); 234238405Sjkim 235238405Sjkim if (BN_hex2bn(&dh->p, modulus) == 0) 236238405Sjkim fatal("BN_hex2bn p"); 237238405Sjkim if (BN_hex2bn(&dh->g, gen) == 0) 238238405Sjkim fatal("BN_hex2bn g"); 239238405Sjkim 240238202Seadler return (dh); 241238202Seadler} 242242481Santoine 243242481Santoine/* 244237005Sdes * This just returns the group, we still need to generate the exchange 245237006Sdes * value. 246237011Sdes */ 247237006Sdes 248242481SantoineDH * 249237006Sdesdh_new_group(BIGNUM *gen, BIGNUM *modulus) 250236281Smiwi{ 251237006Sdes DH *dh; 252242481Santoine 253242481Santoine if ((dh = DH_new()) == NULL) 254242481Santoine fatal("dh_new_group: DH_new"); 255235058Sdim dh->p = modulus; 256235058Sdim dh->g = gen; 257235331Santoine 258235331Santoine return (dh); 259235331Santoine} 260235331Santoine 261235331SantoineDH * 262235331Santoinedh_new_group1(void) 263235331Santoine{ 264235331Santoine static char *gen = "2", *group1 = 265235331Santoine "FFFFFFFF" "FFFFFFFF" "C90FDAA2" "2168C234" "C4C6628B" "80DC1CD1" 266235331Santoine "29024E08" "8A67CC74" "020BBEA6" "3B139B22" "514A0879" "8E3404DD" 267234728Shselasky "EF9519B3" "CD3A431B" "302B0A6D" "F25F1437" "4FE1356D" "6D51C245" 268234728Shselasky "E485B576" "625E7EC6" "F44C42E9" "A637ED6B" "0BFF5CB6" "F406B7ED" 269234728Shselasky "EE386BFB" "5A899FA5" "AE9F2411" "7C4B1FE6" "49286651" "ECE65381" 270235331Santoine "FFFFFFFF" "FFFFFFFF"; 271234353Sdim 272234353Sdim return (dh_new_group_asc(gen, group1)); 273234353Sdim} 274234353Sdim 275234353Sdim/* 276234353Sdim * Estimates the group order for a Diffie-Hellman group that has an 277234353Sdim * attack complexity approximately the same as O(2**bits). Estimate 278234353Sdim * with: O(exp(1.9223 * (ln q)^(1/3) (ln ln q)^(2/3))) 279234353Sdim */ 280234353Sdim 281234353Sdimint 282234353Sdimdh_estimate(int bits) 283234353Sdim{ 284234353Sdim 285234353Sdim if (bits <= 128) 286234353Sdim return (1024); /* O(2**86) */ 287235331Santoine if (bits <= 192) 288235331Santoine return (2048); /* O(2**116) */ 289235331Santoine return (4096); /* O(2**156) */ 290235331Santoine} 291235331Santoine