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