1 /* $OpenBSD: krl.c,v 1.59 2023/07/17 05:22:30 djm Exp $ */
3 * Copyright (c) 2012 Damien Miller <djm@mindrot.org>
5 * Permission to use, copy, modify, and distribute this software for any
6 * purpose with or without fee is hereby granted, provided that the above
7 * copyright notice and this permission notice appear in all copies.
9 * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
10 * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
11 * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
12 * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
13 * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
14 * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
15 * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
20 #include <sys/types.h>
21 #include <openbsd-compat/sys-tree.h>
22 #include <openbsd-compat/sys-queue.h>
44 /* #define DEBUG_KRL */
46 # define KRL_DBG(x) debug3_f x
52 * Trees of revoked serial numbers, key IDs and keys. This allows
53 * quick searching, querying and producing lists in canonical order.
56 /* Tree of serial numbers. XXX make smarter: really need a real sparse bitmap */
57 struct revoked_serial
{
59 RB_ENTRY(revoked_serial
) tree_entry
;
61 static int serial_cmp(struct revoked_serial
*a
, struct revoked_serial
*b
);
62 RB_HEAD(revoked_serial_tree
, revoked_serial
);
63 RB_GENERATE_STATIC(revoked_serial_tree
, revoked_serial
, tree_entry
, serial_cmp
)
66 struct revoked_key_id
{
68 RB_ENTRY(revoked_key_id
) tree_entry
;
70 static int key_id_cmp(struct revoked_key_id
*a
, struct revoked_key_id
*b
);
71 RB_HEAD(revoked_key_id_tree
, revoked_key_id
);
72 RB_GENERATE_STATIC(revoked_key_id_tree
, revoked_key_id
, tree_entry
, key_id_cmp
)
74 /* Tree of blobs (used for keys and fingerprints) */
78 RB_ENTRY(revoked_blob
) tree_entry
;
80 static int blob_cmp(struct revoked_blob
*a
, struct revoked_blob
*b
);
81 RB_HEAD(revoked_blob_tree
, revoked_blob
);
82 RB_GENERATE_STATIC(revoked_blob_tree
, revoked_blob
, tree_entry
, blob_cmp
)
84 /* Tracks revoked certs for a single CA */
85 struct revoked_certs
{
86 struct sshkey
*ca_key
;
87 struct revoked_serial_tree revoked_serials
;
88 struct revoked_key_id_tree revoked_key_ids
;
89 TAILQ_ENTRY(revoked_certs
) entry
;
91 TAILQ_HEAD(revoked_certs_list
, revoked_certs
);
94 u_int64_t krl_version
;
95 u_int64_t generated_date
;
98 struct revoked_blob_tree revoked_keys
;
99 struct revoked_blob_tree revoked_sha1s
;
100 struct revoked_blob_tree revoked_sha256s
;
101 struct revoked_certs_list revoked_certs
;
104 /* Return equal if a and b overlap */
106 serial_cmp(struct revoked_serial
*a
, struct revoked_serial
*b
)
108 if (a
->hi
>= b
->lo
&& a
->lo
<= b
->hi
)
110 return a
->lo
< b
->lo
? -1 : 1;
114 key_id_cmp(struct revoked_key_id
*a
, struct revoked_key_id
*b
)
116 return strcmp(a
->key_id
, b
->key_id
);
120 blob_cmp(struct revoked_blob
*a
, struct revoked_blob
*b
)
124 if (a
->len
!= b
->len
) {
125 if ((r
= memcmp(a
->blob
, b
->blob
, MINIMUM(a
->len
, b
->len
))) != 0)
127 return a
->len
> b
->len
? 1 : -1;
129 return memcmp(a
->blob
, b
->blob
, a
->len
);
137 if ((krl
= calloc(1, sizeof(*krl
))) == NULL
)
139 RB_INIT(&krl
->revoked_keys
);
140 RB_INIT(&krl
->revoked_sha1s
);
141 RB_INIT(&krl
->revoked_sha256s
);
142 TAILQ_INIT(&krl
->revoked_certs
);
147 revoked_certs_free(struct revoked_certs
*rc
)
149 struct revoked_serial
*rs
, *trs
;
150 struct revoked_key_id
*rki
, *trki
;
152 RB_FOREACH_SAFE(rs
, revoked_serial_tree
, &rc
->revoked_serials
, trs
) {
153 RB_REMOVE(revoked_serial_tree
, &rc
->revoked_serials
, rs
);
156 RB_FOREACH_SAFE(rki
, revoked_key_id_tree
, &rc
->revoked_key_ids
, trki
) {
157 RB_REMOVE(revoked_key_id_tree
, &rc
->revoked_key_ids
, rki
);
161 sshkey_free(rc
->ca_key
);
165 ssh_krl_free(struct ssh_krl
*krl
)
167 struct revoked_blob
*rb
, *trb
;
168 struct revoked_certs
*rc
, *trc
;
174 RB_FOREACH_SAFE(rb
, revoked_blob_tree
, &krl
->revoked_keys
, trb
) {
175 RB_REMOVE(revoked_blob_tree
, &krl
->revoked_keys
, rb
);
179 RB_FOREACH_SAFE(rb
, revoked_blob_tree
, &krl
->revoked_sha1s
, trb
) {
180 RB_REMOVE(revoked_blob_tree
, &krl
->revoked_sha1s
, rb
);
184 RB_FOREACH_SAFE(rb
, revoked_blob_tree
, &krl
->revoked_sha256s
, trb
) {
185 RB_REMOVE(revoked_blob_tree
, &krl
->revoked_sha256s
, rb
);
189 TAILQ_FOREACH_SAFE(rc
, &krl
->revoked_certs
, entry
, trc
) {
190 TAILQ_REMOVE(&krl
->revoked_certs
, rc
, entry
);
191 revoked_certs_free(rc
);
197 ssh_krl_set_version(struct ssh_krl
*krl
, u_int64_t version
)
199 krl
->krl_version
= version
;
203 ssh_krl_set_comment(struct ssh_krl
*krl
, const char *comment
)
206 if ((krl
->comment
= strdup(comment
)) == NULL
)
207 return SSH_ERR_ALLOC_FAIL
;
212 * Find the revoked_certs struct for a CA key. If allow_create is set then
213 * create a new one in the tree if one did not exist already.
216 revoked_certs_for_ca_key(struct ssh_krl
*krl
, const struct sshkey
*ca_key
,
217 struct revoked_certs
**rcp
, int allow_create
)
219 struct revoked_certs
*rc
;
223 TAILQ_FOREACH(rc
, &krl
->revoked_certs
, entry
) {
224 if ((ca_key
== NULL
&& rc
->ca_key
== NULL
) ||
225 sshkey_equal(rc
->ca_key
, ca_key
)) {
232 /* If this CA doesn't exist in the list then add it now */
233 if ((rc
= calloc(1, sizeof(*rc
))) == NULL
)
234 return SSH_ERR_ALLOC_FAIL
;
237 else if ((r
= sshkey_from_private(ca_key
, &rc
->ca_key
)) != 0) {
241 RB_INIT(&rc
->revoked_serials
);
242 RB_INIT(&rc
->revoked_key_ids
);
243 TAILQ_INSERT_TAIL(&krl
->revoked_certs
, rc
, entry
);
244 KRL_DBG(("new CA %s", ca_key
== NULL
? "*" : sshkey_type(ca_key
)));
250 insert_serial_range(struct revoked_serial_tree
*rt
, u_int64_t lo
, u_int64_t hi
)
252 struct revoked_serial rs
, *ers
, *crs
, *irs
;
254 KRL_DBG(("insert %llu:%llu", lo
, hi
));
255 memset(&rs
, 0, sizeof(rs
));
258 ers
= RB_NFIND(revoked_serial_tree
, rt
, &rs
);
259 if (ers
== NULL
|| serial_cmp(ers
, &rs
) != 0) {
260 /* No entry matches. Just insert */
261 if ((irs
= malloc(sizeof(rs
))) == NULL
)
262 return SSH_ERR_ALLOC_FAIL
;
263 memcpy(irs
, &rs
, sizeof(*irs
));
264 ers
= RB_INSERT(revoked_serial_tree
, rt
, irs
);
266 KRL_DBG(("bad: ers != NULL"));
267 /* Shouldn't happen */
269 return SSH_ERR_INTERNAL_ERROR
;
273 KRL_DBG(("overlap found %llu:%llu", ers
->lo
, ers
->hi
));
275 * The inserted entry overlaps an existing one. Grow the
285 * The inserted or revised range might overlap or abut adjacent ones;
286 * coalesce as necessary.
289 /* Check predecessors */
290 while ((crs
= RB_PREV(revoked_serial_tree
, rt
, ers
)) != NULL
) {
291 KRL_DBG(("pred %llu:%llu", crs
->lo
, crs
->hi
));
292 if (ers
->lo
!= 0 && crs
->hi
< ers
->lo
- 1)
294 /* This entry overlaps. */
295 if (crs
->lo
< ers
->lo
) {
297 KRL_DBG(("pred extend %llu:%llu", ers
->lo
, ers
->hi
));
299 RB_REMOVE(revoked_serial_tree
, rt
, crs
);
302 /* Check successors */
303 while ((crs
= RB_NEXT(revoked_serial_tree
, rt
, ers
)) != NULL
) {
304 KRL_DBG(("succ %llu:%llu", crs
->lo
, crs
->hi
));
305 if (ers
->hi
!= (u_int64_t
)-1 && crs
->lo
> ers
->hi
+ 1)
307 /* This entry overlaps. */
308 if (crs
->hi
> ers
->hi
) {
310 KRL_DBG(("succ extend %llu:%llu", ers
->lo
, ers
->hi
));
312 RB_REMOVE(revoked_serial_tree
, rt
, crs
);
315 KRL_DBG(("done, final %llu:%llu", ers
->lo
, ers
->hi
));
320 ssh_krl_revoke_cert_by_serial(struct ssh_krl
*krl
, const struct sshkey
*ca_key
,
323 return ssh_krl_revoke_cert_by_serial_range(krl
, ca_key
, serial
, serial
);
327 ssh_krl_revoke_cert_by_serial_range(struct ssh_krl
*krl
,
328 const struct sshkey
*ca_key
, u_int64_t lo
, u_int64_t hi
)
330 struct revoked_certs
*rc
;
333 if (lo
> hi
|| lo
== 0)
334 return SSH_ERR_INVALID_ARGUMENT
;
335 if ((r
= revoked_certs_for_ca_key(krl
, ca_key
, &rc
, 1)) != 0)
337 return insert_serial_range(&rc
->revoked_serials
, lo
, hi
);
341 ssh_krl_revoke_cert_by_key_id(struct ssh_krl
*krl
, const struct sshkey
*ca_key
,
344 struct revoked_key_id
*rki
, *erki
;
345 struct revoked_certs
*rc
;
348 if ((r
= revoked_certs_for_ca_key(krl
, ca_key
, &rc
, 1)) != 0)
351 KRL_DBG(("revoke %s", key_id
));
352 if ((rki
= calloc(1, sizeof(*rki
))) == NULL
||
353 (rki
->key_id
= strdup(key_id
)) == NULL
) {
355 return SSH_ERR_ALLOC_FAIL
;
357 erki
= RB_INSERT(revoked_key_id_tree
, &rc
->revoked_key_ids
, rki
);
365 /* Convert "key" to a public key blob without any certificate information */
367 plain_key_blob(const struct sshkey
*key
, u_char
**blob
, size_t *blen
)
369 struct sshkey
*kcopy
;
372 if ((r
= sshkey_from_private(key
, &kcopy
)) != 0)
374 if (sshkey_is_cert(kcopy
)) {
375 if ((r
= sshkey_drop_cert(kcopy
)) != 0) {
380 r
= sshkey_to_blob(kcopy
, blob
, blen
);
385 /* Revoke a key blob. Ownership of blob is transferred to the tree */
387 revoke_blob(struct revoked_blob_tree
*rbt
, u_char
*blob
, size_t len
)
389 struct revoked_blob
*rb
, *erb
;
391 if ((rb
= calloc(1, sizeof(*rb
))) == NULL
)
392 return SSH_ERR_ALLOC_FAIL
;
395 erb
= RB_INSERT(revoked_blob_tree
, rbt
, rb
);
404 ssh_krl_revoke_key_explicit(struct ssh_krl
*krl
, const struct sshkey
*key
)
410 debug3_f("revoke type %s", sshkey_type(key
));
411 if ((r
= plain_key_blob(key
, &blob
, &len
)) != 0)
413 return revoke_blob(&krl
->revoked_keys
, blob
, len
);
417 revoke_by_hash(struct revoked_blob_tree
*target
, const u_char
*p
, size_t len
)
422 /* need to copy hash, as revoke_blob steals ownership */
423 if ((blob
= malloc(len
)) == NULL
)
424 return SSH_ERR_SYSTEM_ERROR
;
425 memcpy(blob
, p
, len
);
426 if ((r
= revoke_blob(target
, blob
, len
)) != 0) {
434 ssh_krl_revoke_key_sha1(struct ssh_krl
*krl
, const u_char
*p
, size_t len
)
436 debug3_f("revoke by sha1");
438 return SSH_ERR_INVALID_FORMAT
;
439 return revoke_by_hash(&krl
->revoked_sha1s
, p
, len
);
443 ssh_krl_revoke_key_sha256(struct ssh_krl
*krl
, const u_char
*p
, size_t len
)
445 debug3_f("revoke by sha256");
447 return SSH_ERR_INVALID_FORMAT
;
448 return revoke_by_hash(&krl
->revoked_sha256s
, p
, len
);
452 ssh_krl_revoke_key(struct ssh_krl
*krl
, const struct sshkey
*key
)
454 /* XXX replace with SHA256? */
455 if (!sshkey_is_cert(key
))
456 return ssh_krl_revoke_key_explicit(krl
, key
);
458 if (key
->cert
->serial
== 0) {
459 return ssh_krl_revoke_cert_by_key_id(krl
,
460 key
->cert
->signature_key
,
463 return ssh_krl_revoke_cert_by_serial(krl
,
464 key
->cert
->signature_key
,
470 * Select the most compact section type to emit next in a KRL based on
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
474 * that will minimise the size of the resultant KRL.
477 choose_next_state(int current_state
, u_int64_t contig
, int final
,
478 u_int64_t last_gap
, u_int64_t next_gap
, int *force_new_section
)
481 u_int64_t cost
, cost_list
, cost_range
, cost_bitmap
, cost_bitmap_restart
;
484 * Avoid unsigned overflows.
485 * The limits are high enough to avoid confusing the calculations.
487 contig
= MINIMUM(contig
, 1ULL<<31);
488 last_gap
= MINIMUM(last_gap
, 1ULL<<31);
489 next_gap
= MINIMUM(next_gap
, 1ULL<<31);
492 * Calculate the cost to switch from the current state to candidates.
493 * NB. range sections only ever contain a single range, so their
494 * switching cost is independent of the current_state.
496 cost_list
= cost_bitmap
= cost_bitmap_restart
= 0;
498 switch (current_state
) {
499 case KRL_SECTION_CERT_SERIAL_LIST
:
500 cost_bitmap_restart
= cost_bitmap
= 8 + 64;
502 case KRL_SECTION_CERT_SERIAL_BITMAP
:
504 cost_bitmap_restart
= 8 + 64;
506 case KRL_SECTION_CERT_SERIAL_RANGE
:
508 cost_bitmap_restart
= cost_bitmap
= 8 + 64;
512 /* Estimate base cost in bits of each section type */
513 cost_list
+= 64 * contig
+ (final
? 0 : 8+64);
514 cost_range
+= (2 * 64) + (final
? 0 : 8+64);
515 cost_bitmap
+= last_gap
+ contig
+ (final
? 0 : MINIMUM(next_gap
, 8+64));
516 cost_bitmap_restart
+= contig
+ (final
? 0 : MINIMUM(next_gap
, 8+64));
518 /* Convert to byte costs for actual comparison */
519 cost_list
= (cost_list
+ 7) / 8;
520 cost_bitmap
= (cost_bitmap
+ 7) / 8;
521 cost_bitmap_restart
= (cost_bitmap_restart
+ 7) / 8;
522 cost_range
= (cost_range
+ 7) / 8;
524 /* Now pick the best choice */
525 *force_new_section
= 0;
526 new_state
= KRL_SECTION_CERT_SERIAL_BITMAP
;
528 if (cost_range
< cost
) {
529 new_state
= KRL_SECTION_CERT_SERIAL_RANGE
;
532 if (cost_list
< cost
) {
533 new_state
= KRL_SECTION_CERT_SERIAL_LIST
;
536 if (cost_bitmap_restart
< cost
) {
537 new_state
= KRL_SECTION_CERT_SERIAL_BITMAP
;
538 *force_new_section
= 1;
539 cost
= cost_bitmap_restart
;
541 KRL_DBG(("contig %llu last_gap %llu next_gap %llu final %d, costs:"
542 "list %llu range %llu bitmap %llu new bitmap %llu, "
543 "selected 0x%02x%s", (long long unsigned)contig
,
544 (long long unsigned)last_gap
, (long long unsigned)next_gap
, final
,
545 (long long unsigned)cost_list
, (long long unsigned)cost_range
,
546 (long long unsigned)cost_bitmap
,
547 (long long unsigned)cost_bitmap_restart
, new_state
,
548 *force_new_section
? " restart" : ""));
553 put_bitmap(struct sshbuf
*buf
, struct bitmap
*bitmap
)
559 len
= bitmap_nbytes(bitmap
);
560 if ((blob
= malloc(len
)) == NULL
)
561 return SSH_ERR_ALLOC_FAIL
;
562 if (bitmap_to_string(bitmap
, blob
, len
) != 0) {
564 return SSH_ERR_INTERNAL_ERROR
;
566 r
= sshbuf_put_bignum2_bytes(buf
, blob
, len
);
571 /* Generate a KRL_SECTION_CERTIFICATES KRL section */
573 revoked_certs_generate(struct revoked_certs
*rc
, struct sshbuf
*buf
)
575 int final
, force_new_sect
, r
= SSH_ERR_INTERNAL_ERROR
;
576 u_int64_t i
, contig
, gap
, last
= 0, bitmap_start
= 0;
577 struct revoked_serial
*rs
, *nrs
;
578 struct revoked_key_id
*rki
;
579 int next_state
, state
= 0;
581 struct bitmap
*bitmap
= NULL
;
583 if ((sect
= sshbuf_new()) == NULL
)
584 return SSH_ERR_ALLOC_FAIL
;
586 /* Store the header: optional CA scope key, reserved */
587 if (rc
->ca_key
== NULL
) {
588 if ((r
= sshbuf_put_string(buf
, NULL
, 0)) != 0)
591 if ((r
= sshkey_puts(rc
->ca_key
, buf
)) != 0)
594 if ((r
= sshbuf_put_string(buf
, NULL
, 0)) != 0)
597 /* Store the revoked serials. */
598 for (rs
= RB_MIN(revoked_serial_tree
, &rc
->revoked_serials
);
600 rs
= RB_NEXT(revoked_serial_tree
, &rc
->revoked_serials
, rs
)) {
601 KRL_DBG(("serial %llu:%llu state 0x%02x",
602 (long long unsigned)rs
->lo
, (long long unsigned)rs
->hi
,
605 /* Check contiguous length and gap to next section (if any) */
606 nrs
= RB_NEXT(revoked_serial_tree
, &rc
->revoked_serials
, rs
);
608 gap
= nrs
== NULL
? 0 : nrs
->lo
- rs
->hi
;
609 contig
= 1 + (rs
->hi
- rs
->lo
);
611 /* Choose next state based on these */
612 next_state
= choose_next_state(state
, contig
, final
,
613 state
== 0 ? 0 : rs
->lo
- last
, gap
, &force_new_sect
);
616 * If the current section is a range section or has a different
617 * type to the next section, then finish it off now.
619 if (state
!= 0 && (force_new_sect
|| next_state
!= state
||
620 state
== KRL_SECTION_CERT_SERIAL_RANGE
)) {
621 KRL_DBG(("finish state 0x%02x", state
));
623 case KRL_SECTION_CERT_SERIAL_LIST
:
624 case KRL_SECTION_CERT_SERIAL_RANGE
:
626 case KRL_SECTION_CERT_SERIAL_BITMAP
:
627 if ((r
= put_bitmap(sect
, bitmap
)) != 0)
633 if ((r
= sshbuf_put_u8(buf
, state
)) != 0 ||
634 (r
= sshbuf_put_stringb(buf
, sect
)) != 0)
639 /* If we are starting a new section then prepare it now */
640 if (next_state
!= state
|| force_new_sect
) {
641 KRL_DBG(("start state 0x%02x",
646 case KRL_SECTION_CERT_SERIAL_LIST
:
647 case KRL_SECTION_CERT_SERIAL_RANGE
:
649 case KRL_SECTION_CERT_SERIAL_BITMAP
:
650 if ((bitmap
= bitmap_new()) == NULL
) {
651 r
= SSH_ERR_ALLOC_FAIL
;
654 bitmap_start
= rs
->lo
;
655 if ((r
= sshbuf_put_u64(sect
,
662 /* Perform section-specific processing */
664 case KRL_SECTION_CERT_SERIAL_LIST
:
665 for (i
= 0; i
< contig
; i
++) {
666 if ((r
= sshbuf_put_u64(sect
, rs
->lo
+ i
)) != 0)
670 case KRL_SECTION_CERT_SERIAL_RANGE
:
671 if ((r
= sshbuf_put_u64(sect
, rs
->lo
)) != 0 ||
672 (r
= sshbuf_put_u64(sect
, rs
->hi
)) != 0)
675 case KRL_SECTION_CERT_SERIAL_BITMAP
:
676 if (rs
->lo
- bitmap_start
> INT_MAX
) {
677 error_f("insane bitmap gap");
680 for (i
= 0; i
< contig
; i
++) {
681 if (bitmap_set_bit(bitmap
,
682 rs
->lo
+ i
- bitmap_start
) != 0) {
683 r
= SSH_ERR_ALLOC_FAIL
;
691 /* Flush the remaining section, if any */
693 KRL_DBG(("serial final flush for state 0x%02x", state
));
695 case KRL_SECTION_CERT_SERIAL_LIST
:
696 case KRL_SECTION_CERT_SERIAL_RANGE
:
698 case KRL_SECTION_CERT_SERIAL_BITMAP
:
699 if ((r
= put_bitmap(sect
, bitmap
)) != 0)
705 if ((r
= sshbuf_put_u8(buf
, state
)) != 0 ||
706 (r
= sshbuf_put_stringb(buf
, sect
)) != 0)
709 KRL_DBG(("serial done "));
711 /* Now output a section for any revocations by key ID */
713 RB_FOREACH(rki
, revoked_key_id_tree
, &rc
->revoked_key_ids
) {
714 KRL_DBG(("key ID %s", rki
->key_id
));
715 if ((r
= sshbuf_put_cstring(sect
, rki
->key_id
)) != 0)
718 if (sshbuf_len(sect
) != 0) {
719 if ((r
= sshbuf_put_u8(buf
, KRL_SECTION_CERT_KEY_ID
)) != 0 ||
720 (r
= sshbuf_put_stringb(buf
, sect
)) != 0)
731 ssh_krl_to_blob(struct ssh_krl
*krl
, struct sshbuf
*buf
)
733 int r
= SSH_ERR_INTERNAL_ERROR
;
734 struct revoked_certs
*rc
;
735 struct revoked_blob
*rb
;
737 u_char
*sblob
= NULL
;
739 if (krl
->generated_date
== 0)
740 krl
->generated_date
= time(NULL
);
742 if ((sect
= sshbuf_new()) == NULL
)
743 return SSH_ERR_ALLOC_FAIL
;
745 /* Store the header */
746 if ((r
= sshbuf_put(buf
, KRL_MAGIC
, sizeof(KRL_MAGIC
) - 1)) != 0 ||
747 (r
= sshbuf_put_u32(buf
, KRL_FORMAT_VERSION
)) != 0 ||
748 (r
= sshbuf_put_u64(buf
, krl
->krl_version
)) != 0 ||
749 (r
= sshbuf_put_u64(buf
, krl
->generated_date
)) != 0 ||
750 (r
= sshbuf_put_u64(buf
, krl
->flags
)) != 0 ||
751 (r
= sshbuf_put_string(buf
, NULL
, 0)) != 0 ||
752 (r
= sshbuf_put_cstring(buf
, krl
->comment
)) != 0)
755 /* Store sections for revoked certificates */
756 TAILQ_FOREACH(rc
, &krl
->revoked_certs
, entry
) {
758 if ((r
= revoked_certs_generate(rc
, sect
)) != 0)
760 if ((r
= sshbuf_put_u8(buf
, KRL_SECTION_CERTIFICATES
)) != 0 ||
761 (r
= sshbuf_put_stringb(buf
, sect
)) != 0)
765 /* Finally, output sections for revocations by public key/hash */
767 RB_FOREACH(rb
, revoked_blob_tree
, &krl
->revoked_keys
) {
768 KRL_DBG(("key len %zu ", rb
->len
));
769 if ((r
= sshbuf_put_string(sect
, rb
->blob
, rb
->len
)) != 0)
772 if (sshbuf_len(sect
) != 0) {
773 if ((r
= sshbuf_put_u8(buf
, KRL_SECTION_EXPLICIT_KEY
)) != 0 ||
774 (r
= sshbuf_put_stringb(buf
, sect
)) != 0)
778 RB_FOREACH(rb
, revoked_blob_tree
, &krl
->revoked_sha1s
) {
779 KRL_DBG(("hash len %zu ", rb
->len
));
780 if ((r
= sshbuf_put_string(sect
, rb
->blob
, rb
->len
)) != 0)
783 if (sshbuf_len(sect
) != 0) {
784 if ((r
= sshbuf_put_u8(buf
,
785 KRL_SECTION_FINGERPRINT_SHA1
)) != 0 ||
786 (r
= sshbuf_put_stringb(buf
, sect
)) != 0)
790 RB_FOREACH(rb
, revoked_blob_tree
, &krl
->revoked_sha256s
) {
791 KRL_DBG(("hash len %zu ", rb
->len
));
792 if ((r
= sshbuf_put_string(sect
, rb
->blob
, rb
->len
)) != 0)
795 if (sshbuf_len(sect
) != 0) {
796 if ((r
= sshbuf_put_u8(buf
,
797 KRL_SECTION_FINGERPRINT_SHA256
)) != 0 ||
798 (r
= sshbuf_put_stringb(buf
, sect
)) != 0)
810 format_timestamp(u_int64_t timestamp
, char *ts
, size_t nts
)
818 strlcpy(ts
, "<INVALID>", nts
);
821 strftime(ts
, nts
, "%Y%m%dT%H%M%S", tm
);
826 cert_extension_subsection(struct sshbuf
*subsect
, struct ssh_krl
*krl
)
828 int r
= SSH_ERR_INTERNAL_ERROR
;
830 struct sshbuf
*value
= NULL
;
833 if ((r
= sshbuf_get_cstring(subsect
, &name
, NULL
)) != 0 ||
834 (r
= sshbuf_get_u8(subsect
, &critical
)) != 0 ||
835 (r
= sshbuf_froms(subsect
, &value
)) != 0) {
836 debug_fr(r
, "parse");
837 error("KRL has invalid certificate extension subsection");
838 r
= SSH_ERR_INVALID_FORMAT
;
841 if (sshbuf_len(subsect
) != 0) {
842 error("KRL has invalid certificate extension subsection: "
844 r
= SSH_ERR_INVALID_FORMAT
;
847 debug_f("cert extension %s critical %u len %zu",
848 name
, critical
, sshbuf_len(value
));
849 /* no extensions are currently supported */
851 error("KRL contains unsupported critical certificate "
852 "subsection \"%s\"", name
);
853 r
= SSH_ERR_FEATURE_UNSUPPORTED
;
865 parse_revoked_certs(struct sshbuf
*buf
, struct ssh_krl
*krl
)
867 int r
= SSH_ERR_INTERNAL_ERROR
;
871 struct sshbuf
*subsect
= NULL
;
872 u_int64_t serial
, serial_lo
, serial_hi
;
873 struct bitmap
*bitmap
= NULL
;
875 struct sshkey
*ca_key
= NULL
;
877 if ((subsect
= sshbuf_new()) == NULL
)
878 return SSH_ERR_ALLOC_FAIL
;
880 /* Header: key, reserved */
881 if ((r
= sshbuf_get_string_direct(buf
, &blob
, &blen
)) != 0 ||
882 (r
= sshbuf_skip_string(buf
)) != 0)
884 if (blen
!= 0 && (r
= sshkey_from_blob(blob
, blen
, &ca_key
)) != 0)
887 while (sshbuf_len(buf
) > 0) {
888 sshbuf_free(subsect
);
890 if ((r
= sshbuf_get_u8(buf
, &type
)) != 0 ||
891 (r
= sshbuf_froms(buf
, &subsect
)) != 0)
893 KRL_DBG(("subsection type 0x%02x", type
));
894 /* sshbuf_dump(subsect, stderr); */
897 case KRL_SECTION_CERT_SERIAL_LIST
:
898 while (sshbuf_len(subsect
) > 0) {
899 if ((r
= sshbuf_get_u64(subsect
, &serial
)) != 0)
901 if ((r
= ssh_krl_revoke_cert_by_serial(krl
,
902 ca_key
, serial
)) != 0)
906 case KRL_SECTION_CERT_SERIAL_RANGE
:
907 if ((r
= sshbuf_get_u64(subsect
, &serial_lo
)) != 0 ||
908 (r
= sshbuf_get_u64(subsect
, &serial_hi
)) != 0)
910 if ((r
= ssh_krl_revoke_cert_by_serial_range(krl
,
911 ca_key
, serial_lo
, serial_hi
)) != 0)
914 case KRL_SECTION_CERT_SERIAL_BITMAP
:
915 if ((bitmap
= bitmap_new()) == NULL
) {
916 r
= SSH_ERR_ALLOC_FAIL
;
919 if ((r
= sshbuf_get_u64(subsect
, &serial_lo
)) != 0 ||
920 (r
= sshbuf_get_bignum2_bytes_direct(subsect
,
923 if (bitmap_from_string(bitmap
, blob
, blen
) != 0) {
924 r
= SSH_ERR_INVALID_FORMAT
;
927 nbits
= bitmap_nbits(bitmap
);
928 for (serial
= 0; serial
< (u_int64_t
)nbits
; serial
++) {
929 if (serial
> 0 && serial_lo
+ serial
== 0) {
930 error_f("bitmap wraps u64");
931 r
= SSH_ERR_INVALID_FORMAT
;
934 if (!bitmap_test_bit(bitmap
, serial
))
936 if ((r
= ssh_krl_revoke_cert_by_serial(krl
,
937 ca_key
, serial_lo
+ serial
)) != 0)
943 case KRL_SECTION_CERT_KEY_ID
:
944 while (sshbuf_len(subsect
) > 0) {
945 if ((r
= sshbuf_get_cstring(subsect
,
946 &key_id
, NULL
)) != 0)
948 if ((r
= ssh_krl_revoke_cert_by_key_id(krl
,
949 ca_key
, key_id
)) != 0)
955 case KRL_SECTION_CERT_EXTENSION
:
956 if ((r
= cert_extension_subsection(subsect
, krl
)) != 0)
960 error("Unsupported KRL certificate section %u", type
);
961 r
= SSH_ERR_INVALID_FORMAT
;
964 if (sshbuf_len(subsect
) > 0) {
965 error("KRL certificate section contains unparsed data");
966 r
= SSH_ERR_INVALID_FORMAT
;
977 sshbuf_free(subsect
);
982 blob_section(struct sshbuf
*sect
, struct revoked_blob_tree
*target_tree
,
985 u_char
*rdata
= NULL
;
989 while (sshbuf_len(sect
) > 0) {
990 if ((r
= sshbuf_get_string(sect
, &rdata
, &rlen
)) != 0)
992 if (expected_len
!= 0 && rlen
!= expected_len
) {
993 error_f("bad length");
995 return SSH_ERR_INVALID_FORMAT
;
997 if ((r
= revoke_blob(target_tree
, rdata
, rlen
)) != 0) {
1006 extension_section(struct sshbuf
*sect
, struct ssh_krl
*krl
)
1008 int r
= SSH_ERR_INTERNAL_ERROR
;
1009 u_char critical
= 1;
1010 struct sshbuf
*value
= NULL
;
1013 if ((r
= sshbuf_get_cstring(sect
, &name
, NULL
)) != 0 ||
1014 (r
= sshbuf_get_u8(sect
, &critical
)) != 0 ||
1015 (r
= sshbuf_froms(sect
, &value
)) != 0) {
1016 debug_fr(r
, "parse");
1017 error("KRL has invalid extension section");
1018 r
= SSH_ERR_INVALID_FORMAT
;
1021 if (sshbuf_len(sect
) != 0) {
1022 error("KRL has invalid extension section: trailing data");
1023 r
= SSH_ERR_INVALID_FORMAT
;
1026 debug_f("extension %s critical %u len %zu",
1027 name
, critical
, sshbuf_len(value
));
1028 /* no extensions are currently supported */
1030 error("KRL contains unsupported critical section \"%s\"", name
);
1031 r
= SSH_ERR_FEATURE_UNSUPPORTED
;
1042 /* Attempt to parse a KRL */
1044 ssh_krl_from_blob(struct sshbuf
*buf
, struct ssh_krl
**krlp
)
1046 struct sshbuf
*copy
= NULL
, *sect
= NULL
;
1047 struct ssh_krl
*krl
= NULL
;
1049 int r
= SSH_ERR_INTERNAL_ERROR
;
1051 u_int format_version
;
1055 /* KRL must begin with magic string */
1056 if ((r
= sshbuf_cmp(buf
, 0, KRL_MAGIC
, sizeof(KRL_MAGIC
) - 1)) != 0) {
1057 debug2_f("bad KRL magic header");
1058 return SSH_ERR_KRL_BAD_MAGIC
;
1061 if ((krl
= ssh_krl_init()) == NULL
) {
1062 error_f("alloc failed");
1065 /* Don't modify buffer */
1066 if ((copy
= sshbuf_fromb(buf
)) == NULL
) {
1067 r
= SSH_ERR_ALLOC_FAIL
;
1070 if ((r
= sshbuf_consume(copy
, sizeof(KRL_MAGIC
) - 1)) != 0 ||
1071 (r
= sshbuf_get_u32(copy
, &format_version
)) != 0)
1073 if (format_version
!= KRL_FORMAT_VERSION
) {
1074 error_f("unsupported KRL format version %u", format_version
);
1075 r
= SSH_ERR_INVALID_FORMAT
;
1078 if ((r
= sshbuf_get_u64(copy
, &krl
->krl_version
)) != 0 ||
1079 (r
= sshbuf_get_u64(copy
, &krl
->generated_date
)) != 0 ||
1080 (r
= sshbuf_get_u64(copy
, &krl
->flags
)) != 0 ||
1081 (r
= sshbuf_skip_string(copy
)) != 0 ||
1082 (r
= sshbuf_get_cstring(copy
, &krl
->comment
, NULL
)) != 0) {
1083 error_fr(r
, "parse KRL header");
1086 format_timestamp(krl
->generated_date
, timestamp
, sizeof(timestamp
));
1087 debug("KRL version %llu generated at %s%s%s",
1088 (long long unsigned)krl
->krl_version
, timestamp
,
1089 *krl
->comment
? ": " : "", krl
->comment
);
1091 /* Parse and load the KRL sections. */
1092 while (sshbuf_len(copy
) > 0) {
1095 if ((r
= sshbuf_get_u8(copy
, &type
)) != 0 ||
1096 (r
= sshbuf_froms(copy
, §
)) != 0)
1098 KRL_DBG(("section 0x%02x", type
));
1101 case KRL_SECTION_CERTIFICATES
:
1102 if ((r
= parse_revoked_certs(sect
, krl
)) != 0)
1105 case KRL_SECTION_EXPLICIT_KEY
:
1106 if ((r
= blob_section(sect
,
1107 &krl
->revoked_keys
, 0)) != 0)
1110 case KRL_SECTION_FINGERPRINT_SHA1
:
1111 if ((r
= blob_section(sect
,
1112 &krl
->revoked_sha1s
, 20)) != 0)
1115 case KRL_SECTION_FINGERPRINT_SHA256
:
1116 if ((r
= blob_section(sect
,
1117 &krl
->revoked_sha256s
, 32)) != 0)
1120 case KRL_SECTION_EXTENSION
:
1121 if ((r
= extension_section(sect
, krl
)) != 0)
1124 case KRL_SECTION_SIGNATURE
:
1125 /* Handled above, but still need to stay in synch */
1128 if ((r
= sshbuf_skip_string(copy
)) != 0)
1132 error("Unsupported KRL section %u", type
);
1133 r
= SSH_ERR_INVALID_FORMAT
;
1136 if (sect
!= NULL
&& sshbuf_len(sect
) > 0) {
1137 error("KRL section contains unparsed data");
1138 r
= SSH_ERR_INVALID_FORMAT
;
1154 /* Checks certificate serial number and key ID revocation */
1156 is_cert_revoked(const struct sshkey
*key
, struct revoked_certs
*rc
)
1158 struct revoked_serial rs
, *ers
;
1159 struct revoked_key_id rki
, *erki
;
1161 /* Check revocation by cert key ID */
1162 memset(&rki
, 0, sizeof(rki
));
1163 rki
.key_id
= key
->cert
->key_id
;
1164 erki
= RB_FIND(revoked_key_id_tree
, &rc
->revoked_key_ids
, &rki
);
1166 KRL_DBG(("revoked by key ID"));
1167 return SSH_ERR_KEY_REVOKED
;
1171 * Zero serials numbers are ignored (it's the default when the
1172 * CA doesn't specify one).
1174 if (key
->cert
->serial
== 0)
1177 memset(&rs
, 0, sizeof(rs
));
1178 rs
.lo
= rs
.hi
= key
->cert
->serial
;
1179 ers
= RB_FIND(revoked_serial_tree
, &rc
->revoked_serials
, &rs
);
1181 KRL_DBG(("revoked serial %llu matched %llu:%llu",
1182 key
->cert
->serial
, ers
->lo
, ers
->hi
));
1183 return SSH_ERR_KEY_REVOKED
;
1188 /* Checks whether a given key/cert is revoked. Does not check its CA */
1190 is_key_revoked(struct ssh_krl
*krl
, const struct sshkey
*key
)
1192 struct revoked_blob rb
, *erb
;
1193 struct revoked_certs
*rc
;
1196 /* Check explicitly revoked hashes first */
1197 memset(&rb
, 0, sizeof(rb
));
1198 if ((r
= sshkey_fingerprint_raw(key
, SSH_DIGEST_SHA1
,
1199 &rb
.blob
, &rb
.len
)) != 0)
1201 erb
= RB_FIND(revoked_blob_tree
, &krl
->revoked_sha1s
, &rb
);
1204 KRL_DBG(("revoked by key SHA1"));
1205 return SSH_ERR_KEY_REVOKED
;
1207 memset(&rb
, 0, sizeof(rb
));
1208 if ((r
= sshkey_fingerprint_raw(key
, SSH_DIGEST_SHA256
,
1209 &rb
.blob
, &rb
.len
)) != 0)
1211 erb
= RB_FIND(revoked_blob_tree
, &krl
->revoked_sha256s
, &rb
);
1214 KRL_DBG(("revoked by key SHA256"));
1215 return SSH_ERR_KEY_REVOKED
;
1218 /* Next, explicit keys */
1219 memset(&rb
, 0, sizeof(rb
));
1220 if ((r
= plain_key_blob(key
, &rb
.blob
, &rb
.len
)) != 0)
1222 erb
= RB_FIND(revoked_blob_tree
, &krl
->revoked_keys
, &rb
);
1225 KRL_DBG(("revoked by explicit key"));
1226 return SSH_ERR_KEY_REVOKED
;
1229 if (!sshkey_is_cert(key
))
1232 /* Check cert revocation for the specified CA */
1233 if ((r
= revoked_certs_for_ca_key(krl
, key
->cert
->signature_key
,
1237 if ((r
= is_cert_revoked(key
, rc
)) != 0)
1240 /* Check cert revocation for the wildcard CA */
1241 if ((r
= revoked_certs_for_ca_key(krl
, NULL
, &rc
, 0)) != 0)
1244 if ((r
= is_cert_revoked(key
, rc
)) != 0)
1248 KRL_DBG(("%llu no match", key
->cert
->serial
));
1253 ssh_krl_check_key(struct ssh_krl
*krl
, const struct sshkey
*key
)
1257 KRL_DBG(("checking key"));
1258 if ((r
= is_key_revoked(krl
, key
)) != 0)
1260 if (sshkey_is_cert(key
)) {
1261 debug2_f("checking CA key");
1262 if ((r
= is_key_revoked(krl
, key
->cert
->signature_key
)) != 0)
1265 KRL_DBG(("key okay"));
1270 ssh_krl_file_contains_key(const char *path
, const struct sshkey
*key
)
1272 struct sshbuf
*krlbuf
= NULL
;
1273 struct ssh_krl
*krl
= NULL
;
1278 if ((r
= sshbuf_load_file(path
, &krlbuf
)) != 0) {
1282 if ((r
= ssh_krl_from_blob(krlbuf
, &krl
)) != 0)
1284 debug2_f("checking KRL %s", path
);
1285 r
= ssh_krl_check_key(krl
, key
);
1287 sshbuf_free(krlbuf
);
1295 krl_dump(struct ssh_krl
*krl
, FILE *f
)
1297 struct sshkey
*key
= NULL
;
1298 struct revoked_blob
*rb
;
1299 struct revoked_certs
*rc
;
1300 struct revoked_serial
*rs
;
1301 struct revoked_key_id
*rki
;
1303 char *fp
, timestamp
[64];
1305 /* Try to print in a KRL spec-compatible format */
1306 format_timestamp(krl
->generated_date
, timestamp
, sizeof(timestamp
));
1307 fprintf(f
, "# KRL version %llu\n",
1308 (unsigned long long)krl
->krl_version
);
1309 fprintf(f
, "# Generated at %s\n", timestamp
);
1310 if (krl
->comment
!= NULL
&& *krl
->comment
!= '\0') {
1312 asmprintf(&fp
, INT_MAX
, &r
, "%s", krl
->comment
);
1313 fprintf(f
, "# Comment: %s\n", fp
);
1318 RB_FOREACH(rb
, revoked_blob_tree
, &krl
->revoked_keys
) {
1319 if ((r
= sshkey_from_blob(rb
->blob
, rb
->len
, &key
)) != 0) {
1320 ret
= SSH_ERR_INVALID_FORMAT
;
1321 error_r(r
, "parse KRL key");
1324 if ((fp
= sshkey_fingerprint(key
, SSH_FP_HASH_DEFAULT
,
1325 SSH_FP_DEFAULT
)) == NULL
) {
1326 ret
= SSH_ERR_INVALID_FORMAT
;
1327 error("sshkey_fingerprint failed");
1330 fprintf(f
, "hash: %s # %s\n", fp
, sshkey_ssh_name(key
));
1334 RB_FOREACH(rb
, revoked_blob_tree
, &krl
->revoked_sha256s
) {
1335 fp
= tohex(rb
->blob
, rb
->len
);
1336 fprintf(f
, "hash: SHA256:%s\n", fp
);
1339 RB_FOREACH(rb
, revoked_blob_tree
, &krl
->revoked_sha1s
) {
1341 * There is not KRL spec keyword for raw SHA1 hashes, so
1342 * print them as comments.
1344 fp
= tohex(rb
->blob
, rb
->len
);
1345 fprintf(f
, "# hash SHA1:%s\n", fp
);
1349 TAILQ_FOREACH(rc
, &krl
->revoked_certs
, entry
) {
1351 if (rc
->ca_key
== NULL
)
1352 fprintf(f
, "# Wildcard CA\n");
1354 if ((fp
= sshkey_fingerprint(rc
->ca_key
,
1355 SSH_FP_HASH_DEFAULT
, SSH_FP_DEFAULT
)) == NULL
) {
1356 ret
= SSH_ERR_INVALID_FORMAT
;
1357 error("sshkey_fingerprint failed");
1360 fprintf(f
, "# CA key %s %s\n",
1361 sshkey_ssh_name(rc
->ca_key
), fp
);
1364 RB_FOREACH(rs
, revoked_serial_tree
, &rc
->revoked_serials
) {
1365 if (rs
->lo
== rs
->hi
) {
1366 fprintf(f
, "serial: %llu\n",
1367 (unsigned long long)rs
->lo
);
1369 fprintf(f
, "serial: %llu-%llu\n",
1370 (unsigned long long)rs
->lo
,
1371 (unsigned long long)rs
->hi
);
1374 RB_FOREACH(rki
, revoked_key_id_tree
, &rc
->revoked_key_ids
) {
1376 * We don't want key IDs with embedded newlines to
1377 * mess up the display.
1380 asmprintf(&fp
, INT_MAX
, &r
, "%s", rki
->key_id
);
1381 fprintf(f
, "id: %s\n", fp
);