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