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.12 2000/10/11 20:27:23 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
  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         unsigned 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 DH *
 142 dh_gen_key(DH *dh)
 143 {
 144         int tries = 0;
 145
 146         do {
 147                 if (DH_generate_key(dh) == 0)
 148                         fatal("DH_generate_key");
 149                 if (tries++ > 10)
 150                         fatal("dh_new_group1: too many bad keys: giving up");
 151         } while (!dh_pub_is_valid(dh, dh->pub_key));
 152         return dh;
 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_gen_key(dh));
 171 }
 172
 173 DH *
 174 dh_new_group(BIGNUM *gen, BIGNUM *modulus)
 175 {
 176         DH *dh;
 177
 178         dh = DH_new();
 179         if (dh == NULL)
 180                 fatal("DH_new");
 181         dh->p = modulus;
 182         dh->g = gen;
 183
 184         return (dh_gen_key(dh));
 185 }
 186
 187 DH *
 188 dh_new_group1()
 189 {
 190         static char *gen = "2", *group1 =
 191             "FFFFFFFF" "FFFFFFFF" "C90FDAA2" "2168C234" "C4C6628B" "80DC1CD1"
 192             "29024E08" "8A67CC74" "020BBEA6" "3B139B22" "514A0879" "8E3404DD"
 193             "EF9519B3" "CD3A431B" "302B0A6D" "F25F1437" "4FE1356D" "6D51C245"
 194             "E485B576" "625E7EC6" "F44C42E9" "A637ED6B" "0BFF5CB6" "F406B7ED"
 195             "EE386BFB" "5A899FA5" "AE9F2411" "7C4B1FE6" "49286651" "ECE65381"
 196             "FFFFFFFF" "FFFFFFFF";
 197
 198         return (dh_new_group_asc(gen, group1));
 199 }
 200
 201 void
 202 dump_digest(unsigned char *digest, int len)
 203 {
 204         int i;
 205         for (i = 0; i< len; i++){
 206                 fprintf(stderr, "%02x", digest[i]);
 207                 if(i%2!=0)
 208                         fprintf(stderr, " ");
 209         }
 210         fprintf(stderr, "\n");
 211 }
 212
 213 unsigned char *
 214 kex_hash(
 215     char *client_version_string,
 216     char *server_version_string,
 217     char *ckexinit, int ckexinitlen,
 218     char *skexinit, int skexinitlen,
 219     char *serverhostkeyblob, int sbloblen,
 220     BIGNUM *client_dh_pub,
 221     BIGNUM *server_dh_pub,
 222     BIGNUM *shared_secret)
 223 {
 224         Buffer b;
 225         static unsigned char digest[EVP_MAX_MD_SIZE];
 226         EVP_MD *evp_md = EVP_sha1();
 227         EVP_MD_CTX md;
 228
 229         buffer_init(&b);
 230         buffer_put_string(&b, client_version_string, strlen(client_version_string));
 231         buffer_put_string(&b, server_version_string, strlen(server_version_string));
 232
 233         /* kexinit messages: fake header: len+SSH2_MSG_KEXINIT */
 234         buffer_put_int(&b, ckexinitlen+1);
 235         buffer_put_char(&b, SSH2_MSG_KEXINIT);
 236         buffer_append(&b, ckexinit, ckexinitlen);
 237         buffer_put_int(&b, skexinitlen+1);
 238         buffer_put_char(&b, SSH2_MSG_KEXINIT);
 239         buffer_append(&b, skexinit, skexinitlen);
 240
 241         buffer_put_string(&b, serverhostkeyblob, sbloblen);
 242         buffer_put_bignum2(&b, client_dh_pub);
 243         buffer_put_bignum2(&b, server_dh_pub);
 244         buffer_put_bignum2(&b, shared_secret);
 245
 246 #ifdef DEBUG_KEX
 247         buffer_dump(&b);
 248 #endif
 249
 250         EVP_DigestInit(&md, evp_md);
 251         EVP_DigestUpdate(&md, buffer_ptr(&b), buffer_len(&b));
 252         EVP_DigestFinal(&md, digest, NULL);
 253
 254         buffer_free(&b);
 255
 256 #ifdef DEBUG_KEX
 257         dump_digest(digest, evp_md->md_size);
 258 #endif
 259         return digest;
 260 }
 261
 262 unsigned char *
 263 kex_hash_gex(
 264     char *client_version_string,
 265     char *server_version_string,
 266     char *ckexinit, int ckexinitlen,
 267     char *skexinit, int skexinitlen,
 268     char *serverhostkeyblob, int sbloblen,
 269     int minbits, BIGNUM *prime, BIGNUM *gen,
 270     BIGNUM *client_dh_pub,
 271     BIGNUM *server_dh_pub,
 272     BIGNUM *shared_secret)
 273 {
 274         Buffer b;
 275         static unsigned char digest[EVP_MAX_MD_SIZE];
 276         EVP_MD *evp_md = EVP_sha1();
 277         EVP_MD_CTX md;
 278
 279         buffer_init(&b);
 280         buffer_put_string(&b, client_version_string, strlen(client_version_string));
 281         buffer_put_string(&b, server_version_string, strlen(server_version_string));
 282
 283         /* kexinit messages: fake header: len+SSH2_MSG_KEXINIT */
 284         buffer_put_int(&b, ckexinitlen+1);
 285         buffer_put_char(&b, SSH2_MSG_KEXINIT);
 286         buffer_append(&b, ckexinit, ckexinitlen);
 287         buffer_put_int(&b, skexinitlen+1);
 288         buffer_put_char(&b, SSH2_MSG_KEXINIT);
 289         buffer_append(&b, skexinit, skexinitlen);
 290
 291         buffer_put_string(&b, serverhostkeyblob, sbloblen);
 292         buffer_put_int(&b, minbits);
 293         buffer_put_bignum2(&b, prime);
 294         buffer_put_bignum2(&b, gen);
 295         buffer_put_bignum2(&b, client_dh_pub);
 296         buffer_put_bignum2(&b, server_dh_pub);
 297         buffer_put_bignum2(&b, shared_secret);
 298
 299 #ifdef DEBUG_KEX
 300         buffer_dump(&b);
 301 #endif
 302
 303         EVP_DigestInit(&md, evp_md);
 304         EVP_DigestUpdate(&md, buffer_ptr(&b), buffer_len(&b));
 305         EVP_DigestFinal(&md, digest, NULL);
 306
 307         buffer_free(&b);
 308
 309 #ifdef DEBUG_KEX
 310         dump_digest(digest, evp_md->md_size);
 311 #endif
 312         return digest;
 313 }
 314
 315 unsigned char *
 316 derive_key(int id, int need, char unsigned *hash, BIGNUM *shared_secret)
 317 {
 318         Buffer b;
 319         EVP_MD *evp_md = EVP_sha1();
 320         EVP_MD_CTX md;
 321         char c = id;
 322         int have;
 323         int mdsz = evp_md->md_size;
 324         unsigned char *digest = xmalloc(((need+mdsz-1)/mdsz)*mdsz);
 325
 326         buffer_init(&b);
 327         buffer_put_bignum2(&b, shared_secret);
 328
 329         EVP_DigestInit(&md, evp_md);
 330         EVP_DigestUpdate(&md, buffer_ptr(&b), buffer_len(&b));  /* shared_secret K */
 331         EVP_DigestUpdate(&md, hash, mdsz);              /* transport-06 */
 332         EVP_DigestUpdate(&md, &c, 1);                   /* key id */
 333         EVP_DigestUpdate(&md, hash, mdsz);              /* session id */
 334         EVP_DigestFinal(&md, digest, NULL);
 335
 336         /* expand */
 337         for (have = mdsz; need > have; have += mdsz) {
 338                 EVP_DigestInit(&md, evp_md);
 339                 EVP_DigestUpdate(&md, buffer_ptr(&b), buffer_len(&b));
 340                 EVP_DigestUpdate(&md, hash, mdsz);
 341                 EVP_DigestUpdate(&md, digest, have);
 342                 EVP_DigestFinal(&md, digest + have, NULL);
 343         }
 344         buffer_free(&b);
 345 #ifdef DEBUG_KEX
 346         fprintf(stderr, "Digest '%c'== ", c);
 347         dump_digest(digest, need);
 348 #endif
 349         return digest;
 350 }
 351
 352 #define NKEYS   6
 353
 354 #define MAX_PROP        20
 355 #define SEP     ","
 356
 357 char *
 358 get_match(char *client, char *server)
 359 {
 360         char *sproposals[MAX_PROP];
 361         char *c, *s, *p, *ret, *cp, *sp;
 362         int i, j, nproposals;
 363
 364         c = cp = xstrdup(client);
 365         s = sp = xstrdup(server);
 366
 367         for ((p = strsep(&sp, SEP)), i=0; p && *p != '\0';
 368              (p = strsep(&sp, SEP)), i++) {
 369                 if (i < MAX_PROP)
 370                         sproposals[i] = p;
 371                 else
 372                         break;
 373         }
 374         nproposals = i;
 375
 376         for ((p = strsep(&cp, SEP)), i=0; p && *p != '\0';
 377              (p = strsep(&cp, SEP)), i++) {
 378                 for (j = 0; j < nproposals; j++) {
 379                         if (strcmp(p, sproposals[j]) == 0) {
 380                                 ret = xstrdup(p);
 381                                 xfree(c);
 382                                 xfree(s);
 383                                 return ret;
 384                         }
 385                 }
 386         }
 387         xfree(c);
 388         xfree(s);
 389         return NULL;
 390 }
 391 void
 392 choose_enc(Enc *enc, char *client, char *server)
 393 {
 394         char *name = get_match(client, server);
 395         if (name == NULL)
 396                 fatal("no matching cipher found: client %s server %s", client, server);
 397         enc->cipher = cipher_by_name(name);
 398         if (enc->cipher == NULL)
 399                 fatal("matching cipher is not supported: %s", name);
 400         enc->name = name;
 401         enc->enabled = 0;
 402         enc->iv = NULL;
 403         enc->key = NULL;
 404 }
 405 void
 406 choose_mac(Mac *mac, char *client, char *server)
 407 {
 408         char *name = get_match(client, server);
 409         if (name == NULL)
 410                 fatal("no matching mac found: client %s server %s", client, server);
 411         if (strcmp(name, "hmac-md5") == 0) {
 412                 mac->md = EVP_md5();
 413         } else if (strcmp(name, "hmac-sha1") == 0) {
 414                 mac->md = EVP_sha1();
 415         } else if (strcmp(name, "hmac-ripemd160@openssh.com") == 0) {
 416                 mac->md = EVP_ripemd160();
 417         } else {
 418                 fatal("unsupported mac %s", name);
 419         }
 420         mac->name = name;
 421         mac->mac_len = mac->md->md_size;
 422         mac->key_len = (datafellows & SSH_BUG_HMAC) ? 16 : mac->mac_len;
 423         mac->key = NULL;
 424         mac->enabled = 0;
 425 }
 426 void
 427 choose_comp(Comp *comp, char *client, char *server)
 428 {
 429         char *name = get_match(client, server);
 430         if (name == NULL)
 431                 fatal("no matching comp found: client %s server %s", client, server);
 432         if (strcmp(name, "zlib") == 0) {
 433                 comp->type = 1;
 434         } else if (strcmp(name, "none") == 0) {
 435                 comp->type = 0;
 436         } else {
 437                 fatal("unsupported comp %s", name);
 438         }
 439         comp->name = name;
 440 }
 441 void
 442 choose_kex(Kex *k, char *client, char *server)
 443 {
 444         k->name = get_match(client, server);
 445         if (k->name == NULL)
 446                 fatal("no kex alg");
 447         if (strcmp(k->name, KEX_DH1) == 0) {
 448                 k->kex_type = DH_GRP1_SHA1;
 449         } else if (strcmp(k->name, KEX_DHGEX) == 0) {
 450                 k->kex_type = DH_GEX_SHA1;
 451         } else
 452                 fatal("bad kex alg %s", k->name);
 453 }
 454 void
 455 choose_hostkeyalg(Kex *k, char *client, char *server)
 456 {
 457         k->hostkeyalg = get_match(client, server);
 458         if (k->hostkeyalg == NULL)
 459                 fatal("no hostkey alg");
 460         if (strcmp(k->hostkeyalg, KEX_DSS) != 0)
 461                 fatal("bad hostkey alg %s", k->hostkeyalg);
 462 }
 463
 464 Kex *
 465 kex_choose_conf(char *cprop[PROPOSAL_MAX], char *sprop[PROPOSAL_MAX], int server)
 466 {
 467         int mode;
 468         int ctos;                               /* direction: if true client-to-server */
 469         int need;
 470         Kex *k;
 471
 472         k = xmalloc(sizeof(*k));
 473         memset(k, 0, sizeof(*k));
 474         k->server = server;
 475
 476         for (mode = 0; mode < MODE_MAX; mode++) {
 477                 int nenc, nmac, ncomp;
 478                 ctos = (!k->server && mode == MODE_OUT) || (k->server && mode == MODE_IN);
 479                 nenc  = ctos ? PROPOSAL_ENC_ALGS_CTOS  : PROPOSAL_ENC_ALGS_STOC;
 480                 nmac  = ctos ? PROPOSAL_MAC_ALGS_CTOS  : PROPOSAL_MAC_ALGS_STOC;
 481                 ncomp = ctos ? PROPOSAL_COMP_ALGS_CTOS : PROPOSAL_COMP_ALGS_STOC;
 482                 choose_enc (&k->enc [mode], cprop[nenc],  sprop[nenc]);
 483                 choose_mac (&k->mac [mode], cprop[nmac],  sprop[nmac]);
 484                 choose_comp(&k->comp[mode], cprop[ncomp], sprop[ncomp]);
 485                 debug("kex: %s %s %s %s",
 486                     ctos ? "client->server" : "server->client",
 487                     k->enc[mode].name,
 488                     k->mac[mode].name,
 489                     k->comp[mode].name);
 490         }
 491         choose_kex(k, cprop[PROPOSAL_KEX_ALGS], sprop[PROPOSAL_KEX_ALGS]);
 492         choose_hostkeyalg(k, cprop[PROPOSAL_SERVER_HOST_KEY_ALGS],
 493             sprop[PROPOSAL_SERVER_HOST_KEY_ALGS]);
 494         need = 0;
 495         for (mode = 0; mode < MODE_MAX; mode++) {
 496             if (need < k->enc[mode].cipher->key_len)
 497                     need = k->enc[mode].cipher->key_len;
 498             if (need < k->enc[mode].cipher->block_size)
 499                     need = k->enc[mode].cipher->block_size;
 500             if (need < k->mac[mode].key_len)
 501                     need = k->mac[mode].key_len;
 502         }
 503         /* XXX need runden? */
 504         k->we_need = need;
 505         return k;
 506 }
 507
 508 int
 509 kex_derive_keys(Kex *k, unsigned char *hash, BIGNUM *shared_secret)
 510 {
 511         int i;
 512         int mode;
 513         int ctos;
 514         unsigned char *keys[NKEYS];
 515
 516         for (i = 0; i < NKEYS; i++)
 517                 keys[i] = derive_key('A'+i, k->we_need, hash, shared_secret);
 518
 519         for (mode = 0; mode < MODE_MAX; mode++) {
 520                 ctos = (!k->server && mode == MODE_OUT) || (k->server && mode == MODE_IN);
 521                 k->enc[mode].iv  = keys[ctos ? 0 : 1];
 522                 k->enc[mode].key = keys[ctos ? 2 : 3];
 523                 k->mac[mode].key = keys[ctos ? 4 : 5];
 524         }
 525         return 0;
 526 }