kex.c

   1 /*
   2  * Copyright (c) 2000 Markus Friedl.  All rights reserved.
   3  *
   4  * Redistribution and use in source and binary forms, with or without
   5  * modification, are permitted provided that the following conditions
   6  * are met:
   7  * 1. Redistributions of source code must retain the above copyright
   8  *    notice, this list of conditions and the following disclaimer.
   9  * 2. Redistributions in binary form must reproduce the above copyright
  10  *    notice, this list of conditions and the following disclaimer in the
  11  *    documentation and/or other materials provided with the distribution.
  12  *
  13  * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
  14  * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
  15  * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
  16  * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
  17  * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
  18  * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
  19  * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
  20  * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
  21  * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
  22  * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  23  */
  24
  25 #include "includes.h"
  26 RCSID("$OpenBSD: kex.c,v 1.24 2001/03/28 21:59:40 provos Exp $");
  27
  28 #include <openssl/crypto.h>
  29 #include <openssl/bio.h>
  30 #include <openssl/bn.h>
  31 #include <openssl/dh.h>
  32 #include <openssl/pem.h>
  33
  34 #include "ssh2.h"
  35 #include "xmalloc.h"
  36 #include "buffer.h"
  37 #include "bufaux.h"
  38 #include "packet.h"
  39 #include "compat.h"
  40 #include "cipher.h"
  41 #include "kex.h"
  42 #include "key.h"
  43 #include "log.h"
  44 #include "mac.h"
  45 #include "match.h"
  46
  47 #define KEX_COOKIE_LEN  16
  48
  49 Buffer *
  50 kex_init(char *myproposal[PROPOSAL_MAX])
  51 {
  52         int first_kex_packet_follows = 0;
  53         u_char cookie[KEX_COOKIE_LEN];
  54         u_int32_t rand = 0;
  55         int i;
  56         Buffer *ki = xmalloc(sizeof(*ki));
  57         for (i = 0; i < KEX_COOKIE_LEN; i++) {
  58                 if (i % 4 == 0)
  59                         rand = arc4random();
  60                 cookie[i] = rand & 0xff;
  61                 rand >>= 8;
  62         }
  63         buffer_init(ki);
  64         buffer_append(ki, (char *)cookie, sizeof cookie);
  65         for (i = 0; i < PROPOSAL_MAX; i++)
  66                 buffer_put_cstring(ki, myproposal[i]);
  67         buffer_put_char(ki, first_kex_packet_follows);
  68         buffer_put_int(ki, 0);                          /* uint32 reserved */
  69         return ki;
  70 }
  71
  72 /* send kexinit, parse and save reply */
  73 void
  74 kex_exchange_kexinit(
  75     Buffer *my_kexinit, Buffer *peer_kexint,
  76     char *peer_proposal[PROPOSAL_MAX])
  77 {
  78         int i;
  79         char *ptr;
  80         int plen;
  81
  82         debug("send KEXINIT");
  83         packet_start(SSH2_MSG_KEXINIT);
  84         packet_put_raw(buffer_ptr(my_kexinit), buffer_len(my_kexinit));
  85         packet_send();
  86         packet_write_wait();
  87         debug("done");
  88
  89         /*
  90          * read and save raw KEXINIT payload in buffer. this is used during
  91          * computation of the session_id and the session keys.
  92          */
  93         debug("wait KEXINIT");
  94         packet_read_expect(&plen, SSH2_MSG_KEXINIT);
  95         ptr = packet_get_raw(&plen);
  96         buffer_append(peer_kexint, ptr, plen);
  97
  98         /* parse packet and save algorithm proposal */
  99         /* skip cookie */
 100         for (i = 0; i < KEX_COOKIE_LEN; i++)
 101                 packet_get_char();
 102         /* extract kex init proposal strings */
 103         for (i = 0; i < PROPOSAL_MAX; i++) {
 104                 peer_proposal[i] = packet_get_string(NULL);
 105                 debug("got kexinit: %s", peer_proposal[i]);
 106         }
 107         /* first kex follow / reserved */
 108         i = packet_get_char();
 109         debug("first kex follow: %d ", i);
 110         i = packet_get_int();
 111         debug("reserved: %d ", i);
 112         packet_done();
 113         debug("done");
 114 }
 115
 116 /* diffie-hellman-group1-sha1 */
 117
 118 int
 119 dh_pub_is_valid(DH *dh, BIGNUM *dh_pub)
 120 {
 121         int i;
 122         int n = BN_num_bits(dh_pub);
 123         int bits_set = 0;
 124
 125         if (dh_pub->neg) {
 126                 log("invalid public DH value: negativ");
 127                 return 0;
 128         }
 129         for (i = 0; i <= n; i++)
 130                 if (BN_is_bit_set(dh_pub, i))
 131                         bits_set++;
 132         debug("bits set: %d/%d", bits_set, BN_num_bits(dh->p));
 133
 134         /* if g==2 and bits_set==1 then computing log_g(dh_pub) is trivial */
 135         if (bits_set > 1 && (BN_cmp(dh_pub, dh->p) == -1))
 136                 return 1;
 137         log("invalid public DH value (%d/%d)", bits_set, BN_num_bits(dh->p));
 138         return 0;
 139 }
 140
 141 void
 142 dh_gen_key(DH *dh, int need)
 143 {
 144         int i, bits_set = 0, tries = 0;
 145
 146         if (dh->p == NULL)
 147                 fatal("dh_gen_key: dh->p == NULL");
 148         if (2*need >= BN_num_bits(dh->p))
 149                 fatal("dh_gen_key: group too small: %d (2*need %d)",
 150                     BN_num_bits(dh->p), 2*need);
 151         do {
 152                 if (dh->priv_key != NULL)
 153                         BN_free(dh->priv_key);
 154                 dh->priv_key = BN_new();
 155                 if (dh->priv_key == NULL)
 156                         fatal("dh_gen_key: BN_new failed");
 157                 /* generate a 2*need bits random private exponent */
 158                 if (!BN_rand(dh->priv_key, 2*need, 0, 0))
 159                         fatal("dh_gen_key: BN_rand failed");
 160                 if (DH_generate_key(dh) == 0)
 161                         fatal("DH_generate_key");
 162                 for (i = 0; i <= BN_num_bits(dh->priv_key); i++)
 163                         if (BN_is_bit_set(dh->priv_key, i))
 164                                 bits_set++;
 165                 debug("dh_gen_key: priv key bits set: %d/%d",
 166                     bits_set, BN_num_bits(dh->priv_key));
 167                 if (tries++ > 10)
 168                         fatal("dh_gen_key: too many bad keys: giving up");
 169         } while (!dh_pub_is_valid(dh, dh->pub_key));
 170 }
 171
 172 DH *
 173 dh_new_group_asc(const char *gen, const char *modulus)
 174 {
 175         DH *dh;
 176         int ret;
 177
 178         dh = DH_new();
 179         if (dh == NULL)
 180                 fatal("DH_new");
 181
 182         if ((ret = BN_hex2bn(&dh->p, modulus)) < 0)
 183                 fatal("BN_hex2bn p");
 184         if ((ret = BN_hex2bn(&dh->g, gen)) < 0)
 185                 fatal("BN_hex2bn g");
 186
 187         return (dh);
 188 }
 189
 190 /*
 191  * This just returns the group, we still need to generate the exchange
 192  * value.
 193  */
 194
 195 DH *
 196 dh_new_group(BIGNUM *gen, BIGNUM *modulus)
 197 {
 198         DH *dh;
 199
 200         dh = DH_new();
 201         if (dh == NULL)
 202                 fatal("DH_new");
 203         dh->p = modulus;
 204         dh->g = gen;
 205
 206         return (dh);
 207 }
 208
 209 DH *
 210 dh_new_group1(void)
 211 {
 212         static char *gen = "2", *group1 =
 213             "FFFFFFFF" "FFFFFFFF" "C90FDAA2" "2168C234" "C4C6628B" "80DC1CD1"
 214             "29024E08" "8A67CC74" "020BBEA6" "3B139B22" "514A0879" "8E3404DD"
 215             "EF9519B3" "CD3A431B" "302B0A6D" "F25F1437" "4FE1356D" "6D51C245"
 216             "E485B576" "625E7EC6" "F44C42E9" "A637ED6B" "0BFF5CB6" "F406B7ED"
 217             "EE386BFB" "5A899FA5" "AE9F2411" "7C4B1FE6" "49286651" "ECE65381"
 218             "FFFFFFFF" "FFFFFFFF";
 219
 220         return (dh_new_group_asc(gen, group1));
 221 }
 222
 223 #ifdef DEBUG_KEX
 224 void
 225 dump_digest(u_char *digest, int len)
 226 {
 227         int i;
 228         for (i = 0; i< len; i++){
 229                 fprintf(stderr, "%02x", digest[i]);
 230                 if(i%2!=0)
 231                         fprintf(stderr, " ");
 232         }
 233         fprintf(stderr, "\n");
 234 }
 235 #endif
 236
 237 u_char *
 238 kex_hash(
 239     char *client_version_string,
 240     char *server_version_string,
 241     char *ckexinit, int ckexinitlen,
 242     char *skexinit, int skexinitlen,
 243     char *serverhostkeyblob, int sbloblen,
 244     BIGNUM *client_dh_pub,
 245     BIGNUM *server_dh_pub,
 246     BIGNUM *shared_secret)
 247 {
 248         Buffer b;
 249         static u_char digest[EVP_MAX_MD_SIZE];
 250         EVP_MD *evp_md = EVP_sha1();
 251         EVP_MD_CTX md;
 252
 253         buffer_init(&b);
 254         buffer_put_string(&b, client_version_string, strlen(client_version_string));
 255         buffer_put_string(&b, server_version_string, strlen(server_version_string));
 256
 257         /* kexinit messages: fake header: len+SSH2_MSG_KEXINIT */
 258         buffer_put_int(&b, ckexinitlen+1);
 259         buffer_put_char(&b, SSH2_MSG_KEXINIT);
 260         buffer_append(&b, ckexinit, ckexinitlen);
 261         buffer_put_int(&b, skexinitlen+1);
 262         buffer_put_char(&b, SSH2_MSG_KEXINIT);
 263         buffer_append(&b, skexinit, skexinitlen);
 264
 265         buffer_put_string(&b, serverhostkeyblob, sbloblen);
 266         buffer_put_bignum2(&b, client_dh_pub);
 267         buffer_put_bignum2(&b, server_dh_pub);
 268         buffer_put_bignum2(&b, shared_secret);
 269
 270 #ifdef DEBUG_KEX
 271         buffer_dump(&b);
 272 #endif
 273
 274         EVP_DigestInit(&md, evp_md);
 275         EVP_DigestUpdate(&md, buffer_ptr(&b), buffer_len(&b));
 276         EVP_DigestFinal(&md, digest, NULL);
 277
 278         buffer_free(&b);
 279
 280 #ifdef DEBUG_KEX
 281         dump_digest(digest, evp_md->md_size);
 282 #endif
 283         return digest;
 284 }
 285
 286 u_char *
 287 kex_hash_gex(
 288     char *client_version_string,
 289     char *server_version_string,
 290     char *ckexinit, int ckexinitlen,
 291     char *skexinit, int skexinitlen,
 292     char *serverhostkeyblob, int sbloblen,
 293     int min, int wantbits, int max, BIGNUM *prime, BIGNUM *gen,
 294     BIGNUM *client_dh_pub,
 295     BIGNUM *server_dh_pub,
 296     BIGNUM *shared_secret)
 297 {
 298         Buffer b;
 299         static u_char digest[EVP_MAX_MD_SIZE];
 300         EVP_MD *evp_md = EVP_sha1();
 301         EVP_MD_CTX md;
 302
 303         buffer_init(&b);
 304         buffer_put_string(&b, client_version_string, strlen(client_version_string));
 305         buffer_put_string(&b, server_version_string, strlen(server_version_string));
 306
 307         /* kexinit messages: fake header: len+SSH2_MSG_KEXINIT */
 308         buffer_put_int(&b, ckexinitlen+1);
 309         buffer_put_char(&b, SSH2_MSG_KEXINIT);
 310         buffer_append(&b, ckexinit, ckexinitlen);
 311         buffer_put_int(&b, skexinitlen+1);
 312         buffer_put_char(&b, SSH2_MSG_KEXINIT);
 313         buffer_append(&b, skexinit, skexinitlen);
 314
 315         buffer_put_string(&b, serverhostkeyblob, sbloblen);
 316         if (min == -1 || max == -1)
 317                 buffer_put_int(&b, wantbits);
 318         else {
 319                 buffer_put_int(&b, min);
 320                 buffer_put_int(&b, wantbits);
 321                 buffer_put_int(&b, max);
 322         }
 323         buffer_put_bignum2(&b, prime);
 324         buffer_put_bignum2(&b, gen);
 325         buffer_put_bignum2(&b, client_dh_pub);
 326         buffer_put_bignum2(&b, server_dh_pub);
 327         buffer_put_bignum2(&b, shared_secret);
 328
 329 #ifdef DEBUG_KEX
 330         buffer_dump(&b);
 331 #endif
 332
 333         EVP_DigestInit(&md, evp_md);
 334         EVP_DigestUpdate(&md, buffer_ptr(&b), buffer_len(&b));
 335         EVP_DigestFinal(&md, digest, NULL);
 336
 337         buffer_free(&b);
 338
 339 #ifdef DEBUG_KEX
 340         dump_digest(digest, evp_md->md_size);
 341 #endif
 342         return digest;
 343 }
 344
 345 u_char *
 346 derive_key(int id, int need, u_char *hash, BIGNUM *shared_secret)
 347 {
 348         Buffer b;
 349         EVP_MD *evp_md = EVP_sha1();
 350         EVP_MD_CTX md;
 351         char c = id;
 352         int have;
 353         int mdsz = evp_md->md_size;
 354         u_char *digest = xmalloc(((need+mdsz-1)/mdsz)*mdsz);
 355
 356         buffer_init(&b);
 357         buffer_put_bignum2(&b, shared_secret);
 358
 359         EVP_DigestInit(&md, evp_md);
 360         EVP_DigestUpdate(&md, buffer_ptr(&b), buffer_len(&b));  /* shared_secret K */
 361         EVP_DigestUpdate(&md, hash, mdsz);              /* transport-06 */
 362         EVP_DigestUpdate(&md, &c, 1);                   /* key id */
 363         EVP_DigestUpdate(&md, hash, mdsz);              /* session id */
 364         EVP_DigestFinal(&md, digest, NULL);
 365
 366         /* expand */
 367         for (have = mdsz; need > have; have += mdsz) {
 368                 EVP_DigestInit(&md, evp_md);
 369                 EVP_DigestUpdate(&md, buffer_ptr(&b), buffer_len(&b));
 370                 EVP_DigestUpdate(&md, hash, mdsz);
 371                 EVP_DigestUpdate(&md, digest, have);
 372                 EVP_DigestFinal(&md, digest + have, NULL);
 373         }
 374         buffer_free(&b);
 375 #ifdef DEBUG_KEX
 376         fprintf(stderr, "Digest '%c'== ", c);
 377         dump_digest(digest, need);
 378 #endif
 379         return digest;
 380 }
 381
 382 void
 383 choose_enc(Enc *enc, char *client, char *server)
 384 {
 385         char *name = match_list(client, server, NULL);
 386         if (name == NULL)
 387                 fatal("no matching cipher found: client %s server %s", client, server);
 388         enc->cipher = cipher_by_name(name);
 389         if (enc->cipher == NULL)
 390                 fatal("matching cipher is not supported: %s", name);
 391         enc->name = name;
 392         enc->enabled = 0;
 393         enc->iv = NULL;
 394         enc->key = NULL;
 395 }
 396 void
 397 choose_mac(Mac *mac, char *client, char *server)
 398 {
 399         char *name = match_list(client, server, NULL);
 400         if (name == NULL)
 401                 fatal("no matching mac found: client %s server %s", client, server);
 402         if (mac_init(mac, name) < 0)
 403                 fatal("unsupported mac %s", name);
 404         /* truncate the key */
 405         if (datafellows & SSH_BUG_HMAC)
 406                 mac->key_len = 16;
 407         mac->name = name;
 408         mac->key = NULL;
 409         mac->enabled = 0;
 410 }
 411 void
 412 choose_comp(Comp *comp, char *client, char *server)
 413 {
 414         char *name = match_list(client, server, NULL);
 415         if (name == NULL)
 416                 fatal("no matching comp found: client %s server %s", client, server);
 417         if (strcmp(name, "zlib") == 0) {
 418                 comp->type = 1;
 419         } else if (strcmp(name, "none") == 0) {
 420                 comp->type = 0;
 421         } else {
 422                 fatal("unsupported comp %s", name);
 423         }
 424         comp->name = name;
 425 }
 426 void
 427 choose_kex(Kex *k, char *client, char *server)
 428 {
 429         k->name = match_list(client, server, NULL);
 430         if (k->name == NULL)
 431                 fatal("no kex alg");
 432         if (strcmp(k->name, KEX_DH1) == 0) {
 433                 k->kex_type = DH_GRP1_SHA1;
 434         } else if (strcmp(k->name, KEX_DHGEX) == 0) {
 435                 k->kex_type = DH_GEX_SHA1;
 436         } else
 437                 fatal("bad kex alg %s", k->name);
 438 }
 439 void
 440 choose_hostkeyalg(Kex *k, char *client, char *server)
 441 {
 442         char *hostkeyalg = match_list(client, server, NULL);
 443         if (hostkeyalg == NULL)
 444                 fatal("no hostkey alg");
 445         k->hostkey_type = key_type_from_name(hostkeyalg);
 446         if (k->hostkey_type == KEY_UNSPEC)
 447                 fatal("bad hostkey alg '%s'", hostkeyalg);
 448         xfree(hostkeyalg);
 449 }
 450
 451 Kex *
 452 kex_choose_conf(char *cprop[PROPOSAL_MAX], char *sprop[PROPOSAL_MAX], int server)
 453 {
 454         int mode;
 455         int ctos;                               /* direction: if true client-to-server */
 456         int need;
 457         Kex *k;
 458
 459         k = xmalloc(sizeof(*k));
 460         memset(k, 0, sizeof(*k));
 461         k->server = server;
 462
 463         for (mode = 0; mode < MODE_MAX; mode++) {
 464                 int nenc, nmac, ncomp;
 465                 ctos = (!k->server && mode == MODE_OUT) || (k->server && mode == MODE_IN);
 466                 nenc  = ctos ? PROPOSAL_ENC_ALGS_CTOS  : PROPOSAL_ENC_ALGS_STOC;
 467                 nmac  = ctos ? PROPOSAL_MAC_ALGS_CTOS  : PROPOSAL_MAC_ALGS_STOC;
 468                 ncomp = ctos ? PROPOSAL_COMP_ALGS_CTOS : PROPOSAL_COMP_ALGS_STOC;
 469                 choose_enc (&k->enc [mode], cprop[nenc],  sprop[nenc]);
 470                 choose_mac (&k->mac [mode], cprop[nmac],  sprop[nmac]);
 471                 choose_comp(&k->comp[mode], cprop[ncomp], sprop[ncomp]);
 472                 debug("kex: %s %s %s %s",
 473                     ctos ? "client->server" : "server->client",
 474                     k->enc[mode].name,
 475                     k->mac[mode].name,
 476                     k->comp[mode].name);
 477         }
 478         choose_kex(k, cprop[PROPOSAL_KEX_ALGS], sprop[PROPOSAL_KEX_ALGS]);
 479         choose_hostkeyalg(k, cprop[PROPOSAL_SERVER_HOST_KEY_ALGS],
 480             sprop[PROPOSAL_SERVER_HOST_KEY_ALGS]);
 481         need = 0;
 482         for (mode = 0; mode < MODE_MAX; mode++) {
 483             if (need < k->enc[mode].cipher->key_len)
 484                     need = k->enc[mode].cipher->key_len;
 485             if (need < k->enc[mode].cipher->block_size)
 486                     need = k->enc[mode].cipher->block_size;
 487             if (need < k->mac[mode].key_len)
 488                     need = k->mac[mode].key_len;
 489         }
 490         /* XXX need runden? */
 491         k->we_need = need;
 492         return k;
 493 }
 494
 495 #define NKEYS   6
 496 int
 497 kex_derive_keys(Kex *k, u_char *hash, BIGNUM *shared_secret)
 498 {
 499         int i;
 500         int mode;
 501         int ctos;
 502         u_char *keys[NKEYS];
 503
 504         for (i = 0; i < NKEYS; i++)
 505                 keys[i] = derive_key('A'+i, k->we_need, hash, shared_secret);
 506
 507         for (mode = 0; mode < MODE_MAX; mode++) {
 508                 ctos = (!k->server && mode == MODE_OUT) || (k->server && mode == MODE_IN);
 509                 k->enc[mode].iv  = keys[ctos ? 0 : 1];
 510                 k->enc[mode].key = keys[ctos ? 2 : 3];
 511                 k->mac[mode].key = keys[ctos ? 4 : 5];
 512         }
 513         return 0;
 514 }