crypto/openssh/kex.c

   1 /* $OpenBSD: kex.c,v 1.136 2018/02/07 02:06:50 jsing Exp $ */
   2 /*
   3  * Copyright (c) 2000, 2001 Markus Friedl.  All rights reserved.
   4  *
   5  * Redistribution and use in source and binary forms, with or without
   6  * modification, are permitted provided that the following conditions
   7  * are met:
   8  * 1. Redistributions of source code must retain the above copyright
   9  *    notice, this list of conditions and the following disclaimer.
  10  * 2. Redistributions in binary form must reproduce the above copyright
  11  *    notice, this list of conditions and the following disclaimer in the
  12  *    documentation and/or other materials provided with the distribution.
  13  *
  14  * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
  15  * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
  16  * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
  17  * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
  18  * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
  19  * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
  20  * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
  21  * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
  22  * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
  23  * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  24  */
  25
  26 #include "includes.h"
  27
  28
  29 #include <signal.h>
  30 #include <stdarg.h>
  31 #include <stdio.h>
  32 #include <stdlib.h>
  33 #include <string.h>
  34
  35 #ifdef WITH_OPENSSL
  36 #include <openssl/crypto.h>
  37 #include <openssl/dh.h>
  38 #endif
  39
  40 #include "ssh2.h"
  41 #include "packet.h"
  42 #include "compat.h"
  43 #include "cipher.h"
  44 #include "sshkey.h"
  45 #include "kex.h"
  46 #include "log.h"
  47 #include "mac.h"
  48 #include "match.h"
  49 #include "misc.h"
  50 #include "dispatch.h"
  51 #include "monitor.h"
  52
  53 #include "ssherr.h"
  54 #include "sshbuf.h"
  55 #include "digest.h"
  56
  57 /* prototype */
  58 static int kex_choose_conf(struct ssh *);
  59 static int kex_input_newkeys(int, u_int32_t, struct ssh *);
  60
  61 static const char *proposal_names[PROPOSAL_MAX] = {
  62         "KEX algorithms",
  63         "host key algorithms",
  64         "ciphers ctos",
  65         "ciphers stoc",
  66         "MACs ctos",
  67         "MACs stoc",
  68         "compression ctos",
  69         "compression stoc",
  70         "languages ctos",
  71         "languages stoc",
  72 };
  73
  74 struct kexalg {
  75         char *name;
  76         u_int type;
  77         int ec_nid;
  78         int hash_alg;
  79 };
  80 static const struct kexalg kexalgs[] = {
  81 #ifdef WITH_OPENSSL
  82         { KEX_DH1, KEX_DH_GRP1_SHA1, 0, SSH_DIGEST_SHA1 },
  83         { KEX_DH14_SHA1, KEX_DH_GRP14_SHA1, 0, SSH_DIGEST_SHA1 },
  84         { KEX_DH14_SHA256, KEX_DH_GRP14_SHA256, 0, SSH_DIGEST_SHA256 },
  85         { KEX_DH16_SHA512, KEX_DH_GRP16_SHA512, 0, SSH_DIGEST_SHA512 },
  86         { KEX_DH18_SHA512, KEX_DH_GRP18_SHA512, 0, SSH_DIGEST_SHA512 },
  87         { KEX_DHGEX_SHA1, KEX_DH_GEX_SHA1, 0, SSH_DIGEST_SHA1 },
  88 #ifdef HAVE_EVP_SHA256
  89         { KEX_DHGEX_SHA256, KEX_DH_GEX_SHA256, 0, SSH_DIGEST_SHA256 },
  90 #endif /* HAVE_EVP_SHA256 */
  91 #ifdef OPENSSL_HAS_ECC
  92         { KEX_ECDH_SHA2_NISTP256, KEX_ECDH_SHA2,
  93             NID_X9_62_prime256v1, SSH_DIGEST_SHA256 },
  94         { KEX_ECDH_SHA2_NISTP384, KEX_ECDH_SHA2, NID_secp384r1,
  95             SSH_DIGEST_SHA384 },
  96 # ifdef OPENSSL_HAS_NISTP521
  97         { KEX_ECDH_SHA2_NISTP521, KEX_ECDH_SHA2, NID_secp521r1,
  98             SSH_DIGEST_SHA512 },
  99 # endif /* OPENSSL_HAS_NISTP521 */
 100 #endif /* OPENSSL_HAS_ECC */
 101 #endif /* WITH_OPENSSL */
 102 #if defined(HAVE_EVP_SHA256) || !defined(WITH_OPENSSL)
 103         { KEX_CURVE25519_SHA256, KEX_C25519_SHA256, 0, SSH_DIGEST_SHA256 },
 104         { KEX_CURVE25519_SHA256_OLD, KEX_C25519_SHA256, 0, SSH_DIGEST_SHA256 },
 105 #endif /* HAVE_EVP_SHA256 || !WITH_OPENSSL */
 106         { NULL, -1, -1, -1},
 107 };
 108
 109 char *
 110 kex_alg_list(char sep)
 111 {
 112         char *ret = NULL, *tmp;
 113         size_t nlen, rlen = 0;
 114         const struct kexalg *k;
 115
 116         for (k = kexalgs; k->name != NULL; k++) {
 117                 if (ret != NULL)
 118                         ret[rlen++] = sep;
 119                 nlen = strlen(k->name);
 120                 if ((tmp = realloc(ret, rlen + nlen + 2)) == NULL) {
 121                         free(ret);
 122                         return NULL;
 123                 }
 124                 ret = tmp;
 125                 memcpy(ret + rlen, k->name, nlen + 1);
 126                 rlen += nlen;
 127         }
 128         return ret;
 129 }
 130
 131 static const struct kexalg *
 132 kex_alg_by_name(const char *name)
 133 {
 134         const struct kexalg *k;
 135
 136         for (k = kexalgs; k->name != NULL; k++) {
 137                 if (strcmp(k->name, name) == 0)
 138                         return k;
 139         }
 140         return NULL;
 141 }
 142
 143 /* Validate KEX method name list */
 144 int
 145 kex_names_valid(const char *names)
 146 {
 147         char *s, *cp, *p;
 148
 149         if (names == NULL || strcmp(names, "") == 0)
 150                 return 0;
 151         if ((s = cp = strdup(names)) == NULL)
 152                 return 0;
 153         for ((p = strsep(&cp, ",")); p && *p != '\0';
 154             (p = strsep(&cp, ","))) {
 155                 if (kex_alg_by_name(p) == NULL) {
 156                         error("Unsupported KEX algorithm \"%.100s\"", p);
 157                         free(s);
 158                         return 0;
 159                 }
 160         }
 161         debug3("kex names ok: [%s]", names);
 162         free(s);
 163         return 1;
 164 }
 165
 166 /*
 167  * Concatenate algorithm names, avoiding duplicates in the process.
 168  * Caller must free returned string.
 169  */
 170 char *
 171 kex_names_cat(const char *a, const char *b)
 172 {
 173         char *ret = NULL, *tmp = NULL, *cp, *p, *m;
 174         size_t len;
 175
 176         if (a == NULL || *a == '\0')
 177                 return NULL;
 178         if (b == NULL || *b == '\0')
 179                 return strdup(a);
 180         if (strlen(b) > 1024*1024)
 181                 return NULL;
 182         len = strlen(a) + strlen(b) + 2;
 183         if ((tmp = cp = strdup(b)) == NULL ||
 184             (ret = calloc(1, len)) == NULL) {
 185                 free(tmp);
 186                 return NULL;
 187         }
 188         strlcpy(ret, a, len);
 189         for ((p = strsep(&cp, ",")); p && *p != '\0'; (p = strsep(&cp, ","))) {
 190                 if ((m = match_list(ret, p, NULL)) != NULL) {
 191                         free(m);
 192                         continue; /* Algorithm already present */
 193                 }
 194                 if (strlcat(ret, ",", len) >= len ||
 195                     strlcat(ret, p, len) >= len) {
 196                         free(tmp);
 197                         free(ret);
 198                         return NULL; /* Shouldn't happen */
 199                 }
 200         }
 201         free(tmp);
 202         return ret;
 203 }
 204
 205 /*
 206  * Assemble a list of algorithms from a default list and a string from a
 207  * configuration file. The user-provided string may begin with '+' to
 208  * indicate that it should be appended to the default or '-' that the
 209  * specified names should be removed.
 210  */
 211 int
 212 kex_assemble_names(const char *def, char **list)
 213 {
 214         char *ret;
 215
 216         if (list == NULL || *list == NULL || **list == '\0') {
 217                 *list = strdup(def);
 218                 return 0;
 219         }
 220         if (**list == '+') {
 221                 if ((ret = kex_names_cat(def, *list + 1)) == NULL)
 222                         return SSH_ERR_ALLOC_FAIL;
 223                 free(*list);
 224                 *list = ret;
 225         } else if (**list == '-') {
 226                 if ((ret = match_filter_list(def, *list + 1)) == NULL)
 227                         return SSH_ERR_ALLOC_FAIL;
 228                 free(*list);
 229                 *list = ret;
 230         }
 231
 232         return 0;
 233 }
 234
 235 /* put algorithm proposal into buffer */
 236 int
 237 kex_prop2buf(struct sshbuf *b, char *proposal[PROPOSAL_MAX])
 238 {
 239         u_int i;
 240         int r;
 241
 242         sshbuf_reset(b);
 243
 244         /*
 245          * add a dummy cookie, the cookie will be overwritten by
 246          * kex_send_kexinit(), each time a kexinit is set
 247          */
 248         for (i = 0; i < KEX_COOKIE_LEN; i++) {
 249                 if ((r = sshbuf_put_u8(b, 0)) != 0)
 250                         return r;
 251         }
 252         for (i = 0; i < PROPOSAL_MAX; i++) {
 253                 if ((r = sshbuf_put_cstring(b, proposal[i])) != 0)
 254                         return r;
 255         }
 256         if ((r = sshbuf_put_u8(b, 0)) != 0 ||   /* first_kex_packet_follows */
 257             (r = sshbuf_put_u32(b, 0)) != 0)    /* uint32 reserved */
 258                 return r;
 259         return 0;
 260 }
 261
 262 /* parse buffer and return algorithm proposal */
 263 int
 264 kex_buf2prop(struct sshbuf *raw, int *first_kex_follows, char ***propp)
 265 {
 266         struct sshbuf *b = NULL;
 267         u_char v;
 268         u_int i;
 269         char **proposal = NULL;
 270         int r;
 271
 272         *propp = NULL;
 273         if ((proposal = calloc(PROPOSAL_MAX, sizeof(char *))) == NULL)
 274                 return SSH_ERR_ALLOC_FAIL;
 275         if ((b = sshbuf_fromb(raw)) == NULL) {
 276                 r = SSH_ERR_ALLOC_FAIL;
 277                 goto out;
 278         }
 279         if ((r = sshbuf_consume(b, KEX_COOKIE_LEN)) != 0) /* skip cookie */
 280                 goto out;
 281         /* extract kex init proposal strings */
 282         for (i = 0; i < PROPOSAL_MAX; i++) {
 283                 if ((r = sshbuf_get_cstring(b, &(proposal[i]), NULL)) != 0)
 284                         goto out;
 285                 debug2("%s: %s", proposal_names[i], proposal[i]);
 286         }
 287         /* first kex follows / reserved */
 288         if ((r = sshbuf_get_u8(b, &v)) != 0 ||  /* first_kex_follows */
 289             (r = sshbuf_get_u32(b, &i)) != 0)   /* reserved */
 290                 goto out;
 291         if (first_kex_follows != NULL)
 292                 *first_kex_follows = v;
 293         debug2("first_kex_follows %d ", v);
 294         debug2("reserved %u ", i);
 295         r = 0;
 296         *propp = proposal;
 297  out:
 298         if (r != 0 && proposal != NULL)
 299                 kex_prop_free(proposal);
 300         sshbuf_free(b);
 301         return r;
 302 }
 303
 304 void
 305 kex_prop_free(char **proposal)
 306 {
 307         u_int i;
 308
 309         if (proposal == NULL)
 310                 return;
 311         for (i = 0; i < PROPOSAL_MAX; i++)
 312                 free(proposal[i]);
 313         free(proposal);
 314 }
 315
 316 /* ARGSUSED */
 317 static int
 318 kex_protocol_error(int type, u_int32_t seq, struct ssh *ssh)
 319 {
 320         int r;
 321
 322         error("kex protocol error: type %d seq %u", type, seq);
 323         if ((r = sshpkt_start(ssh, SSH2_MSG_UNIMPLEMENTED)) != 0 ||
 324             (r = sshpkt_put_u32(ssh, seq)) != 0 ||
 325             (r = sshpkt_send(ssh)) != 0)
 326                 return r;
 327         return 0;
 328 }
 329
 330 static void
 331 kex_reset_dispatch(struct ssh *ssh)
 332 {
 333         ssh_dispatch_range(ssh, SSH2_MSG_TRANSPORT_MIN,
 334             SSH2_MSG_TRANSPORT_MAX, &kex_protocol_error);
 335 }
 336
 337 static int
 338 kex_send_ext_info(struct ssh *ssh)
 339 {
 340         int r;
 341         char *algs;
 342
 343         if ((algs = sshkey_alg_list(0, 1, 1, ',')) == NULL)
 344                 return SSH_ERR_ALLOC_FAIL;
 345         if ((r = sshpkt_start(ssh, SSH2_MSG_EXT_INFO)) != 0 ||
 346             (r = sshpkt_put_u32(ssh, 1)) != 0 ||
 347             (r = sshpkt_put_cstring(ssh, "server-sig-algs")) != 0 ||
 348             (r = sshpkt_put_cstring(ssh, algs)) != 0 ||
 349             (r = sshpkt_send(ssh)) != 0)
 350                 goto out;
 351         /* success */
 352         r = 0;
 353  out:
 354         free(algs);
 355         return r;
 356 }
 357
 358 int
 359 kex_send_newkeys(struct ssh *ssh)
 360 {
 361         int r;
 362
 363         kex_reset_dispatch(ssh);
 364         if ((r = sshpkt_start(ssh, SSH2_MSG_NEWKEYS)) != 0 ||
 365             (r = sshpkt_send(ssh)) != 0)
 366                 return r;
 367         debug("SSH2_MSG_NEWKEYS sent");
 368         debug("expecting SSH2_MSG_NEWKEYS");
 369         ssh_dispatch_set(ssh, SSH2_MSG_NEWKEYS, &kex_input_newkeys);
 370         if (ssh->kex->ext_info_c)
 371                 if ((r = kex_send_ext_info(ssh)) != 0)
 372                         return r;
 373         return 0;
 374 }
 375
 376 int
 377 kex_input_ext_info(int type, u_int32_t seq, struct ssh *ssh)
 378 {
 379         struct kex *kex = ssh->kex;
 380         u_int32_t i, ninfo;
 381         char *name, *found;
 382         u_char *val;
 383         size_t vlen;
 384         int r;
 385
 386         debug("SSH2_MSG_EXT_INFO received");
 387         ssh_dispatch_set(ssh, SSH2_MSG_EXT_INFO, &kex_protocol_error);
 388         if ((r = sshpkt_get_u32(ssh, &ninfo)) != 0)
 389                 return r;
 390         for (i = 0; i < ninfo; i++) {
 391                 if ((r = sshpkt_get_cstring(ssh, &name, NULL)) != 0)
 392                         return r;
 393                 if ((r = sshpkt_get_string(ssh, &val, &vlen)) != 0) {
 394                         free(name);
 395                         return r;
 396                 }
 397                 if (strcmp(name, "server-sig-algs") == 0) {
 398                         /* Ensure no \0 lurking in value */
 399                         if (memchr(val, '\0', vlen) != NULL) {
 400                                 error("%s: nul byte in %s", __func__, name);
 401                                 return SSH_ERR_INVALID_FORMAT;
 402                         }
 403                         debug("%s: %s=<%s>", __func__, name, val);
 404                         found = match_list("rsa-sha2-256", val, NULL);
 405                         if (found) {
 406                                 kex->rsa_sha2 = 256;
 407                                 free(found);
 408                         }
 409                         found = match_list("rsa-sha2-512", val, NULL);
 410                         if (found) {
 411                                 kex->rsa_sha2 = 512;
 412                                 free(found);
 413                         }
 414                 } else
 415                         debug("%s: %s (unrecognised)", __func__, name);
 416                 free(name);
 417                 free(val);
 418         }
 419         return sshpkt_get_end(ssh);
 420 }
 421
 422 static int
 423 kex_input_newkeys(int type, u_int32_t seq, struct ssh *ssh)
 424 {
 425         struct kex *kex = ssh->kex;
 426         int r;
 427
 428         debug("SSH2_MSG_NEWKEYS received");
 429         ssh_dispatch_set(ssh, SSH2_MSG_NEWKEYS, &kex_protocol_error);
 430         ssh_dispatch_set(ssh, SSH2_MSG_KEXINIT, &kex_input_kexinit);
 431         if ((r = sshpkt_get_end(ssh)) != 0)
 432                 return r;
 433         if ((r = ssh_set_newkeys(ssh, MODE_IN)) != 0)
 434                 return r;
 435         kex->done = 1;
 436         sshbuf_reset(kex->peer);
 437         /* sshbuf_reset(kex->my); */
 438         kex->flags &= ~KEX_INIT_SENT;
 439         free(kex->name);
 440         kex->name = NULL;
 441         return 0;
 442 }
 443
 444 int
 445 kex_send_kexinit(struct ssh *ssh)
 446 {
 447         u_char *cookie;
 448         struct kex *kex = ssh->kex;
 449         int r;
 450
 451         if (kex == NULL)
 452                 return SSH_ERR_INTERNAL_ERROR;
 453         if (kex->flags & KEX_INIT_SENT)
 454                 return 0;
 455         kex->done = 0;
 456
 457         /* generate a random cookie */
 458         if (sshbuf_len(kex->my) < KEX_COOKIE_LEN)
 459                 return SSH_ERR_INVALID_FORMAT;
 460         if ((cookie = sshbuf_mutable_ptr(kex->my)) == NULL)
 461                 return SSH_ERR_INTERNAL_ERROR;
 462         arc4random_buf(cookie, KEX_COOKIE_LEN);
 463
 464         if ((r = sshpkt_start(ssh, SSH2_MSG_KEXINIT)) != 0 ||
 465             (r = sshpkt_putb(ssh, kex->my)) != 0 ||
 466             (r = sshpkt_send(ssh)) != 0)
 467                 return r;
 468         debug("SSH2_MSG_KEXINIT sent");
 469         kex->flags |= KEX_INIT_SENT;
 470         return 0;
 471 }
 472
 473 /* ARGSUSED */
 474 int
 475 kex_input_kexinit(int type, u_int32_t seq, struct ssh *ssh)
 476 {
 477         struct kex *kex = ssh->kex;
 478         const u_char *ptr;
 479         u_int i;
 480         size_t dlen;
 481         int r;
 482
 483         debug("SSH2_MSG_KEXINIT received");
 484         if (kex == NULL)
 485                 return SSH_ERR_INVALID_ARGUMENT;
 486
 487         ssh_dispatch_set(ssh, SSH2_MSG_KEXINIT, NULL);
 488         ptr = sshpkt_ptr(ssh, &dlen);
 489         if ((r = sshbuf_put(kex->peer, ptr, dlen)) != 0)
 490                 return r;
 491
 492         /* discard packet */
 493         for (i = 0; i < KEX_COOKIE_LEN; i++)
 494                 if ((r = sshpkt_get_u8(ssh, NULL)) != 0)
 495                         return r;
 496         for (i = 0; i < PROPOSAL_MAX; i++)
 497                 if ((r = sshpkt_get_string(ssh, NULL, NULL)) != 0)
 498                         return r;
 499         /*
 500          * XXX RFC4253 sec 7: "each side MAY guess" - currently no supported
 501          * KEX method has the server move first, but a server might be using
 502          * a custom method or one that we otherwise don't support. We should
 503          * be prepared to remember first_kex_follows here so we can eat a
 504          * packet later.
 505          * XXX2 - RFC4253 is kind of ambiguous on what first_kex_follows means
 506          * for cases where the server *doesn't* go first. I guess we should
 507          * ignore it when it is set for these cases, which is what we do now.
 508          */
 509         if ((r = sshpkt_get_u8(ssh, NULL)) != 0 ||      /* first_kex_follows */
 510             (r = sshpkt_get_u32(ssh, NULL)) != 0 ||     /* reserved */
 511             (r = sshpkt_get_end(ssh)) != 0)
 512                         return r;
 513
 514         if (!(kex->flags & KEX_INIT_SENT))
 515                 if ((r = kex_send_kexinit(ssh)) != 0)
 516                         return r;
 517         if ((r = kex_choose_conf(ssh)) != 0)
 518                 return r;
 519
 520         if (kex->kex_type < KEX_MAX && kex->kex[kex->kex_type] != NULL)
 521                 return (kex->kex[kex->kex_type])(ssh);
 522
 523         return SSH_ERR_INTERNAL_ERROR;
 524 }
 525
 526 int
 527 kex_new(struct ssh *ssh, char *proposal[PROPOSAL_MAX], struct kex **kexp)
 528 {
 529         struct kex *kex;
 530         int r;
 531
 532         *kexp = NULL;
 533         if ((kex = calloc(1, sizeof(*kex))) == NULL)
 534                 return SSH_ERR_ALLOC_FAIL;
 535         if ((kex->peer = sshbuf_new()) == NULL ||
 536             (kex->my = sshbuf_new()) == NULL) {
 537                 r = SSH_ERR_ALLOC_FAIL;
 538                 goto out;
 539         }
 540         if ((r = kex_prop2buf(kex->my, proposal)) != 0)
 541                 goto out;
 542         kex->done = 0;
 543         kex_reset_dispatch(ssh);
 544         ssh_dispatch_set(ssh, SSH2_MSG_KEXINIT, &kex_input_kexinit);
 545         r = 0;
 546         *kexp = kex;
 547  out:
 548         if (r != 0)
 549                 kex_free(kex);
 550         return r;
 551 }
 552
 553 void
 554 kex_free_newkeys(struct newkeys *newkeys)
 555 {
 556         if (newkeys == NULL)
 557                 return;
 558         if (newkeys->enc.key) {
 559                 explicit_bzero(newkeys->enc.key, newkeys->enc.key_len);
 560                 free(newkeys->enc.key);
 561                 newkeys->enc.key = NULL;
 562         }
 563         if (newkeys->enc.iv) {
 564                 explicit_bzero(newkeys->enc.iv, newkeys->enc.iv_len);
 565                 free(newkeys->enc.iv);
 566                 newkeys->enc.iv = NULL;
 567         }
 568         free(newkeys->enc.name);
 569         explicit_bzero(&newkeys->enc, sizeof(newkeys->enc));
 570         free(newkeys->comp.name);
 571         explicit_bzero(&newkeys->comp, sizeof(newkeys->comp));
 572         mac_clear(&newkeys->mac);
 573         if (newkeys->mac.key) {
 574                 explicit_bzero(newkeys->mac.key, newkeys->mac.key_len);
 575                 free(newkeys->mac.key);
 576                 newkeys->mac.key = NULL;
 577         }
 578         free(newkeys->mac.name);
 579         explicit_bzero(&newkeys->mac, sizeof(newkeys->mac));
 580         explicit_bzero(newkeys, sizeof(*newkeys));
 581         free(newkeys);
 582 }
 583
 584 void
 585 kex_free(struct kex *kex)
 586 {
 587         u_int mode;
 588
 589 #ifdef WITH_OPENSSL
 590         DH_free(kex->dh);
 591 #ifdef OPENSSL_HAS_ECC
 592         EC_KEY_free(kex->ec_client_key);
 593 #endif /* OPENSSL_HAS_ECC */
 594 #endif /* WITH_OPENSSL */
 595         for (mode = 0; mode < MODE_MAX; mode++) {
 596                 kex_free_newkeys(kex->newkeys[mode]);
 597                 kex->newkeys[mode] = NULL;
 598         }
 599         sshbuf_free(kex->peer);
 600         sshbuf_free(kex->my);
 601         free(kex->session_id);
 602         free(kex->client_version_string);
 603         free(kex->server_version_string);
 604         free(kex->failed_choice);
 605         free(kex->hostkey_alg);
 606         free(kex->name);
 607         free(kex);
 608 }
 609
 610 int
 611 kex_setup(struct ssh *ssh, char *proposal[PROPOSAL_MAX])
 612 {
 613         int r;
 614
 615         if ((r = kex_new(ssh, proposal, &ssh->kex)) != 0)
 616                 return r;
 617         if ((r = kex_send_kexinit(ssh)) != 0) {         /* we start */
 618                 kex_free(ssh->kex);
 619                 ssh->kex = NULL;
 620                 return r;
 621         }
 622         return 0;
 623 }
 624
 625 /*
 626  * Request key re-exchange, returns 0 on success or a ssherr.h error
 627  * code otherwise. Must not be called if KEX is incomplete or in-progress.
 628  */
 629 int
 630 kex_start_rekex(struct ssh *ssh)
 631 {
 632         if (ssh->kex == NULL) {
 633                 error("%s: no kex", __func__);
 634                 return SSH_ERR_INTERNAL_ERROR;
 635         }
 636         if (ssh->kex->done == 0) {
 637                 error("%s: requested twice", __func__);
 638                 return SSH_ERR_INTERNAL_ERROR;
 639         }
 640         ssh->kex->done = 0;
 641         return kex_send_kexinit(ssh);
 642 }
 643
 644 static int
 645 choose_enc(struct sshenc *enc, char *client, char *server)
 646 {
 647         char *name = match_list(client, server, NULL);
 648
 649         if (name == NULL)
 650                 return SSH_ERR_NO_CIPHER_ALG_MATCH;
 651         if ((enc->cipher = cipher_by_name(name)) == NULL) {
 652                 free(name);
 653                 return SSH_ERR_INTERNAL_ERROR;
 654         }
 655         enc->name = name;
 656         enc->enabled = 0;
 657         enc->iv = NULL;
 658         enc->iv_len = cipher_ivlen(enc->cipher);
 659         enc->key = NULL;
 660         enc->key_len = cipher_keylen(enc->cipher);
 661         enc->block_size = cipher_blocksize(enc->cipher);
 662         return 0;
 663 }
 664
 665 static int
 666 choose_mac(struct ssh *ssh, struct sshmac *mac, char *client, char *server)
 667 {
 668         char *name = match_list(client, server, NULL);
 669
 670         if (name == NULL)
 671                 return SSH_ERR_NO_MAC_ALG_MATCH;
 672         if (mac_setup(mac, name) < 0) {
 673                 free(name);
 674                 return SSH_ERR_INTERNAL_ERROR;
 675         }
 676         mac->name = name;
 677         mac->key = NULL;
 678         mac->enabled = 0;
 679         return 0;
 680 }
 681
 682 static int
 683 choose_comp(struct sshcomp *comp, char *client, char *server)
 684 {
 685         char *name = match_list(client, server, NULL);
 686
 687         if (name == NULL)
 688                 return SSH_ERR_NO_COMPRESS_ALG_MATCH;
 689         if (strcmp(name, "zlib@openssh.com") == 0) {
 690                 comp->type = COMP_DELAYED;
 691         } else if (strcmp(name, "zlib") == 0) {
 692                 comp->type = COMP_ZLIB;
 693         } else if (strcmp(name, "none") == 0) {
 694                 comp->type = COMP_NONE;
 695         } else {
 696                 free(name);
 697                 return SSH_ERR_INTERNAL_ERROR;
 698         }
 699         comp->name = name;
 700         return 0;
 701 }
 702
 703 static int
 704 choose_kex(struct kex *k, char *client, char *server)
 705 {
 706         const struct kexalg *kexalg;
 707
 708         k->name = match_list(client, server, NULL);
 709
 710         debug("kex: algorithm: %s", k->name ? k->name : "(no match)");
 711         if (k->name == NULL)
 712                 return SSH_ERR_NO_KEX_ALG_MATCH;
 713         if ((kexalg = kex_alg_by_name(k->name)) == NULL)
 714                 return SSH_ERR_INTERNAL_ERROR;
 715         k->kex_type = kexalg->type;
 716         k->hash_alg = kexalg->hash_alg;
 717         k->ec_nid = kexalg->ec_nid;
 718         return 0;
 719 }
 720
 721 static int
 722 choose_hostkeyalg(struct kex *k, char *client, char *server)
 723 {
 724         k->hostkey_alg = match_list(client, server, NULL);
 725
 726         debug("kex: host key algorithm: %s",
 727             k->hostkey_alg ? k->hostkey_alg : "(no match)");
 728         if (k->hostkey_alg == NULL)
 729                 return SSH_ERR_NO_HOSTKEY_ALG_MATCH;
 730         k->hostkey_type = sshkey_type_from_name(k->hostkey_alg);
 731         if (k->hostkey_type == KEY_UNSPEC)
 732                 return SSH_ERR_INTERNAL_ERROR;
 733         k->hostkey_nid = sshkey_ecdsa_nid_from_name(k->hostkey_alg);
 734         return 0;
 735 }
 736
 737 static int
 738 proposals_match(char *my[PROPOSAL_MAX], char *peer[PROPOSAL_MAX])
 739 {
 740         static int check[] = {
 741                 PROPOSAL_KEX_ALGS, PROPOSAL_SERVER_HOST_KEY_ALGS, -1
 742         };
 743         int *idx;
 744         char *p;
 745
 746         for (idx = &check[0]; *idx != -1; idx++) {
 747                 if ((p = strchr(my[*idx], ',')) != NULL)
 748                         *p = '\0';
 749                 if ((p = strchr(peer[*idx], ',')) != NULL)
 750                         *p = '\0';
 751                 if (strcmp(my[*idx], peer[*idx]) != 0) {
 752                         debug2("proposal mismatch: my %s peer %s",
 753                             my[*idx], peer[*idx]);
 754                         return (0);
 755                 }
 756         }
 757         debug2("proposals match");
 758         return (1);
 759 }
 760
 761 static int
 762 kex_choose_conf(struct ssh *ssh)
 763 {
 764         struct kex *kex = ssh->kex;
 765         struct newkeys *newkeys;
 766         char **my = NULL, **peer = NULL;
 767         char **cprop, **sprop;
 768         int nenc, nmac, ncomp;
 769         u_int mode, ctos, need, dh_need, authlen;
 770         int r, first_kex_follows;
 771
 772         debug2("local %s KEXINIT proposal", kex->server ? "server" : "client");
 773         if ((r = kex_buf2prop(kex->my, NULL, &my)) != 0)
 774                 goto out;
 775         debug2("peer %s KEXINIT proposal", kex->server ? "client" : "server");
 776         if ((r = kex_buf2prop(kex->peer, &first_kex_follows, &peer)) != 0)
 777                 goto out;
 778
 779         if (kex->server) {
 780                 cprop=peer;
 781                 sprop=my;
 782         } else {
 783                 cprop=my;
 784                 sprop=peer;
 785         }
 786
 787         /* Check whether client supports ext_info_c */
 788         if (kex->server) {
 789                 char *ext;
 790
 791                 ext = match_list("ext-info-c", peer[PROPOSAL_KEX_ALGS], NULL);
 792                 kex->ext_info_c = (ext != NULL);
 793                 free(ext);
 794         }
 795
 796         /* Algorithm Negotiation */
 797         if ((r = choose_kex(kex, cprop[PROPOSAL_KEX_ALGS],
 798             sprop[PROPOSAL_KEX_ALGS])) != 0) {
 799                 kex->failed_choice = peer[PROPOSAL_KEX_ALGS];
 800                 peer[PROPOSAL_KEX_ALGS] = NULL;
 801                 goto out;
 802         }
 803         if ((r = choose_hostkeyalg(kex, cprop[PROPOSAL_SERVER_HOST_KEY_ALGS],
 804             sprop[PROPOSAL_SERVER_HOST_KEY_ALGS])) != 0) {
 805                 kex->failed_choice = peer[PROPOSAL_SERVER_HOST_KEY_ALGS];
 806                 peer[PROPOSAL_SERVER_HOST_KEY_ALGS] = NULL;
 807                 goto out;
 808         }
 809         for (mode = 0; mode < MODE_MAX; mode++) {
 810                 if ((newkeys = calloc(1, sizeof(*newkeys))) == NULL) {
 811                         r = SSH_ERR_ALLOC_FAIL;
 812                         goto out;
 813                 }
 814                 kex->newkeys[mode] = newkeys;
 815                 ctos = (!kex->server && mode == MODE_OUT) ||
 816                     (kex->server && mode == MODE_IN);
 817                 nenc  = ctos ? PROPOSAL_ENC_ALGS_CTOS  : PROPOSAL_ENC_ALGS_STOC;
 818                 nmac  = ctos ? PROPOSAL_MAC_ALGS_CTOS  : PROPOSAL_MAC_ALGS_STOC;
 819                 ncomp = ctos ? PROPOSAL_COMP_ALGS_CTOS : PROPOSAL_COMP_ALGS_STOC;
 820                 if ((r = choose_enc(&newkeys->enc, cprop[nenc],
 821                     sprop[nenc])) != 0) {
 822                         kex->failed_choice = peer[nenc];
 823                         peer[nenc] = NULL;
 824                         goto out;
 825                 }
 826                 authlen = cipher_authlen(newkeys->enc.cipher);
 827                 /* ignore mac for authenticated encryption */
 828                 if (authlen == 0 &&
 829                     (r = choose_mac(ssh, &newkeys->mac, cprop[nmac],
 830                     sprop[nmac])) != 0) {
 831                         kex->failed_choice = peer[nmac];
 832                         peer[nmac] = NULL;
 833                         goto out;
 834                 }
 835                 if ((r = choose_comp(&newkeys->comp, cprop[ncomp],
 836                     sprop[ncomp])) != 0) {
 837                         kex->failed_choice = peer[ncomp];
 838                         peer[ncomp] = NULL;
 839                         goto out;
 840                 }
 841                 debug("kex: %s cipher: %s MAC: %s compression: %s",
 842                     ctos ? "client->server" : "server->client",
 843                     newkeys->enc.name,
 844                     authlen == 0 ? newkeys->mac.name : "<implicit>",
 845                     newkeys->comp.name);
 846         }
 847         need = dh_need = 0;
 848         for (mode = 0; mode < MODE_MAX; mode++) {
 849                 newkeys = kex->newkeys[mode];
 850                 need = MAXIMUM(need, newkeys->enc.key_len);
 851                 need = MAXIMUM(need, newkeys->enc.block_size);
 852                 need = MAXIMUM(need, newkeys->enc.iv_len);
 853                 need = MAXIMUM(need, newkeys->mac.key_len);
 854                 dh_need = MAXIMUM(dh_need, cipher_seclen(newkeys->enc.cipher));
 855                 dh_need = MAXIMUM(dh_need, newkeys->enc.block_size);
 856                 dh_need = MAXIMUM(dh_need, newkeys->enc.iv_len);
 857                 dh_need = MAXIMUM(dh_need, newkeys->mac.key_len);
 858         }
 859         /* XXX need runden? */
 860         kex->we_need = need;
 861         kex->dh_need = dh_need;
 862
 863         /* ignore the next message if the proposals do not match */
 864         if (first_kex_follows && !proposals_match(my, peer))
 865                 ssh->dispatch_skip_packets = 1;
 866         r = 0;
 867  out:
 868         kex_prop_free(my);
 869         kex_prop_free(peer);
 870         return r;
 871 }
 872
 873 static int
 874 derive_key(struct ssh *ssh, int id, u_int need, u_char *hash, u_int hashlen,
 875     const struct sshbuf *shared_secret, u_char **keyp)
 876 {
 877         struct kex *kex = ssh->kex;
 878         struct ssh_digest_ctx *hashctx = NULL;
 879         char c = id;
 880         u_int have;
 881         size_t mdsz;
 882         u_char *digest;
 883         int r;
 884
 885         if ((mdsz = ssh_digest_bytes(kex->hash_alg)) == 0)
 886                 return SSH_ERR_INVALID_ARGUMENT;
 887         if ((digest = calloc(1, ROUNDUP(need, mdsz))) == NULL) {
 888                 r = SSH_ERR_ALLOC_FAIL;
 889                 goto out;
 890         }
 891
 892         /* K1 = HASH(K || H || "A" || session_id) */
 893         if ((hashctx = ssh_digest_start(kex->hash_alg)) == NULL ||
 894             ssh_digest_update_buffer(hashctx, shared_secret) != 0 ||
 895             ssh_digest_update(hashctx, hash, hashlen) != 0 ||
 896             ssh_digest_update(hashctx, &c, 1) != 0 ||
 897             ssh_digest_update(hashctx, kex->session_id,
 898             kex->session_id_len) != 0 ||
 899             ssh_digest_final(hashctx, digest, mdsz) != 0) {
 900                 r = SSH_ERR_LIBCRYPTO_ERROR;
 901                 goto out;
 902         }
 903         ssh_digest_free(hashctx);
 904         hashctx = NULL;
 905
 906         /*
 907          * expand key:
 908          * Kn = HASH(K || H || K1 || K2 || ... || Kn-1)
 909          * Key = K1 || K2 || ... || Kn
 910          */
 911         for (have = mdsz; need > have; have += mdsz) {
 912                 if ((hashctx = ssh_digest_start(kex->hash_alg)) == NULL ||
 913                     ssh_digest_update_buffer(hashctx, shared_secret) != 0 ||
 914                     ssh_digest_update(hashctx, hash, hashlen) != 0 ||
 915                     ssh_digest_update(hashctx, digest, have) != 0 ||
 916                     ssh_digest_final(hashctx, digest + have, mdsz) != 0) {
 917                         r = SSH_ERR_LIBCRYPTO_ERROR;
 918                         goto out;
 919                 }
 920                 ssh_digest_free(hashctx);
 921                 hashctx = NULL;
 922         }
 923 #ifdef DEBUG_KEX
 924         fprintf(stderr, "key '%c'== ", c);
 925         dump_digest("key", digest, need);
 926 #endif
 927         *keyp = digest;
 928         digest = NULL;
 929         r = 0;
 930  out:
 931         free(digest);
 932         ssh_digest_free(hashctx);
 933         return r;
 934 }
 935
 936 #define NKEYS   6
 937 int
 938 kex_derive_keys(struct ssh *ssh, u_char *hash, u_int hashlen,
 939     const struct sshbuf *shared_secret)
 940 {
 941         struct kex *kex = ssh->kex;
 942         u_char *keys[NKEYS];
 943         u_int i, j, mode, ctos;
 944         int r;
 945
 946         for (i = 0; i < NKEYS; i++) {
 947                 if ((r = derive_key(ssh, 'A'+i, kex->we_need, hash, hashlen,
 948                     shared_secret, &keys[i])) != 0) {
 949                         for (j = 0; j < i; j++)
 950                                 free(keys[j]);
 951                         return r;
 952                 }
 953         }
 954         for (mode = 0; mode < MODE_MAX; mode++) {
 955                 ctos = (!kex->server && mode == MODE_OUT) ||
 956                     (kex->server && mode == MODE_IN);
 957                 kex->newkeys[mode]->enc.iv  = keys[ctos ? 0 : 1];
 958                 kex->newkeys[mode]->enc.key = keys[ctos ? 2 : 3];
 959                 kex->newkeys[mode]->mac.key = keys[ctos ? 4 : 5];
 960         }
 961         return 0;
 962 }
 963
 964 #ifdef WITH_OPENSSL
 965 int
 966 kex_derive_keys_bn(struct ssh *ssh, u_char *hash, u_int hashlen,
 967     const BIGNUM *secret)
 968 {
 969         struct sshbuf *shared_secret;
 970         int r;
 971
 972         if ((shared_secret = sshbuf_new()) == NULL)
 973                 return SSH_ERR_ALLOC_FAIL;
 974         if ((r = sshbuf_put_bignum2(shared_secret, secret)) == 0)
 975                 r = kex_derive_keys(ssh, hash, hashlen, shared_secret);
 976         sshbuf_free(shared_secret);
 977         return r;
 978 }
 979 #endif
 980
 981
 982 #if defined(DEBUG_KEX) || defined(DEBUG_KEXDH) || defined(DEBUG_KEXECDH)
 983 void
 984 dump_digest(char *msg, u_char *digest, int len)
 985 {
 986         fprintf(stderr, "%s\n", msg);
 987         sshbuf_dump_data(digest, len, stderr);
 988 }
 989 #endif