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

   1 /* -*-c-*-
   2  *
   3  * $Id: keyset.c,v 1.7 2003/05/17 11:00:47 mdw Exp $
   4  *
   5  * Handling of symmetric keysets
   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: keyset.c,v $
  32  * Revision 1.7  2003/05/17 11:00:47  mdw
  33  * Don't make scary messages just because one key didn't work on a message:
  34  * only be frightened if they all fail.  Set initial keyset refcount
  35  * correctly.
  36  *
  37  * Revision 1.6  2003/04/06 10:26:35  mdw
  38  * Report peer name on decrypt errors.
  39  *
  40  * Revision 1.5  2001/06/19 22:07:43  mdw
  41  * Change the encrypted packet format to be non-malleable.
  42  *
  43  * Revision 1.4  2001/06/16 14:06:40  mdw
  44  * Quantify collision probabilities for the stated data volume bounds.
  45  *
  46  * Revision 1.3  2001/02/16 21:39:55  mdw
  47  * Major overhaul.  Separate functions for manipulating keysets from
  48  * functions for manipulating keyset lists.  Introduce a concept of
  49  * listening-only keys.
  50  *
  51  * Revision 1.2  2001/02/05 19:53:23  mdw
  52  * Add sequence number protection.
  53  *
  54  * Revision 1.1  2001/02/03 20:26:37  mdw
  55  * Initial checkin.
  56  *
  57  */
  58
  59 /*----- Header files ------------------------------------------------------*/
  60
  61 #include "tripe.h"
  62
  63 /*----- Tunable parameters ------------------------------------------------*/
  64
  65 /* --- Note on size limits --- *
  66  *
  67  * For a 64-bit block cipher (e.g., Blowfish), the probability of a collision
  68  * occurring after 32 MB is less than %$2^{-21}$%, and the probability of a
  69  * collision occurring after 64 MB is less than %$2^{-19}$%.
  70  */
  71
  72 #define T_EXP MIN(60)                   /* Expiry time for a key */
  73 #define T_REGEN MIN(45)                 /* Regeneration time for a key */
  74 #define SZ_EXP MEG(64)                  /* Expiry data size for a key */
  75 #define SZ_REGEN MEG(32)                /* Data size threshold for regen */
  76
  77 /*----- Handy macros ------------------------------------------------------*/
  78
  79 #define KEYOK(ks, now) ((ks)->sz_exp > 0 && (ks)->t_exp > now)
  80
  81 /*----- Low-level packet encryption and decryption ------------------------*/
  82
  83 /* --- Encrypted data format --- *
  84  *
  85  * Let %$p_i$% be the %$i$%-th plaintext message.  We first compute
  86  *
  87  *   %$c_i = \mathcal{E}\textrm{-CBC}_{K_{\text{E}}}(p_i)$%
  88  *
  89  * as the CBC-ciphertext of %$p_i$%, and then
  90  *
  91  *   %$\sigma_i = \mathcal{T}_{K_{\text{M}}}(i, c_i)$%
  92  *
  93  * as a MAC on the %%\emph{ciphertext}%%.  The message sent is then the pair
  94  * %$(\sigma_i, c_i)$%.  This construction is provably secure in the NM-CCA
  95  * sense (assuming that the cipher is IND-CPA, and the MAC is SUF-CMA)
  96  * [Bellare and Namprempre].
  97  *
  98  * This also ensures that, assuming the key is good, we have a secure channel
  99  * [Krawczyk].  Actually, [Krawczyk] shows that, if the cipher is either a
 100  * simple stream cipher or a block cipher in CBC mode, we can use the MAC-
 101  * then-encrypt scheme and still have a secure channel.  However, I like the
 102  * NM-CCA guarantee from [Bellare and Namprempre].  I'm less worried about
 103  * the Horton Principle [Wagner and Schneier].
 104  */
 105
 106 /* --- @doencrypt@ --- *
 107  *
 108  * Arguments:   @keyset *ks@ = pointer to keyset to use
 109  *              @buf *b@ = pointer to an input buffer
 110  *              @buf *bb@ = pointer to an output buffer
 111  *
 112  * Returns:     Zero if OK, nonzero if a new key is required.
 113  *
 114  * Use:         Encrypts a message with the given key.  We assume that the
 115  *              keyset is OK to use.
 116  */
 117
 118 static int doencrypt(keyset *ks, buf *b, buf *bb)
 119 {
 120   ghash *h;
 121   gcipher *c;
 122   const octet *p = BCUR(b);
 123   size_t sz = BLEFT(b);
 124   octet *qmac, *qseq, *qiv, *qpk;
 125   uint32 oseq;
 126   size_t osz, nsz;
 127   int rc = 0;
 128
 129   /* --- Allocate the required buffer space --- */
 130
 131   c = ks->cout;
 132   if (buf_ensure(bb, MACSZ + SEQSZ + IVSZ + sz))
 133     return (0); /* Caution! */
 134   qmac = BCUR(bb); qseq = qmac + MACSZ; qiv = qseq + SEQSZ; qpk = qiv + IVSZ;
 135   BSTEP(bb, MACSZ + SEQSZ + IVSZ + sz);
 136
 137   /* --- Encrypt the packet --- */
 138
 139   oseq = ks->oseq++; STORE32(qseq, oseq);
 140   rand_get(RAND_GLOBAL, qiv, IVSZ);
 141   c->ops->setiv(c, qiv);
 142   c->ops->encrypt(c, p, qpk, sz);
 143   IF_TRACING(T_KEYSET, {
 144     trace(T_KEYSET, "keyset: encrypting packet %lu using keyset %u",
 145           (unsigned long)oseq, ks->seq);
 146     trace_block(T_CRYPTO, "crypto: encrypted packet", qpk, sz);
 147   })
 148
 149   /* --- Now compute the MAC --- */
 150
 151   h = ks->mout->ops->init(ks->mout);
 152   h->ops->hash(h, qseq, SEQSZ + IVSZ + sz);
 153   memcpy(qmac, h->ops->done(h, 0), MACSZ);
 154   h->ops->destroy(h);
 155   IF_TRACING(T_KEYSET, {
 156     trace_block(T_CRYPTO, "crypto: computed MAC", qmac, MACSZ);
 157   })
 158
 159   /* --- Deduct the packet size from the key's data life --- */
 160
 161   osz = ks->sz_exp;
 162   if (osz > sz)
 163     nsz = osz - sz;
 164   else
 165     nsz = 0;
 166   if (osz >= SZ_REGEN && nsz < SZ_REGEN) {
 167     T( trace(T_KEYSET, "keyset: keyset %u data regen limit exceeded -- "
 168              "forcing exchange", ks->seq); )
 169     rc = -1;
 170   }
 171   ks->sz_exp = nsz;
 172   return (rc);
 173 }
 174
 175 /* --- @dodecrypt@ --- *
 176  *
 177  * Arguments:   @keyset *ks@ = pointer to keyset to use
 178  *              @buf *b@ = pointer to an input buffer
 179  *              @buf *bb@ = pointer to an output buffer
 180  *              @uint32 *seq@ = where to store the sequence number
 181  *
 182  * Returns:     Zero if OK, nonzero if it failed.
 183  *
 184  * Use:         Attempts to decrypt a message with the given key.  No other
 185  *              checking (e.g., sequence number checks) is performed.  We
 186  *              assume that the keyset is OK to use, and that there is
 187  *              sufficient output buffer space reserved.  If the decryption
 188  *              is successful, the buffer pointer is moved past the decrypted
 189  *              packet, and the packet's sequence number is stored in @*seq@.
 190  */
 191
 192 static int dodecrypt(keyset *ks, buf *b, buf *bb, uint32 *seq)
 193 {
 194   const octet *pmac, *piv, *pseq, *ppk;
 195   size_t psz = BLEFT(b);
 196   size_t sz;
 197   octet *q = BCUR(bb);
 198   ghash *h;
 199   gcipher *c = ks->cin;
 200   size_t ivsz = c->ops->c->blksz;
 201   octet *mac;
 202   int eq;
 203
 204   /* --- Break up the packet into its components --- */
 205
 206   if (psz < ivsz + 4) {
 207     T( trace(T_KEYSET, "keyset: block too small for keyset %u", ks->seq); )
 208     return (-1);
 209   }
 210   sz = psz - IVSZ - SEQSZ - MACSZ;
 211   pmac = BCUR(b); pseq = pmac + MACSZ; piv = pseq + SEQSZ; ppk = piv + IVSZ;
 212
 213   /* --- Verify the MAC on the packet --- */
 214
 215   h = ks->min->ops->init(ks->min);
 216   h->ops->hash(h, pseq, SEQSZ + IVSZ + sz);
 217   mac = h->ops->done(h, 0);
 218   eq = !memcmp(mac, pmac, MACSZ);
 219   IF_TRACING(T_KEYSET, {
 220     trace(T_KEYSET, "keyset: decrypting using keyset %u", ks->seq);
 221     trace_block(T_CRYPTO, "crypto: computed MAC", mac, MACSZ);
 222   })
 223   h->ops->destroy(h);
 224   if (!eq) {
 225     IF_TRACING(T_KEYSET, {
 226       trace(T_KEYSET, "keyset: incorrect MAC: decryption failed");
 227       trace_block(T_CRYPTO, "crypto: expected MAC", pmac, MACSZ);
 228     })
 229     return (-1);
 230   }
 231
 232   /* --- Decrypt the packet --- */
 233
 234   c->ops->setiv(c, piv);
 235   c->ops->decrypt(c, ppk, q, sz);
 236   if (seq)
 237     *seq = LOAD32(pseq);
 238   IF_TRACING(T_KEYSET, {
 239     trace(T_KEYSET, "keyset: decrypted OK (sequence = %lu)",
 240           (unsigned long)LOAD32(pseq));
 241     trace_block(T_CRYPTO, "crypto: decrypted packet", q, sz);
 242   })
 243   BSTEP(bb, sz);
 244   return (0);
 245 }
 246
 247 /* --- @dosequence@ --- *
 248  *
 249  * Arguments:   @keyset *ks@ = pointer to a keyset
 250  *              @uint32 seq@ = a sequence number from a packet
 251  *
 252  * Returns:     Zero if the sequence number is OK, nonzero if it's not.
 253  *
 254  * Use:         Checks a sequence number.  The data in the keyset which keeps
 255  *              track of valid sequence numbers is updated if the sequence
 256  *              number given is good.  It's assumed that the sequence number
 257  *              has already been checked for authenticity.
 258  */
 259
 260 static int dosequence(keyset *ks, uint32 seq)
 261 {
 262   uint32 seqbit;
 263   uint32 n;
 264
 265   if (seq < ks->iseq) {
 266     a_warn("received packet has old sequence number (possible replay)");
 267     return (-1);
 268   }
 269   if (seq >= ks->iseq + KS_SEQWINSZ) {
 270     n = seq - (ks->iseq + KS_SEQWINSZ - 1);
 271     if (n < KS_SEQWINSZ)
 272       ks->iwin >>= n;
 273     else
 274       ks->iwin = 0;
 275     ks->iseq += n;
 276   }
 277   seqbit = 1 << (seq - ks->iseq);
 278   if (ks->iwin & seqbit) {
 279     a_warn("received packet repeats old sequence number");
 280     return (-1);
 281   }
 282   ks->iwin |= seqbit;
 283   return (0);
 284 }
 285
 286 /*----- Operations on a single keyset -------------------------------------*/
 287
 288 /* --- @ks_drop@ --- *
 289  *
 290  * Arguments:   @keyset *ks@ = pointer to a keyset
 291  *
 292  * Returns:     ---
 293  *
 294  * Use:         Decrements a keyset's reference counter.  If the counter hits
 295  *              zero, the keyset is freed.
 296  */
 297
 298 void ks_drop(keyset *ks)
 299 {
 300   if (--ks->ref)
 301     return;
 302   ks->cin->ops->destroy(ks->cin);
 303   ks->cout->ops->destroy(ks->cout);
 304   ks->min->ops->destroy(ks->min);
 305   ks->mout->ops->destroy(ks->mout);
 306   DESTROY(ks);
 307 }
 308
 309 /* --- @ks_gen@ --- *
 310  *
 311  * Arguments:   @const void *k@ = pointer to key material
 312  *              @size_t x, y, z@ = offsets into key material (see below)
 313  *              @peer *p@ = pointer to peer information
 314  *
 315  * Returns:     A pointer to the new keyset.
 316  *
 317  * Use:         Derives a new keyset from the given key material.  The
 318  *              offsets @x@, @y@ and @z@ separate the key material into three
 319  *              parts.  Between the @k@ and @k + x@ is `my' contribution to
 320  *              the key material; between @k + x@ and @k + y@ is `your'
 321  *              contribution; and between @k + y@ and @k + z@ is a shared
 322  *              value we made together.  These are used to construct two
 323  *              pairs of symmetric keys.  Each pair consists of an encryption
 324  *              key and a message authentication key.  One pair is used for
 325  *              outgoing messages, the other for incoming messages.
 326  *
 327  *              The new key is marked so that it won't be selected for output
 328  *              by @ksl_encrypt@.  You can still encrypt data with it by
 329  *              calling @ks_encrypt@ directly.
 330  */
 331
 332 keyset *ks_gen(const void *k, size_t x, size_t y, size_t z, peer *p)
 333 {
 334   HASH_CTX h;
 335   octet buf[HASHSZ];
 336   keyset *ks = CREATE(keyset);
 337   time_t now = time(0);
 338   const octet *pp = k;
 339   T( static unsigned seq = 0; )
 340
 341   T( trace(T_KEYSET, "keyset: adding new keyset %u", seq); )
 342
 343   /* --- Construct the various keys --- *
 344    *
 345    * This is done with macros, because it's quite tedious.
 346    */
 347
 348 #define MINE HASH(&h, pp, x)
 349 #define YOURS HASH(&h, pp + x, y - x)
 350 #define OURS HASH(&h, pp + y, z - y)
 351
 352 #define IN MINE; YOURS; OURS
 353 #define OUT YOURS; MINE; OURS
 354 #define STR_IN "incoming"
 355 #define STR_OUT "outgoing"
 356
 357 #define GETHASH(str, dir) do {                                          \
 358   HASH_INIT(&h);                                                        \
 359   HASH_STRING(&h, "tripe-" str);                                        \
 360   dir;                                                                  \
 361   HASH_DONE(&h, buf);                                                   \
 362   IF_TRACING(T_KEYSET, {                                                \
 363     trace_block(T_CRYPTO, "crypto: " STR_##dir " key " str,             \
 364                 buf, sizeof(buf));                                      \
 365   })                                                                    \
 366 } while (0)
 367
 368   GETHASH("encryption", IN); ks->cin = CIPHER->init(buf, sizeof(buf));
 369   GETHASH("integrity", IN); ks->min = MAC->key(buf, sizeof(buf));
 370   GETHASH("encryption", OUT); ks->cout = CIPHER->init(buf, sizeof(buf));
 371   GETHASH("integrity", OUT); ks->mout = MAC->key(buf, sizeof(buf));
 372
 373 #undef MINE
 374 #undef YOURS
 375 #undef OURS
 376 #undef IN
 377 #undef OUT
 378 #undef STR_IN
 379 #undef STR_OUT
 380 #undef GETHASH
 381
 382   T( ks->seq = seq++; )
 383   ks->ref = 1;
 384   ks->t_exp = now + T_EXP;
 385   ks->sz_exp = SZ_EXP;
 386   ks->oseq = ks->iseq = 0;
 387   ks->iwin = 0;
 388   ks->next = 0;
 389   ks->p = p;
 390   ks->f = KSF_LISTEN;
 391   BURN(buf);
 392   return (ks);
 393 }
 394
 395 /* --- @ks_tregen@ --- *
 396  *
 397  * Arguments:   @keyset *ks@ = pointer to a keyset
 398  *
 399  * Returns:     The time at which moves ought to be made to replace this key.
 400  */
 401
 402 time_t ks_tregen(keyset *ks) { return (ks->t_exp - T_EXP + T_REGEN); }
 403
 404 /* --- @ks_activate@ --- *
 405  *
 406  * Arguments:   @keyset *ks@ = pointer to a keyset
 407  *
 408  * Returns:     ---
 409  *
 410  * Use:         Activates a keyset, so that it can be used for encrypting
 411  *              outgoing messages.
 412  */
 413
 414 void ks_activate(keyset *ks)
 415 {
 416   if (ks->f & KSF_LISTEN) {
 417     T( trace(T_KEYSET, "keyset: activating keyset %u", ks->seq); )
 418     ks->f &= ~KSF_LISTEN;
 419   }
 420 }
 421
 422 /* --- @ks_encrypt@ --- *
 423  *
 424  * Arguments:   @keyset *ks@ = pointer to a keyset
 425  *              @buf *b@ = pointer to input buffer
 426  *              @buf *bb@ = pointer to output buffer
 427  *
 428  * Returns:     Zero if OK, nonzero if the key needs replacing.  If the
 429  *              encryption failed, the output buffer is broken and zero is
 430  *              returned.
 431  *
 432  * Use:         Encrypts a block of data using the key.  Note that the `key
 433  *              ought to be replaced' notification is only ever given once
 434  *              for each key.  Also note that this call forces a keyset to be
 435  *              used even if it's marked as not for data output.
 436  */
 437
 438 int ks_encrypt(keyset *ks, buf *b, buf *bb)
 439 {
 440   time_t now = time(0);
 441
 442   if (!KEYOK(ks, now)) {
 443     buf_break(bb);
 444     return (0);
 445   }
 446   return (doencrypt(ks, b, bb));
 447 }
 448
 449 /* --- @ks_decrypt@ --- *
 450  *
 451  * Arguments:   @keyset *ks@ = pointer to a keyset
 452  *              @buf *b@ = pointer to an input buffer
 453  *              @buf *bb@ = pointer to an output buffer
 454  *
 455  * Returns:     Zero on success, or nonzero if there was some problem.
 456  *
 457  * Use:         Attempts to decrypt a message using a given key.  Note that
 458  *              requesting decryption with a key directly won't clear a
 459  *              marking that it's not for encryption.
 460  */
 461
 462 int ks_decrypt(keyset *ks, buf *b, buf *bb)
 463 {
 464   time_t now = time(0);
 465   uint32 seq;
 466
 467   if (!KEYOK(ks, now) ||
 468       buf_ensure(bb, BLEN(b)) ||
 469       dodecrypt(ks, b, bb, &seq) ||
 470       dosequence(ks, seq))
 471     return (-1);
 472   return (0);
 473 }
 474
 475 /*----- Keyset list handling ----------------------------------------------*/
 476
 477 /* --- @ksl_free@ --- *
 478  *
 479  * Arguments:   @keyset **ksroot@ = pointer to keyset list head
 480  *
 481  * Returns:     ---
 482  *
 483  * Use:         Frees (releases references to) all of the keys in a keyset.
 484  */
 485
 486 void ksl_free(keyset **ksroot)
 487 {
 488   keyset *ks, *ksn;
 489   for (ks = *ksroot; ks; ks = ksn) {
 490     ksn = ks->next;
 491     ks->f &= ~KSF_LINK;
 492     ks_drop(ks);
 493   }
 494 }
 495
 496 /* --- @ksl_link@ --- *
 497  *
 498  * Arguments:   @keyset **ksroot@ = pointer to keyset list head
 499  *              @keyset *ks@ = pointer to a keyset
 500  *
 501  * Returns:     ---
 502  *
 503  * Use:         Links a keyset into a list.  A keyset can only be on one list
 504  *              at a time.  Bad things happen otherwise.
 505  */
 506
 507 void ksl_link(keyset **ksroot, keyset *ks)
 508 {
 509   assert(!(ks->f & KSF_LINK));
 510   ks->next = *ksroot;
 511   *ksroot = ks;
 512   ks->f |= KSF_LINK;
 513   ks->ref++;
 514 }
 515
 516 /* --- @ksl_prune@ --- *
 517  *
 518  * Arguments:   @keyset **ksroot@ = pointer to keyset list head
 519  *
 520  * Returns:     ---
 521  *
 522  * Use:         Prunes the keyset list by removing keys which mustn't be used
 523  *              any more.
 524  */
 525
 526 void ksl_prune(keyset **ksroot)
 527 {
 528   time_t now = time(0);
 529
 530   while (*ksroot) {
 531     keyset *ks = *ksroot;
 532
 533     if (ks->t_exp <= now) {
 534       T( trace(T_KEYSET, "keyset: expiring keyset %u (time limit reached)",
 535                ks->seq); )
 536       goto kill;
 537     } else if (ks->sz_exp == 0) {
 538       T( trace(T_KEYSET, "keyset: expiring keyset %u (data limit reached)",
 539                ks->seq); )
 540       goto kill;
 541     } else {
 542       ksroot = &ks->next;
 543       continue;
 544     }
 545
 546   kill:
 547     *ksroot = ks->next;
 548     ks->f &= ~KSF_LINK;
 549     ks_drop(ks);
 550   }
 551 }
 552
 553 /* --- @ksl_encrypt@ --- *
 554  *
 555  * Arguments:   @keyset **ksroot@ = pointer to keyset list head
 556  *              @buf *b@ = pointer to input buffer
 557  *              @buf *bb@ = pointer to output buffer
 558  *
 559  * Returns:     Nonzero if a new key is needed.
 560  *
 561  * Use:         Encrypts a packet.
 562  */
 563
 564 int ksl_encrypt(keyset **ksroot, buf *b, buf *bb)
 565 {
 566   time_t now = time(0);
 567   keyset *ks = *ksroot;
 568
 569   for (;;) {
 570     if (!ks) {
 571       T( trace(T_KEYSET, "keyset: no suitable keysets found"); )
 572       buf_break(bb);
 573       return (-1);
 574     }
 575     if (KEYOK(ks, now) && !(ks->f & KSF_LISTEN))
 576       break;
 577     ks = ks->next;
 578   }
 579
 580   return (doencrypt(ks, b, bb));
 581 }
 582
 583 /* --- @ksl_decrypt@ --- *
 584  *
 585  * Arguments:   @keyset **ksroot@ = pointer to keyset list head
 586  *              @buf *b@ = pointer to input buffer
 587  *              @buf *bb@ = pointer to output buffer
 588  *
 589  * Returns:     Nonzero if the packet couldn't be decrypted.
 590  *
 591  * Use:         Decrypts a packet.
 592  */
 593
 594 int ksl_decrypt(keyset **ksroot, buf *b, buf *bb)
 595 {
 596   time_t now = time(0);
 597   keyset *ks;
 598   uint32 seq;
 599
 600   if (buf_ensure(bb, BLEN(b)))
 601     return (-1);
 602
 603   for (ks = *ksroot; ks; ks = ks->next) {
 604     if (!KEYOK(ks, now))
 605       continue;
 606     if (!dodecrypt(ks, b, bb, &seq)) {
 607       if (ks->f & KSF_LISTEN) {
 608         T( trace(T_KEYSET, "keyset: implicitly activating keyset %u",
 609                  ks->seq); )
 610         ks->f &= ~KSF_LISTEN;
 611       }
 612       return (dosequence(ks, seq));
 613     }
 614   }
 615   T( trace(T_KEYSET, "keyset: no matching keys, or incorrect MAC"); )
 616   return (-1);
 617 }
 618
 619 /*----- That's all, folks -------------------------------------------------*/