2 * Copyright (c) 2012 Damien Miller <djm@mindrot.org>
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.
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.
17 /* $OpenBSD: krl.c,v 1.37 2015/12/31 00:33:52 djm Exp $ */
21 #include <sys/param.h> /* MIN */
22 #include <sys/types.h>
23 #include <openbsd-compat/sys-tree.h>
24 #include <openbsd-compat/sys-queue.h>
44 /* #define DEBUG_KRL */
46 # define KRL_DBG(x) debug3 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_certs_list revoked_certs
;
103 /* Return equal if a and b overlap */
105 serial_cmp(struct revoked_serial
*a
, struct revoked_serial
*b
)
107 if (a
->hi
>= b
->lo
&& a
->lo
<= b
->hi
)
109 return a
->lo
< b
->lo
? -1 : 1;
113 key_id_cmp(struct revoked_key_id
*a
, struct revoked_key_id
*b
)
115 return strcmp(a
->key_id
, b
->key_id
);
119 blob_cmp(struct revoked_blob
*a
, struct revoked_blob
*b
)
123 if (a
->len
!= b
->len
) {
124 if ((r
= memcmp(a
->blob
, b
->blob
, MIN(a
->len
, b
->len
))) != 0)
126 return a
->len
> b
->len
? 1 : -1;
128 return memcmp(a
->blob
, b
->blob
, a
->len
);
136 if ((krl
= calloc(1, sizeof(*krl
))) == NULL
)
138 RB_INIT(&krl
->revoked_keys
);
139 RB_INIT(&krl
->revoked_sha1s
);
140 TAILQ_INIT(&krl
->revoked_certs
);
145 revoked_certs_free(struct revoked_certs
*rc
)
147 struct revoked_serial
*rs
, *trs
;
148 struct revoked_key_id
*rki
, *trki
;
150 RB_FOREACH_SAFE(rs
, revoked_serial_tree
, &rc
->revoked_serials
, trs
) {
151 RB_REMOVE(revoked_serial_tree
, &rc
->revoked_serials
, rs
);
154 RB_FOREACH_SAFE(rki
, revoked_key_id_tree
, &rc
->revoked_key_ids
, trki
) {
155 RB_REMOVE(revoked_key_id_tree
, &rc
->revoked_key_ids
, rki
);
159 sshkey_free(rc
->ca_key
);
163 ssh_krl_free(struct ssh_krl
*krl
)
165 struct revoked_blob
*rb
, *trb
;
166 struct revoked_certs
*rc
, *trc
;
172 RB_FOREACH_SAFE(rb
, revoked_blob_tree
, &krl
->revoked_keys
, trb
) {
173 RB_REMOVE(revoked_blob_tree
, &krl
->revoked_keys
, rb
);
177 RB_FOREACH_SAFE(rb
, revoked_blob_tree
, &krl
->revoked_sha1s
, trb
) {
178 RB_REMOVE(revoked_blob_tree
, &krl
->revoked_sha1s
, rb
);
182 TAILQ_FOREACH_SAFE(rc
, &krl
->revoked_certs
, entry
, trc
) {
183 TAILQ_REMOVE(&krl
->revoked_certs
, rc
, entry
);
184 revoked_certs_free(rc
);
189 ssh_krl_set_version(struct ssh_krl
*krl
, u_int64_t version
)
191 krl
->krl_version
= version
;
195 ssh_krl_set_comment(struct ssh_krl
*krl
, const char *comment
)
198 if ((krl
->comment
= strdup(comment
)) == NULL
)
199 return SSH_ERR_ALLOC_FAIL
;
204 * Find the revoked_certs struct for a CA key. If allow_create is set then
205 * create a new one in the tree if one did not exist already.
208 revoked_certs_for_ca_key(struct ssh_krl
*krl
, const struct sshkey
*ca_key
,
209 struct revoked_certs
**rcp
, int allow_create
)
211 struct revoked_certs
*rc
;
215 TAILQ_FOREACH(rc
, &krl
->revoked_certs
, entry
) {
216 if ((ca_key
== NULL
&& rc
->ca_key
== NULL
) ||
217 sshkey_equal(rc
->ca_key
, ca_key
)) {
224 /* If this CA doesn't exist in the list then add it now */
225 if ((rc
= calloc(1, sizeof(*rc
))) == NULL
)
226 return SSH_ERR_ALLOC_FAIL
;
229 else if ((r
= sshkey_from_private(ca_key
, &rc
->ca_key
)) != 0) {
233 RB_INIT(&rc
->revoked_serials
);
234 RB_INIT(&rc
->revoked_key_ids
);
235 TAILQ_INSERT_TAIL(&krl
->revoked_certs
, rc
, entry
);
236 KRL_DBG(("%s: new CA %s", __func__
,
237 ca_key
== NULL
? "*" : sshkey_type(ca_key
)));
243 insert_serial_range(struct revoked_serial_tree
*rt
, u_int64_t lo
, u_int64_t hi
)
245 struct revoked_serial rs
, *ers
, *crs
, *irs
;
247 KRL_DBG(("%s: insert %llu:%llu", __func__
, lo
, hi
));
248 memset(&rs
, 0, sizeof(rs
));
251 ers
= RB_NFIND(revoked_serial_tree
, rt
, &rs
);
252 if (ers
== NULL
|| serial_cmp(ers
, &rs
) != 0) {
253 /* No entry matches. Just insert */
254 if ((irs
= malloc(sizeof(rs
))) == NULL
)
255 return SSH_ERR_ALLOC_FAIL
;
256 memcpy(irs
, &rs
, sizeof(*irs
));
257 ers
= RB_INSERT(revoked_serial_tree
, rt
, irs
);
259 KRL_DBG(("%s: bad: ers != NULL", __func__
));
260 /* Shouldn't happen */
262 return SSH_ERR_INTERNAL_ERROR
;
266 KRL_DBG(("%s: overlap found %llu:%llu", __func__
,
269 * The inserted entry overlaps an existing one. Grow the
279 * The inserted or revised range might overlap or abut adjacent ones;
280 * coalesce as necessary.
283 /* Check predecessors */
284 while ((crs
= RB_PREV(revoked_serial_tree
, rt
, ers
)) != NULL
) {
285 KRL_DBG(("%s: pred %llu:%llu", __func__
, crs
->lo
, crs
->hi
));
286 if (ers
->lo
!= 0 && crs
->hi
< ers
->lo
- 1)
288 /* This entry overlaps. */
289 if (crs
->lo
< ers
->lo
) {
291 KRL_DBG(("%s: pred extend %llu:%llu", __func__
,
294 RB_REMOVE(revoked_serial_tree
, rt
, crs
);
297 /* Check successors */
298 while ((crs
= RB_NEXT(revoked_serial_tree
, rt
, ers
)) != NULL
) {
299 KRL_DBG(("%s: succ %llu:%llu", __func__
, crs
->lo
, crs
->hi
));
300 if (ers
->hi
!= (u_int64_t
)-1 && crs
->lo
> ers
->hi
+ 1)
302 /* This entry overlaps. */
303 if (crs
->hi
> ers
->hi
) {
305 KRL_DBG(("%s: succ extend %llu:%llu", __func__
,
308 RB_REMOVE(revoked_serial_tree
, rt
, crs
);
311 KRL_DBG(("%s: done, final %llu:%llu", __func__
, ers
->lo
, ers
->hi
));
316 ssh_krl_revoke_cert_by_serial(struct ssh_krl
*krl
, const struct sshkey
*ca_key
,
319 return ssh_krl_revoke_cert_by_serial_range(krl
, ca_key
, serial
, serial
);
323 ssh_krl_revoke_cert_by_serial_range(struct ssh_krl
*krl
,
324 const struct sshkey
*ca_key
, u_int64_t lo
, u_int64_t hi
)
326 struct revoked_certs
*rc
;
329 if (lo
> hi
|| lo
== 0)
330 return SSH_ERR_INVALID_ARGUMENT
;
331 if ((r
= revoked_certs_for_ca_key(krl
, ca_key
, &rc
, 1)) != 0)
333 return insert_serial_range(&rc
->revoked_serials
, lo
, hi
);
337 ssh_krl_revoke_cert_by_key_id(struct ssh_krl
*krl
, const struct sshkey
*ca_key
,
340 struct revoked_key_id
*rki
, *erki
;
341 struct revoked_certs
*rc
;
344 if ((r
= revoked_certs_for_ca_key(krl
, ca_key
, &rc
, 1)) != 0)
347 KRL_DBG(("%s: revoke %s", __func__
, key_id
));
348 if ((rki
= calloc(1, sizeof(*rki
))) == NULL
||
349 (rki
->key_id
= strdup(key_id
)) == NULL
) {
351 return SSH_ERR_ALLOC_FAIL
;
353 erki
= RB_INSERT(revoked_key_id_tree
, &rc
->revoked_key_ids
, rki
);
361 /* Convert "key" to a public key blob without any certificate information */
363 plain_key_blob(const struct sshkey
*key
, u_char
**blob
, size_t *blen
)
365 struct sshkey
*kcopy
;
368 if ((r
= sshkey_from_private(key
, &kcopy
)) != 0)
370 if (sshkey_is_cert(kcopy
)) {
371 if ((r
= sshkey_drop_cert(kcopy
)) != 0) {
376 r
= sshkey_to_blob(kcopy
, blob
, blen
);
381 /* Revoke a key blob. Ownership of blob is transferred to the tree */
383 revoke_blob(struct revoked_blob_tree
*rbt
, u_char
*blob
, size_t len
)
385 struct revoked_blob
*rb
, *erb
;
387 if ((rb
= calloc(1, sizeof(*rb
))) == NULL
)
388 return SSH_ERR_ALLOC_FAIL
;
391 erb
= RB_INSERT(revoked_blob_tree
, rbt
, rb
);
400 ssh_krl_revoke_key_explicit(struct ssh_krl
*krl
, const struct sshkey
*key
)
406 debug3("%s: revoke type %s", __func__
, sshkey_type(key
));
407 if ((r
= plain_key_blob(key
, &blob
, &len
)) != 0)
409 return revoke_blob(&krl
->revoked_keys
, blob
, len
);
413 ssh_krl_revoke_key_sha1(struct ssh_krl
*krl
, const struct sshkey
*key
)
419 debug3("%s: revoke type %s by sha1", __func__
, sshkey_type(key
));
420 if ((r
= sshkey_fingerprint_raw(key
, SSH_DIGEST_SHA1
,
423 return revoke_blob(&krl
->revoked_sha1s
, blob
, len
);
427 ssh_krl_revoke_key(struct ssh_krl
*krl
, const struct sshkey
*key
)
429 if (!sshkey_is_cert(key
))
430 return ssh_krl_revoke_key_sha1(krl
, key
);
432 if (key
->cert
->serial
== 0) {
433 return ssh_krl_revoke_cert_by_key_id(krl
,
434 key
->cert
->signature_key
,
437 return ssh_krl_revoke_cert_by_serial(krl
,
438 key
->cert
->signature_key
,
444 * Select the most compact section type to emit next in a KRL based on
445 * the current section type, the run length of contiguous revoked serial
446 * numbers and the gaps from the last and to the next revoked serial.
447 * Applies a mostly-accurate bit cost model to select the section type
448 * that will minimise the size of the resultant KRL.
451 choose_next_state(int current_state
, u_int64_t contig
, int final
,
452 u_int64_t last_gap
, u_int64_t next_gap
, int *force_new_section
)
455 u_int64_t cost
, cost_list
, cost_range
, cost_bitmap
, cost_bitmap_restart
;
458 * Avoid unsigned overflows.
459 * The limits are high enough to avoid confusing the calculations.
461 contig
= MIN(contig
, 1ULL<<31);
462 last_gap
= MIN(last_gap
, 1ULL<<31);
463 next_gap
= MIN(next_gap
, 1ULL<<31);
466 * Calculate the cost to switch from the current state to candidates.
467 * NB. range sections only ever contain a single range, so their
468 * switching cost is independent of the current_state.
470 cost_list
= cost_bitmap
= cost_bitmap_restart
= 0;
472 switch (current_state
) {
473 case KRL_SECTION_CERT_SERIAL_LIST
:
474 cost_bitmap_restart
= cost_bitmap
= 8 + 64;
476 case KRL_SECTION_CERT_SERIAL_BITMAP
:
478 cost_bitmap_restart
= 8 + 64;
480 case KRL_SECTION_CERT_SERIAL_RANGE
:
482 cost_bitmap_restart
= cost_bitmap
= 8 + 64;
486 /* Estimate base cost in bits of each section type */
487 cost_list
+= 64 * contig
+ (final
? 0 : 8+64);
488 cost_range
+= (2 * 64) + (final
? 0 : 8+64);
489 cost_bitmap
+= last_gap
+ contig
+ (final
? 0 : MIN(next_gap
, 8+64));
490 cost_bitmap_restart
+= contig
+ (final
? 0 : MIN(next_gap
, 8+64));
492 /* Convert to byte costs for actual comparison */
493 cost_list
= (cost_list
+ 7) / 8;
494 cost_bitmap
= (cost_bitmap
+ 7) / 8;
495 cost_bitmap_restart
= (cost_bitmap_restart
+ 7) / 8;
496 cost_range
= (cost_range
+ 7) / 8;
498 /* Now pick the best choice */
499 *force_new_section
= 0;
500 new_state
= KRL_SECTION_CERT_SERIAL_BITMAP
;
502 if (cost_range
< cost
) {
503 new_state
= KRL_SECTION_CERT_SERIAL_RANGE
;
506 if (cost_list
< cost
) {
507 new_state
= KRL_SECTION_CERT_SERIAL_LIST
;
510 if (cost_bitmap_restart
< cost
) {
511 new_state
= KRL_SECTION_CERT_SERIAL_BITMAP
;
512 *force_new_section
= 1;
513 cost
= cost_bitmap_restart
;
515 KRL_DBG(("%s: contig %llu last_gap %llu next_gap %llu final %d, costs:"
516 "list %llu range %llu bitmap %llu new bitmap %llu, "
517 "selected 0x%02x%s", __func__
, (long long unsigned)contig
,
518 (long long unsigned)last_gap
, (long long unsigned)next_gap
, final
,
519 (long long unsigned)cost_list
, (long long unsigned)cost_range
,
520 (long long unsigned)cost_bitmap
,
521 (long long unsigned)cost_bitmap_restart
, new_state
,
522 *force_new_section
? " restart" : ""));
527 put_bitmap(struct sshbuf
*buf
, struct bitmap
*bitmap
)
533 len
= bitmap_nbytes(bitmap
);
534 if ((blob
= malloc(len
)) == NULL
)
535 return SSH_ERR_ALLOC_FAIL
;
536 if (bitmap_to_string(bitmap
, blob
, len
) != 0) {
538 return SSH_ERR_INTERNAL_ERROR
;
540 r
= sshbuf_put_bignum2_bytes(buf
, blob
, len
);
545 /* Generate a KRL_SECTION_CERTIFICATES KRL section */
547 revoked_certs_generate(struct revoked_certs
*rc
, struct sshbuf
*buf
)
549 int final
, force_new_sect
, r
= SSH_ERR_INTERNAL_ERROR
;
550 u_int64_t i
, contig
, gap
, last
= 0, bitmap_start
= 0;
551 struct revoked_serial
*rs
, *nrs
;
552 struct revoked_key_id
*rki
;
553 int next_state
, state
= 0;
555 struct bitmap
*bitmap
= NULL
;
557 if ((sect
= sshbuf_new()) == NULL
)
558 return SSH_ERR_ALLOC_FAIL
;
560 /* Store the header: optional CA scope key, reserved */
561 if (rc
->ca_key
== NULL
) {
562 if ((r
= sshbuf_put_string(buf
, NULL
, 0)) != 0)
565 if ((r
= sshkey_puts(rc
->ca_key
, buf
)) != 0)
568 if ((r
= sshbuf_put_string(buf
, NULL
, 0)) != 0)
571 /* Store the revoked serials. */
572 for (rs
= RB_MIN(revoked_serial_tree
, &rc
->revoked_serials
);
574 rs
= RB_NEXT(revoked_serial_tree
, &rc
->revoked_serials
, rs
)) {
575 KRL_DBG(("%s: serial %llu:%llu state 0x%02x", __func__
,
576 (long long unsigned)rs
->lo
, (long long unsigned)rs
->hi
,
579 /* Check contiguous length and gap to next section (if any) */
580 nrs
= RB_NEXT(revoked_serial_tree
, &rc
->revoked_serials
, rs
);
582 gap
= nrs
== NULL
? 0 : nrs
->lo
- rs
->hi
;
583 contig
= 1 + (rs
->hi
- rs
->lo
);
585 /* Choose next state based on these */
586 next_state
= choose_next_state(state
, contig
, final
,
587 state
== 0 ? 0 : rs
->lo
- last
, gap
, &force_new_sect
);
590 * If the current section is a range section or has a different
591 * type to the next section, then finish it off now.
593 if (state
!= 0 && (force_new_sect
|| next_state
!= state
||
594 state
== KRL_SECTION_CERT_SERIAL_RANGE
)) {
595 KRL_DBG(("%s: finish state 0x%02x", __func__
, state
));
597 case KRL_SECTION_CERT_SERIAL_LIST
:
598 case KRL_SECTION_CERT_SERIAL_RANGE
:
600 case KRL_SECTION_CERT_SERIAL_BITMAP
:
601 if ((r
= put_bitmap(sect
, bitmap
)) != 0)
607 if ((r
= sshbuf_put_u8(buf
, state
)) != 0 ||
608 (r
= sshbuf_put_stringb(buf
, sect
)) != 0)
613 /* If we are starting a new section then prepare it now */
614 if (next_state
!= state
|| force_new_sect
) {
615 KRL_DBG(("%s: start state 0x%02x", __func__
,
620 case KRL_SECTION_CERT_SERIAL_LIST
:
621 case KRL_SECTION_CERT_SERIAL_RANGE
:
623 case KRL_SECTION_CERT_SERIAL_BITMAP
:
624 if ((bitmap
= bitmap_new()) == NULL
) {
625 r
= SSH_ERR_ALLOC_FAIL
;
628 bitmap_start
= rs
->lo
;
629 if ((r
= sshbuf_put_u64(sect
,
636 /* Perform section-specific processing */
638 case KRL_SECTION_CERT_SERIAL_LIST
:
639 for (i
= 0; i
< contig
; i
++) {
640 if ((r
= sshbuf_put_u64(sect
, rs
->lo
+ i
)) != 0)
644 case KRL_SECTION_CERT_SERIAL_RANGE
:
645 if ((r
= sshbuf_put_u64(sect
, rs
->lo
)) != 0 ||
646 (r
= sshbuf_put_u64(sect
, rs
->hi
)) != 0)
649 case KRL_SECTION_CERT_SERIAL_BITMAP
:
650 if (rs
->lo
- bitmap_start
> INT_MAX
) {
651 error("%s: insane bitmap gap", __func__
);
654 for (i
= 0; i
< contig
; i
++) {
655 if (bitmap_set_bit(bitmap
,
656 rs
->lo
+ i
- bitmap_start
) != 0) {
657 r
= SSH_ERR_ALLOC_FAIL
;
665 /* Flush the remaining section, if any */
667 KRL_DBG(("%s: serial final flush for state 0x%02x",
670 case KRL_SECTION_CERT_SERIAL_LIST
:
671 case KRL_SECTION_CERT_SERIAL_RANGE
:
673 case KRL_SECTION_CERT_SERIAL_BITMAP
:
674 if ((r
= put_bitmap(sect
, bitmap
)) != 0)
680 if ((r
= sshbuf_put_u8(buf
, state
)) != 0 ||
681 (r
= sshbuf_put_stringb(buf
, sect
)) != 0)
684 KRL_DBG(("%s: serial done ", __func__
));
686 /* Now output a section for any revocations by key ID */
688 RB_FOREACH(rki
, revoked_key_id_tree
, &rc
->revoked_key_ids
) {
689 KRL_DBG(("%s: key ID %s", __func__
, rki
->key_id
));
690 if ((r
= sshbuf_put_cstring(sect
, rki
->key_id
)) != 0)
693 if (sshbuf_len(sect
) != 0) {
694 if ((r
= sshbuf_put_u8(buf
, KRL_SECTION_CERT_KEY_ID
)) != 0 ||
695 (r
= sshbuf_put_stringb(buf
, sect
)) != 0)
706 ssh_krl_to_blob(struct ssh_krl
*krl
, struct sshbuf
*buf
,
707 const struct sshkey
**sign_keys
, u_int nsign_keys
)
709 int r
= SSH_ERR_INTERNAL_ERROR
;
710 struct revoked_certs
*rc
;
711 struct revoked_blob
*rb
;
713 u_char
*sblob
= NULL
;
716 if (krl
->generated_date
== 0)
717 krl
->generated_date
= time(NULL
);
719 if ((sect
= sshbuf_new()) == NULL
)
720 return SSH_ERR_ALLOC_FAIL
;
722 /* Store the header */
723 if ((r
= sshbuf_put(buf
, KRL_MAGIC
, sizeof(KRL_MAGIC
) - 1)) != 0 ||
724 (r
= sshbuf_put_u32(buf
, KRL_FORMAT_VERSION
)) != 0 ||
725 (r
= sshbuf_put_u64(buf
, krl
->krl_version
)) != 0 ||
726 (r
= sshbuf_put_u64(buf
, krl
->generated_date
)) != 0 ||
727 (r
= sshbuf_put_u64(buf
, krl
->flags
)) != 0 ||
728 (r
= sshbuf_put_string(buf
, NULL
, 0)) != 0 ||
729 (r
= sshbuf_put_cstring(buf
, krl
->comment
)) != 0)
732 /* Store sections for revoked certificates */
733 TAILQ_FOREACH(rc
, &krl
->revoked_certs
, entry
) {
735 if ((r
= revoked_certs_generate(rc
, sect
)) != 0)
737 if ((r
= sshbuf_put_u8(buf
, KRL_SECTION_CERTIFICATES
)) != 0 ||
738 (r
= sshbuf_put_stringb(buf
, sect
)) != 0)
742 /* Finally, output sections for revocations by public key/hash */
744 RB_FOREACH(rb
, revoked_blob_tree
, &krl
->revoked_keys
) {
745 KRL_DBG(("%s: key len %zu ", __func__
, rb
->len
));
746 if ((r
= sshbuf_put_string(sect
, rb
->blob
, rb
->len
)) != 0)
749 if (sshbuf_len(sect
) != 0) {
750 if ((r
= sshbuf_put_u8(buf
, KRL_SECTION_EXPLICIT_KEY
)) != 0 ||
751 (r
= sshbuf_put_stringb(buf
, sect
)) != 0)
755 RB_FOREACH(rb
, revoked_blob_tree
, &krl
->revoked_sha1s
) {
756 KRL_DBG(("%s: hash len %zu ", __func__
, rb
->len
));
757 if ((r
= sshbuf_put_string(sect
, rb
->blob
, rb
->len
)) != 0)
760 if (sshbuf_len(sect
) != 0) {
761 if ((r
= sshbuf_put_u8(buf
,
762 KRL_SECTION_FINGERPRINT_SHA1
)) != 0 ||
763 (r
= sshbuf_put_stringb(buf
, sect
)) != 0)
767 for (i
= 0; i
< nsign_keys
; i
++) {
768 KRL_DBG(("%s: signature key %s", __func__
,
769 sshkey_ssh_name(sign_keys
[i
])));
770 if ((r
= sshbuf_put_u8(buf
, KRL_SECTION_SIGNATURE
)) != 0 ||
771 (r
= sshkey_puts(sign_keys
[i
], buf
)) != 0)
774 if ((r
= sshkey_sign(sign_keys
[i
], &sblob
, &slen
,
775 sshbuf_ptr(buf
), sshbuf_len(buf
), NULL
, 0)) != 0)
777 KRL_DBG(("%s: signature sig len %zu", __func__
, slen
));
778 if ((r
= sshbuf_put_string(buf
, sblob
, slen
)) != 0)
790 format_timestamp(u_int64_t timestamp
, char *ts
, size_t nts
)
798 strlcpy(ts
, "<INVALID>", nts
);
801 strftime(ts
, nts
, "%Y%m%dT%H%M%S", tm
);
806 parse_revoked_certs(struct sshbuf
*buf
, struct ssh_krl
*krl
)
808 int r
= SSH_ERR_INTERNAL_ERROR
;
812 struct sshbuf
*subsect
= NULL
;
813 u_int64_t serial
, serial_lo
, serial_hi
;
814 struct bitmap
*bitmap
= NULL
;
816 struct sshkey
*ca_key
= NULL
;
818 if ((subsect
= sshbuf_new()) == NULL
)
819 return SSH_ERR_ALLOC_FAIL
;
821 /* Header: key, reserved */
822 if ((r
= sshbuf_get_string_direct(buf
, &blob
, &blen
)) != 0 ||
823 (r
= sshbuf_skip_string(buf
)) != 0)
825 if (blen
!= 0 && (r
= sshkey_from_blob(blob
, blen
, &ca_key
)) != 0)
828 while (sshbuf_len(buf
) > 0) {
829 sshbuf_free(subsect
);
831 if ((r
= sshbuf_get_u8(buf
, &type
)) != 0 ||
832 (r
= sshbuf_froms(buf
, &subsect
)) != 0)
834 KRL_DBG(("%s: subsection type 0x%02x", __func__
, type
));
835 /* sshbuf_dump(subsect, stderr); */
838 case KRL_SECTION_CERT_SERIAL_LIST
:
839 while (sshbuf_len(subsect
) > 0) {
840 if ((r
= sshbuf_get_u64(subsect
, &serial
)) != 0)
842 if ((r
= ssh_krl_revoke_cert_by_serial(krl
,
843 ca_key
, serial
)) != 0)
847 case KRL_SECTION_CERT_SERIAL_RANGE
:
848 if ((r
= sshbuf_get_u64(subsect
, &serial_lo
)) != 0 ||
849 (r
= sshbuf_get_u64(subsect
, &serial_hi
)) != 0)
851 if ((r
= ssh_krl_revoke_cert_by_serial_range(krl
,
852 ca_key
, serial_lo
, serial_hi
)) != 0)
855 case KRL_SECTION_CERT_SERIAL_BITMAP
:
856 if ((bitmap
= bitmap_new()) == NULL
) {
857 r
= SSH_ERR_ALLOC_FAIL
;
860 if ((r
= sshbuf_get_u64(subsect
, &serial_lo
)) != 0 ||
861 (r
= sshbuf_get_bignum2_bytes_direct(subsect
,
864 if (bitmap_from_string(bitmap
, blob
, blen
) != 0) {
865 r
= SSH_ERR_INVALID_FORMAT
;
868 nbits
= bitmap_nbits(bitmap
);
869 for (serial
= 0; serial
< (u_int64_t
)nbits
; serial
++) {
870 if (serial
> 0 && serial_lo
+ serial
== 0) {
871 error("%s: bitmap wraps u64", __func__
);
872 r
= SSH_ERR_INVALID_FORMAT
;
875 if (!bitmap_test_bit(bitmap
, serial
))
877 if ((r
= ssh_krl_revoke_cert_by_serial(krl
,
878 ca_key
, serial_lo
+ serial
)) != 0)
884 case KRL_SECTION_CERT_KEY_ID
:
885 while (sshbuf_len(subsect
) > 0) {
886 if ((r
= sshbuf_get_cstring(subsect
,
887 &key_id
, NULL
)) != 0)
889 if ((r
= ssh_krl_revoke_cert_by_key_id(krl
,
890 ca_key
, key_id
)) != 0)
897 error("Unsupported KRL certificate section %u", type
);
898 r
= SSH_ERR_INVALID_FORMAT
;
901 if (sshbuf_len(subsect
) > 0) {
902 error("KRL certificate section contains unparsed data");
903 r
= SSH_ERR_INVALID_FORMAT
;
914 sshbuf_free(subsect
);
919 /* Attempt to parse a KRL, checking its signature (if any) with sign_ca_keys. */
921 ssh_krl_from_blob(struct sshbuf
*buf
, struct ssh_krl
**krlp
,
922 const struct sshkey
**sign_ca_keys
, size_t nsign_ca_keys
)
924 struct sshbuf
*copy
= NULL
, *sect
= NULL
;
925 struct ssh_krl
*krl
= NULL
;
927 int r
= SSH_ERR_INTERNAL_ERROR
, sig_seen
;
928 struct sshkey
*key
= NULL
, **ca_used
= NULL
, **tmp_ca_used
;
929 u_char type
, *rdata
= NULL
;
931 size_t i
, j
, sig_off
, sects_off
, rlen
, blen
, nca_used
;
932 u_int format_version
;
936 if (sshbuf_len(buf
) < sizeof(KRL_MAGIC
) - 1 ||
937 memcmp(sshbuf_ptr(buf
), KRL_MAGIC
, sizeof(KRL_MAGIC
) - 1) != 0) {
938 debug3("%s: not a KRL", __func__
);
939 return SSH_ERR_KRL_BAD_MAGIC
;
942 /* Take a copy of the KRL buffer so we can verify its signature later */
943 if ((copy
= sshbuf_fromb(buf
)) == NULL
) {
944 r
= SSH_ERR_ALLOC_FAIL
;
947 if ((r
= sshbuf_consume(copy
, sizeof(KRL_MAGIC
) - 1)) != 0)
950 if ((krl
= ssh_krl_init()) == NULL
) {
951 error("%s: alloc failed", __func__
);
955 if ((r
= sshbuf_get_u32(copy
, &format_version
)) != 0)
957 if (format_version
!= KRL_FORMAT_VERSION
) {
958 r
= SSH_ERR_INVALID_FORMAT
;
961 if ((r
= sshbuf_get_u64(copy
, &krl
->krl_version
)) != 0 ||
962 (r
= sshbuf_get_u64(copy
, &krl
->generated_date
)) != 0 ||
963 (r
= sshbuf_get_u64(copy
, &krl
->flags
)) != 0 ||
964 (r
= sshbuf_skip_string(copy
)) != 0 ||
965 (r
= sshbuf_get_cstring(copy
, &krl
->comment
, NULL
)) != 0)
968 format_timestamp(krl
->generated_date
, timestamp
, sizeof(timestamp
));
969 debug("KRL version %llu generated at %s%s%s",
970 (long long unsigned)krl
->krl_version
, timestamp
,
971 *krl
->comment
? ": " : "", krl
->comment
);
974 * 1st pass: verify signatures, if any. This is done to avoid
975 * detailed parsing of data whose provenance is unverified.
978 if (sshbuf_len(buf
) < sshbuf_len(copy
)) {
979 /* Shouldn't happen */
980 r
= SSH_ERR_INTERNAL_ERROR
;
983 sects_off
= sshbuf_len(buf
) - sshbuf_len(copy
);
984 while (sshbuf_len(copy
) > 0) {
985 if ((r
= sshbuf_get_u8(copy
, &type
)) != 0 ||
986 (r
= sshbuf_get_string_direct(copy
, &blob
, &blen
)) != 0)
988 KRL_DBG(("%s: first pass, section 0x%02x", __func__
, type
));
989 if (type
!= KRL_SECTION_SIGNATURE
) {
991 error("KRL contains non-signature section "
993 r
= SSH_ERR_INVALID_FORMAT
;
996 /* Not interested for now. */
1000 /* First string component is the signing key */
1001 if ((r
= sshkey_from_blob(blob
, blen
, &key
)) != 0) {
1002 r
= SSH_ERR_INVALID_FORMAT
;
1005 if (sshbuf_len(buf
) < sshbuf_len(copy
)) {
1006 /* Shouldn't happen */
1007 r
= SSH_ERR_INTERNAL_ERROR
;
1010 sig_off
= sshbuf_len(buf
) - sshbuf_len(copy
);
1011 /* Second string component is the signature itself */
1012 if ((r
= sshbuf_get_string_direct(copy
, &blob
, &blen
)) != 0) {
1013 r
= SSH_ERR_INVALID_FORMAT
;
1016 /* Check signature over entire KRL up to this point */
1017 if ((r
= sshkey_verify(key
, blob
, blen
,
1018 sshbuf_ptr(buf
), sig_off
, 0)) != 0)
1020 /* Check if this key has already signed this KRL */
1021 for (i
= 0; i
< nca_used
; i
++) {
1022 if (sshkey_equal(ca_used
[i
], key
)) {
1023 error("KRL signed more than once with "
1025 r
= SSH_ERR_INVALID_FORMAT
;
1029 /* Record keys used to sign the KRL */
1030 tmp_ca_used
= reallocarray(ca_used
, nca_used
+ 1,
1032 if (tmp_ca_used
== NULL
) {
1033 r
= SSH_ERR_ALLOC_FAIL
;
1036 ca_used
= tmp_ca_used
;
1037 ca_used
[nca_used
++] = key
;
1041 if (sshbuf_len(copy
) != 0) {
1042 /* Shouldn't happen */
1043 r
= SSH_ERR_INTERNAL_ERROR
;
1048 * 2nd pass: parse and load the KRL, skipping the header to the point
1049 * where the section start.
1052 if ((copy
= sshbuf_fromb(buf
)) == NULL
) {
1053 r
= SSH_ERR_ALLOC_FAIL
;
1056 if ((r
= sshbuf_consume(copy
, sects_off
)) != 0)
1058 while (sshbuf_len(copy
) > 0) {
1061 if ((r
= sshbuf_get_u8(copy
, &type
)) != 0 ||
1062 (r
= sshbuf_froms(copy
, §
)) != 0)
1064 KRL_DBG(("%s: second pass, section 0x%02x", __func__
, type
));
1067 case KRL_SECTION_CERTIFICATES
:
1068 if ((r
= parse_revoked_certs(sect
, krl
)) != 0)
1071 case KRL_SECTION_EXPLICIT_KEY
:
1072 case KRL_SECTION_FINGERPRINT_SHA1
:
1073 while (sshbuf_len(sect
) > 0) {
1074 if ((r
= sshbuf_get_string(sect
,
1075 &rdata
, &rlen
)) != 0)
1077 if (type
== KRL_SECTION_FINGERPRINT_SHA1
&&
1079 error("%s: bad SHA1 length", __func__
);
1080 r
= SSH_ERR_INVALID_FORMAT
;
1083 if ((r
= revoke_blob(
1084 type
== KRL_SECTION_EXPLICIT_KEY
?
1085 &krl
->revoked_keys
: &krl
->revoked_sha1s
,
1088 rdata
= NULL
; /* revoke_blob frees rdata */
1091 case KRL_SECTION_SIGNATURE
:
1092 /* Handled above, but still need to stay in synch */
1095 if ((r
= sshbuf_skip_string(copy
)) != 0)
1099 error("Unsupported KRL section %u", type
);
1100 r
= SSH_ERR_INVALID_FORMAT
;
1103 if (sect
!= NULL
&& sshbuf_len(sect
) > 0) {
1104 error("KRL section contains unparsed data");
1105 r
= SSH_ERR_INVALID_FORMAT
;
1110 /* Check that the key(s) used to sign the KRL weren't revoked */
1112 for (i
= 0; i
< nca_used
; i
++) {
1113 if (ssh_krl_check_key(krl
, ca_used
[i
]) == 0)
1116 sshkey_free(ca_used
[i
]);
1120 if (nca_used
&& !sig_seen
) {
1121 error("All keys used to sign KRL were revoked");
1122 r
= SSH_ERR_KEY_REVOKED
;
1126 /* If we have CA keys, then verify that one was used to sign the KRL */
1127 if (sig_seen
&& nsign_ca_keys
!= 0) {
1129 for (i
= 0; !sig_seen
&& i
< nsign_ca_keys
; i
++) {
1130 for (j
= 0; j
< nca_used
; j
++) {
1131 if (ca_used
[j
] == NULL
)
1133 if (sshkey_equal(ca_used
[j
], sign_ca_keys
[i
])) {
1140 r
= SSH_ERR_SIGNATURE_INVALID
;
1141 error("KRL not signed with any trusted key");
1151 for (i
= 0; i
< nca_used
; i
++)
1152 sshkey_free(ca_used
[i
]);
1161 /* Checks certificate serial number and key ID revocation */
1163 is_cert_revoked(const struct sshkey
*key
, struct revoked_certs
*rc
)
1165 struct revoked_serial rs
, *ers
;
1166 struct revoked_key_id rki
, *erki
;
1168 /* Check revocation by cert key ID */
1169 memset(&rki
, 0, sizeof(rki
));
1170 rki
.key_id
= key
->cert
->key_id
;
1171 erki
= RB_FIND(revoked_key_id_tree
, &rc
->revoked_key_ids
, &rki
);
1173 KRL_DBG(("%s: revoked by key ID", __func__
));
1174 return SSH_ERR_KEY_REVOKED
;
1178 * Zero serials numbers are ignored (it's the default when the
1179 * CA doesn't specify one).
1181 if (key
->cert
->serial
== 0)
1184 memset(&rs
, 0, sizeof(rs
));
1185 rs
.lo
= rs
.hi
= key
->cert
->serial
;
1186 ers
= RB_FIND(revoked_serial_tree
, &rc
->revoked_serials
, &rs
);
1188 KRL_DBG(("%s: revoked serial %llu matched %llu:%llu", __func__
,
1189 key
->cert
->serial
, ers
->lo
, ers
->hi
));
1190 return SSH_ERR_KEY_REVOKED
;
1195 /* Checks whether a given key/cert is revoked. Does not check its CA */
1197 is_key_revoked(struct ssh_krl
*krl
, const struct sshkey
*key
)
1199 struct revoked_blob rb
, *erb
;
1200 struct revoked_certs
*rc
;
1203 /* Check explicitly revoked hashes first */
1204 memset(&rb
, 0, sizeof(rb
));
1205 if ((r
= sshkey_fingerprint_raw(key
, SSH_DIGEST_SHA1
,
1206 &rb
.blob
, &rb
.len
)) != 0)
1208 erb
= RB_FIND(revoked_blob_tree
, &krl
->revoked_sha1s
, &rb
);
1211 KRL_DBG(("%s: revoked by key SHA1", __func__
));
1212 return SSH_ERR_KEY_REVOKED
;
1215 /* Next, explicit keys */
1216 memset(&rb
, 0, sizeof(rb
));
1217 if ((r
= plain_key_blob(key
, &rb
.blob
, &rb
.len
)) != 0)
1219 erb
= RB_FIND(revoked_blob_tree
, &krl
->revoked_keys
, &rb
);
1222 KRL_DBG(("%s: revoked by explicit key", __func__
));
1223 return SSH_ERR_KEY_REVOKED
;
1226 if (!sshkey_is_cert(key
))
1229 /* Check cert revocation for the specified CA */
1230 if ((r
= revoked_certs_for_ca_key(krl
, key
->cert
->signature_key
,
1234 if ((r
= is_cert_revoked(key
, rc
)) != 0)
1237 /* Check cert revocation for the wildcard CA */
1238 if ((r
= revoked_certs_for_ca_key(krl
, NULL
, &rc
, 0)) != 0)
1241 if ((r
= is_cert_revoked(key
, rc
)) != 0)
1245 KRL_DBG(("%s: %llu no match", __func__
, key
->cert
->serial
));
1250 ssh_krl_check_key(struct ssh_krl
*krl
, const struct sshkey
*key
)
1254 KRL_DBG(("%s: checking key", __func__
));
1255 if ((r
= is_key_revoked(krl
, key
)) != 0)
1257 if (sshkey_is_cert(key
)) {
1258 debug2("%s: checking CA key", __func__
);
1259 if ((r
= is_key_revoked(krl
, key
->cert
->signature_key
)) != 0)
1262 KRL_DBG(("%s: key okay", __func__
));
1267 ssh_krl_file_contains_key(const char *path
, const struct sshkey
*key
)
1269 struct sshbuf
*krlbuf
= NULL
;
1270 struct ssh_krl
*krl
= NULL
;
1271 int oerrno
= 0, r
, fd
;
1276 if ((krlbuf
= sshbuf_new()) == NULL
)
1277 return SSH_ERR_ALLOC_FAIL
;
1278 if ((fd
= open(path
, O_RDONLY
)) == -1) {
1279 r
= SSH_ERR_SYSTEM_ERROR
;
1283 if ((r
= sshkey_load_file(fd
, krlbuf
)) != 0) {
1287 if ((r
= ssh_krl_from_blob(krlbuf
, &krl
, NULL
, 0)) != 0)
1289 debug2("%s: checking KRL %s", __func__
, path
);
1290 r
= ssh_krl_check_key(krl
, key
);
1293 sshbuf_free(krlbuf
);