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.22 2001/03/05 17:17:20 markus 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
  46 #define KEX_COOKIE_LEN  16
  47
  48 Buffer *
  49 kex_init(char *myproposal[PROPOSAL_MAX])
  50 {
  51         int first_kex_packet_follows = 0;
  52         u_char cookie[KEX_COOKIE_LEN];
  53         u_int32_t rand = 0;
  54         int i;
  55         Buffer *ki = xmalloc(sizeof(*ki));
  56         for (i = 0; i < KEX_COOKIE_LEN; i++) {
  57                 if (i % 4 == 0)
  58                         rand = arc4random();
  59                 cookie[i] = rand & 0xff;
  60                 rand >>= 8;
  61         }
  62         buffer_init(ki);
  63         buffer_append(ki, (char *)cookie, sizeof cookie);
  64         for (i = 0; i < PROPOSAL_MAX; i++)
  65                 buffer_put_cstring(ki, myproposal[i]);
  66         buffer_put_char(ki, first_kex_packet_follows);
  67         buffer_put_int(ki, 0);                          /* uint32 reserved */
  68         return ki;
  69 }
  70
  71 /* send kexinit, parse and save reply */
  72 void
  73 kex_exchange_kexinit(
  74     Buffer *my_kexinit, Buffer *peer_kexint,
  75     char *peer_proposal[PROPOSAL_MAX])
  76 {
  77         int i;
  78         char *ptr;
  79         int plen;
  80
  81         debug("send KEXINIT");
  82         packet_start(SSH2_MSG_KEXINIT);
  83         packet_put_raw(buffer_ptr(my_kexinit), buffer_len(my_kexinit));
  84         packet_send();
  85         packet_write_wait();
  86         debug("done");
  87
  88         /*
  89          * read and save raw KEXINIT payload in buffer. this is used during
  90          * computation of the session_id and the session keys.
  91          */
  92         debug("wait KEXINIT");
  93         packet_read_expect(&plen, SSH2_MSG_KEXINIT);
  94         ptr = packet_get_raw(&plen);
  95         buffer_append(peer_kexint, ptr, plen);
  96
  97         /* parse packet and save algorithm proposal */
  98         /* skip cookie */
  99         for (i = 0; i < KEX_COOKIE_LEN; i++)
 100                 packet_get_char();
 101         /* extract kex init proposal strings */
 102         for (i = 0; i < PROPOSAL_MAX; i++) {
 103                 peer_proposal[i] = packet_get_string(NULL);
 104                 debug("got kexinit: %s", peer_proposal[i]);
 105         }
 106         /* first kex follow / reserved */
 107         i = packet_get_char();
 108         debug("first kex follow: %d ", i);
 109         i = packet_get_int();
 110         debug("reserved: %d ", i);
 111         packet_done();
 112         debug("done");
 113 }
 114
 115 /* diffie-hellman-group1-sha1 */
 116
 117 int
 118 dh_pub_is_valid(DH *dh, BIGNUM *dh_pub)
 119 {
 120         int i;
 121         int n = BN_num_bits(dh_pub);
 122         int bits_set = 0;
 123
 124         if (dh_pub->neg) {
 125                 log("invalid public DH value: negativ");
 126                 return 0;
 127         }
 128         for (i = 0; i <= n; i++)
 129                 if (BN_is_bit_set(dh_pub, i))
 130                         bits_set++;
 131         debug("bits set: %d/%d", bits_set, BN_num_bits(dh->p));
 132
 133         /* if g==2 and bits_set==1 then computing log_g(dh_pub) is trivial */
 134         if (bits_set > 1 && (BN_cmp(dh_pub, dh->p) == -1))
 135                 return 1;
 136         log("invalid public DH value (%d/%d)", bits_set, BN_num_bits(dh->p));
 137         return 0;
 138 }
 139
 140 void
 141 dh_gen_key(DH *dh, int need)
 142 {
 143         int i, bits_set = 0, tries = 0;
 144
 145         if (dh->p == NULL)
 146                 fatal("dh_gen_key: dh->p == NULL");
 147         if (2*need >= BN_num_bits(dh->p))
 148                 fatal("dh_gen_key: group too small: %d (2*need %d)",
 149                     BN_num_bits(dh->p), 2*need);
 150         do {
 151                 if (dh->priv_key != NULL)
 152                         BN_free(dh->priv_key);
 153                 dh->priv_key = BN_new();
 154                 if (dh->priv_key == NULL)
 155                         fatal("dh_gen_key: BN_new failed");
 156                 /* generate a 2*need bits random private exponent */
 157                 if (!BN_rand(dh->priv_key, 2*need, 0, 0))
 158                         fatal("dh_gen_key: BN_rand failed");
 159                 if (DH_generate_key(dh) == 0)
 160                         fatal("DH_generate_key");
 161                 for (i = 0; i <= BN_num_bits(dh->priv_key); i++)
 162                         if (BN_is_bit_set(dh->priv_key, i))
 163                                 bits_set++;
 164                 debug("dh_gen_key: priv key bits set: %d/%d",
 165                     bits_set, BN_num_bits(dh->priv_key));
 166                 if (tries++ > 10)
 167                         fatal("dh_gen_key: too many bad keys: giving up");
 168         } while (!dh_pub_is_valid(dh, dh->pub_key));
 169 }
 170
 171 DH *
 172 dh_new_group_asc(const char *gen, const char *modulus)
 173 {
 174         DH *dh;
 175         int ret;
 176
 177         dh = DH_new();
 178         if (dh == NULL)
 179                 fatal("DH_new");
 180
 181         if ((ret = BN_hex2bn(&dh->p, modulus)) < 0)
 182                 fatal("BN_hex2bn p");
 183         if ((ret = BN_hex2bn(&dh->g, gen)) < 0)
 184                 fatal("BN_hex2bn g");
 185
 186         return (dh);
 187 }
 188
 189 /*
 190  * This just returns the group, we still need to generate the exchange
 191  * value.
 192  */
 193
 194 DH *
 195 dh_new_group(BIGNUM *gen, BIGNUM *modulus)
 196 {
 197         DH *dh;
 198
 199         dh = DH_new();
 200         if (dh == NULL)
 201                 fatal("DH_new");
 202         dh->p = modulus;
 203         dh->g = gen;
 204
 205         return (dh);
 206 }
 207
 208 DH *
 209 dh_new_group1(void)
 210 {
 211         static char *gen = "2", *group1 =
 212             "FFFFFFFF" "FFFFFFFF" "C90FDAA2" "2168C234" "C4C6628B" "80DC1CD1"
 213             "29024E08" "8A67CC74" "020BBEA6" "3B139B22" "514A0879" "8E3404DD"
 214             "EF9519B3" "CD3A431B" "302B0A6D" "F25F1437" "4FE1356D" "6D51C245"
 215             "E485B576" "625E7EC6" "F44C42E9" "A637ED6B" "0BFF5CB6" "F406B7ED"
 216             "EE386BFB" "5A899FA5" "AE9F2411" "7C4B1FE6" "49286651" "ECE65381"
 217             "FFFFFFFF" "FFFFFFFF";
 218
 219         return (dh_new_group_asc(gen, group1));
 220 }
 221
 222 #ifdef DEBUG_KEX
 223 void
 224 dump_digest(u_char *digest, int len)
 225 {
 226         int i;
 227         for (i = 0; i< len; i++){
 228                 fprintf(stderr, "%02x", digest[i]);
 229                 if(i%2!=0)
 230                         fprintf(stderr, " ");
 231         }
 232         fprintf(stderr, "\n");
 233 }
 234 #endif
 235
 236 u_char *
 237 kex_hash(
 238     char *client_version_string,
 239     char *server_version_string,
 240     char *ckexinit, int ckexinitlen,
 241     char *skexinit, int skexinitlen,
 242     char *serverhostkeyblob, int sbloblen,
 243     BIGNUM *client_dh_pub,
 244     BIGNUM *server_dh_pub,
 245     BIGNUM *shared_secret)
 246 {
 247         Buffer b;
 248         static u_char digest[EVP_MAX_MD_SIZE];
 249         EVP_MD *evp_md = EVP_sha1();
 250         EVP_MD_CTX md;
 251
 252         buffer_init(&b);
 253         buffer_put_string(&b, client_version_string, strlen(client_version_string));
 254         buffer_put_string(&b, server_version_string, strlen(server_version_string));
 255
 256         /* kexinit messages: fake header: len+SSH2_MSG_KEXINIT */
 257         buffer_put_int(&b, ckexinitlen+1);
 258         buffer_put_char(&b, SSH2_MSG_KEXINIT);
 259         buffer_append(&b, ckexinit, ckexinitlen);
 260         buffer_put_int(&b, skexinitlen+1);
 261         buffer_put_char(&b, SSH2_MSG_KEXINIT);
 262         buffer_append(&b, skexinit, skexinitlen);
 263
 264         buffer_put_string(&b, serverhostkeyblob, sbloblen);
 265         buffer_put_bignum2(&b, client_dh_pub);
 266         buffer_put_bignum2(&b, server_dh_pub);
 267         buffer_put_bignum2(&b, shared_secret);
 268
 269 #ifdef DEBUG_KEX
 270         buffer_dump(&b);
 271 #endif
 272
 273         EVP_DigestInit(&md, evp_md);
 274         EVP_DigestUpdate(&md, buffer_ptr(&b), buffer_len(&b));
 275         EVP_DigestFinal(&md, digest, NULL);
 276
 277         buffer_free(&b);
 278
 279 #ifdef DEBUG_KEX
 280         dump_digest(digest, evp_md->md_size);
 281 #endif
 282         return digest;
 283 }
 284
 285 u_char *
 286 kex_hash_gex(
 287     char *client_version_string,
 288     char *server_version_string,
 289     char *ckexinit, int ckexinitlen,
 290     char *skexinit, int skexinitlen,
 291     char *serverhostkeyblob, int sbloblen,
 292     int minbits, BIGNUM *prime, BIGNUM *gen,
 293     BIGNUM *client_dh_pub,
 294     BIGNUM *server_dh_pub,
 295     BIGNUM *shared_secret)
 296 {
 297         Buffer b;
 298         static u_char digest[EVP_MAX_MD_SIZE];
 299         EVP_MD *evp_md = EVP_sha1();
 300         EVP_MD_CTX md;
 301
 302         buffer_init(&b);
 303         buffer_put_string(&b, client_version_string, strlen(client_version_string));
 304         buffer_put_string(&b, server_version_string, strlen(server_version_string));
 305
 306         /* kexinit messages: fake header: len+SSH2_MSG_KEXINIT */
 307         buffer_put_int(&b, ckexinitlen+1);
 308         buffer_put_char(&b, SSH2_MSG_KEXINIT);
 309         buffer_append(&b, ckexinit, ckexinitlen);
 310         buffer_put_int(&b, skexinitlen+1);
 311         buffer_put_char(&b, SSH2_MSG_KEXINIT);
 312         buffer_append(&b, skexinit, skexinitlen);
 313
 314         buffer_put_string(&b, serverhostkeyblob, sbloblen);
 315         buffer_put_int(&b, minbits);
 316         buffer_put_bignum2(&b, prime);
 317         buffer_put_bignum2(&b, gen);
 318         buffer_put_bignum2(&b, client_dh_pub);
 319         buffer_put_bignum2(&b, server_dh_pub);
 320         buffer_put_bignum2(&b, shared_secret);
 321
 322 #ifdef DEBUG_KEX
 323         buffer_dump(&b);
 324 #endif
 325
 326         EVP_DigestInit(&md, evp_md);
 327         EVP_DigestUpdate(&md, buffer_ptr(&b), buffer_len(&b));
 328         EVP_DigestFinal(&md, digest, NULL);
 329
 330         buffer_free(&b);
 331
 332 #ifdef DEBUG_KEX
 333         dump_digest(digest, evp_md->md_size);
 334 #endif
 335         return digest;
 336 }
 337
 338 u_char *
 339 derive_key(int id, int need, u_char *hash, BIGNUM *shared_secret)
 340 {
 341         Buffer b;
 342         EVP_MD *evp_md = EVP_sha1();
 343         EVP_MD_CTX md;
 344         char c = id;
 345         int have;
 346         int mdsz = evp_md->md_size;
 347         u_char *digest = xmalloc(((need+mdsz-1)/mdsz)*mdsz);
 348
 349         buffer_init(&b);
 350         buffer_put_bignum2(&b, shared_secret);
 351
 352         EVP_DigestInit(&md, evp_md);
 353         EVP_DigestUpdate(&md, buffer_ptr(&b), buffer_len(&b));  /* shared_secret K */
 354         EVP_DigestUpdate(&md, hash, mdsz);              /* transport-06 */
 355         EVP_DigestUpdate(&md, &c, 1);                   /* key id */
 356         EVP_DigestUpdate(&md, hash, mdsz);              /* session id */
 357         EVP_DigestFinal(&md, digest, NULL);
 358
 359         /* expand */
 360         for (have = mdsz; need > have; have += mdsz) {
 361                 EVP_DigestInit(&md, evp_md);
 362                 EVP_DigestUpdate(&md, buffer_ptr(&b), buffer_len(&b));
 363                 EVP_DigestUpdate(&md, hash, mdsz);
 364                 EVP_DigestUpdate(&md, digest, have);
 365                 EVP_DigestFinal(&md, digest + have, NULL);
 366         }
 367         buffer_free(&b);
 368 #ifdef DEBUG_KEX
 369         fprintf(stderr, "Digest '%c'== ", c);
 370         dump_digest(digest, need);
 371 #endif
 372         return digest;
 373 }
 374
 375 #define NKEYS   6
 376
 377 #define MAX_PROP        20
 378 #define SEP     ","
 379
 380 char *
 381 get_match(char *client, char *server)
 382 {
 383         char *sproposals[MAX_PROP];
 384         char *c, *s, *p, *ret, *cp, *sp;
 385         int i, j, nproposals;
 386
 387         c = cp = xstrdup(client);
 388         s = sp = xstrdup(server);
 389
 390         for ((p = strsep(&sp, SEP)), i=0; p && *p != '\0';
 391              (p = strsep(&sp, SEP)), i++) {
 392                 if (i < MAX_PROP)
 393                         sproposals[i] = p;
 394                 else
 395                         break;
 396         }
 397         nproposals = i;
 398
 399         for ((p = strsep(&cp, SEP)), i=0; p && *p != '\0';
 400              (p = strsep(&cp, SEP)), i++) {
 401                 for (j = 0; j < nproposals; j++) {
 402                         if (strcmp(p, sproposals[j]) == 0) {
 403                                 ret = xstrdup(p);
 404                                 xfree(c);
 405                                 xfree(s);
 406                                 return ret;
 407                         }
 408                 }
 409         }
 410         xfree(c);
 411         xfree(s);
 412         return NULL;
 413 }
 414 void
 415 choose_enc(Enc *enc, char *client, char *server)
 416 {
 417         char *name = get_match(client, server);
 418         if (name == NULL)
 419                 fatal("no matching cipher found: client %s server %s", client, server);
 420         enc->cipher = cipher_by_name(name);
 421         if (enc->cipher == NULL)
 422                 fatal("matching cipher is not supported: %s", name);
 423         enc->name = name;
 424         enc->enabled = 0;
 425         enc->iv = NULL;
 426         enc->key = NULL;
 427 }
 428 void
 429 choose_mac(Mac *mac, char *client, char *server)
 430 {
 431         char *name = get_match(client, server);
 432         if (name == NULL)
 433                 fatal("no matching mac found: client %s server %s", client, server);
 434         if (mac_init(mac, name) < 0)
 435                 fatal("unsupported mac %s", name);
 436         /* truncate the key */
 437         if (datafellows & SSH_BUG_HMAC)
 438                 mac->key_len = 16;
 439         mac->name = name;
 440         mac->key = NULL;
 441         mac->enabled = 0;
 442 }
 443 void
 444 choose_comp(Comp *comp, char *client, char *server)
 445 {
 446         char *name = get_match(client, server);
 447         if (name == NULL)
 448                 fatal("no matching comp found: client %s server %s", client, server);
 449         if (strcmp(name, "zlib") == 0) {
 450                 comp->type = 1;
 451         } else if (strcmp(name, "none") == 0) {
 452                 comp->type = 0;
 453         } else {
 454                 fatal("unsupported comp %s", name);
 455         }
 456         comp->name = name;
 457 }
 458 void
 459 choose_kex(Kex *k, char *client, char *server)
 460 {
 461         k->name = get_match(client, server);
 462         if (k->name == NULL)
 463                 fatal("no kex alg");
 464         if (strcmp(k->name, KEX_DH1) == 0) {
 465                 k->kex_type = DH_GRP1_SHA1;
 466         } else if (strcmp(k->name, KEX_DHGEX) == 0) {
 467                 k->kex_type = DH_GEX_SHA1;
 468         } else
 469                 fatal("bad kex alg %s", k->name);
 470 }
 471 void
 472 choose_hostkeyalg(Kex *k, char *client, char *server)
 473 {
 474         char *hostkeyalg = get_match(client, server);
 475         if (hostkeyalg == NULL)
 476                 fatal("no hostkey alg");
 477         k->hostkey_type = key_type_from_name(hostkeyalg);
 478         if (k->hostkey_type == KEY_UNSPEC)
 479                 fatal("bad hostkey alg '%s'", hostkeyalg);
 480         xfree(hostkeyalg);
 481 }
 482
 483 Kex *
 484 kex_choose_conf(char *cprop[PROPOSAL_MAX], char *sprop[PROPOSAL_MAX], int server)
 485 {
 486         int mode;
 487         int ctos;                               /* direction: if true client-to-server */
 488         int need;
 489         Kex *k;
 490
 491         k = xmalloc(sizeof(*k));
 492         memset(k, 0, sizeof(*k));
 493         k->server = server;
 494
 495         for (mode = 0; mode < MODE_MAX; mode++) {
 496                 int nenc, nmac, ncomp;
 497                 ctos = (!k->server && mode == MODE_OUT) || (k->server && mode == MODE_IN);
 498                 nenc  = ctos ? PROPOSAL_ENC_ALGS_CTOS  : PROPOSAL_ENC_ALGS_STOC;
 499                 nmac  = ctos ? PROPOSAL_MAC_ALGS_CTOS  : PROPOSAL_MAC_ALGS_STOC;
 500                 ncomp = ctos ? PROPOSAL_COMP_ALGS_CTOS : PROPOSAL_COMP_ALGS_STOC;
 501                 choose_enc (&k->enc [mode], cprop[nenc],  sprop[nenc]);
 502                 choose_mac (&k->mac [mode], cprop[nmac],  sprop[nmac]);
 503                 choose_comp(&k->comp[mode], cprop[ncomp], sprop[ncomp]);
 504                 debug("kex: %s %s %s %s",
 505                     ctos ? "client->server" : "server->client",
 506                     k->enc[mode].name,
 507                     k->mac[mode].name,
 508                     k->comp[mode].name);
 509         }
 510         choose_kex(k, cprop[PROPOSAL_KEX_ALGS], sprop[PROPOSAL_KEX_ALGS]);
 511         choose_hostkeyalg(k, cprop[PROPOSAL_SERVER_HOST_KEY_ALGS],
 512             sprop[PROPOSAL_SERVER_HOST_KEY_ALGS]);
 513         need = 0;
 514         for (mode = 0; mode < MODE_MAX; mode++) {
 515             if (need < k->enc[mode].cipher->key_len)
 516                     need = k->enc[mode].cipher->key_len;
 517             if (need < k->enc[mode].cipher->block_size)
 518                     need = k->enc[mode].cipher->block_size;
 519             if (need < k->mac[mode].key_len)
 520                     need = k->mac[mode].key_len;
 521         }
 522         /* XXX need runden? */
 523         k->we_need = need;
 524         return k;
 525 }
 526
 527 int
 528 kex_derive_keys(Kex *k, u_char *hash, BIGNUM *shared_secret)
 529 {
 530         int i;
 531         int mode;
 532         int ctos;
 533         u_char *keys[NKEYS];
 534
 535         for (i = 0; i < NKEYS; i++)
 536                 keys[i] = derive_key('A'+i, k->we_need, hash, shared_secret);
 537
 538         for (mode = 0; mode < MODE_MAX; mode++) {
 539                 ctos = (!k->server && mode == MODE_OUT) || (k->server && mode == MODE_IN);
 540                 k->enc[mode].iv  = keys[ctos ? 0 : 1];
 541                 k->enc[mode].key = keys[ctos ? 2 : 3];
 542                 k->mac[mode].key = keys[ctos ? 4 : 5];
 543         }
 544         return 0;
 545 }