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