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