21 #include <openbsd-compat/sys-tree.h>
22 #include <openbsd-compat/sys-queue.h>
52  * Trees of revoked serial numbers, key IDs and keys. This allows
56 /* Tree of serial numbers. XXX make smarter: really need a real sparse bitmap */
108 	if (a->hi >= b->lo && a->lo <= b->hi)  in serial_cmp()
110 	return a->lo < b->lo ? -1 : 1;  in serial_cmp()
116 	return strcmp(a->key_id, b->key_id);  in key_id_cmp()
124 	if (a->len != b->len) {  in blob_cmp()
125 		if ((r = memcmp(a->blob, b->blob, MINIMUM(a->len, b->len))) != 0)  in blob_cmp()
127 		return a->len > b->len ? 1 : -1;  in blob_cmp()
129 		return memcmp(a->blob, b->blob, a->len);  in blob_cmp()
139 	RB_INIT(&krl->revoked_keys);  in ssh_krl_init()
140 	RB_INIT(&krl->revoked_sha1s);  in ssh_krl_init()
141 	RB_INIT(&krl->revoked_sha256s);  in ssh_krl_init()
142 	TAILQ_INIT(&krl->revoked_certs);  in ssh_krl_init()
152 	RB_FOREACH_SAFE(rs, revoked_serial_tree, &rc->revoked_serials, trs) {  in revoked_certs_free()
153 		RB_REMOVE(revoked_serial_tree, &rc->revoked_serials, rs);  in revoked_certs_free()
156 	RB_FOREACH_SAFE(rki, revoked_key_id_tree, &rc->revoked_key_ids, trki) {  in revoked_certs_free()
157 		RB_REMOVE(revoked_key_id_tree, &rc->revoked_key_ids, rki);  in revoked_certs_free()
158 		free(rki->key_id);  in revoked_certs_free()
161 	sshkey_free(rc->ca_key);  in revoked_certs_free()
173 	free(krl->comment);  in ssh_krl_free()
174 	RB_FOREACH_SAFE(rb, revoked_blob_tree, &krl->revoked_keys, trb) {  in ssh_krl_free()
175 		RB_REMOVE(revoked_blob_tree, &krl->revoked_keys, rb);  in ssh_krl_free()
176 		free(rb->blob);  in ssh_krl_free()
179 	RB_FOREACH_SAFE(rb, revoked_blob_tree, &krl->revoked_sha1s, trb) {  in ssh_krl_free()
180 		RB_REMOVE(revoked_blob_tree, &krl->revoked_sha1s, rb);  in ssh_krl_free()
181 		free(rb->blob);  in ssh_krl_free()
184 	RB_FOREACH_SAFE(rb, revoked_blob_tree, &krl->revoked_sha256s, trb) {  in ssh_krl_free()
185 		RB_REMOVE(revoked_blob_tree, &krl->revoked_sha256s, rb);  in ssh_krl_free()
186 		free(rb->blob);  in ssh_krl_free()
189 	TAILQ_FOREACH_SAFE(rc, &krl->revoked_certs, entry, trc) {  in ssh_krl_free()
190 		TAILQ_REMOVE(&krl->revoked_certs, rc, entry);  in ssh_krl_free()
199 	krl->krl_version = version;  in ssh_krl_set_version()
205 	free(krl->comment);  in ssh_krl_set_comment()
206 	if ((krl->comment = strdup(comment)) == NULL)  in ssh_krl_set_comment()
223 	TAILQ_FOREACH(rc, &krl->revoked_certs, entry) {  in revoked_certs_for_ca_key()
224 		if ((ca_key == NULL && rc->ca_key == NULL) ||  in revoked_certs_for_ca_key()
225 		    sshkey_equal(rc->ca_key, ca_key)) {  in revoked_certs_for_ca_key()
236 		rc->ca_key = NULL;  in revoked_certs_for_ca_key()
237 	else if ((r = sshkey_from_private(ca_key, &rc->ca_key)) != 0) {  in revoked_certs_for_ca_key()
241 	RB_INIT(&rc->revoked_serials);  in revoked_certs_for_ca_key()
242 	RB_INIT(&rc->revoked_key_ids);  in revoked_certs_for_ca_key()
243 	TAILQ_INSERT_TAIL(&krl->revoked_certs, rc, entry);  in revoked_certs_for_ca_key()
273 		KRL_DBG(("overlap found %llu:%llu", ers->lo, ers->hi));  in insert_serial_range()
278 		if (ers->lo > lo)  in insert_serial_range()
279 			ers->lo = lo;  in insert_serial_range()
280 		if (ers->hi < hi)  in insert_serial_range()
281 			ers->hi = hi;  in insert_serial_range()
291 		KRL_DBG(("pred %llu:%llu", crs->lo, crs->hi));  in insert_serial_range()
292 		if (ers->lo != 0 && crs->hi < ers->lo - 1)  in insert_serial_range()
295 		if (crs->lo < ers->lo) {  in insert_serial_range()
296 			ers->lo = crs->lo;  in insert_serial_range()
297 			KRL_DBG(("pred extend %llu:%llu", ers->lo, ers->hi));  in insert_serial_range()
304 		KRL_DBG(("succ %llu:%llu", crs->lo, crs->hi));  in insert_serial_range()
305 		if (ers->hi != (u_int64_t)-1 && crs->lo > ers->hi + 1)  in insert_serial_range()
308 		if (crs->hi > ers->hi) {  in insert_serial_range()
309 			ers->hi = crs->hi;  in insert_serial_range()
310 			KRL_DBG(("succ extend %llu:%llu", ers->lo, ers->hi));  in insert_serial_range()
315 	KRL_DBG(("done, final %llu:%llu", ers->lo, ers->hi));  in insert_serial_range()
321     u_int64_t serial)  in ssh_krl_revoke_cert_by_serial()  argument
323 	return ssh_krl_revoke_cert_by_serial_range(krl, ca_key, serial, serial);  in ssh_krl_revoke_cert_by_serial()
337 	return insert_serial_range(&rc->revoked_serials, lo, hi);  in ssh_krl_revoke_cert_by_serial_range()
353 	    (rki->key_id = strdup(key_id)) == NULL) {  in ssh_krl_revoke_cert_by_key_id()
357 	erki = RB_INSERT(revoked_key_id_tree, &rc->revoked_key_ids, rki);  in ssh_krl_revoke_cert_by_key_id()
359 		free(rki->key_id);  in ssh_krl_revoke_cert_by_key_id()
393 	rb->blob = blob;  in revoke_blob()
394 	rb->len = len;  in revoke_blob()
397 		free(rb->blob);  in revoke_blob()
413 	return revoke_blob(&krl->revoked_keys, blob, len);  in ssh_krl_revoke_key_explicit()
439 	return revoke_by_hash(&krl->revoked_sha1s, p, len);  in ssh_krl_revoke_key_sha1()
448 	return revoke_by_hash(&krl->revoked_sha256s, p, len);  in ssh_krl_revoke_key_sha256()
458 	if (key->cert->serial == 0) {  in ssh_krl_revoke_key()
460 		    key->cert->signature_key,  in ssh_krl_revoke_key()
461 		    key->cert->key_id);  in ssh_krl_revoke_key()
464 		    key->cert->signature_key,  in ssh_krl_revoke_key()
465 		    key->cert->serial);  in ssh_krl_revoke_key()
471  * the current section type, the run length of contiguous revoked serial
472  * numbers and the gaps from the last and to the next revoked serial.
473  * Applies a mostly-accurate bit cost model to select the section type
492 	 * Calculate the cost to switch from the current state to candidates.  in choose_next_state()
579 	int next_state, state = 0;  in revoked_certs_generate()  local
587 	if (rc->ca_key == NULL) {  in revoked_certs_generate()
591 		if ((r = sshkey_puts(rc->ca_key, buf)) != 0)  in revoked_certs_generate()
598 	for (rs = RB_MIN(revoked_serial_tree, &rc->revoked_serials);  in revoked_certs_generate()
600 	     rs = RB_NEXT(revoked_serial_tree, &rc->revoked_serials, rs)) {  in revoked_certs_generate()
601 		KRL_DBG(("serial %llu:%llu state 0x%02x",  in revoked_certs_generate()
602 		    (long long unsigned)rs->lo, (long long unsigned)rs->hi,  in revoked_certs_generate()
603 		    state));  in revoked_certs_generate()
606 		nrs = RB_NEXT(revoked_serial_tree, &rc->revoked_serials, rs);  in revoked_certs_generate()
608 		gap = nrs == NULL ? 0 : nrs->lo - rs->hi;  in revoked_certs_generate()
609 		contig = 1 + (rs->hi - rs->lo);  in revoked_certs_generate()
611 		/* Choose next state based on these */  in revoked_certs_generate()
612 		next_state = choose_next_state(state, contig, final,  in revoked_certs_generate()
613 		    state == 0 ? 0 : rs->lo - last, gap, &force_new_sect);  in revoked_certs_generate()
619 		if (state != 0 && (force_new_sect || next_state != state ||  in revoked_certs_generate()
620 		    state == KRL_SECTION_CERT_SERIAL_RANGE)) {  in revoked_certs_generate()
621 			KRL_DBG(("finish state 0x%02x", state));  in revoked_certs_generate()
622 			switch (state) {  in revoked_certs_generate()
633 			if ((r = sshbuf_put_u8(buf, state)) != 0 ||  in revoked_certs_generate()
640 		if (next_state != state || force_new_sect) {  in revoked_certs_generate()
641 			KRL_DBG(("start state 0x%02x",  in revoked_certs_generate()
643 			state = next_state;  in revoked_certs_generate()
645 			switch (state) {  in revoked_certs_generate()
654 				bitmap_start = rs->lo;  in revoked_certs_generate()
662 		/* Perform section-specific processing */  in revoked_certs_generate()
663 		switch (state) {  in revoked_certs_generate()
666 				if ((r = sshbuf_put_u64(sect, rs->lo + i)) != 0)  in revoked_certs_generate()
671 			if ((r = sshbuf_put_u64(sect, rs->lo)) != 0 ||  in revoked_certs_generate()
672 			    (r = sshbuf_put_u64(sect, rs->hi)) != 0)  in revoked_certs_generate()
676 			if (rs->lo - bitmap_start > INT_MAX) {  in revoked_certs_generate()
683 				    rs->lo + i - bitmap_start) != 0) {  in revoked_certs_generate()
690 		last = rs->hi;  in revoked_certs_generate()
693 	if (state != 0) {  in revoked_certs_generate()
694 		KRL_DBG(("serial final flush for state 0x%02x", state));  in revoked_certs_generate()
695 		switch (state) {  in revoked_certs_generate()
706 		if ((r = sshbuf_put_u8(buf, state)) != 0 ||  in revoked_certs_generate()
710 	KRL_DBG(("serial done "));  in revoked_certs_generate()
714 	RB_FOREACH(rki, revoked_key_id_tree, &rc->revoked_key_ids) {  in revoked_certs_generate()
715 		KRL_DBG(("key ID %s", rki->key_id));  in revoked_certs_generate()
716 		if ((r = sshbuf_put_cstring(sect, rki->key_id)) != 0)  in revoked_certs_generate()
740 	if (krl->generated_date == 0)  in ssh_krl_to_blob()
741 		krl->generated_date = time(NULL);  in ssh_krl_to_blob()
747 	if ((r = sshbuf_put(buf, KRL_MAGIC, sizeof(KRL_MAGIC) - 1)) != 0 ||  in ssh_krl_to_blob()
749 	    (r = sshbuf_put_u64(buf, krl->krl_version)) != 0 ||  in ssh_krl_to_blob()
750 	    (r = sshbuf_put_u64(buf, krl->generated_date)) != 0 ||  in ssh_krl_to_blob()
751 	    (r = sshbuf_put_u64(buf, krl->flags)) != 0 ||  in ssh_krl_to_blob()
753 	    (r = sshbuf_put_cstring(buf, krl->comment)) != 0)  in ssh_krl_to_blob()
757 	TAILQ_FOREACH(rc, &krl->revoked_certs, entry) {  in ssh_krl_to_blob()
768 	RB_FOREACH(rb, revoked_blob_tree, &krl->revoked_keys) {  in ssh_krl_to_blob()
769 		KRL_DBG(("key len %zu ", rb->len));  in ssh_krl_to_blob()
770 		if ((r = sshbuf_put_string(sect, rb->blob, rb->len)) != 0)  in ssh_krl_to_blob()
779 	RB_FOREACH(rb, revoked_blob_tree, &krl->revoked_sha1s) {  in ssh_krl_to_blob()
780 		KRL_DBG(("hash len %zu ", rb->len));  in ssh_krl_to_blob()
781 		if ((r = sshbuf_put_string(sect, rb->blob, rb->len)) != 0)  in ssh_krl_to_blob()
791 	RB_FOREACH(rb, revoked_blob_tree, &krl->revoked_sha256s) {  in ssh_krl_to_blob()
792 		KRL_DBG(("hash len %zu ", rb->len));  in ssh_krl_to_blob()
793 		if ((r = sshbuf_put_string(sect, rb->blob, rb->len)) != 0)  in ssh_krl_to_blob()
873 	u_int64_t serial, serial_lo, serial_hi;  in parse_revoked_certs()  local
900 				if ((r = sshbuf_get_u64(subsect, &serial)) != 0)  in parse_revoked_certs()
903 				    ca_key, serial)) != 0)  in parse_revoked_certs()
929 			for (serial = 0; serial < (u_int64_t)nbits; serial++) {  in parse_revoked_certs()
930 				if (serial > 0 && serial_lo + serial == 0) {  in parse_revoked_certs()
935 				if (!bitmap_test_bit(bitmap, serial))  in parse_revoked_certs()
938 				    ca_key, serial_lo + serial)) != 0)  in parse_revoked_certs()
1057 	if ((r = sshbuf_cmp(buf, 0, KRL_MAGIC, sizeof(KRL_MAGIC) - 1)) != 0) {  in ssh_krl_from_blob()
1072 	if ((r = sshbuf_consume(copy, sizeof(KRL_MAGIC) - 1)) != 0 ||  in ssh_krl_from_blob()
1080 	if ((r = sshbuf_get_u64(copy, &krl->krl_version)) != 0 ||  in ssh_krl_from_blob()
1081 	    (r = sshbuf_get_u64(copy, &krl->generated_date)) != 0 ||  in ssh_krl_from_blob()
1082 	    (r = sshbuf_get_u64(copy, &krl->flags)) != 0 ||  in ssh_krl_from_blob()
1084 	    (r = sshbuf_get_cstring(copy, &krl->comment, NULL)) != 0) {  in ssh_krl_from_blob()
1088 	format_timestamp(krl->generated_date, timestamp, sizeof(timestamp));  in ssh_krl_from_blob()
1090 	    (long long unsigned)krl->krl_version, timestamp,  in ssh_krl_from_blob()
1091 	    *krl->comment ? ": " : "", krl->comment);  in ssh_krl_from_blob()
1109 			    &krl->revoked_keys, 0)) != 0)  in ssh_krl_from_blob()
1114 			    &krl->revoked_sha1s, 20)) != 0)  in ssh_krl_from_blob()
1119 			    &krl->revoked_sha256s, 32)) != 0)  in ssh_krl_from_blob()
1156 /* Checks certificate serial number and key ID revocation */
1165 	rki.key_id = key->cert->key_id;  in is_cert_revoked()
1166 	erki = RB_FIND(revoked_key_id_tree, &rc->revoked_key_ids, &rki);  in is_cert_revoked()
1176 	if (key->cert->serial == 0)  in is_cert_revoked()
1180 	rs.lo = rs.hi = key->cert->serial;  in is_cert_revoked()
1181 	ers = RB_FIND(revoked_serial_tree, &rc->revoked_serials, &rs);  in is_cert_revoked()
1183 		KRL_DBG(("revoked serial %llu matched %llu:%llu",  in is_cert_revoked()
1184 		    key->cert->serial, ers->lo, ers->hi));  in is_cert_revoked()
1203 	erb = RB_FIND(revoked_blob_tree, &krl->revoked_sha1s, &rb);  in is_key_revoked()
1213 	erb = RB_FIND(revoked_blob_tree, &krl->revoked_sha256s, &rb);  in is_key_revoked()
1224 	erb = RB_FIND(revoked_blob_tree, &krl->revoked_keys, &rb);  in is_key_revoked()
1235 	if ((r = revoked_certs_for_ca_key(krl, key->cert->signature_key,  in is_key_revoked()
1250 	KRL_DBG(("%llu no match", key->cert->serial));  in is_key_revoked()
1264 		if ((r = is_key_revoked(krl, key->cert->signature_key)) != 0)  in ssh_krl_check_key()
1307 	/* Try to print in a KRL spec-compatible format */  in krl_dump()
1308 	format_timestamp(krl->generated_date, timestamp, sizeof(timestamp));  in krl_dump()
1310 	    (unsigned long long)krl->krl_version);  in krl_dump()
1312 	if (krl->comment != NULL && *krl->comment != '\0') {  in krl_dump()
1314 		asmprintf(&fp, INT_MAX, &r, "%s", krl->comment);  in krl_dump()
1320 	RB_FOREACH(rb, revoked_blob_tree, &krl->revoked_keys) {  in krl_dump()
1321 		if ((r = sshkey_from_blob(rb->blob, rb->len, &key)) != 0) {  in krl_dump()
1336 	RB_FOREACH(rb, revoked_blob_tree, &krl->revoked_sha256s) {  in krl_dump()
1337 		fp = tohex(rb->blob, rb->len);  in krl_dump()
1341 	RB_FOREACH(rb, revoked_blob_tree, &krl->revoked_sha1s) {  in krl_dump()
1346 		fp = tohex(rb->blob, rb->len);  in krl_dump()
1351 	TAILQ_FOREACH(rc, &krl->revoked_certs, entry) {  in krl_dump()
1353 		if (rc->ca_key == NULL)  in krl_dump()
1356 			if ((fp = sshkey_fingerprint(rc->ca_key,  in krl_dump()
1363 			    sshkey_ssh_name(rc->ca_key), fp);  in krl_dump()
1366 		RB_FOREACH(rs, revoked_serial_tree, &rc->revoked_serials) {  in krl_dump()
1367 			if (rs->lo == rs->hi) {  in krl_dump()
1368 				fprintf(f, "serial: %llu\n",  in krl_dump()
1369 				    (unsigned long long)rs->lo);  in krl_dump()
1371 				fprintf(f, "serial: %llu-%llu\n",  in krl_dump()
1372 				    (unsigned long long)rs->lo,  in krl_dump()
1373 				    (unsigned long long)rs->hi);  in krl_dump()
1376 		RB_FOREACH(rki, revoked_key_id_tree, &rc->revoked_key_ids) {  in krl_dump()
1382 			asmprintf(&fp, INT_MAX, &r, "%s", rki->key_id);  in krl_dump()