xref: /openssh-portable/krl.c (revision 816036f1)
1f3747bf4SDamien Miller /*
2f3747bf4SDamien Miller  * Copyright (c) 2012 Damien Miller <djm@mindrot.org>
3f3747bf4SDamien Miller  *
4f3747bf4SDamien Miller  * Permission to use, copy, modify, and distribute this software for any
5f3747bf4SDamien Miller  * purpose with or without fee is hereby granted, provided that the above
6f3747bf4SDamien Miller  * copyright notice and this permission notice appear in all copies.
7f3747bf4SDamien Miller  *
8f3747bf4SDamien Miller  * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
9f3747bf4SDamien Miller  * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
10f3747bf4SDamien Miller  * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
11f3747bf4SDamien Miller  * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
12f3747bf4SDamien Miller  * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
13f3747bf4SDamien Miller  * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
14f3747bf4SDamien Miller  * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
15f3747bf4SDamien Miller  */
16f3747bf4SDamien Miller 
17*816036f1Sdjm@openbsd.org /* $OpenBSD: krl.c,v 1.52 2020/10/18 11:32:01 djm Exp $ */
18f3747bf4SDamien Miller 
19f3747bf4SDamien Miller #include "includes.h"
20f3747bf4SDamien Miller 
21f3747bf4SDamien Miller #include <sys/types.h>
22d60b2108SDamien Miller #include <openbsd-compat/sys-tree.h>
23d60b2108SDamien Miller #include <openbsd-compat/sys-queue.h>
24f3747bf4SDamien Miller 
25f3747bf4SDamien Miller #include <errno.h>
26f3747bf4SDamien Miller #include <fcntl.h>
27f3747bf4SDamien Miller #include <limits.h>
282ea60312SDarren Tucker #include <stdlib.h>
29f3747bf4SDamien Miller #include <string.h>
30f3747bf4SDamien Miller #include <time.h>
31f3747bf4SDamien Miller #include <unistd.h>
32f3747bf4SDamien Miller 
3374de254bSdjm@openbsd.org #include "sshbuf.h"
34e7fd952fSdjm@openbsd.org #include "ssherr.h"
3574de254bSdjm@openbsd.org #include "sshkey.h"
36f3747bf4SDamien Miller #include "authfile.h"
37f3747bf4SDamien Miller #include "misc.h"
38f3747bf4SDamien Miller #include "log.h"
3956d1c83cSdjm@openbsd.org #include "digest.h"
40a165bab6Sdjm@openbsd.org #include "bitmap.h"
416ec74571Sdjm@openbsd.org #include "utf8.h"
42f3747bf4SDamien Miller 
43f3747bf4SDamien Miller #include "krl.h"
44f3747bf4SDamien Miller 
45f3747bf4SDamien Miller /* #define DEBUG_KRL */
46f3747bf4SDamien Miller #ifdef DEBUG_KRL
47*816036f1Sdjm@openbsd.org # define KRL_DBG(x) debug3_f x
48f3747bf4SDamien Miller #else
49f3747bf4SDamien Miller # define KRL_DBG(x)
50f3747bf4SDamien Miller #endif
51f3747bf4SDamien Miller 
52f3747bf4SDamien Miller /*
53f3747bf4SDamien Miller  * Trees of revoked serial numbers, key IDs and keys. This allows
54f3747bf4SDamien Miller  * quick searching, querying and producing lists in canonical order.
55f3747bf4SDamien Miller  */
56f3747bf4SDamien Miller 
57f3747bf4SDamien Miller /* Tree of serial numbers. XXX make smarter: really need a real sparse bitmap */
58f3747bf4SDamien Miller struct revoked_serial {
59f3747bf4SDamien Miller 	u_int64_t lo, hi;
60f3747bf4SDamien Miller 	RB_ENTRY(revoked_serial) tree_entry;
61f3747bf4SDamien Miller };
62f3747bf4SDamien Miller static int serial_cmp(struct revoked_serial *a, struct revoked_serial *b);
63f3747bf4SDamien Miller RB_HEAD(revoked_serial_tree, revoked_serial);
64f3747bf4SDamien Miller RB_GENERATE_STATIC(revoked_serial_tree, revoked_serial, tree_entry, serial_cmp);
65f3747bf4SDamien Miller 
66f3747bf4SDamien Miller /* Tree of key IDs */
67f3747bf4SDamien Miller struct revoked_key_id {
68f3747bf4SDamien Miller 	char *key_id;
69f3747bf4SDamien Miller 	RB_ENTRY(revoked_key_id) tree_entry;
70f3747bf4SDamien Miller };
71f3747bf4SDamien Miller static int key_id_cmp(struct revoked_key_id *a, struct revoked_key_id *b);
72f3747bf4SDamien Miller RB_HEAD(revoked_key_id_tree, revoked_key_id);
73f3747bf4SDamien Miller RB_GENERATE_STATIC(revoked_key_id_tree, revoked_key_id, tree_entry, key_id_cmp);
74f3747bf4SDamien Miller 
75f3747bf4SDamien Miller /* Tree of blobs (used for keys and fingerprints) */
76f3747bf4SDamien Miller struct revoked_blob {
77f3747bf4SDamien Miller 	u_char *blob;
7874de254bSdjm@openbsd.org 	size_t len;
79f3747bf4SDamien Miller 	RB_ENTRY(revoked_blob) tree_entry;
80f3747bf4SDamien Miller };
81f3747bf4SDamien Miller static int blob_cmp(struct revoked_blob *a, struct revoked_blob *b);
82f3747bf4SDamien Miller RB_HEAD(revoked_blob_tree, revoked_blob);
83f3747bf4SDamien Miller RB_GENERATE_STATIC(revoked_blob_tree, revoked_blob, tree_entry, blob_cmp);
84f3747bf4SDamien Miller 
85f3747bf4SDamien Miller /* Tracks revoked certs for a single CA */
86f3747bf4SDamien Miller struct revoked_certs {
8774de254bSdjm@openbsd.org 	struct sshkey *ca_key;
88f3747bf4SDamien Miller 	struct revoked_serial_tree revoked_serials;
89f3747bf4SDamien Miller 	struct revoked_key_id_tree revoked_key_ids;
90f3747bf4SDamien Miller 	TAILQ_ENTRY(revoked_certs) entry;
91f3747bf4SDamien Miller };
92f3747bf4SDamien Miller TAILQ_HEAD(revoked_certs_list, revoked_certs);
93f3747bf4SDamien Miller 
94f3747bf4SDamien Miller struct ssh_krl {
95f3747bf4SDamien Miller 	u_int64_t krl_version;
96f3747bf4SDamien Miller 	u_int64_t generated_date;
97f3747bf4SDamien Miller 	u_int64_t flags;
98f3747bf4SDamien Miller 	char *comment;
99f3747bf4SDamien Miller 	struct revoked_blob_tree revoked_keys;
100f3747bf4SDamien Miller 	struct revoked_blob_tree revoked_sha1s;
1019405c621Sdjm@openbsd.org 	struct revoked_blob_tree revoked_sha256s;
102f3747bf4SDamien Miller 	struct revoked_certs_list revoked_certs;
103f3747bf4SDamien Miller };
104f3747bf4SDamien Miller 
105f3747bf4SDamien Miller /* Return equal if a and b overlap */
106f3747bf4SDamien Miller static int
serial_cmp(struct revoked_serial * a,struct revoked_serial * b)107f3747bf4SDamien Miller serial_cmp(struct revoked_serial *a, struct revoked_serial *b)
108f3747bf4SDamien Miller {
109f3747bf4SDamien Miller 	if (a->hi >= b->lo && a->lo <= b->hi)
110f3747bf4SDamien Miller 		return 0;
111f3747bf4SDamien Miller 	return a->lo < b->lo ? -1 : 1;
112f3747bf4SDamien Miller }
113f3747bf4SDamien Miller 
114f3747bf4SDamien Miller static int
key_id_cmp(struct revoked_key_id * a,struct revoked_key_id * b)115f3747bf4SDamien Miller key_id_cmp(struct revoked_key_id *a, struct revoked_key_id *b)
116f3747bf4SDamien Miller {
117f3747bf4SDamien Miller 	return strcmp(a->key_id, b->key_id);
118f3747bf4SDamien Miller }
119f3747bf4SDamien Miller 
120f3747bf4SDamien Miller static int
blob_cmp(struct revoked_blob * a,struct revoked_blob * b)121f3747bf4SDamien Miller blob_cmp(struct revoked_blob *a, struct revoked_blob *b)
122f3747bf4SDamien Miller {
123f3747bf4SDamien Miller 	int r;
124f3747bf4SDamien Miller 
125f3747bf4SDamien Miller 	if (a->len != b->len) {
1269136ec13Sderaadt@openbsd.org 		if ((r = memcmp(a->blob, b->blob, MINIMUM(a->len, b->len))) != 0)
127f3747bf4SDamien Miller 			return r;
128f3747bf4SDamien Miller 		return a->len > b->len ? 1 : -1;
129f3747bf4SDamien Miller 	} else
130f3747bf4SDamien Miller 		return memcmp(a->blob, b->blob, a->len);
131f3747bf4SDamien Miller }
132f3747bf4SDamien Miller 
133f3747bf4SDamien Miller struct ssh_krl *
ssh_krl_init(void)134f3747bf4SDamien Miller ssh_krl_init(void)
135f3747bf4SDamien Miller {
136f3747bf4SDamien Miller 	struct ssh_krl *krl;
137f3747bf4SDamien Miller 
138f3747bf4SDamien Miller 	if ((krl = calloc(1, sizeof(*krl))) == NULL)
139f3747bf4SDamien Miller 		return NULL;
140f3747bf4SDamien Miller 	RB_INIT(&krl->revoked_keys);
141f3747bf4SDamien Miller 	RB_INIT(&krl->revoked_sha1s);
1429405c621Sdjm@openbsd.org 	RB_INIT(&krl->revoked_sha256s);
143f3747bf4SDamien Miller 	TAILQ_INIT(&krl->revoked_certs);
144f3747bf4SDamien Miller 	return krl;
145f3747bf4SDamien Miller }
146f3747bf4SDamien Miller 
147f3747bf4SDamien Miller static void
revoked_certs_free(struct revoked_certs * rc)148f3747bf4SDamien Miller revoked_certs_free(struct revoked_certs *rc)
149f3747bf4SDamien Miller {
150f3747bf4SDamien Miller 	struct revoked_serial *rs, *trs;
151f3747bf4SDamien Miller 	struct revoked_key_id *rki, *trki;
152f3747bf4SDamien Miller 
153f3747bf4SDamien Miller 	RB_FOREACH_SAFE(rs, revoked_serial_tree, &rc->revoked_serials, trs) {
154f3747bf4SDamien Miller 		RB_REMOVE(revoked_serial_tree, &rc->revoked_serials, rs);
155f3747bf4SDamien Miller 		free(rs);
156f3747bf4SDamien Miller 	}
157f3747bf4SDamien Miller 	RB_FOREACH_SAFE(rki, revoked_key_id_tree, &rc->revoked_key_ids, trki) {
158f3747bf4SDamien Miller 		RB_REMOVE(revoked_key_id_tree, &rc->revoked_key_ids, rki);
159f3747bf4SDamien Miller 		free(rki->key_id);
160f3747bf4SDamien Miller 		free(rki);
161f3747bf4SDamien Miller 	}
16274de254bSdjm@openbsd.org 	sshkey_free(rc->ca_key);
163f3747bf4SDamien Miller }
164f3747bf4SDamien Miller 
165f3747bf4SDamien Miller void
ssh_krl_free(struct ssh_krl * krl)166f3747bf4SDamien Miller ssh_krl_free(struct ssh_krl *krl)
167f3747bf4SDamien Miller {
168f3747bf4SDamien Miller 	struct revoked_blob *rb, *trb;
169f3747bf4SDamien Miller 	struct revoked_certs *rc, *trc;
170f3747bf4SDamien Miller 
171f3747bf4SDamien Miller 	if (krl == NULL)
172f3747bf4SDamien Miller 		return;
173f3747bf4SDamien Miller 
174f3747bf4SDamien Miller 	free(krl->comment);
175f3747bf4SDamien Miller 	RB_FOREACH_SAFE(rb, revoked_blob_tree, &krl->revoked_keys, trb) {
176f3747bf4SDamien Miller 		RB_REMOVE(revoked_blob_tree, &krl->revoked_keys, rb);
177f3747bf4SDamien Miller 		free(rb->blob);
178f3747bf4SDamien Miller 		free(rb);
179f3747bf4SDamien Miller 	}
180f3747bf4SDamien Miller 	RB_FOREACH_SAFE(rb, revoked_blob_tree, &krl->revoked_sha1s, trb) {
181f3747bf4SDamien Miller 		RB_REMOVE(revoked_blob_tree, &krl->revoked_sha1s, rb);
182f3747bf4SDamien Miller 		free(rb->blob);
183f3747bf4SDamien Miller 		free(rb);
184f3747bf4SDamien Miller 	}
1859405c621Sdjm@openbsd.org 	RB_FOREACH_SAFE(rb, revoked_blob_tree, &krl->revoked_sha256s, trb) {
1869405c621Sdjm@openbsd.org 		RB_REMOVE(revoked_blob_tree, &krl->revoked_sha256s, rb);
1879405c621Sdjm@openbsd.org 		free(rb->blob);
1889405c621Sdjm@openbsd.org 		free(rb);
1899405c621Sdjm@openbsd.org 	}
190f3747bf4SDamien Miller 	TAILQ_FOREACH_SAFE(rc, &krl->revoked_certs, entry, trc) {
191f3747bf4SDamien Miller 		TAILQ_REMOVE(&krl->revoked_certs, rc, entry);
192f3747bf4SDamien Miller 		revoked_certs_free(rc);
193f3747bf4SDamien Miller 	}
194f3747bf4SDamien Miller }
195f3747bf4SDamien Miller 
196f3747bf4SDamien Miller void
ssh_krl_set_version(struct ssh_krl * krl,u_int64_t version)197f3747bf4SDamien Miller ssh_krl_set_version(struct ssh_krl *krl, u_int64_t version)
198f3747bf4SDamien Miller {
199f3747bf4SDamien Miller 	krl->krl_version = version;
200f3747bf4SDamien Miller }
201f3747bf4SDamien Miller 
20274de254bSdjm@openbsd.org int
ssh_krl_set_comment(struct ssh_krl * krl,const char * comment)203f3747bf4SDamien Miller ssh_krl_set_comment(struct ssh_krl *krl, const char *comment)
204f3747bf4SDamien Miller {
205f3747bf4SDamien Miller 	free(krl->comment);
206f3747bf4SDamien Miller 	if ((krl->comment = strdup(comment)) == NULL)
20774de254bSdjm@openbsd.org 		return SSH_ERR_ALLOC_FAIL;
20874de254bSdjm@openbsd.org 	return 0;
209f3747bf4SDamien Miller }
210f3747bf4SDamien Miller 
211f3747bf4SDamien Miller /*
212f3747bf4SDamien Miller  * Find the revoked_certs struct for a CA key. If allow_create is set then
213f3747bf4SDamien Miller  * create a new one in the tree if one did not exist already.
214f3747bf4SDamien Miller  */
215f3747bf4SDamien Miller static int
revoked_certs_for_ca_key(struct ssh_krl * krl,const struct sshkey * ca_key,struct revoked_certs ** rcp,int allow_create)21674de254bSdjm@openbsd.org revoked_certs_for_ca_key(struct ssh_krl *krl, const struct sshkey *ca_key,
217f3747bf4SDamien Miller     struct revoked_certs **rcp, int allow_create)
218f3747bf4SDamien Miller {
219f3747bf4SDamien Miller 	struct revoked_certs *rc;
22074de254bSdjm@openbsd.org 	int r;
221f3747bf4SDamien Miller 
222f3747bf4SDamien Miller 	*rcp = NULL;
223f3747bf4SDamien Miller 	TAILQ_FOREACH(rc, &krl->revoked_certs, entry) {
224669aee99Sdjm@openbsd.org 		if ((ca_key == NULL && rc->ca_key == NULL) ||
225669aee99Sdjm@openbsd.org 		    sshkey_equal(rc->ca_key, ca_key)) {
226f3747bf4SDamien Miller 			*rcp = rc;
227f3747bf4SDamien Miller 			return 0;
228f3747bf4SDamien Miller 		}
229f3747bf4SDamien Miller 	}
230f3747bf4SDamien Miller 	if (!allow_create)
231f3747bf4SDamien Miller 		return 0;
232f3747bf4SDamien Miller 	/* If this CA doesn't exist in the list then add it now */
233f3747bf4SDamien Miller 	if ((rc = calloc(1, sizeof(*rc))) == NULL)
23474de254bSdjm@openbsd.org 		return SSH_ERR_ALLOC_FAIL;
235669aee99Sdjm@openbsd.org 	if (ca_key == NULL)
236669aee99Sdjm@openbsd.org 		rc->ca_key = NULL;
237669aee99Sdjm@openbsd.org 	else if ((r = sshkey_from_private(ca_key, &rc->ca_key)) != 0) {
238f3747bf4SDamien Miller 		free(rc);
23974de254bSdjm@openbsd.org 		return r;
240f3747bf4SDamien Miller 	}
241f3747bf4SDamien Miller 	RB_INIT(&rc->revoked_serials);
242f3747bf4SDamien Miller 	RB_INIT(&rc->revoked_key_ids);
243f3747bf4SDamien Miller 	TAILQ_INSERT_TAIL(&krl->revoked_certs, rc, entry);
244*816036f1Sdjm@openbsd.org 	KRL_DBG(("new CA %s", ca_key == NULL ? "*" : sshkey_type(ca_key)));
245f3747bf4SDamien Miller 	*rcp = rc;
246f3747bf4SDamien Miller 	return 0;
247f3747bf4SDamien Miller }
248f3747bf4SDamien Miller 
249f3747bf4SDamien Miller static int
insert_serial_range(struct revoked_serial_tree * rt,u_int64_t lo,u_int64_t hi)250f3747bf4SDamien Miller insert_serial_range(struct revoked_serial_tree *rt, u_int64_t lo, u_int64_t hi)
251f3747bf4SDamien Miller {
252f3747bf4SDamien Miller 	struct revoked_serial rs, *ers, *crs, *irs;
253f3747bf4SDamien Miller 
254*816036f1Sdjm@openbsd.org 	KRL_DBG(("insert %llu:%llu", lo, hi));
2551d2c4564SDamien Miller 	memset(&rs, 0, sizeof(rs));
256f3747bf4SDamien Miller 	rs.lo = lo;
257f3747bf4SDamien Miller 	rs.hi = hi;
258f3747bf4SDamien Miller 	ers = RB_NFIND(revoked_serial_tree, rt, &rs);
259f3747bf4SDamien Miller 	if (ers == NULL || serial_cmp(ers, &rs) != 0) {
260f3747bf4SDamien Miller 		/* No entry matches. Just insert */
261f3747bf4SDamien Miller 		if ((irs = malloc(sizeof(rs))) == NULL)
26274de254bSdjm@openbsd.org 			return SSH_ERR_ALLOC_FAIL;
263f3747bf4SDamien Miller 		memcpy(irs, &rs, sizeof(*irs));
264f3747bf4SDamien Miller 		ers = RB_INSERT(revoked_serial_tree, rt, irs);
265f3747bf4SDamien Miller 		if (ers != NULL) {
266*816036f1Sdjm@openbsd.org 			KRL_DBG(("bad: ers != NULL"));
267f3747bf4SDamien Miller 			/* Shouldn't happen */
268a7522d9fSDamien Miller 			free(irs);
269e7fd952fSdjm@openbsd.org 			return SSH_ERR_INTERNAL_ERROR;
270f3747bf4SDamien Miller 		}
271f3747bf4SDamien Miller 		ers = irs;
272f3747bf4SDamien Miller 	} else {
273*816036f1Sdjm@openbsd.org 		KRL_DBG(("overlap found %llu:%llu", ers->lo, ers->hi));
274f3747bf4SDamien Miller 		/*
275f3747bf4SDamien Miller 		 * The inserted entry overlaps an existing one. Grow the
276f3747bf4SDamien Miller 		 * existing entry.
277f3747bf4SDamien Miller 		 */
278f3747bf4SDamien Miller 		if (ers->lo > lo)
279f3747bf4SDamien Miller 			ers->lo = lo;
280f3747bf4SDamien Miller 		if (ers->hi < hi)
281f3747bf4SDamien Miller 			ers->hi = hi;
282f3747bf4SDamien Miller 	}
283e7fd952fSdjm@openbsd.org 
284f3747bf4SDamien Miller 	/*
285f3747bf4SDamien Miller 	 * The inserted or revised range might overlap or abut adjacent ones;
286f3747bf4SDamien Miller 	 * coalesce as necessary.
287f3747bf4SDamien Miller 	 */
288f3747bf4SDamien Miller 
289f3747bf4SDamien Miller 	/* Check predecessors */
290f3747bf4SDamien Miller 	while ((crs = RB_PREV(revoked_serial_tree, rt, ers)) != NULL) {
291*816036f1Sdjm@openbsd.org 		KRL_DBG(("pred %llu:%llu", crs->lo, crs->hi));
292f3747bf4SDamien Miller 		if (ers->lo != 0 && crs->hi < ers->lo - 1)
293f3747bf4SDamien Miller 			break;
294f3747bf4SDamien Miller 		/* This entry overlaps. */
295f3747bf4SDamien Miller 		if (crs->lo < ers->lo) {
296f3747bf4SDamien Miller 			ers->lo = crs->lo;
297*816036f1Sdjm@openbsd.org 			KRL_DBG(("pred extend %llu:%llu", ers->lo, ers->hi));
298f3747bf4SDamien Miller 		}
299f3747bf4SDamien Miller 		RB_REMOVE(revoked_serial_tree, rt, crs);
300f3747bf4SDamien Miller 		free(crs);
301f3747bf4SDamien Miller 	}
302f3747bf4SDamien Miller 	/* Check successors */
303f3747bf4SDamien Miller 	while ((crs = RB_NEXT(revoked_serial_tree, rt, ers)) != NULL) {
304*816036f1Sdjm@openbsd.org 		KRL_DBG(("succ %llu:%llu", crs->lo, crs->hi));
305f3747bf4SDamien Miller 		if (ers->hi != (u_int64_t)-1 && crs->lo > ers->hi + 1)
306f3747bf4SDamien Miller 			break;
307f3747bf4SDamien Miller 		/* This entry overlaps. */
308f3747bf4SDamien Miller 		if (crs->hi > ers->hi) {
309f3747bf4SDamien Miller 			ers->hi = crs->hi;
310*816036f1Sdjm@openbsd.org 			KRL_DBG(("succ extend %llu:%llu", ers->lo, ers->hi));
311f3747bf4SDamien Miller 		}
312f3747bf4SDamien Miller 		RB_REMOVE(revoked_serial_tree, rt, crs);
313f3747bf4SDamien Miller 		free(crs);
314f3747bf4SDamien Miller 	}
315*816036f1Sdjm@openbsd.org 	KRL_DBG(("done, final %llu:%llu", ers->lo, ers->hi));
316f3747bf4SDamien Miller 	return 0;
317f3747bf4SDamien Miller }
318f3747bf4SDamien Miller 
319f3747bf4SDamien Miller int
ssh_krl_revoke_cert_by_serial(struct ssh_krl * krl,const struct sshkey * ca_key,u_int64_t serial)32074de254bSdjm@openbsd.org ssh_krl_revoke_cert_by_serial(struct ssh_krl *krl, const struct sshkey *ca_key,
321f3747bf4SDamien Miller     u_int64_t serial)
322f3747bf4SDamien Miller {
323f3747bf4SDamien Miller 	return ssh_krl_revoke_cert_by_serial_range(krl, ca_key, serial, serial);
324f3747bf4SDamien Miller }
325f3747bf4SDamien Miller 
326f3747bf4SDamien Miller int
ssh_krl_revoke_cert_by_serial_range(struct ssh_krl * krl,const struct sshkey * ca_key,u_int64_t lo,u_int64_t hi)327e7fd952fSdjm@openbsd.org ssh_krl_revoke_cert_by_serial_range(struct ssh_krl *krl,
328e7fd952fSdjm@openbsd.org     const struct sshkey *ca_key, u_int64_t lo, u_int64_t hi)
329f3747bf4SDamien Miller {
330f3747bf4SDamien Miller 	struct revoked_certs *rc;
33174de254bSdjm@openbsd.org 	int r;
332f3747bf4SDamien Miller 
333f3747bf4SDamien Miller 	if (lo > hi || lo == 0)
334e7fd952fSdjm@openbsd.org 		return SSH_ERR_INVALID_ARGUMENT;
33574de254bSdjm@openbsd.org 	if ((r = revoked_certs_for_ca_key(krl, ca_key, &rc, 1)) != 0)
33674de254bSdjm@openbsd.org 		return r;
337f3747bf4SDamien Miller 	return insert_serial_range(&rc->revoked_serials, lo, hi);
338f3747bf4SDamien Miller }
339f3747bf4SDamien Miller 
340f3747bf4SDamien Miller int
ssh_krl_revoke_cert_by_key_id(struct ssh_krl * krl,const struct sshkey * ca_key,const char * key_id)34174de254bSdjm@openbsd.org ssh_krl_revoke_cert_by_key_id(struct ssh_krl *krl, const struct sshkey *ca_key,
342f3747bf4SDamien Miller     const char *key_id)
343f3747bf4SDamien Miller {
344f3747bf4SDamien Miller 	struct revoked_key_id *rki, *erki;
345f3747bf4SDamien Miller 	struct revoked_certs *rc;
34674de254bSdjm@openbsd.org 	int r;
347f3747bf4SDamien Miller 
34874de254bSdjm@openbsd.org 	if ((r = revoked_certs_for_ca_key(krl, ca_key, &rc, 1)) != 0)
34974de254bSdjm@openbsd.org 		return r;
350f3747bf4SDamien Miller 
351*816036f1Sdjm@openbsd.org 	KRL_DBG(("revoke %s", key_id));
352f3747bf4SDamien Miller 	if ((rki = calloc(1, sizeof(*rki))) == NULL ||
353f3747bf4SDamien Miller 	    (rki->key_id = strdup(key_id)) == NULL) {
354f3747bf4SDamien Miller 		free(rki);
35574de254bSdjm@openbsd.org 		return SSH_ERR_ALLOC_FAIL;
356f3747bf4SDamien Miller 	}
357f3747bf4SDamien Miller 	erki = RB_INSERT(revoked_key_id_tree, &rc->revoked_key_ids, rki);
358f3747bf4SDamien Miller 	if (erki != NULL) {
359f3747bf4SDamien Miller 		free(rki->key_id);
360f3747bf4SDamien Miller 		free(rki);
361f3747bf4SDamien Miller 	}
362f3747bf4SDamien Miller 	return 0;
363f3747bf4SDamien Miller }
364f3747bf4SDamien Miller 
365f3747bf4SDamien Miller /* Convert "key" to a public key blob without any certificate information */
366f3747bf4SDamien Miller static int
plain_key_blob(const struct sshkey * key,u_char ** blob,size_t * blen)36774de254bSdjm@openbsd.org plain_key_blob(const struct sshkey *key, u_char **blob, size_t *blen)
368f3747bf4SDamien Miller {
36974de254bSdjm@openbsd.org 	struct sshkey *kcopy;
370f3747bf4SDamien Miller 	int r;
371f3747bf4SDamien Miller 
37274de254bSdjm@openbsd.org 	if ((r = sshkey_from_private(key, &kcopy)) != 0)
37374de254bSdjm@openbsd.org 		return r;
37474de254bSdjm@openbsd.org 	if (sshkey_is_cert(kcopy)) {
37574de254bSdjm@openbsd.org 		if ((r = sshkey_drop_cert(kcopy)) != 0) {
37674de254bSdjm@openbsd.org 			sshkey_free(kcopy);
37774de254bSdjm@openbsd.org 			return r;
378f3747bf4SDamien Miller 		}
379f3747bf4SDamien Miller 	}
38074de254bSdjm@openbsd.org 	r = sshkey_to_blob(kcopy, blob, blen);
381905fe30fSmarkus@openbsd.org 	sshkey_free(kcopy);
3828668706dSDamien Miller 	return r;
383f3747bf4SDamien Miller }
384f3747bf4SDamien Miller 
385f3747bf4SDamien Miller /* Revoke a key blob. Ownership of blob is transferred to the tree */
386f3747bf4SDamien Miller static int
revoke_blob(struct revoked_blob_tree * rbt,u_char * blob,size_t len)387e7fd952fSdjm@openbsd.org revoke_blob(struct revoked_blob_tree *rbt, u_char *blob, size_t len)
388f3747bf4SDamien Miller {
389f3747bf4SDamien Miller 	struct revoked_blob *rb, *erb;
390f3747bf4SDamien Miller 
391f3747bf4SDamien Miller 	if ((rb = calloc(1, sizeof(*rb))) == NULL)
39274de254bSdjm@openbsd.org 		return SSH_ERR_ALLOC_FAIL;
393f3747bf4SDamien Miller 	rb->blob = blob;
394f3747bf4SDamien Miller 	rb->len = len;
395f3747bf4SDamien Miller 	erb = RB_INSERT(revoked_blob_tree, rbt, rb);
396f3747bf4SDamien Miller 	if (erb != NULL) {
397f3747bf4SDamien Miller 		free(rb->blob);
398f3747bf4SDamien Miller 		free(rb);
399f3747bf4SDamien Miller 	}
400f3747bf4SDamien Miller 	return 0;
401f3747bf4SDamien Miller }
402f3747bf4SDamien Miller 
403f3747bf4SDamien Miller int
ssh_krl_revoke_key_explicit(struct ssh_krl * krl,const struct sshkey * key)40474de254bSdjm@openbsd.org ssh_krl_revoke_key_explicit(struct ssh_krl *krl, const struct sshkey *key)
405f3747bf4SDamien Miller {
406f3747bf4SDamien Miller 	u_char *blob;
40774de254bSdjm@openbsd.org 	size_t len;
40874de254bSdjm@openbsd.org 	int r;
409f3747bf4SDamien Miller 
410*816036f1Sdjm@openbsd.org 	debug3_f("revoke type %s", sshkey_type(key));
41174de254bSdjm@openbsd.org 	if ((r = plain_key_blob(key, &blob, &len)) != 0)
41274de254bSdjm@openbsd.org 		return r;
413f3747bf4SDamien Miller 	return revoke_blob(&krl->revoked_keys, blob, len);
414f3747bf4SDamien Miller }
415f3747bf4SDamien Miller 
4169405c621Sdjm@openbsd.org static int
revoke_by_hash(struct revoked_blob_tree * target,const u_char * p,size_t len)4179405c621Sdjm@openbsd.org revoke_by_hash(struct revoked_blob_tree *target, const u_char *p, size_t len)
418f3747bf4SDamien Miller {
419f3747bf4SDamien Miller 	u_char *blob;
42074de254bSdjm@openbsd.org 	int r;
421f3747bf4SDamien Miller 
4229405c621Sdjm@openbsd.org 	/* need to copy hash, as revoke_blob steals ownership */
4239405c621Sdjm@openbsd.org 	if ((blob = malloc(len)) == NULL)
4249405c621Sdjm@openbsd.org 		return SSH_ERR_SYSTEM_ERROR;
4259405c621Sdjm@openbsd.org 	memcpy(blob, p, len);
4269405c621Sdjm@openbsd.org 	if ((r = revoke_blob(target, blob, len)) != 0) {
4279405c621Sdjm@openbsd.org 		free(blob);
42874de254bSdjm@openbsd.org 		return r;
4299405c621Sdjm@openbsd.org 	}
4309405c621Sdjm@openbsd.org 	return 0;
4319405c621Sdjm@openbsd.org }
4329405c621Sdjm@openbsd.org 
4339405c621Sdjm@openbsd.org int
ssh_krl_revoke_key_sha1(struct ssh_krl * krl,const u_char * p,size_t len)4349405c621Sdjm@openbsd.org ssh_krl_revoke_key_sha1(struct ssh_krl *krl, const u_char *p, size_t len)
4359405c621Sdjm@openbsd.org {
436*816036f1Sdjm@openbsd.org 	debug3_f("revoke by sha1");
4379405c621Sdjm@openbsd.org 	if (len != 20)
4389405c621Sdjm@openbsd.org 		return SSH_ERR_INVALID_FORMAT;
4399405c621Sdjm@openbsd.org 	return revoke_by_hash(&krl->revoked_sha1s, p, len);
4409405c621Sdjm@openbsd.org }
4419405c621Sdjm@openbsd.org 
4429405c621Sdjm@openbsd.org int
ssh_krl_revoke_key_sha256(struct ssh_krl * krl,const u_char * p,size_t len)4439405c621Sdjm@openbsd.org ssh_krl_revoke_key_sha256(struct ssh_krl *krl, const u_char *p, size_t len)
4449405c621Sdjm@openbsd.org {
445*816036f1Sdjm@openbsd.org 	debug3_f("revoke by sha256");
4469405c621Sdjm@openbsd.org 	if (len != 32)
4479405c621Sdjm@openbsd.org 		return SSH_ERR_INVALID_FORMAT;
4489405c621Sdjm@openbsd.org 	return revoke_by_hash(&krl->revoked_sha256s, p, len);
449f3747bf4SDamien Miller }
450f3747bf4SDamien Miller 
451f3747bf4SDamien Miller int
ssh_krl_revoke_key(struct ssh_krl * krl,const struct sshkey * key)45274de254bSdjm@openbsd.org ssh_krl_revoke_key(struct ssh_krl *krl, const struct sshkey *key)
453f3747bf4SDamien Miller {
4549405c621Sdjm@openbsd.org 	/* XXX replace with SHA256? */
45574de254bSdjm@openbsd.org 	if (!sshkey_is_cert(key))
4569405c621Sdjm@openbsd.org 		return ssh_krl_revoke_key_explicit(krl, key);
457f3747bf4SDamien Miller 
458c28fc62dSdjm@openbsd.org 	if (key->cert->serial == 0) {
459f3747bf4SDamien Miller 		return ssh_krl_revoke_cert_by_key_id(krl,
460f3747bf4SDamien Miller 		    key->cert->signature_key,
461f3747bf4SDamien Miller 		    key->cert->key_id);
462f3747bf4SDamien Miller 	} else {
463f3747bf4SDamien Miller 		return ssh_krl_revoke_cert_by_serial(krl,
464f3747bf4SDamien Miller 		    key->cert->signature_key,
465f3747bf4SDamien Miller 		    key->cert->serial);
466f3747bf4SDamien Miller 	}
467f3747bf4SDamien Miller }
468f3747bf4SDamien Miller 
469f3747bf4SDamien Miller /*
47074de254bSdjm@openbsd.org  * Select the most compact section type to emit next in a KRL based on
47174de254bSdjm@openbsd.org  * the current section type, the run length of contiguous revoked serial
472f3747bf4SDamien Miller  * numbers and the gaps from the last and to the next revoked serial.
473f3747bf4SDamien Miller  * Applies a mostly-accurate bit cost model to select the section type
474f3747bf4SDamien Miller  * that will minimise the size of the resultant KRL.
475f3747bf4SDamien Miller  */
476f3747bf4SDamien Miller static int
choose_next_state(int current_state,u_int64_t contig,int final,u_int64_t last_gap,u_int64_t next_gap,int * force_new_section)477f3747bf4SDamien Miller choose_next_state(int current_state, u_int64_t contig, int final,
478f3747bf4SDamien Miller     u_int64_t last_gap, u_int64_t next_gap, int *force_new_section)
479f3747bf4SDamien Miller {
480f3747bf4SDamien Miller 	int new_state;
481f3747bf4SDamien Miller 	u_int64_t cost, cost_list, cost_range, cost_bitmap, cost_bitmap_restart;
482f3747bf4SDamien Miller 
483f3747bf4SDamien Miller 	/*
484f3747bf4SDamien Miller 	 * Avoid unsigned overflows.
485f3747bf4SDamien Miller 	 * The limits are high enough to avoid confusing the calculations.
486f3747bf4SDamien Miller 	 */
4879136ec13Sderaadt@openbsd.org 	contig = MINIMUM(contig, 1ULL<<31);
4889136ec13Sderaadt@openbsd.org 	last_gap = MINIMUM(last_gap, 1ULL<<31);
4899136ec13Sderaadt@openbsd.org 	next_gap = MINIMUM(next_gap, 1ULL<<31);
490f3747bf4SDamien Miller 
491f3747bf4SDamien Miller 	/*
492f3747bf4SDamien Miller 	 * Calculate the cost to switch from the current state to candidates.
493f3747bf4SDamien Miller 	 * NB. range sections only ever contain a single range, so their
494f3747bf4SDamien Miller 	 * switching cost is independent of the current_state.
495f3747bf4SDamien Miller 	 */
496f3747bf4SDamien Miller 	cost_list = cost_bitmap = cost_bitmap_restart = 0;
497f3747bf4SDamien Miller 	cost_range = 8;
498f3747bf4SDamien Miller 	switch (current_state) {
499f3747bf4SDamien Miller 	case KRL_SECTION_CERT_SERIAL_LIST:
500f3747bf4SDamien Miller 		cost_bitmap_restart = cost_bitmap = 8 + 64;
501f3747bf4SDamien Miller 		break;
502f3747bf4SDamien Miller 	case KRL_SECTION_CERT_SERIAL_BITMAP:
503f3747bf4SDamien Miller 		cost_list = 8;
504f3747bf4SDamien Miller 		cost_bitmap_restart = 8 + 64;
505f3747bf4SDamien Miller 		break;
506f3747bf4SDamien Miller 	case KRL_SECTION_CERT_SERIAL_RANGE:
507f3747bf4SDamien Miller 	case 0:
508f3747bf4SDamien Miller 		cost_bitmap_restart = cost_bitmap = 8 + 64;
509f3747bf4SDamien Miller 		cost_list = 8;
510f3747bf4SDamien Miller 	}
511f3747bf4SDamien Miller 
512f3747bf4SDamien Miller 	/* Estimate base cost in bits of each section type */
513f3747bf4SDamien Miller 	cost_list += 64 * contig + (final ? 0 : 8+64);
514f3747bf4SDamien Miller 	cost_range += (2 * 64) + (final ? 0 : 8+64);
5159136ec13Sderaadt@openbsd.org 	cost_bitmap += last_gap + contig + (final ? 0 : MINIMUM(next_gap, 8+64));
5169136ec13Sderaadt@openbsd.org 	cost_bitmap_restart += contig + (final ? 0 : MINIMUM(next_gap, 8+64));
517f3747bf4SDamien Miller 
518f3747bf4SDamien Miller 	/* Convert to byte costs for actual comparison */
519f3747bf4SDamien Miller 	cost_list = (cost_list + 7) / 8;
520f3747bf4SDamien Miller 	cost_bitmap = (cost_bitmap + 7) / 8;
521f3747bf4SDamien Miller 	cost_bitmap_restart = (cost_bitmap_restart + 7) / 8;
522f3747bf4SDamien Miller 	cost_range = (cost_range + 7) / 8;
523f3747bf4SDamien Miller 
524f3747bf4SDamien Miller 	/* Now pick the best choice */
525f3747bf4SDamien Miller 	*force_new_section = 0;
526f3747bf4SDamien Miller 	new_state = KRL_SECTION_CERT_SERIAL_BITMAP;
527f3747bf4SDamien Miller 	cost = cost_bitmap;
528f3747bf4SDamien Miller 	if (cost_range < cost) {
529f3747bf4SDamien Miller 		new_state = KRL_SECTION_CERT_SERIAL_RANGE;
530f3747bf4SDamien Miller 		cost = cost_range;
531f3747bf4SDamien Miller 	}
532f3747bf4SDamien Miller 	if (cost_list < cost) {
533f3747bf4SDamien Miller 		new_state = KRL_SECTION_CERT_SERIAL_LIST;
534f3747bf4SDamien Miller 		cost = cost_list;
535f3747bf4SDamien Miller 	}
536f3747bf4SDamien Miller 	if (cost_bitmap_restart < cost) {
537f3747bf4SDamien Miller 		new_state = KRL_SECTION_CERT_SERIAL_BITMAP;
538f3747bf4SDamien Miller 		*force_new_section = 1;
539f3747bf4SDamien Miller 		cost = cost_bitmap_restart;
540f3747bf4SDamien Miller 	}
541*816036f1Sdjm@openbsd.org 	KRL_DBG(("contig %llu last_gap %llu next_gap %llu final %d, costs:"
542f3747bf4SDamien Miller 	    "list %llu range %llu bitmap %llu new bitmap %llu, "
543*816036f1Sdjm@openbsd.org 	    "selected 0x%02x%s", (long long unsigned)contig,
544d677ad14SDamien Miller 	    (long long unsigned)last_gap, (long long unsigned)next_gap, final,
545d677ad14SDamien Miller 	    (long long unsigned)cost_list, (long long unsigned)cost_range,
546d677ad14SDamien Miller 	    (long long unsigned)cost_bitmap,
547d677ad14SDamien Miller 	    (long long unsigned)cost_bitmap_restart, new_state,
548e7fd952fSdjm@openbsd.org 	    *force_new_section ? " restart" : ""));
549f3747bf4SDamien Miller 	return new_state;
550f3747bf4SDamien Miller }
551f3747bf4SDamien Miller 
552a165bab6Sdjm@openbsd.org static int
put_bitmap(struct sshbuf * buf,struct bitmap * bitmap)553a165bab6Sdjm@openbsd.org put_bitmap(struct sshbuf *buf, struct bitmap *bitmap)
554a165bab6Sdjm@openbsd.org {
555a165bab6Sdjm@openbsd.org 	size_t len;
556a165bab6Sdjm@openbsd.org 	u_char *blob;
557a165bab6Sdjm@openbsd.org 	int r;
558a165bab6Sdjm@openbsd.org 
559a165bab6Sdjm@openbsd.org 	len = bitmap_nbytes(bitmap);
560a165bab6Sdjm@openbsd.org 	if ((blob = malloc(len)) == NULL)
561a165bab6Sdjm@openbsd.org 		return SSH_ERR_ALLOC_FAIL;
562a165bab6Sdjm@openbsd.org 	if (bitmap_to_string(bitmap, blob, len) != 0) {
563a165bab6Sdjm@openbsd.org 		free(blob);
564a165bab6Sdjm@openbsd.org 		return SSH_ERR_INTERNAL_ERROR;
565a165bab6Sdjm@openbsd.org 	}
566a165bab6Sdjm@openbsd.org 	r = sshbuf_put_bignum2_bytes(buf, blob, len);
567a165bab6Sdjm@openbsd.org 	free(blob);
568a165bab6Sdjm@openbsd.org 	return r;
569a165bab6Sdjm@openbsd.org }
570a165bab6Sdjm@openbsd.org 
571f3747bf4SDamien Miller /* Generate a KRL_SECTION_CERTIFICATES KRL section */
572f3747bf4SDamien Miller static int
revoked_certs_generate(struct revoked_certs * rc,struct sshbuf * buf)57374de254bSdjm@openbsd.org revoked_certs_generate(struct revoked_certs *rc, struct sshbuf *buf)
574f3747bf4SDamien Miller {
575e7fd952fSdjm@openbsd.org 	int final, force_new_sect, r = SSH_ERR_INTERNAL_ERROR;
576f3747bf4SDamien Miller 	u_int64_t i, contig, gap, last = 0, bitmap_start = 0;
577f3747bf4SDamien Miller 	struct revoked_serial *rs, *nrs;
578f3747bf4SDamien Miller 	struct revoked_key_id *rki;
579f3747bf4SDamien Miller 	int next_state, state = 0;
58074de254bSdjm@openbsd.org 	struct sshbuf *sect;
581a165bab6Sdjm@openbsd.org 	struct bitmap *bitmap = NULL;
582f3747bf4SDamien Miller 
58374de254bSdjm@openbsd.org 	if ((sect = sshbuf_new()) == NULL)
58474de254bSdjm@openbsd.org 		return SSH_ERR_ALLOC_FAIL;
585f3747bf4SDamien Miller 
586669aee99Sdjm@openbsd.org 	/* Store the header: optional CA scope key, reserved */
587669aee99Sdjm@openbsd.org 	if (rc->ca_key == NULL) {
588669aee99Sdjm@openbsd.org 		if ((r = sshbuf_put_string(buf, NULL, 0)) != 0)
589669aee99Sdjm@openbsd.org 			goto out;
590669aee99Sdjm@openbsd.org 	} else {
591669aee99Sdjm@openbsd.org 		if ((r = sshkey_puts(rc->ca_key, buf)) != 0)
592669aee99Sdjm@openbsd.org 			goto out;
593669aee99Sdjm@openbsd.org 	}
594669aee99Sdjm@openbsd.org 	if ((r = sshbuf_put_string(buf, NULL, 0)) != 0)
59574de254bSdjm@openbsd.org 		goto out;
596f3747bf4SDamien Miller 
597f3747bf4SDamien Miller 	/* Store the revoked serials.  */
598f3747bf4SDamien Miller 	for (rs = RB_MIN(revoked_serial_tree, &rc->revoked_serials);
599f3747bf4SDamien Miller 	     rs != NULL;
600f3747bf4SDamien Miller 	     rs = RB_NEXT(revoked_serial_tree, &rc->revoked_serials, rs)) {
601*816036f1Sdjm@openbsd.org 		KRL_DBG(("serial %llu:%llu state 0x%02x",
602d677ad14SDamien Miller 		    (long long unsigned)rs->lo, (long long unsigned)rs->hi,
603e7fd952fSdjm@openbsd.org 		    state));
604f3747bf4SDamien Miller 
605f3747bf4SDamien Miller 		/* Check contiguous length and gap to next section (if any) */
606f3747bf4SDamien Miller 		nrs = RB_NEXT(revoked_serial_tree, &rc->revoked_serials, rs);
607f3747bf4SDamien Miller 		final = nrs == NULL;
608