chiark - git - mdw - tripe/blob - keyexch.c

   1 /* -*-c-*-
   2  *
   3  * $Id: keyexch.c,v 1.10 2003/10/15 09:29:38 mdw Exp $
   4  *
   5  * Key exchange protocol
   6  *
   7  * (c) 2001 Straylight/Edgeware
   8  */
   9
  10 /*----- Licensing notice --------------------------------------------------*
  11  *
  12  * This file is part of Trivial IP Encryption (TrIPE).
  13  *
  14  * TrIPE is free software; you can redistribute it and/or modify
  15  * it under the terms of the GNU General Public License as published by
  16  * the Free Software Foundation; either version 2 of the License, or
  17  * (at your option) any later version.
  18  *
  19  * TrIPE is distributed in the hope that it will be useful,
  20  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  21  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  22  * GNU General Public License for more details.
  23  *
  24  * You should have received a copy of the GNU General Public License
  25  * along with TrIPE; if not, write to the Free Software Foundation,
  26  * Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.
  27  */
  28
  29 /*----- Revision history --------------------------------------------------*
  30  *
  31  * $Log: keyexch.c,v $
  32  * Revision 1.10  2003/10/15 09:29:38  mdw
  33  * Cosmetic fix to changelog comment.
  34  *
  35  * Revision 1.9  2003/07/13 11:53:14  mdw
  36  * Add protocol commentary.
  37  *
  38  * Revision 1.8  2003/07/13 11:19:49  mdw
  39  * Incompatible protocol fix!  Include message type code under MAC tag to
  40  * prevent cut-and-paste from key-exchange messages to general packet
  41  * transport.
  42  *
  43  * Revision 1.7  2003/05/17 11:01:28  mdw
  44  * Handle flags on challenge timers correctly to prevent confusing the event
  45  * list.
  46  *
  47  * Revision 1.6  2003/04/06 10:26:35  mdw
  48  * Report peer name on decrypt errors.
  49  *
  50  * Revision 1.5  2002/01/13 14:54:40  mdw
  51  * Patch up zero-knowledge property by passing an encrypted log with a
  52  * challenge, so that the prover can verify that the challenge is good.
  53  *
  54  * Revision 1.4  2001/06/22 19:40:36  mdw
  55  * Support expiry of other peers' public keys.
  56  *
  57  * Revision 1.3  2001/06/19 22:07:09  mdw
  58  * Cosmetic fixes.
  59  *
  60  * Revision 1.2  2001/02/16 21:24:27  mdw
  61  * Rewrite for new key exchange protocol.
  62  *
  63  * Revision 1.1  2001/02/03 20:26:37  mdw
  64  * Initial checkin.
  65  *
  66  */
  67
  68 /*----- Header files ------------------------------------------------------*/
  69
  70 #include "tripe.h"
  71
  72 /*----- Brief protocol overview -------------------------------------------*
  73  *
  74  * Let %$G$% be a cyclic group; let %$g$% be a generator of %$G$%, and let
  75  * %$q$% be the order of %$G$%; for a key %$K$%, let %$E_K(\cdot)$% denote
  76  * application of the symmetric packet protocol to a message; let
  77  * %$H(\cdot)$% be the random oracle.  Let $\alpha \inr \{0,\ldots,q - 1\}$%
  78  * be Alice's private key; let %$a = g^\alpha$% be her public key; let %$b$%
  79  * be Bob's public key.
  80  *
  81  * At the beginning of the session, Alice chooses
  82  *
  83  *   %$\rho_A \inr \{0, \ldots q - 1\}$%
  84  *
  85  * We also have:
  86  *
  87  * %$r_A = g^{\rho_A}$%                 Alice's challenge
  88  * %$c_A = H(\cookie{cookie}, r_A)$%    Alice's cookie
  89  * %$v_A = \rho_A \xor H(\cookie{expected-reply}, r_A, r_B, b^{\rho_A})$%
  90  *                                      Alice's challenge check value
  91  * %$r_B^\alpha = a^{\rho_B}$%          Alice's reply
  92  * %$K = r_B^{\rho_A} = r_B^{\rho_A} = g^{\rho_A\rho_B}$%
  93  *                                      Alice and Bob's shared secret key
  94  * %$w_A = H(\cookie{switch-request}, c_A, c_B)$%
  95  *                                      Alice's switch request value
  96  * %$u_A = H(\cookie{switch-confirm}, c_A, c_B)$%
  97  *                                      Alice's switch confirm value
  98  *
  99  * The messages are then:
 100  *
 101  * %$\cookie{kx-pre-challenge}, r_A$%
 102  *      Initial greeting.  In state @KXS_CHAL@.
 103  *
 104  * %$\cookie{kx-cookie}, r_A, c_B$%
 105  *      My table is full but I got your message.
 106  *
 107  * %$\cookie{kx-challenge}, r_A, c_B, v_A$%
 108  *      Here's a full challenge for you to answer.
 109  *
 110  * %$\cookie{kx-reply}, c_A, c_B, v_A, E_K(r_B^\alpha))$%
 111  *      Challenge accpeted: here's the answer.  Commit to my challenge.  Move
 112  *      to @KXS_COMMIT@.
 113  *
 114  * %$\cookie{kx-switch}, c_A, c_B, E_K(r_B^\alpha, w_A))$%
 115  *      Reply received: here's my reply.  Committed; send data; move to
 116  *      @KXS_SWITCH@.
 117  *
 118  * %$\cookie{kx-switch-ok}, E_K(u_A))$%
 119  *      Switch received.  Committed; send data; move to @KXS_SWITCH@.
 120  */
 121
 122 /*----- Tunable parameters ------------------------------------------------*/
 123
 124 #define T_VALID MIN(2)                  /* Challenge validity period */
 125 #define T_RETRY SEC(10)                 /* Challenge retransmit interval */
 126
 127 #define ISVALID(kx, now) ((now) < (kx)->t_valid)
 128
 129 /*----- Various utilities -------------------------------------------------*/
 130
 131 /* --- @hashmp@ --- *
 132  *
 133  * Arguments:   @HASH_CTX *r@ = pointer to hash context
 134  *              @mp *m@ = pointer to multiprecision integer
 135  *
 136  * Returns:     ---
 137  *
 138  * Use:         Adds the hash of a multiprecision integer to the context.
 139  *              Corrupts @buf_t@.
 140  */
 141
 142 static void hashmp(HASH_CTX *r, mp *m)
 143 {
 144   buf b;
 145   buf_init(&b, buf_t, sizeof(buf_t));
 146   buf_putmp(&b, m);
 147   assert(BOK(&b));
 148   HASH(r, BBASE(&b), BLEN(&b));
 149 }
 150
 151 /* --- @mpcrypt@ --- *
 152  *
 153  * Arguments:   @mp *d@ = the destination integer
 154  *              @mp *x@ = the plaintext/ciphertext integer
 155  *              @size_t sz@ = the expected size of the plaintext
 156  *              @const octet *k@ = pointer to key material
 157  *              @size_t ksz@ = size of the key
 158  *
 159  * Returns:     The encrypted/decrypted integer.
 160  *
 161  * Use:         Encrypts (or decrypts) a multiprecision integer using another
 162  *              multiprecision integer as the key.  This is a slightly grotty
 163  *              way to do this, but it's easier than the alternatives.
 164  */
 165
 166 static mp *mpcrypt(mp *d, mp *x, size_t sz, const octet *k, size_t ksz)
 167 {
 168   MGF_CTX m;
 169
 170   MGF_INIT(&m, k, ksz, 0);
 171   mp_storeb(x, buf_t, sz);
 172   MGF_CRYPT(&m, buf_t, buf_t, sz);
 173   return (mp_loadb(d, buf_t, sz));
 174 }
 175
 176 /* --- @timer@ --- *
 177  *
 178  * Arguments:   @struct timeval *tv@ = the current time
 179  *              @void *v@ = pointer to key exchange context
 180  *
 181  * Returns:     ---
 182  *
 183  * Use:         Acts when the key exchange timer goes off.
 184  */
 185
 186 static void timer(struct timeval *tv, void *v)
 187 {
 188   keyexch *kx = v;
 189   kx->f &= ~KXF_TIMER;
 190   T( trace(T_KEYEXCH, "keyexch: timer has popped"); )
 191   kx_start(kx);
 192 }
 193
 194 /* --- @settimer@ --- *
 195  *
 196  * Arguments:   @keyexch *kx@ = pointer to key exchange context
 197  *              @time_t t@ = when to set the timer for
 198  *
 199  * Returns:     ---
 200  *
 201  * Use:         Sets the timer for the next key exchange attempt.
 202  */
 203
 204 static void settimer(keyexch *kx, time_t t)
 205 {
 206   struct timeval tv;
 207   if (kx->f & KXF_TIMER)
 208     sel_rmtimer(&kx->t);
 209   tv.tv_sec = t;
 210   tv.tv_usec = 0;
 211   sel_addtimer(&sel, &kx->t, &tv, timer, kx);
 212   kx->f |= KXF_TIMER;
 213 }
 214
 215 /*----- Challenge management ----------------------------------------------*/
 216
 217 /* --- Notes on challenge management --- *
 218  *
 219  * We may get multiple different replies to our key exchange; some will be
 220  * correct, some inserted by attackers.  Up until @KX_THRESH@, all challenges
 221  * received will be added to the table and given a full response.  After
 222  * @KX_THRESH@ distinct challenges are received, we return only a `cookie':
 223  * our existing challenge, followed by a hash of the sender's challenge.  We
 224  * do %%\emph{not}%% give a bare challenge a reply slot at this stage.  All
 225  * properly-formed cookies are assigned a table slot: if none is spare, a
 226  * used slot is randomly selected and destroyed.  A cookie always receives a
 227  * full reply.
 228  */
 229
 230 /* --- @kxc_destroy@ --- *
 231  *
 232  * Arguments:   @kxchal *kxc@ = pointer to the challenge block
 233  *
 234  * Returns:     ---
 235  *
 236  * Use:         Disposes of a challenge block.
 237  */
 238
 239 static void kxc_destroy(kxchal *kxc)
 240 {
 241   if (kxc->f & KXF_TIMER)
 242     sel_rmtimer(&kxc->t);
 243   mp_drop(kxc->c);
 244   mp_drop(kxc->r);
 245   mp_drop(kxc->ck);
 246   ks_drop(kxc->ks);
 247   DESTROY(kxc);
 248 }
 249
 250 /* --- @kxc_stoptimer@ --- *
 251  *
 252  * Arguments:   @kxchal *kxc@ = pointer to the challenge block
 253  *
 254  * Returns:     ---
 255  *
 256  * Use:         Stops the challenge's retry timer from sending messages.
 257  *              Useful when the state machine is in the endgame of the
 258  *              exchange.
 259  */
 260
 261 static void kxc_stoptimer(kxchal *kxc)
 262 {
 263   if (kxc->f & KXF_TIMER)
 264     sel_rmtimer(&kxc->t);
 265   kxc->f &= ~KXF_TIMER;
 266 }
 267
 268 /* --- @kxc_new@ --- *
 269  *
 270  * Arguments:   @keyexch *kx@ = pointer to key exchange block
 271  *
 272  * Returns:     A pointer to the challenge block.
 273  *
 274  * Use:         Returns a pointer to a new challenge block to fill in.
 275  */
 276
 277 static kxchal *kxc_new(keyexch *kx)
 278 {
 279   kxchal *kxc;
 280   unsigned i;
 281
 282   /* --- If we're over reply threshold, discard one at random --- */
 283
 284   if (kx->nr < KX_NCHAL)
 285     i = kx->nr++;
 286   else {
 287     i = rand_global.ops->range(&rand_global, KX_NCHAL);
 288     kxc_destroy(kx->r[i]);
 289   }
 290
 291   /* --- Fill in the new structure --- */
 292
 293   kxc = CREATE(kxchal);
 294   kxc->c = 0;
 295   kxc->r = 0;
 296   kxc->ck = 0;
 297   kxc->ks = 0;
 298   kxc->kx = kx;
 299   kxc->f = 0;
 300   kx->r[i] = kxc;
 301   return (kxc);
 302 }
 303
 304 /* --- @kxc_bychal@ --- *
 305  *
 306  * Arguments:   @keyexch *kx@ = pointer to key exchange block
 307  *              @mp *c@ = challenge from remote host
 308  *
 309  * Returns:     Pointer to the challenge block, or null.
 310  *
 311  * Use:         Finds a challenge block, given its challenge.
 312  */
 313
 314 static kxchal *kxc_bychal(keyexch *kx, mp *c)
 315 {
 316   unsigned i;
 317
 318   for (i = 0; i < kx->nr; i++) {
 319     if (MP_EQ(c, kx->r[i]->c))
 320       return (kx->r[i]);
 321   }
 322   return (0);
 323 }
 324
 325 /* --- @kxc_byhc@ --- *
 326  *
 327  * Arguments:   @keyexch *kx@ = pointer to key exchange block
 328  *              @const octet *hc@ = challenge hash from remote host
 329  *
 330  * Returns:     Pointer to the challenge block, or null.
 331  *
 332  * Use:         Finds a challenge block, given a hash of its challenge.
 333  */
 334
 335 static kxchal *kxc_byhc(keyexch *kx, const octet *hc)
 336 {
 337   unsigned i;
 338
 339   for (i = 0; i < kx->nr; i++) {
 340     if (memcmp(hc, kx->r[i]->hc, HASHSZ) == 0)
 341       return (kx->r[i]);
 342   }
 343   return (0);
 344 }
 345
 346 /* --- @kxc_answer@ --- *
 347  *
 348  * Arguments:   @keyexch *kx@ = pointer to key exchange block
 349  *              @kxchal *kxc@ = pointer to challenge block
 350  *
 351  * Returns:     ---
 352  *
 353  * Use:         Sends a reply to the remote host, according to the data in
 354  *              this challenge block.
 355  */
 356
 357 static void kxc_answer(keyexch *kx, kxchal *kxc);
 358
 359 static void kxc_timer(struct timeval *tv, void *v)
 360 {
 361   kxchal *kxc = v;
 362   kxc->f &= ~KXF_TIMER;
 363   kxc_answer(kxc->kx, kxc);
 364 }
 365
 366 static void kxc_answer(keyexch *kx, kxchal *kxc)
 367 {
 368   stats *st = p_stats(kx->p);
 369   buf *b = p_txstart(kx->p, MSG_KEYEXCH | (kxc->r ? KX_REPLY : KX_CHAL));
 370   struct timeval tv;
 371   buf bb;
 372
 373   /* --- Build the reply packet --- */
 374
 375   if (!kxc->r)
 376     buf_putmp(b, kx->c);
 377   else
 378     buf_put(b, kx->hc, HASHSZ);
 379   buf_put(b, kxc->hc, HASHSZ);
 380   buf_putmp(b, kxc->ck);
 381
 382   /* --- Maybe send an actual reply, if we have one --- */
 383
 384   if (!kxc->r) {
 385     T( trace(T_KEYEXCH, "keyexch: resending challenge to `%s'",
 386              p_name(kx->p)); )
 387   } else {
 388     T( trace(T_KEYEXCH, "keyexch: sending reply to `%s'", p_name(kx->p)); )
 389     buf_init(&bb, buf_i, sizeof(buf_i));
 390     buf_putmp(&bb, kxc->r);
 391     buf_flip(&bb);
 392     ks_encrypt(kxc->ks, MSG_KEYEXCH | KX_REPLY, &bb, b);
 393   }
 394
 395   /* --- Update the statistics --- */
 396
 397   if (BOK(b)) {
 398     st->n_kxout++;
 399     st->sz_kxout += BLEN(b);
 400     p_txend(kx->p);
 401   }
 402
 403   /* --- Schedule another resend --- */
 404
 405   if (kxc->f & KXF_TIMER)
 406     sel_rmtimer(&kxc->t);
 407   gettimeofday(&tv, 0);
 408   tv.tv_sec += T_RETRY;
 409   sel_addtimer(&sel, &kxc->t, &tv, kxc_timer, kxc);
 410   kxc->f |= KXF_TIMER;
 411 }
 412
 413 /*----- Individual message handlers ---------------------------------------*/
 414
 415 /* --- @getreply@ --- *
 416  *
 417  * Arguments:   @keyexch *kx@ = pointer to key exchange context
 418  *              @mp *c@ = a challenge
 419  *              @mp *ck@ = the supplied expected-reply check value
 420  *
 421  * Returns:     A pointer to the reply, or null if the reply-hash was wrong.
 422  *
 423  * Use:         Computes replies to challenges.
 424  */
 425
 426 static mp *getreply(keyexch *kx, mp *c, mp *ck)
 427 {
 428   mp *r = mpmont_exp(&mg, MP_NEW, c, kpriv.x);
 429   mp *a;
 430   HASH_CTX h;
 431   octet buf[HASHSZ];
 432   int ok;
 433
 434   HASH_INIT(&h);
 435   HASH_STRING(&h, "tripe-expected-reply");
 436   hashmp(&h, c);
 437   hashmp(&h, kx->c);
 438   hashmp(&h, r);
 439   HASH_DONE(&h, buf);
 440
 441   a = mpcrypt(MP_NEW, ck, mp_octets(kpriv.dp.q), buf, sizeof(buf));
 442   IF_TRACING(T_KEYEXCH, IF_TRACING(T_CRYPTO, {
 443     trace(T_CRYPTO, "crypto: computed reply = %s", mpstr(r));
 444     trace_block(T_CRYPTO, "crypto: computed reply hash", buf, HASHSZ);
 445     trace(T_CRYPTO, "crypto: recovered log = %s", mpstr(a));
 446   }))
 447   a = mpmont_exp(&mg, a, kpriv.dp.g, a);
 448   ok = mp_eq(a, c);
 449   if (!ok) {
 450     a_warn("invalid expected-reply check from `%s'", p_name(kx->p));
 451     IF_TRACING(T_KEYEXCH, IF_TRACING(T_CRYPTO, {
 452       trace(T_CRYPTO, "crypto: computed challenge = %s", mpstr(a));
 453     }))
 454     mp_drop(r);
 455   }
 456   mp_drop(a);
 457   return (ok ? r : 0);
 458 }
 459
 460 /* --- @dochallenge@ --- *
 461  *
 462  * Arguments:   @keyexch *kx@ = pointer to key exchange block
 463  *              @unsigned msg@ = message code for the packet
 464  *              @buf *b@ = buffer containing the packet
 465  *
 466  * Returns:     Zero if OK, nonzero if the packet was rejected.
 467  *
 468  * Use:         Processes a packet containing a challenge.
 469  */
 470
 471 static int dochallenge(keyexch *kx, unsigned msg, buf *b)
 472 {
 473   mp *c = 0, *ck = 0;
 474   const octet *hc = 0;
 475   kxchal *kxc;
 476   HASH_CTX h;
 477   octet buf[HASHSZ];
 478
 479   /* --- Ensure that we're in a sensible state --- */
 480
 481   if (kx->s != KXS_CHAL) {
 482     a_warn("unexpected challenge from `%s'", p_name(kx->p));
 483     goto bad;
 484   }
 485
 486   /* --- Unpack the packet --- */
 487
 488   if ((c = buf_getmp(b)) == 0 ||
 489       (msg >= KX_COOKIE && (hc = buf_get(b, HASHSZ)) == 0) ||
 490       (msg >= KX_CHAL && (ck = buf_getmp(b)) == 0) ||
 491       BLEFT(b)) {
 492     a_warn("malformed packet from `%s'", p_name(kx->p));
 493     goto bad;
 494   }
 495
 496   IF_TRACING(T_KEYEXCH, IF_TRACING(T_CRYPTO, {
 497     trace(T_CRYPTO, "crypto: challenge = %s", mpstr(c));
 498     if (hc) trace_block(T_CRYPTO, "crypto: cookie", hc, HASHSZ);
 499     if (ck) trace(T_CRYPTO, "crypto: check value = %s", mpstr(ck));
 500   }))
 501
 502   /* --- First, handle a bare challenge --- *
 503    *
 504    * If the table is heavily loaded, just emit a cookie and return.
 505    */
 506
 507   if (!hc && kx->nr >= KX_THRESH) {
 508     T( trace(T_KEYEXCH, "keyexch: too many challenges -- sending cookie"); )
 509     b = p_txstart(kx->p, MSG_KEYEXCH | KX_COOKIE);
 510     buf_putmp(b, kx->c);
 511     HASH_INIT(&h);
 512     HASH_STRING(&h, "tripe-cookie");
 513     hashmp(&h, c);
 514     HASH_DONE(&h, buf_get(b, HASHSZ));
 515     p_txend(kx->p);
 516     goto tidy;
 517   }
 518
 519   /* --- Discard a packet with an invalid cookie --- */
 520
 521   if (hc && memcmp(hc, kx->hc, HASHSZ) != 0) {
 522     a_warn("incorrect cookie from `%s'", p_name(kx->p));
 523     goto bad;
 524   }
 525
 526   /* --- Find a challenge block for this packet --- *
 527    *
 528    * If there isn't one already, create a new one.
 529    */
 530
 531   if ((kxc = kxc_bychal(kx, c)) == 0) {
 532     size_t x, y, z;
 533     mp *r;
 534
 535     /* --- Be careful here --- *
 536      *
 537      * If this is a full challenge, and it's the first time I've seen it, I
 538      * want to be able to throw it away before committing a table entry to
 539      * it.
 540      */
 541
 542     if (!ck)
 543       kxc = kxc_new(kx);
 544     else {
 545       if ((r = getreply(kx, c, ck)) == 0)
 546         goto bad;
 547       kxc = kxc_new(kx);
 548       kxc->r = r;
 549     }
 550     kxc->c = mp_copy(c);
 551
 552     /* --- Work out the cookie for this challenge --- */
 553
 554     HASH_INIT(&h);
 555     HASH_STRING(&h, "tripe-cookie");
 556     hashmp(&h, kxc->c);
 557     HASH_DONE(&h, kxc->hc);
 558
 559     /* --- Compute the expected-reply hash --- */
 560
 561     HASH_INIT(&h);
 562     HASH_STRING(&h, "tripe-expected-reply");
 563     hashmp(&h, kx->c);
 564     hashmp(&h, kxc->c);
 565     hashmp(&h, kx->rx);
 566     HASH_DONE(&h, buf);
 567     kxc->ck = mpcrypt(MP_NEW, kx->alpha, mp_octets(kpriv.dp.q),
 568                       buf, sizeof(buf));
 569
 570     /* --- Work out the shared key --- */
 571
 572     trace(T_CRYPTO, "debug: c = %s", mpstr(c));
 573     trace(T_CRYPTO, "debug: alpha = %s", mpstr(kx->alpha));
 574     r = mpmont_exp(&mg, MP_NEW, c, kx->alpha);
 575     trace(T_CRYPTO, "debug: r = %s", mpstr(r));
 576
 577     /* --- Compute the switch messages --- */
 578
 579     HASH_INIT(&h); HASH_STRING(&h, "tripe-switch-request");
 580     hashmp(&h, kx->c); hashmp(&h, kxc->c);
 581     HASH_DONE(&h, kxc->hswrq_out);
 582     HASH_INIT(&h); HASH_STRING(&h, "tripe-switch-confirm");
 583     hashmp(&h, kx->c); hashmp(&h, kxc->c);
 584     HASH_DONE(&h, kxc->hswok_out);
 585
 586     HASH_INIT(&h); HASH_STRING(&h, "tripe-switch-request");
 587     hashmp(&h, kxc->c); hashmp(&h, kx->c);
 588     HASH_DONE(&h, kxc->hswrq_in);
 589     HASH_INIT(&h); HASH_STRING(&h, "tripe-switch-confirm");
 590     hashmp(&h, kxc->c); hashmp(&h, kx->c);
 591     HASH_DONE(&h, kxc->hswok_in);
 592
 593     IF_TRACING(T_KEYEXCH, IF_TRACING(T_CRYPTO, {
 594       trace_block(T_CRYPTO, "crypto: computed cookie", kxc->hc, HASHSZ);
 595       trace_block(T_CRYPTO, "crypto: expected-reply hash",
 596                   buf, HASHSZ);
 597       trace(T_CRYPTO, "crypto: my reply check = %s", mpstr(kxc->ck));
 598       trace(T_CRYPTO, "crypto: shared secret = %s", mpstr(r));
 599       trace_block(T_CRYPTO, "crypto: outbound switch request",
 600                   kxc->hswrq_out, HASHSZ);
 601       trace_block(T_CRYPTO, "crypto: outbound switch confirm",
 602                   kxc->hswok_out, HASHSZ);
 603       trace_block(T_CRYPTO, "crypto: inbound switch request",
 604                   kxc->hswrq_in, HASHSZ);
 605       trace_block(T_CRYPTO, "crypto: inbound switch confirm",
 606                   kxc->hswok_in, HASHSZ);
 607     }))
 608
 609     /* --- Create a new symmetric keyset --- */
 610
 611     buf_init(b, buf_o, sizeof(buf_o));
 612     buf_putmp(b, kx->c); x = BLEN(b);
 613     buf_putmp(b, kxc->c); y = BLEN(b);
 614     buf_putmp(b, r); z = BLEN(b);
 615     assert(BOK(b));
 616
 617     kxc->ks = ks_gen(BBASE(b), x, y, z, kx->p);
 618     mp_drop(r);
 619   }
 620
 621   /* --- Answer the challenge if we need to --- */
 622
 623   if (ck && !kxc->r) {
 624     mp *r;
 625     if ((r = getreply(kx, c, ck)) == 0)
 626       goto bad;
 627     kxc->r = r;
 628   }
 629
 630   kxc_answer(kx, kxc);
 631
 632   /* --- Tidy up and go home --- */
 633
 634 tidy:
 635   mp_drop(c);
 636   mp_drop(ck);
 637   return (0);
 638
 639 bad:
 640   mp_drop(c);
 641   mp_drop(ck);
 642   return (-1);
 643 }
 644
 645 /* --- @resend@ --- *
 646  *
 647  * Arguments:   @keyexch *kx@ = pointer to key exchange context
 648  *
 649  * Returns:     ---
 650  *
 651  * Use:         Sends the next message for a key exchange.
 652  */
 653
 654 static void resend(keyexch *kx)
 655 {
 656   kxchal *kxc;
 657   buf bb;
 658   stats *st = p_stats(kx->p);
 659   buf *b;
 660
 661   switch (kx->s) {
 662     case KXS_CHAL:
 663       T( trace(T_KEYEXCH, "keyexch: sending prechallenge to `%s'",
 664                p_name(kx->p)); )
 665       b = p_txstart(kx->p, MSG_KEYEXCH | KX_PRECHAL);
 666       buf_putmp(b, kx->c);
 667       break;
 668     case KXS_COMMIT:
 669       T( trace(T_KEYEXCH, "keyexch: sending switch request to `%s'",
 670                p_name(kx->p)); )
 671       kxc = kx->r[0];
 672       b = p_txstart(kx->p, MSG_KEYEXCH | KX_SWITCH);
 673       buf_put(b, kx->hc, HASHSZ);
 674       buf_put(b, kxc->hc, HASHSZ);
 675       buf_init(&bb, buf_i, sizeof(buf_i));
 676       buf_putmp(&bb, kxc->r);
 677       buf_put(&bb, kxc->hswrq_out, HASHSZ);
 678       buf_flip(&bb);
 679       ks_encrypt(kxc->ks, MSG_KEYEXCH | KX_SWITCH, &bb, b);
 680       break;
 681     case KXS_SWITCH:
 682       T( trace(T_KEYEXCH, "keyexch: sending switch confirmation to `%s'",
 683                p_name(kx->p)); )
 684       kxc = kx->r[0];
 685       b = p_txstart(kx->p, MSG_KEYEXCH | KX_SWITCHOK);
 686       buf_init(&bb, buf_i, sizeof(buf_i));
 687       buf_put(&bb, kxc->hswok_out, HASHSZ);
 688       buf_flip(&bb);
 689       ks_encrypt(kxc->ks, MSG_KEYEXCH | KX_SWITCHOK, &bb, b);
 690       break;
 691     default:
 692       abort();
 693   }
 694
 695   if (BOK(b)) {
 696     st->n_kxout++;
 697     st->sz_kxout += BLEN(b);
 698     p_txend(kx->p);
 699   }
 700
 701   if (kx->s < KXS_SWITCH)
 702     settimer(kx, time(0) + T_RETRY);
 703 }
 704
 705 /* --- @matchreply@ --- *
 706  *
 707  * Arguments:   @keyexch *kx@ = pointer to key exchange context
 708  *              @unsigned ty@ = type of incoming message
 709  *              @const octet *hc_in@ = a hash of his challenge
 710  *              @const octet *hc_out@ = a hash of my challenge (cookie)
 711  *              @mp *ck@ = his expected-reply hash (optional)
 712  *              @buf *b@ = encrypted remainder of the packet
 713  *
 714  * Returns:     A pointer to the challenge block if OK, or null on failure.
 715  *
 716  * Use:         Checks a reply or switch packet, ensuring that its contents
 717  *              are sensible and correct.  If they are, @*b@ is set to point
 718  *              to the remainder of the encrypted data, and the correct
 719  *              challenge is returned.
 720  */
 721
 722 static kxchal *matchreply(keyexch *kx, unsigned ty, const octet *hc_in,
 723                           const octet *hc_out, mp *ck, buf *b)
 724 {
 725   kxchal *kxc;
 726   buf bb;
 727   mp *r = 0;
 728
 729   /* --- Check the plaintext portions of the data --- */
 730
 731   IF_TRACING(T_KEYEXCH, IF_TRACING(T_CRYPTO, {
 732     trace_block(T_CRYPTO, "crypto: challenge", hc_in, HASHSZ);
 733     trace_block(T_CRYPTO, "crypto: cookie", hc_out, HASHSZ);
 734     if (ck) trace(T_CRYPTO, "crypto: check value = %s", mpstr(ck));
 735   }))
 736   if (memcmp(hc_out, kx->hc, HASHSZ) != 0) {
 737     a_warn("incorrect cookie from `%s'", p_name(kx->p));
 738     goto bad;
 739   }
 740   if ((kxc = kxc_byhc(kx, hc_in)) == 0) {
 741     a_warn("received reply for unknown challenge from `%s'", p_name(kx->p));
 742     goto bad;
 743   }
 744
 745   /* --- Maybe compute a reply for the challenge --- */
 746
 747   if (!kxc->r) {
 748     if (!ck) {
 749       a_warn("unexpected switch request from `%s'", p_name(kx->p));
 750       goto bad;
 751     }
 752     if ((r = getreply(kx, kxc->c, ck)) == 0)
 753       goto bad;
 754     kxc->r = r;
 755     r = 0;
 756   }
 757
 758   /* --- Decrypt the rest of the packet --- */
 759
 760   buf_init(&bb, buf_o, sizeof(buf_o));
 761   if (ks_decrypt(kxc->ks, ty, b, &bb)) {
 762     a_warn("failed to decrypt reply from `%s'", p_name(kx->p));
 763     goto bad;
 764   }
 765   buf_init(b, BBASE(&bb), BLEN(&bb));
 766   if ((r = buf_getmp(b)) == 0) {
 767     a_warn("invalid reply packet from `%s'", p_name(kx->p));
 768     goto bad;
 769   }
 770   IF_TRACING(T_KEYEXCH, IF_TRACING(T_CRYPTO, {
 771     trace(T_CRYPTO, "crypto: reply = %s", mpstr(r));
 772   }))
 773   if (!mp_eq(r, kx->rx)) {
 774     a_warn("incorrect reply from `%s'", p_name(kx->p));
 775     goto bad;
 776   }
 777
 778   /* --- Done --- */
 779
 780   mp_drop(r);
 781   return (kxc);
 782
 783 bad:
 784   mp_drop(r);
 785   return (0);
 786 }
 787
 788 /* --- @commit@ --- *
 789  *
 790  * Arguments:   @keyexch *kx@ = pointer to key exchange context
 791  *              @kxchal *kxc@ = pointer to challenge to commit to
 792  *
 793  * Returns:     ---
 794  *
 795  * Use:         Commits to a particular challenge as being the `right' one,
 796  *              since a reply has arrived for it.
 797  */
 798
 799 static void commit(keyexch *kx, kxchal *kxc)
 800 {
 801   unsigned i;
 802
 803   for (i = 0; i < kx->nr; i++) {
 804     if (kx->r[i] != kxc)
 805       kxc_destroy(kx->r[i]);
 806   }
 807   kx->r[0] = kxc;
 808   kx->nr = 1;
 809   kxc_stoptimer(kxc);
 810   ksl_link(kx->ks, kxc->ks);
 811 }
 812
 813 /* --- @doreply@ --- *
 814  *
 815  * Arguments:   @keyexch *kx@ = pointer to key exchange context
 816  *              @buf *b@ = buffer containing packet
 817  *
 818  * Returns:     Zero if OK, nonzero if the packet was rejected.
 819  *
 820  * Use:         Handles a reply packet.  This doesn't handle the various
 821  *              switch packets: they're rather too different.
 822  */
 823
 824 static int doreply(keyexch *kx, buf *b)
 825 {
 826   const octet *hc_in, *hc_out;
 827   mp *ck = 0;
 828   kxchal *kxc;
 829
 830   if (kx->s != KXS_CHAL && kx->s != KXS_COMMIT) {
 831     a_warn("unexpected reply from `%s'", p_name(kx->p));
 832     goto bad;
 833   }
 834   if ((hc_in = buf_get(b, HASHSZ)) == 0 ||
 835       (hc_out = buf_get(b, HASHSZ)) == 0 ||
 836       (ck = buf_getmp(b)) == 0) {
 837     a_warn("invalid reply packet from `%s'", p_name(kx->p));
 838     goto bad;
 839   }
 840   if ((kxc = matchreply(kx, MSG_KEYEXCH | KX_REPLY,
 841                         hc_in, hc_out, ck, b)) == 0)
 842     goto bad;
 843   if (BLEFT(b)) {
 844     a_warn("invalid reply packet from `%s'", p_name(kx->p));
 845     goto bad;
 846   }
 847   if (kx->s == KXS_CHAL) {
 848     commit(kx, kxc);
 849     kx->s = KXS_COMMIT;
 850   }
 851   resend(kx);
 852   return (0);
 853
 854 bad:
 855   mp_drop(ck);
 856   return (-1);
 857 }
 858
 859 /* --- @doswitch@ --- *
 860  *
 861  * Arguments:   @keyexch *kx@ = pointer to key exchange block
 862  *              @buf *b@ = pointer to buffer containing packet
 863  *
 864  * Returns:     Zero if OK, nonzero if the packet was rejected.
 865  *
 866  * Use:         Handles a reply with a switch request bolted onto it.
 867  */
 868
 869 static int doswitch(keyexch *kx, buf *b)
 870 {
 871   const octet *hc_in, *hc_out, *hswrq;
 872   kxchal *kxc;
 873
 874   if ((hc_in = buf_get(b, HASHSZ)) == 0 ||
 875       (hc_out = buf_get(b, HASHSZ)) == 0) {
 876     a_warn("invalid switch request from `%s'", p_name(kx->p));
 877     goto bad;
 878   }
 879   if ((kxc = matchreply(kx, MSG_KEYEXCH | KX_SWITCH,
 880                         hc_in, hc_out, 0, b)) == 0)
 881     goto bad;
 882   if ((hswrq = buf_get(b, HASHSZ)) == 0 || BLEFT(b)) {
 883     a_warn("invalid switch request from `%s'", p_name(kx->p));
 884     goto bad;
 885   }
 886   IF_TRACING(T_KEYEXCH, {
 887     trace_block(T_CRYPTO, "crypto: switch request hash", hswrq, HASHSZ);
 888   })
 889   if (memcmp(hswrq, kxc->hswrq_in, HASHSZ) != 0) {
 890     a_warn("incorrect switch request hash from `%s'", p_name(kx->p));
 891     goto bad;
 892   }
 893   switch (kx->s) {
 894     case KXS_CHAL:
 895       commit(kx, kxc);
 896     case KXS_COMMIT:
 897       ks_activate(kxc->ks);
 898       settimer(kx, ks_tregen(kxc->ks));
 899       kx->s = KXS_SWITCH;
 900       break;
 901   }
 902   resend(kx);
 903   return (0);
 904
 905 bad:
 906   return (-1);
 907 }
 908
 909 /* --- @doswitchok@ --- *
 910  *
 911  * Arguments:   @keyexch *kx@ = pointer to key exchange block
 912  *              @buf *b@ = pointer to buffer containing packet
 913  *
 914  * Returns:     Zero if OK, nonzero if the packet was rejected.
 915  *
 916  * Use:         Handles a reply with a switch request bolted onto it.
 917  */
 918
 919 static int doswitchok(keyexch *kx, buf *b)
 920 {
 921   const octet *hswok;
 922   kxchal *kxc;
 923   buf bb;
 924
 925   if (kx->s < KXS_COMMIT) {
 926     a_warn("unexpected switch confirmation from `%s'", p_name(kx->p));
 927     goto bad;
 928   }
 929   kxc = kx->r[0];
 930   buf_init(&bb, buf_o, sizeof(buf_o));
 931   if (ks_decrypt(kxc->ks, MSG_KEYEXCH | KX_SWITCHOK, b, &bb)) {
 932     a_warn("failed to decrypt switch confirmation from `%s'", p_name(kx->p));
 933     goto bad;
 934   }
 935   buf_init(b, BBASE(&bb), BLEN(&bb));
 936   if ((hswok = buf_get(b, HASHSZ)) == 0 || BLEFT(b)) {
 937     a_warn("invalid switch confirmation from `%s'", p_name(kx->p));
 938     goto bad;
 939   }
 940   IF_TRACING(T_KEYEXCH, {
 941     trace_block(T_CRYPTO, "crypto: switch confirmation hash", hswok, HASHSZ);
 942   })
 943   if (memcmp(hswok, kxc->hswok_in, HASHSZ) != 0) {
 944     a_warn("incorrect switch confirmation hash from `%s'", p_name(kx->p));
 945     goto bad;
 946   }
 947   if (kx->s < KXS_SWITCH) {
 948     ks_activate(kxc->ks);
 949     settimer(kx, ks_tregen(kxc->ks));
 950     kx->s = KXS_SWITCH;
 951   }
 952   return (0);
 953
 954 bad:
 955   return (-1);
 956 }
 957
 958 /*----- Main code ---------------------------------------------------------*/
 959
 960 /* --- @stop@ --- *
 961  *
 962  * Arguments:   @keyexch *kx@ = pointer to key exchange context
 963  *
 964  * Returns:     ---
 965  *
 966  * Use:         Stops a key exchange dead in its tracks.  Throws away all of
 967  *              the context information.  The context is left in an
 968  *              inconsistent state.  The only functions which understand this
 969  *              state are @kx_free@ and @kx_init@ (which cause it internally
 970  *              it), and @start@ (which expects it to be the prevailing
 971  *              state).
 972  */
 973
 974 static void stop(keyexch *kx)
 975 {
 976   unsigned i;
 977
 978   if (kx->f & KXF_DEAD)
 979     return;
 980
 981   if (kx->f & KXF_TIMER)
 982     sel_rmtimer(&kx->t);
 983   for (i = 0; i < kx->nr; i++)
 984     kxc_destroy(kx->r[i]);
 985   mp_drop(kx->alpha);
 986   mp_drop(kx->c);
 987   mp_drop(kx->rx);
 988   kx->t_valid = 0;
 989   kx->f |= KXF_DEAD;
 990   kx->f &= ~KXF_TIMER;
 991 }
 992
 993 /* --- @start@ --- *
 994  *
 995  * Arguments:   @keyexch *kx@ = pointer to key exchange context
 996  *              @time_t now@ = the current time
 997  *
 998  * Returns:     ---
 999  *
1000  * Use:         Starts a new key exchange with the peer.  The context must be
1001  *              in the bizarre state left by @stop@ or @kx_init@.
1002  */
1003
1004 static void start(keyexch *kx, time_t now)
1005 {
1006   HASH_CTX h;
1007
1008   assert(kx->f & KXF_DEAD);
1009
1010   kx->f &= ~KXF_DEAD;
1011   kx->nr = 0;
1012   kx->alpha = mprand_range(MP_NEW, kpriv.dp.q, &rand_global, 0);
1013   kx->c = mpmont_exp(&mg, MP_NEW, kpriv.dp.g, kx->alpha);
1014   kx->rx = mpmont_exp(&mg, MP_NEW, kx->kpub.y, kx->alpha);
1015   kx->s = KXS_CHAL;
1016   kx->t_valid = now + T_VALID;
1017
1018   HASH_INIT(&h);
1019   HASH_STRING(&h, "tripe-cookie");
1020   hashmp(&h, kx->c);
1021   HASH_DONE(&h, kx->hc);
1022
1023   IF_TRACING(T_KEYEXCH, {
1024     trace(T_KEYEXCH, "keyexch: creating new challenge");
1025     IF_TRACING(T_CRYPTO, {
1026       trace(T_CRYPTO, "crypto: secret = %s", mpstr(kx->alpha));
1027       trace(T_CRYPTO, "crypto: challenge = %s", mpstr(kx->c));
1028       trace(T_CRYPTO, "crypto: expected response = %s", mpstr(kx->rx));
1029       trace_block(T_CRYPTO, "crypto: challenge cookie", kx->hc, HASHSZ);
1030     })
1031   })
1032 }
1033
1034 /* --- @checkpub@ --- *
1035  *
1036  * Arguments:   @keyexch *kx@ = pointer to key exchange context
1037  *
1038  * Returns:     Zero if OK, nonzero if the peer's public key has expired.
1039  *
1040  * Use:         Deactivates the key-exchange until the peer acquires a new
1041  *              public key.
1042  */
1043
1044 static int checkpub(keyexch *kx)
1045 {
1046   time_t now;
1047   if (kx->f & KXF_DEAD)
1048     return (-1);
1049   now = time(0);
1050   if (KEY_EXPIRED(now, kx->texp_kpub)) {
1051     stop(kx);
1052     a_warn("public key for `%s' has expired", p_name(kx->p));
1053     dh_pubfree(&kx->kpub);
1054     kx->f &= ~KXF_PUBKEY;
1055     return (-1);
1056   }
1057   return (0);
1058 }
1059
1060 /* --- @kx_start@ --- *
1061  *
1062  * Arguments:   @keyexch *kx@ = pointer to key exchange context
1063  *
1064  * Returns:     ---
1065  *
1066  * Use:         Stimulates a key exchange.  If a key exchage is in progress,
1067  *              a new challenge is sent (unless the quiet timer forbids
1068  *              this); if no exchange is in progress, one is commenced.
1069  */
1070
1071 void kx_start(keyexch *kx)
1072 {
1073   time_t now = time(0);
1074
1075   if (checkpub(kx))
1076     return;
1077   if (!ISVALID(kx, now)) {
1078     stop(kx);
1079     start(kx, now);
1080   }
1081   resend(kx);
1082 }
1083
1084 /* --- @kx_message@ --- *
1085  *
1086  * Arguments:   @keyexch *kx@ = pointer to key exchange context
1087  *              @unsigned msg@ = the message code
1088  *              @buf *b@ = pointer to buffer containing the packet
1089  *
1090  * Returns:     ---
1091  *
1092  * Use:         Reads a packet containing key exchange messages and handles
1093  *              it.
1094  */
1095
1096 void kx_message(keyexch *kx, unsigned msg, buf *b)
1097 {
1098   time_t now = time(0);
1099   stats *st = p_stats(kx->p);
1100   size_t sz = BSZ(b);
1101   int rc;
1102
1103 #ifndef NTRACE
1104   static const char *const pkname[] = {
1105     "prechallenge", "cookie", "challenge",
1106     "reply", "switch request", "switch confirmation"
1107   };
1108 #endif
1109
1110   if (checkpub(kx))
1111     return;
1112
1113   if (!ISVALID(kx, now)) {
1114     stop(kx);
1115     start(kx, now);
1116   }
1117
1118   T( trace(T_KEYEXCH, "keyexch: processing %s packet from `%s'",
1119            msg < KX_NMSG ? pkname[msg] : "unknown", p_name(kx->p)); )
1120
1121   switch (msg) {
1122     case KX_PRECHAL:
1123     case KX_COOKIE:
1124     case KX_CHAL:
1125       rc = dochallenge(kx, msg, b);
1126       break;
1127     case KX_REPLY:
1128       rc = doreply(kx, b);
1129       break;
1130     case KX_SWITCH:
1131       rc = doswitch(kx, b);
1132       break;
1133     case KX_SWITCHOK:
1134       rc = doswitchok(kx, b);
1135       break;
1136     default:
1137       a_warn("unexpected key exchange message type %u from `%p'",
1138              p_name(kx->p));
1139       rc = -1;
1140       break;
1141   }
1142
1143   if (rc)
1144     st->n_reject++;
1145   else {
1146     st->n_kxin++;
1147     st->sz_kxin += sz;
1148   }
1149 }
1150
1151 /* --- @kx_free@ --- *
1152  *
1153  * Arguments:   @keyexch *kx@ = pointer to key exchange context
1154  *
1155  * Returns:     ---
1156  *
1157  * Use:         Frees everything in a key exchange context.
1158  */
1159
1160 void kx_free(keyexch *kx)
1161 {
1162   stop(kx);
1163   if (kx->f & KXF_PUBKEY)
1164     dh_pubfree(&kx->kpub);
1165 }
1166
1167 /* --- @kx_newkeys@ --- *
1168  *
1169  * Arguments:   @keyexch *kx@ = pointer to key exchange context
1170  *
1171  * Returns:     ---
1172  *
1173  * Use:         Informs the key exchange module that its keys may have
1174  *              changed.  If fetching the new keys fails, the peer will be
1175  *              destroyed, we log messages and struggle along with the old
1176  *              keys.
1177  */
1178
1179 void kx_newkeys(keyexch *kx)
1180 {
1181   dh_pub dp;
1182
1183   if (km_getpubkey(p_name(kx->p), &dp, &kx->texp_kpub))
1184     return;
1185   if (kx->f & KXF_PUBKEY)
1186     dh_pubfree(&kx->kpub);
1187   kx->kpub = dp;
1188   kx->f |= KXF_PUBKEY;
1189   if ((kx->f & KXF_DEAD) || kx->s != KXS_SWITCH) {
1190     T( trace(T_KEYEXCH, "keyexch: restarting key negotiation with `%s'",
1191              p_name(kx->p)); )
1192     stop(kx);
1193     start(kx, time(0));
1194     resend(kx);
1195   }
1196 }
1197
1198 /* --- @kx_init@ --- *
1199  *
1200  * Arguments:   @keyexch *kx@ = pointer to key exchange context
1201  *              @peer *p@ = pointer to peer context
1202  *              @keyset **ks@ = pointer to keyset list
1203  *
1204  * Returns:     Zero if OK, nonzero if it failed.
1205  *
1206  * Use:         Initializes a key exchange module.  The module currently
1207  *              contains no keys, and will attempt to initiate a key
1208  *              exchange.
1209  */
1210
1211 int kx_init(keyexch *kx, peer *p, keyset **ks)
1212 {
1213   kx->ks = ks;
1214   kx->p = p;
1215   if (km_getpubkey(p_name(p), &kx->kpub, &kx->texp_kpub))
1216     return (-1);
1217   kx->f = KXF_DEAD | KXF_PUBKEY;
1218   start(kx, time(0));
1219   resend(kx);
1220   return (0);
1221 }
1222
1223 /*----- That's all, folks -------------------------------------------------*/