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

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