Annotation of src/usr.bin/ssh/krl.c, Revision 1.19
1.1 djm 1: /*
2: * Copyright (c) 2012 Damien Miller <djm@mindrot.org>
3: *
4: * Permission to use, copy, modify, and distribute this software for any
5: * purpose with or without fee is hereby granted, provided that the above
6: * copyright notice and this permission notice appear in all copies.
7: *
8: * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
9: * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
10: * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
11: * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
12: * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
13: * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
14: * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
15: */
16:
1.19 ! djm 17: /* $OpenBSD: krl.c,v 1.18 2014/11/17 00:21:40 djm Exp $ */
1.2 djm 18:
1.1 djm 19: #include <sys/types.h>
20: #include <sys/param.h>
21: #include <sys/tree.h>
22: #include <sys/queue.h>
23:
24: #include <errno.h>
25: #include <fcntl.h>
26: #include <limits.h>
27: #include <string.h>
28: #include <time.h>
29: #include <unistd.h>
30:
31: #include "buffer.h"
32: #include "key.h"
33: #include "authfile.h"
34: #include "misc.h"
35: #include "log.h"
36: #include "xmalloc.h"
37:
38: #include "krl.h"
39:
40: /* #define DEBUG_KRL */
41: #ifdef DEBUG_KRL
42: # define KRL_DBG(x) debug3 x
43: #else
44: # define KRL_DBG(x)
45: #endif
46:
47: /*
48: * Trees of revoked serial numbers, key IDs and keys. This allows
49: * quick searching, querying and producing lists in canonical order.
50: */
51:
52: /* Tree of serial numbers. XXX make smarter: really need a real sparse bitmap */
53: struct revoked_serial {
54: u_int64_t lo, hi;
55: RB_ENTRY(revoked_serial) tree_entry;
56: };
57: static int serial_cmp(struct revoked_serial *a, struct revoked_serial *b);
58: RB_HEAD(revoked_serial_tree, revoked_serial);
59: RB_GENERATE_STATIC(revoked_serial_tree, revoked_serial, tree_entry, serial_cmp);
60:
61: /* Tree of key IDs */
62: struct revoked_key_id {
63: char *key_id;
64: RB_ENTRY(revoked_key_id) tree_entry;
65: };
66: static int key_id_cmp(struct revoked_key_id *a, struct revoked_key_id *b);
67: RB_HEAD(revoked_key_id_tree, revoked_key_id);
68: RB_GENERATE_STATIC(revoked_key_id_tree, revoked_key_id, tree_entry, key_id_cmp);
69:
70: /* Tree of blobs (used for keys and fingerprints) */
71: struct revoked_blob {
72: u_char *blob;
73: u_int len;
74: RB_ENTRY(revoked_blob) tree_entry;
75: };
76: static int blob_cmp(struct revoked_blob *a, struct revoked_blob *b);
77: RB_HEAD(revoked_blob_tree, revoked_blob);
78: RB_GENERATE_STATIC(revoked_blob_tree, revoked_blob, tree_entry, blob_cmp);
79:
80: /* Tracks revoked certs for a single CA */
81: struct revoked_certs {
82: Key *ca_key;
83: struct revoked_serial_tree revoked_serials;
84: struct revoked_key_id_tree revoked_key_ids;
85: TAILQ_ENTRY(revoked_certs) entry;
86: };
87: TAILQ_HEAD(revoked_certs_list, revoked_certs);
88:
89: struct ssh_krl {
90: u_int64_t krl_version;
91: u_int64_t generated_date;
92: u_int64_t flags;
93: char *comment;
94: struct revoked_blob_tree revoked_keys;
95: struct revoked_blob_tree revoked_sha1s;
96: struct revoked_certs_list revoked_certs;
97: };
98:
99: /* Return equal if a and b overlap */
100: static int
101: serial_cmp(struct revoked_serial *a, struct revoked_serial *b)
102: {
103: if (a->hi >= b->lo && a->lo <= b->hi)
104: return 0;
105: return a->lo < b->lo ? -1 : 1;
106: }
107:
108: static int
109: key_id_cmp(struct revoked_key_id *a, struct revoked_key_id *b)
110: {
111: return strcmp(a->key_id, b->key_id);
112: }
113:
114: static int
115: blob_cmp(struct revoked_blob *a, struct revoked_blob *b)
116: {
117: int r;
118:
119: if (a->len != b->len) {
120: if ((r = memcmp(a->blob, b->blob, MIN(a->len, b->len))) != 0)
121: return r;
122: return a->len > b->len ? 1 : -1;
123: } else
124: return memcmp(a->blob, b->blob, a->len);
125: }
126:
127: struct ssh_krl *
128: ssh_krl_init(void)
129: {
130: struct ssh_krl *krl;
131:
132: if ((krl = calloc(1, sizeof(*krl))) == NULL)
133: return NULL;
134: RB_INIT(&krl->revoked_keys);
135: RB_INIT(&krl->revoked_sha1s);
136: TAILQ_INIT(&krl->revoked_certs);
137: return krl;
138: }
139:
140: static void
141: revoked_certs_free(struct revoked_certs *rc)
142: {
143: struct revoked_serial *rs, *trs;
144: struct revoked_key_id *rki, *trki;
145:
146: RB_FOREACH_SAFE(rs, revoked_serial_tree, &rc->revoked_serials, trs) {
147: RB_REMOVE(revoked_serial_tree, &rc->revoked_serials, rs);
148: free(rs);
149: }
150: RB_FOREACH_SAFE(rki, revoked_key_id_tree, &rc->revoked_key_ids, trki) {
151: RB_REMOVE(revoked_key_id_tree, &rc->revoked_key_ids, rki);
152: free(rki->key_id);
153: free(rki);
154: }
155: if (rc->ca_key != NULL)
156: key_free(rc->ca_key);
157: }
158:
159: void
160: ssh_krl_free(struct ssh_krl *krl)
161: {
162: struct revoked_blob *rb, *trb;
163: struct revoked_certs *rc, *trc;
164:
165: if (krl == NULL)
166: return;
167:
168: free(krl->comment);
169: RB_FOREACH_SAFE(rb, revoked_blob_tree, &krl->revoked_keys, trb) {
170: RB_REMOVE(revoked_blob_tree, &krl->revoked_keys, rb);
171: free(rb->blob);
172: free(rb);
173: }
174: RB_FOREACH_SAFE(rb, revoked_blob_tree, &krl->revoked_sha1s, trb) {
175: RB_REMOVE(revoked_blob_tree, &krl->revoked_sha1s, rb);
176: free(rb->blob);
177: free(rb);
178: }
179: TAILQ_FOREACH_SAFE(rc, &krl->revoked_certs, entry, trc) {
180: TAILQ_REMOVE(&krl->revoked_certs, rc, entry);
181: revoked_certs_free(rc);
182: }
183: }
184:
185: void
186: ssh_krl_set_version(struct ssh_krl *krl, u_int64_t version)
187: {
188: krl->krl_version = version;
189: }
190:
191: void
192: ssh_krl_set_comment(struct ssh_krl *krl, const char *comment)
193: {
194: free(krl->comment);
195: if ((krl->comment = strdup(comment)) == NULL)
196: fatal("%s: strdup", __func__);
197: }
198:
199: /*
200: * Find the revoked_certs struct for a CA key. If allow_create is set then
201: * create a new one in the tree if one did not exist already.
202: */
203: static int
204: revoked_certs_for_ca_key(struct ssh_krl *krl, const Key *ca_key,
205: struct revoked_certs **rcp, int allow_create)
206: {
207: struct revoked_certs *rc;
208:
209: *rcp = NULL;
210: TAILQ_FOREACH(rc, &krl->revoked_certs, entry) {
211: if (key_equal(rc->ca_key, ca_key)) {
212: *rcp = rc;
213: return 0;
214: }
215: }
216: if (!allow_create)
217: return 0;
218: /* If this CA doesn't exist in the list then add it now */
219: if ((rc = calloc(1, sizeof(*rc))) == NULL)
220: return -1;
221: if ((rc->ca_key = key_from_private(ca_key)) == NULL) {
222: free(rc);
223: return -1;
224: }
225: RB_INIT(&rc->revoked_serials);
226: RB_INIT(&rc->revoked_key_ids);
227: TAILQ_INSERT_TAIL(&krl->revoked_certs, rc, entry);
228: debug3("%s: new CA %s", __func__, key_type(ca_key));
229: *rcp = rc;
230: return 0;
231: }
232:
233: static int
234: insert_serial_range(struct revoked_serial_tree *rt, u_int64_t lo, u_int64_t hi)
235: {
236: struct revoked_serial rs, *ers, *crs, *irs;
237:
238: KRL_DBG(("%s: insert %llu:%llu", __func__, lo, hi));
1.14 tedu 239: memset(&rs, 0, sizeof(rs));
1.1 djm 240: rs.lo = lo;
241: rs.hi = hi;
242: ers = RB_NFIND(revoked_serial_tree, rt, &rs);
243: if (ers == NULL || serial_cmp(ers, &rs) != 0) {
244: /* No entry matches. Just insert */
245: if ((irs = malloc(sizeof(rs))) == NULL)
246: return -1;
247: memcpy(irs, &rs, sizeof(*irs));
248: ers = RB_INSERT(revoked_serial_tree, rt, irs);
249: if (ers != NULL) {
250: KRL_DBG(("%s: bad: ers != NULL", __func__));
251: /* Shouldn't happen */
1.4 markus 252: free(irs);
1.1 djm 253: return -1;
254: }
255: ers = irs;
256: } else {
257: KRL_DBG(("%s: overlap found %llu:%llu", __func__,
258: ers->lo, ers->hi));
259: /*
260: * The inserted entry overlaps an existing one. Grow the
261: * existing entry.
262: */
263: if (ers->lo > lo)
264: ers->lo = lo;
265: if (ers->hi < hi)
266: ers->hi = hi;
267: }
268: /*
269: * The inserted or revised range might overlap or abut adjacent ones;
270: * coalesce as necessary.
271: */
272:
273: /* Check predecessors */
274: while ((crs = RB_PREV(revoked_serial_tree, rt, ers)) != NULL) {
275: KRL_DBG(("%s: pred %llu:%llu", __func__, crs->lo, crs->hi));
276: if (ers->lo != 0 && crs->hi < ers->lo - 1)
277: break;
278: /* This entry overlaps. */
279: if (crs->lo < ers->lo) {
280: ers->lo = crs->lo;
281: KRL_DBG(("%s: pred extend %llu:%llu", __func__,
282: ers->lo, ers->hi));
283: }
284: RB_REMOVE(revoked_serial_tree, rt, crs);
285: free(crs);
286: }
287: /* Check successors */
288: while ((crs = RB_NEXT(revoked_serial_tree, rt, ers)) != NULL) {
289: KRL_DBG(("%s: succ %llu:%llu", __func__, crs->lo, crs->hi));
290: if (ers->hi != (u_int64_t)-1 && crs->lo > ers->hi + 1)
291: break;
292: /* This entry overlaps. */
293: if (crs->hi > ers->hi) {
294: ers->hi = crs->hi;
295: KRL_DBG(("%s: succ extend %llu:%llu", __func__,
296: ers->lo, ers->hi));
297: }
298: RB_REMOVE(revoked_serial_tree, rt, crs);
299: free(crs);
300: }
301: KRL_DBG(("%s: done, final %llu:%llu", __func__, ers->lo, ers->hi));
302: return 0;
303: }
304:
305: int
306: ssh_krl_revoke_cert_by_serial(struct ssh_krl *krl, const Key *ca_key,
307: u_int64_t serial)
308: {
309: return ssh_krl_revoke_cert_by_serial_range(krl, ca_key, serial, serial);
310: }
311:
312: int
313: ssh_krl_revoke_cert_by_serial_range(struct ssh_krl *krl, const Key *ca_key,
314: u_int64_t lo, u_int64_t hi)
315: {
316: struct revoked_certs *rc;
317:
318: if (lo > hi || lo == 0)
319: return -1;
320: if (revoked_certs_for_ca_key(krl, ca_key, &rc, 1) != 0)
321: return -1;
322: return insert_serial_range(&rc->revoked_serials, lo, hi);
323: }
324:
325: int
326: ssh_krl_revoke_cert_by_key_id(struct ssh_krl *krl, const Key *ca_key,
327: const char *key_id)
328: {
329: struct revoked_key_id *rki, *erki;
330: struct revoked_certs *rc;
331:
332: if (revoked_certs_for_ca_key(krl, ca_key, &rc, 1) != 0)
333: return -1;
334:
335: debug3("%s: revoke %s", __func__, key_id);
336: if ((rki = calloc(1, sizeof(*rki))) == NULL ||
337: (rki->key_id = strdup(key_id)) == NULL) {
338: free(rki);
339: fatal("%s: strdup", __func__);
340: }
341: erki = RB_INSERT(revoked_key_id_tree, &rc->revoked_key_ids, rki);
342: if (erki != NULL) {
343: free(rki->key_id);
344: free(rki);
345: }
346: return 0;
347: }
348:
349: /* Convert "key" to a public key blob without any certificate information */
350: static int
351: plain_key_blob(const Key *key, u_char **blob, u_int *blen)
352: {
353: Key *kcopy;
354: int r;
355:
356: if ((kcopy = key_from_private(key)) == NULL)
357: return -1;
358: if (key_is_cert(kcopy)) {
359: if (key_drop_cert(kcopy) != 0) {
360: error("%s: key_drop_cert", __func__);
361: key_free(kcopy);
362: return -1;
363: }
364: }
365: r = key_to_blob(kcopy, blob, blen);
366: free(kcopy);
1.17 djm 367: return r;
1.1 djm 368: }
369:
370: /* Revoke a key blob. Ownership of blob is transferred to the tree */
371: static int
372: revoke_blob(struct revoked_blob_tree *rbt, u_char *blob, u_int len)
373: {
374: struct revoked_blob *rb, *erb;
375:
376: if ((rb = calloc(1, sizeof(*rb))) == NULL)
377: return -1;
378: rb->blob = blob;
379: rb->len = len;
380: erb = RB_INSERT(revoked_blob_tree, rbt, rb);
381: if (erb != NULL) {
382: free(rb->blob);
383: free(rb);
384: }
385: return 0;
386: }
387:
388: int
389: ssh_krl_revoke_key_explicit(struct ssh_krl *krl, const Key *key)
390: {
391: u_char *blob;
392: u_int len;
393:
394: debug3("%s: revoke type %s", __func__, key_type(key));
1.17 djm 395: if (plain_key_blob(key, &blob, &len) < 0)
1.1 djm 396: return -1;
397: return revoke_blob(&krl->revoked_keys, blob, len);
398: }
399:
400: int
401: ssh_krl_revoke_key_sha1(struct ssh_krl *krl, const Key *key)
402: {
403: u_char *blob;
404: u_int len;
405:
406: debug3("%s: revoke type %s by sha1", __func__, key_type(key));
407: if ((blob = key_fingerprint_raw(key, SSH_FP_SHA1, &len)) == NULL)
408: return -1;
409: return revoke_blob(&krl->revoked_sha1s, blob, len);
410: }
411:
412: int
413: ssh_krl_revoke_key(struct ssh_krl *krl, const Key *key)
414: {
415: if (!key_is_cert(key))
416: return ssh_krl_revoke_key_sha1(krl, key);
417:
418: if (key_cert_is_legacy(key) || key->cert->serial == 0) {
419: return ssh_krl_revoke_cert_by_key_id(krl,
420: key->cert->signature_key,
421: key->cert->key_id);
422: } else {
423: return ssh_krl_revoke_cert_by_serial(krl,
424: key->cert->signature_key,
425: key->cert->serial);
426: }
427: }
428:
429: /*
430: * Select a copact next section type to emit in a KRL based on the
431: * current section type, the run length of contiguous revoked serial
432: * numbers and the gaps from the last and to the next revoked serial.
433: * Applies a mostly-accurate bit cost model to select the section type
434: * that will minimise the size of the resultant KRL.
435: */
436: static int
437: choose_next_state(int current_state, u_int64_t contig, int final,
438: u_int64_t last_gap, u_int64_t next_gap, int *force_new_section)
439: {
440: int new_state;
441: u_int64_t cost, cost_list, cost_range, cost_bitmap, cost_bitmap_restart;
442:
443: /*
444: * Avoid unsigned overflows.
445: * The limits are high enough to avoid confusing the calculations.
446: */
447: contig = MIN(contig, 1ULL<<31);
448: last_gap = MIN(last_gap, 1ULL<<31);
449: next_gap = MIN(next_gap, 1ULL<<31);
450:
451: /*
452: * Calculate the cost to switch from the current state to candidates.
453: * NB. range sections only ever contain a single range, so their
454: * switching cost is independent of the current_state.
455: */
456: cost_list = cost_bitmap = cost_bitmap_restart = 0;
457: cost_range = 8;
458: switch (current_state) {
459: case KRL_SECTION_CERT_SERIAL_LIST:
460: cost_bitmap_restart = cost_bitmap = 8 + 64;
461: break;
462: case KRL_SECTION_CERT_SERIAL_BITMAP:
463: cost_list = 8;
464: cost_bitmap_restart = 8 + 64;
465: break;
466: case KRL_SECTION_CERT_SERIAL_RANGE:
467: case 0:
468: cost_bitmap_restart = cost_bitmap = 8 + 64;
469: cost_list = 8;
470: }
471:
472: /* Estimate base cost in bits of each section type */
473: cost_list += 64 * contig + (final ? 0 : 8+64);
474: cost_range += (2 * 64) + (final ? 0 : 8+64);
475: cost_bitmap += last_gap + contig + (final ? 0 : MIN(next_gap, 8+64));
476: cost_bitmap_restart += contig + (final ? 0 : MIN(next_gap, 8+64));
477:
478: /* Convert to byte costs for actual comparison */
479: cost_list = (cost_list + 7) / 8;
480: cost_bitmap = (cost_bitmap + 7) / 8;
481: cost_bitmap_restart = (cost_bitmap_restart + 7) / 8;
482: cost_range = (cost_range + 7) / 8;
483:
484: /* Now pick the best choice */
485: *force_new_section = 0;
486: new_state = KRL_SECTION_CERT_SERIAL_BITMAP;
487: cost = cost_bitmap;
488: if (cost_range < cost) {
489: new_state = KRL_SECTION_CERT_SERIAL_RANGE;
490: cost = cost_range;
491: }
492: if (cost_list < cost) {
493: new_state = KRL_SECTION_CERT_SERIAL_LIST;
494: cost = cost_list;
495: }
496: if (cost_bitmap_restart < cost) {
497: new_state = KRL_SECTION_CERT_SERIAL_BITMAP;
498: *force_new_section = 1;
499: cost = cost_bitmap_restart;
500: }
501: debug3("%s: contig %llu last_gap %llu next_gap %llu final %d, costs:"
502: "list %llu range %llu bitmap %llu new bitmap %llu, "
1.11 djm 503: "selected 0x%02x%s", __func__, (long long unsigned)contig,
504: (long long unsigned)last_gap, (long long unsigned)next_gap, final,
505: (long long unsigned)cost_list, (long long unsigned)cost_range,
506: (long long unsigned)cost_bitmap,
507: (long long unsigned)cost_bitmap_restart, new_state,
1.1 djm 508: *force_new_section ? " restart" : "");
509: return new_state;
510: }
511:
512: /* Generate a KRL_SECTION_CERTIFICATES KRL section */
513: static int
514: revoked_certs_generate(struct revoked_certs *rc, Buffer *buf)
515: {
516: int final, force_new_sect, r = -1;
517: u_int64_t i, contig, gap, last = 0, bitmap_start = 0;
518: struct revoked_serial *rs, *nrs;
519: struct revoked_key_id *rki;
520: int next_state, state = 0;
521: Buffer sect;
522: u_char *kblob = NULL;
523: u_int klen;
524: BIGNUM *bitmap = NULL;
525:
526: /* Prepare CA scope key blob if we have one supplied */
527: if (key_to_blob(rc->ca_key, &kblob, &klen) == 0)
528: return -1;
529:
530: buffer_init(§);
531:
532: /* Store the header */
533: buffer_put_string(buf, kblob, klen);
534: buffer_put_string(buf, NULL, 0); /* Reserved */
535:
536: free(kblob);
537:
538: /* Store the revoked serials. */
539: for (rs = RB_MIN(revoked_serial_tree, &rc->revoked_serials);
540: rs != NULL;
541: rs = RB_NEXT(revoked_serial_tree, &rc->revoked_serials, rs)) {
542: debug3("%s: serial %llu:%llu state 0x%02x", __func__,
1.11 djm 543: (long long unsigned)rs->lo, (long long unsigned)rs->hi,
544: state);
1.1 djm 545:
546: /* Check contiguous length and gap to next section (if any) */
547: nrs = RB_NEXT(revoked_serial_tree, &rc->revoked_serials, rs);
548: final = nrs == NULL;
549: gap = nrs == NULL ? 0 : nrs->lo - rs->hi;
550: contig = 1 + (rs->hi - rs->lo);
551:
552: /* Choose next state based on these */
553: next_state = choose_next_state(state, contig, final,
554: state == 0 ? 0 : rs->lo - last, gap, &force_new_sect);
555:
556: /*
557: * If the current section is a range section or has a different
558: * type to the next section, then finish it off now.
559: */
560: if (state != 0 && (force_new_sect || next_state != state ||
561: state == KRL_SECTION_CERT_SERIAL_RANGE)) {
562: debug3("%s: finish state 0x%02x", __func__, state);
563: switch (state) {
564: case KRL_SECTION_CERT_SERIAL_LIST:
565: case KRL_SECTION_CERT_SERIAL_RANGE:
566: break;
567: case KRL_SECTION_CERT_SERIAL_BITMAP:
568: buffer_put_bignum2(§, bitmap);
569: BN_free(bitmap);
570: bitmap = NULL;
571: break;
572: }
573: buffer_put_char(buf, state);
574: buffer_put_string(buf,
575: buffer_ptr(§), buffer_len(§));
1.16 djm 576: buffer_clear(§);
1.1 djm 577: }
578:
579: /* If we are starting a new section then prepare it now */
580: if (next_state != state || force_new_sect) {
581: debug3("%s: start state 0x%02x", __func__, next_state);
582: state = next_state;
583: buffer_clear(§);
584: switch (state) {
585: case KRL_SECTION_CERT_SERIAL_LIST:
586: case KRL_SECTION_CERT_SERIAL_RANGE:
587: break;
588: case KRL_SECTION_CERT_SERIAL_BITMAP:
589: if ((bitmap = BN_new()) == NULL)
590: goto out;
591: bitmap_start = rs->lo;
592: buffer_put_int64(§, bitmap_start);
593: break;
594: }
595: }
596:
597: /* Perform section-specific processing */
598: switch (state) {
599: case KRL_SECTION_CERT_SERIAL_LIST:
1.3 djm 600: for (i = 0; i < contig; i++)
1.1 djm 601: buffer_put_int64(§, rs->lo + i);
602: break;
603: case KRL_SECTION_CERT_SERIAL_RANGE:
604: buffer_put_int64(§, rs->lo);
605: buffer_put_int64(§, rs->hi);
606: break;
607: case KRL_SECTION_CERT_SERIAL_BITMAP:
608: if (rs->lo - bitmap_start > INT_MAX) {
609: error("%s: insane bitmap gap", __func__);
610: goto out;
611: }
612: for (i = 0; i < contig; i++) {
613: if (BN_set_bit(bitmap,
614: rs->lo + i - bitmap_start) != 1)
615: goto out;
616: }
617: break;
618: }
619: last = rs->hi;
620: }
621: /* Flush the remaining section, if any */
622: if (state != 0) {
623: debug3("%s: serial final flush for state 0x%02x",
624: __func__, state);
625: switch (state) {
626: case KRL_SECTION_CERT_SERIAL_LIST:
627: case KRL_SECTION_CERT_SERIAL_RANGE:
628: break;
629: case KRL_SECTION_CERT_SERIAL_BITMAP:
630: buffer_put_bignum2(§, bitmap);
631: BN_free(bitmap);
632: bitmap = NULL;
633: break;
634: }
635: buffer_put_char(buf, state);
636: buffer_put_string(buf,
637: buffer_ptr(§), buffer_len(§));
638: }
639: debug3("%s: serial done ", __func__);
640:
641: /* Now output a section for any revocations by key ID */
642: buffer_clear(§);
643: RB_FOREACH(rki, revoked_key_id_tree, &rc->revoked_key_ids) {
644: debug3("%s: key ID %s", __func__, rki->key_id);
645: buffer_put_cstring(§, rki->key_id);
646: }
647: if (buffer_len(§) != 0) {
648: buffer_put_char(buf, KRL_SECTION_CERT_KEY_ID);
649: buffer_put_string(buf, buffer_ptr(§),
650: buffer_len(§));
651: }
652: r = 0;
653: out:
654: if (bitmap != NULL)
655: BN_free(bitmap);
656: buffer_free(§);
657: return r;
658: }
659:
660: int
661: ssh_krl_to_blob(struct ssh_krl *krl, Buffer *buf, const Key **sign_keys,
662: u_int nsign_keys)
663: {
664: int r = -1;
665: struct revoked_certs *rc;
666: struct revoked_blob *rb;
667: Buffer sect;
668: u_char *kblob = NULL, *sblob = NULL;
669: u_int klen, slen, i;
670:
671: if (krl->generated_date == 0)
672: krl->generated_date = time(NULL);
673:
674: buffer_init(§);
675:
676: /* Store the header */
677: buffer_append(buf, KRL_MAGIC, sizeof(KRL_MAGIC) - 1);
678: buffer_put_int(buf, KRL_FORMAT_VERSION);
679: buffer_put_int64(buf, krl->krl_version);
680: buffer_put_int64(buf, krl->generated_date);
681: buffer_put_int64(buf, krl->flags);
682: buffer_put_string(buf, NULL, 0);
683: buffer_put_cstring(buf, krl->comment ? krl->comment : "");
684:
685: /* Store sections for revoked certificates */
686: TAILQ_FOREACH(rc, &krl->revoked_certs, entry) {
1.18 djm 687: buffer_clear(§);
1.1 djm 688: if (revoked_certs_generate(rc, §) != 0)
689: goto out;
690: buffer_put_char(buf, KRL_SECTION_CERTIFICATES);
691: buffer_put_string(buf, buffer_ptr(§),
692: buffer_len(§));
693: }
694:
695: /* Finally, output sections for revocations by public key/hash */
696: buffer_clear(§);
697: RB_FOREACH(rb, revoked_blob_tree, &krl->revoked_keys) {
698: debug3("%s: key len %u ", __func__, rb->len);
699: buffer_put_string(§, rb->blob, rb->len);
700: }
701: if (buffer_len(§) != 0) {
702: buffer_put_char(buf, KRL_SECTION_EXPLICIT_KEY);
703: buffer_put_string(buf, buffer_ptr(§),
704: buffer_len(§));
705: }
706: buffer_clear(§);
707: RB_FOREACH(rb, revoked_blob_tree, &krl->revoked_sha1s) {
708: debug3("%s: hash len %u ", __func__, rb->len);
709: buffer_put_string(§, rb->blob, rb->len);
710: }
711: if (buffer_len(§) != 0) {
712: buffer_put_char(buf, KRL_SECTION_FINGERPRINT_SHA1);
713: buffer_put_string(buf, buffer_ptr(§),
714: buffer_len(§));
715: }
716:
717: for (i = 0; i < nsign_keys; i++) {
718: if (key_to_blob(sign_keys[i], &kblob, &klen) == 0)
719: goto out;
720:
721: debug3("%s: signature key len %u", __func__, klen);
722: buffer_put_char(buf, KRL_SECTION_SIGNATURE);
723: buffer_put_string(buf, kblob, klen);
724:
725: if (key_sign(sign_keys[i], &sblob, &slen,
726: buffer_ptr(buf), buffer_len(buf)) == -1)
727: goto out;
728: debug3("%s: signature sig len %u", __func__, slen);
729: buffer_put_string(buf, sblob, slen);
730: }
731:
732: r = 0;
733: out:
734: free(kblob);
735: free(sblob);
736: buffer_free(§);
737: return r;
738: }
739:
740: static void
741: format_timestamp(u_int64_t timestamp, char *ts, size_t nts)
742: {
743: time_t t;
744: struct tm *tm;
745:
746: t = timestamp;
747: tm = localtime(&t);
1.19 ! djm 748: if (tm == NULL)
! 749: strlcpy(ts, "<INVALID>", sizeof(nts));
! 750: else {
! 751: *ts = '\0';
! 752: strftime(ts, nts, "%Y%m%dT%H%M%S", tm);
! 753: }
1.1 djm 754: }
755:
756: static int
757: parse_revoked_certs(Buffer *buf, struct ssh_krl *krl)
758: {
759: int ret = -1, nbits;
1.15 djm 760: u_char type;
761: const u_char *blob;
1.1 djm 762: u_int blen;
763: Buffer subsect;
764: u_int64_t serial, serial_lo, serial_hi;
765: BIGNUM *bitmap = NULL;
766: char *key_id = NULL;
767: Key *ca_key = NULL;
768:
769: buffer_init(&subsect);
770:
771: if ((blob = buffer_get_string_ptr_ret(buf, &blen)) == NULL ||
772: buffer_get_string_ptr_ret(buf, NULL) == NULL) { /* reserved */
773: error("%s: buffer error", __func__);
774: goto out;
775: }
776: if ((ca_key = key_from_blob(blob, blen)) == NULL)
777: goto out;
778:
779: while (buffer_len(buf) > 0) {
780: if (buffer_get_char_ret(&type, buf) != 0 ||
781: (blob = buffer_get_string_ptr_ret(buf, &blen)) == NULL) {
782: error("%s: buffer error", __func__);
783: goto out;
784: }
785: buffer_clear(&subsect);
786: buffer_append(&subsect, blob, blen);
787: debug3("%s: subsection type 0x%02x", __func__, type);
788: /* buffer_dump(&subsect); */
789:
790: switch (type) {
791: case KRL_SECTION_CERT_SERIAL_LIST:
792: while (buffer_len(&subsect) > 0) {
793: if (buffer_get_int64_ret(&serial,
794: &subsect) != 0) {
795: error("%s: buffer error", __func__);
796: goto out;
797: }
798: if (ssh_krl_revoke_cert_by_serial(krl, ca_key,
799: serial) != 0) {
800: error("%s: update failed", __func__);
801: goto out;
802: }
803: }
804: break;
805: case KRL_SECTION_CERT_SERIAL_RANGE:
806: if (buffer_get_int64_ret(&serial_lo, &subsect) != 0 ||
807: buffer_get_int64_ret(&serial_hi, &subsect) != 0) {
808: error("%s: buffer error", __func__);
809: goto out;
810: }
811: if (ssh_krl_revoke_cert_by_serial_range(krl, ca_key,
812: serial_lo, serial_hi) != 0) {
813: error("%s: update failed", __func__);
814: goto out;
815: }
816: break;
817: case KRL_SECTION_CERT_SERIAL_BITMAP:
818: if ((bitmap = BN_new()) == NULL) {
819: error("%s: BN_new", __func__);
820: goto out;
821: }
822: if (buffer_get_int64_ret(&serial_lo, &subsect) != 0 ||
823: buffer_get_bignum2_ret(&subsect, bitmap) != 0) {
824: error("%s: buffer error", __func__);
825: goto out;
826: }
827: if ((nbits = BN_num_bits(bitmap)) < 0) {
828: error("%s: bitmap bits < 0", __func__);
829: goto out;
830: }
831: for (serial = 0; serial < (u_int)nbits; serial++) {
832: if (serial > 0 && serial_lo + serial == 0) {
833: error("%s: bitmap wraps u64", __func__);
834: goto out;
835: }
836: if (!BN_is_bit_set(bitmap, serial))
837: continue;
838: if (ssh_krl_revoke_cert_by_serial(krl, ca_key,
839: serial_lo + serial) != 0) {
840: error("%s: update failed", __func__);
841: goto out;
842: }
843: }
844: BN_free(bitmap);
845: bitmap = NULL;
846: break;
847: case KRL_SECTION_CERT_KEY_ID:
848: while (buffer_len(&subsect) > 0) {
849: if ((key_id = buffer_get_cstring_ret(&subsect,
850: NULL)) == NULL) {
851: error("%s: buffer error", __func__);
852: goto out;
853: }
854: if (ssh_krl_revoke_cert_by_key_id(krl, ca_key,
855: key_id) != 0) {
856: error("%s: update failed", __func__);
857: goto out;
858: }
859: free(key_id);
860: key_id = NULL;
861: }
862: break;
863: default:
864: error("Unsupported KRL certificate section %u", type);
865: goto out;
866: }
867: if (buffer_len(&subsect) > 0) {
868: error("KRL certificate section contains unparsed data");
869: goto out;
870: }
871: }
872:
873: ret = 0;
874: out:
875: if (ca_key != NULL)
876: key_free(ca_key);
877: if (bitmap != NULL)
878: BN_free(bitmap);
879: free(key_id);
880: buffer_free(&subsect);
881: return ret;
882: }
883:
884:
885: /* Attempt to parse a KRL, checking its signature (if any) with sign_ca_keys. */
886: int
887: ssh_krl_from_blob(Buffer *buf, struct ssh_krl **krlp,
888: const Key **sign_ca_keys, u_int nsign_ca_keys)
889: {
890: Buffer copy, sect;
891: struct ssh_krl *krl;
892: char timestamp[64];
893: int ret = -1, r, sig_seen;
894: Key *key = NULL, **ca_used = NULL;
1.15 djm 895: u_char type, *rdata = NULL;
896: const u_char *blob;
1.12 markus 897: u_int i, j, sig_off, sects_off, rlen, blen, format_version, nca_used;
1.1 djm 898:
1.12 markus 899: nca_used = 0;
1.1 djm 900: *krlp = NULL;
901: if (buffer_len(buf) < sizeof(KRL_MAGIC) - 1 ||
902: memcmp(buffer_ptr(buf), KRL_MAGIC, sizeof(KRL_MAGIC) - 1) != 0) {
903: debug3("%s: not a KRL", __func__);
904: /*
905: * Return success but a NULL *krlp here to signal that the
906: * file might be a simple list of keys.
907: */
908: return 0;
909: }
910:
911: /* Take a copy of the KRL buffer so we can verify its signature later */
912: buffer_init(©);
913: buffer_append(©, buffer_ptr(buf), buffer_len(buf));
914:
915: buffer_init(§);
916: buffer_consume(©, sizeof(KRL_MAGIC) - 1);
917:
918: if ((krl = ssh_krl_init()) == NULL) {
919: error("%s: alloc failed", __func__);
920: goto out;
921: }
922:
923: if (buffer_get_int_ret(&format_version, ©) != 0) {
924: error("%s: KRL truncated", __func__);
925: goto out;
926: }
927: if (format_version != KRL_FORMAT_VERSION) {
928: error("%s: KRL unsupported format version %u",
929: __func__, format_version);
930: goto out;
931: }
932: if (buffer_get_int64_ret(&krl->krl_version, ©) != 0 ||
933: buffer_get_int64_ret(&krl->generated_date, ©) != 0 ||
934: buffer_get_int64_ret(&krl->flags, ©) != 0 ||
935: buffer_get_string_ptr_ret(©, NULL) == NULL || /* reserved */
936: (krl->comment = buffer_get_cstring_ret(©, NULL)) == NULL) {
937: error("%s: buffer error", __func__);
938: goto out;
939: }
940:
941: format_timestamp(krl->generated_date, timestamp, sizeof(timestamp));
1.11 djm 942: debug("KRL version %llu generated at %s%s%s",
943: (long long unsigned)krl->krl_version, timestamp,
944: *krl->comment ? ": " : "", krl->comment);
1.1 djm 945:
946: /*
947: * 1st pass: verify signatures, if any. This is done to avoid
948: * detailed parsing of data whose provenance is unverified.
949: */
950: sig_seen = 0;
951: sects_off = buffer_len(buf) - buffer_len(©);
952: while (buffer_len(©) > 0) {
953: if (buffer_get_char_ret(&type, ©) != 0 ||
954: (blob = buffer_get_string_ptr_ret(©, &blen)) == NULL) {
955: error("%s: buffer error", __func__);
956: goto out;
957: }
958: debug3("%s: first pass, section 0x%02x", __func__, type);
959: if (type != KRL_SECTION_SIGNATURE) {
960: if (sig_seen) {
961: error("KRL contains non-signature section "
962: "after signature");
963: goto out;
964: }
965: /* Not interested for now. */
966: continue;
967: }
968: sig_seen = 1;
969: /* First string component is the signing key */
970: if ((key = key_from_blob(blob, blen)) == NULL) {
971: error("%s: invalid signature key", __func__);
972: goto out;
973: }
974: sig_off = buffer_len(buf) - buffer_len(©);
975: /* Second string component is the signature itself */
976: if ((blob = buffer_get_string_ptr_ret(©, &blen)) == NULL) {
977: error("%s: buffer error", __func__);
978: goto out;
979: }
980: /* Check signature over entire KRL up to this point */
981: if (key_verify(key, blob, blen,
1.13 djm 982: buffer_ptr(buf), buffer_len(buf) - sig_off) != 1) {
1.1 djm 983: error("bad signaure on KRL");
984: goto out;
985: }
986: /* Check if this key has already signed this KRL */
987: for (i = 0; i < nca_used; i++) {
988: if (key_equal(ca_used[i], key)) {
989: error("KRL signed more than once with "
990: "the same key");
991: goto out;
992: }
993: }
994: /* Record keys used to sign the KRL */
1.9 djm 995: ca_used = xrealloc(ca_used, nca_used + 1, sizeof(*ca_used));
1.1 djm 996: ca_used[nca_used++] = key;
997: key = NULL;
998: break;
999: }
1000:
1001: /*
1002: * 2nd pass: parse and load the KRL, skipping the header to the point
1003: * where the section start.
1004: */
1005: buffer_append(©, (u_char*)buffer_ptr(buf) + sects_off,
1006: buffer_len(buf) - sects_off);
1007: while (buffer_len(©) > 0) {
1008: if (buffer_get_char_ret(&type, ©) != 0 ||
1009: (blob = buffer_get_string_ptr_ret(©, &blen)) == NULL) {
1010: error("%s: buffer error", __func__);
1011: goto out;
1012: }
1013: debug3("%s: second pass, section 0x%02x", __func__, type);
1014: buffer_clear(§);
1015: buffer_append(§, blob, blen);
1016:
1017: switch (type) {
1018: case KRL_SECTION_CERTIFICATES:
1019: if ((r = parse_revoked_certs(§, krl)) != 0)
1020: goto out;
1021: break;
1022: case KRL_SECTION_EXPLICIT_KEY:
1023: case KRL_SECTION_FINGERPRINT_SHA1:
1024: while (buffer_len(§) > 0) {
1.12 markus 1025: if ((rdata = buffer_get_string_ret(§,
1026: &rlen)) == NULL) {
1.1 djm 1027: error("%s: buffer error", __func__);
1028: goto out;
1029: }
1030: if (type == KRL_SECTION_FINGERPRINT_SHA1 &&
1.12 markus 1031: rlen != 20) {
1.1 djm 1032: error("%s: bad SHA1 length", __func__);
1033: goto out;
1034: }
1035: if (revoke_blob(
1036: type == KRL_SECTION_EXPLICIT_KEY ?
1037: &krl->revoked_keys : &krl->revoked_sha1s,
1.12 markus 1038: rdata, rlen) != 0)
1039: goto out;
1040: rdata = NULL; /* revoke_blob frees blob */
1.1 djm 1041: }
1042: break;
1043: case KRL_SECTION_SIGNATURE:
1044: /* Handled above, but still need to stay in synch */
1045: buffer_clear(§);
1.5 djm 1046: if ((blob = buffer_get_string_ptr_ret(©,
1.1 djm 1047: &blen)) == NULL) {
1048: error("%s: buffer error", __func__);
1049: goto out;
1050: }
1051: break;
1052: default:
1053: error("Unsupported KRL section %u", type);
1054: goto out;
1055: }
1056: if (buffer_len(§) > 0) {
1057: error("KRL section contains unparsed data");
1058: goto out;
1059: }
1060: }
1061:
1062: /* Check that the key(s) used to sign the KRL weren't revoked */
1063: sig_seen = 0;
1064: for (i = 0; i < nca_used; i++) {
1065: if (ssh_krl_check_key(krl, ca_used[i]) == 0)
1066: sig_seen = 1;
1067: else {
1068: key_free(ca_used[i]);
1069: ca_used[i] = NULL;
1070: }
1071: }
1072: if (nca_used && !sig_seen) {
1073: error("All keys used to sign KRL were revoked");
1074: goto out;
1075: }
1076:
1077: /* If we have CA keys, then verify that one was used to sign the KRL */
1078: if (sig_seen && nsign_ca_keys != 0) {
1079: sig_seen = 0;
1080: for (i = 0; !sig_seen && i < nsign_ca_keys; i++) {
1081: for (j = 0; j < nca_used; j++) {
1082: if (ca_used[j] == NULL)
1083: continue;
1084: if (key_equal(ca_used[j], sign_ca_keys[i])) {
1085: sig_seen = 1;
1086: break;
1087: }
1088: }
1089: }
1090: if (!sig_seen) {
1091: error("KRL not signed with any trusted key");
1092: goto out;
1093: }
1094: }
1095:
1096: *krlp = krl;
1097: ret = 0;
1098: out:
1099: if (ret != 0)
1100: ssh_krl_free(krl);
1101: for (i = 0; i < nca_used; i++) {
1102: if (ca_used[i] != NULL)
1103: key_free(ca_used[i]);
1104: }
1105: free(ca_used);
1.12 markus 1106: free(rdata);
1.1 djm 1107: if (key != NULL)
1108: key_free(key);
1109: buffer_free(©);
1110: buffer_free(§);
1111: return ret;
1112: }
1113:
1114: /* Checks whether a given key/cert is revoked. Does not check its CA */
1115: static int
1116: is_key_revoked(struct ssh_krl *krl, const Key *key)
1117: {
1118: struct revoked_blob rb, *erb;
1119: struct revoked_serial rs, *ers;
1120: struct revoked_key_id rki, *erki;
1121: struct revoked_certs *rc;
1122:
1123: /* Check explicitly revoked hashes first */
1.14 tedu 1124: memset(&rb, 0, sizeof(rb));
1.1 djm 1125: if ((rb.blob = key_fingerprint_raw(key, SSH_FP_SHA1, &rb.len)) == NULL)
1126: return -1;
1127: erb = RB_FIND(revoked_blob_tree, &krl->revoked_sha1s, &rb);
1128: free(rb.blob);
1129: if (erb != NULL) {
1130: debug("%s: revoked by key SHA1", __func__);
1131: return -1;
1132: }
1133:
1134: /* Next, explicit keys */
1.14 tedu 1135: memset(&rb, 0, sizeof(rb));
1.17 djm 1136: if (plain_key_blob(key, &rb.blob, &rb.len) < 0)
1.1 djm 1137: return -1;
1138: erb = RB_FIND(revoked_blob_tree, &krl->revoked_keys, &rb);
1139: free(rb.blob);
1140: if (erb != NULL) {
1141: debug("%s: revoked by explicit key", __func__);
1142: return -1;
1143: }
1144:
1145: if (!key_is_cert(key))
1146: return 0;
1147:
1148: /* Check cert revocation */
1149: if (revoked_certs_for_ca_key(krl, key->cert->signature_key,
1150: &rc, 0) != 0)
1151: return -1;
1152: if (rc == NULL)
1153: return 0; /* No entry for this CA */
1154:
1155: /* Check revocation by cert key ID */
1.14 tedu 1156: memset(&rki, 0, sizeof(rki));
1.1 djm 1157: rki.key_id = key->cert->key_id;
1158: erki = RB_FIND(revoked_key_id_tree, &rc->revoked_key_ids, &rki);
1159: if (erki != NULL) {
1160: debug("%s: revoked by key ID", __func__);
1161: return -1;
1162: }
1163:
1.8 djm 1164: /*
1165: * Legacy cert formats lack serial numbers. Zero serials numbers
1166: * are ignored (it's the default when the CA doesn't specify one).
1167: */
1168: if (key_cert_is_legacy(key) || key->cert->serial == 0)
1.1 djm 1169: return 0;
1170:
1.14 tedu 1171: memset(&rs, 0, sizeof(rs));
1.1 djm 1172: rs.lo = rs.hi = key->cert->serial;
1173: ers = RB_FIND(revoked_serial_tree, &rc->revoked_serials, &rs);
1174: if (ers != NULL) {
1175: KRL_DBG(("%s: %llu matched %llu:%llu", __func__,
1176: key->cert->serial, ers->lo, ers->hi));
1177: debug("%s: revoked by serial", __func__);
1178: return -1;
1179: }
1180: KRL_DBG(("%s: %llu no match", __func__, key->cert->serial));
1181:
1182: return 0;
1183: }
1184:
1185: int
1186: ssh_krl_check_key(struct ssh_krl *krl, const Key *key)
1187: {
1188: int r;
1189:
1190: debug2("%s: checking key", __func__);
1191: if ((r = is_key_revoked(krl, key)) != 0)
1192: return r;
1193: if (key_is_cert(key)) {
1194: debug2("%s: checking CA key", __func__);
1195: if ((r = is_key_revoked(krl, key->cert->signature_key)) != 0)
1196: return r;
1197: }
1198: debug3("%s: key okay", __func__);
1199: return 0;
1200: }
1201:
1202: /* Returns 0 on success, -1 on error or key revoked, -2 if path is not a KRL */
1203: int
1204: ssh_krl_file_contains_key(const char *path, const Key *key)
1205: {
1206: Buffer krlbuf;
1207: struct ssh_krl *krl;
1208: int revoked, fd;
1209:
1210: if (path == NULL)
1211: return 0;
1212:
1213: if ((fd = open(path, O_RDONLY)) == -1) {
1214: error("open %s: %s", path, strerror(errno));
1215: error("Revoked keys file not accessible - refusing public key "
1216: "authentication");
1217: return -1;
1218: }
1219: buffer_init(&krlbuf);
1220: if (!key_load_file(fd, path, &krlbuf)) {
1221: close(fd);
1222: buffer_free(&krlbuf);
1223: error("Revoked keys file not readable - refusing public key "
1224: "authentication");
1225: return -1;
1226: }
1227: close(fd);
1228: if (ssh_krl_from_blob(&krlbuf, &krl, NULL, 0) != 0) {
1229: buffer_free(&krlbuf);
1230: error("Invalid KRL, refusing public key "
1231: "authentication");
1232: return -1;
1233: }
1234: buffer_free(&krlbuf);
1235: if (krl == NULL) {
1236: debug3("%s: %s is not a KRL file", __func__, path);
1237: return -2;
1238: }
1239: debug2("%s: checking KRL %s", __func__, path);
1240: revoked = ssh_krl_check_key(krl, key) != 0;
1241: ssh_krl_free(krl);
1242: return revoked ? -1 : 0;
1243: }