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