crypto/openssh/krl.c

   1 /*
   2  * Copyright (c) 2012 Damien Miller <djm@mindrot.org>
   3  *
   4  * Permission to use, copy, modify, and distribute this software for any
   5  * purpose with or without fee is hereby granted, provided that the above
   6  * copyright notice and this permission notice appear in all copies.
   7  *
   8  * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
   9  * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
  10  * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
  11  * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
  12  * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
  13  * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
  14  * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
  15  */
  16
  17 /* $OpenBSD: krl.c,v 1.55 2023/03/14 07:28:47 dtucker Exp $ */
  18
  19 #include "includes.h"
  20
  21 #include <sys/types.h>
  22 #include <openbsd-compat/sys-tree.h>
  23 #include <openbsd-compat/sys-queue.h>
  24
  25 #include <errno.h>
  26 #include <fcntl.h>
  27 #include <limits.h>
  28 #include <stdlib.h>
  29 #include <string.h>
  30 #include <time.h>
  31 #include <unistd.h>
  32
  33 #include "sshbuf.h"
  34 #include "ssherr.h"
  35 #include "sshkey.h"
  36 #include "authfile.h"
  37 #include "misc.h"
  38 #include "log.h"
  39 #include "digest.h"
  40 #include "bitmap.h"
  41 #include "utf8.h"
  42
  43 #include "krl.h"
  44
  45 /* #define DEBUG_KRL */
  46 #ifdef DEBUG_KRL
  47 # define KRL_DBG(x) debug3_f x
  48 #else
  49 # define KRL_DBG(x)
  50 #endif
  51
  52 /*
  53  * Trees of revoked serial numbers, key IDs and keys. This allows
  54  * quick searching, querying and producing lists in canonical order.
  55  */
  56
  57 /* Tree of serial numbers. XXX make smarter: really need a real sparse bitmap */
  58 struct revoked_serial {
  59         u_int64_t lo, hi;
  60         RB_ENTRY(revoked_serial) tree_entry;
  61 };
  62 static int serial_cmp(struct revoked_serial *a, struct revoked_serial *b);
  63 RB_HEAD(revoked_serial_tree, revoked_serial);
  64 RB_GENERATE_STATIC(revoked_serial_tree, revoked_serial, tree_entry, serial_cmp)
  65
  66 /* Tree of key IDs */
  67 struct revoked_key_id {
  68         char *key_id;
  69         RB_ENTRY(revoked_key_id) tree_entry;
  70 };
  71 static int key_id_cmp(struct revoked_key_id *a, struct revoked_key_id *b);
  72 RB_HEAD(revoked_key_id_tree, revoked_key_id);
  73 RB_GENERATE_STATIC(revoked_key_id_tree, revoked_key_id, tree_entry, key_id_cmp)
  74
  75 /* Tree of blobs (used for keys and fingerprints) */
  76 struct revoked_blob {
  77         u_char *blob;
  78         size_t len;
  79         RB_ENTRY(revoked_blob) tree_entry;
  80 };
  81 static int blob_cmp(struct revoked_blob *a, struct revoked_blob *b);
  82 RB_HEAD(revoked_blob_tree, revoked_blob);
  83 RB_GENERATE_STATIC(revoked_blob_tree, revoked_blob, tree_entry, blob_cmp)
  84
  85 /* Tracks revoked certs for a single CA */
  86 struct revoked_certs {
  87         struct sshkey *ca_key;
  88         struct revoked_serial_tree revoked_serials;
  89         struct revoked_key_id_tree revoked_key_ids;
  90         TAILQ_ENTRY(revoked_certs) entry;
  91 };
  92 TAILQ_HEAD(revoked_certs_list, revoked_certs);
  93
  94 struct ssh_krl {
  95         u_int64_t krl_version;
  96         u_int64_t generated_date;
  97         u_int64_t flags;
  98         char *comment;
  99         struct revoked_blob_tree revoked_keys;
 100         struct revoked_blob_tree revoked_sha1s;
 101         struct revoked_blob_tree revoked_sha256s;
 102         struct revoked_certs_list revoked_certs;
 103 };
 104
 105 /* Return equal if a and b overlap */
 106 static int
 107 serial_cmp(struct revoked_serial *a, struct revoked_serial *b)
 108 {
 109         if (a->hi >= b->lo && a->lo <= b->hi)
 110                 return 0;
 111         return a->lo < b->lo ? -1 : 1;
 112 }
 113
 114 static int
 115 key_id_cmp(struct revoked_key_id *a, struct revoked_key_id *b)
 116 {
 117         return strcmp(a->key_id, b->key_id);
 118 }
 119
 120 static int
 121 blob_cmp(struct revoked_blob *a, struct revoked_blob *b)
 122 {
 123         int r;
 124
 125         if (a->len != b->len) {
 126                 if ((r = memcmp(a->blob, b->blob, MINIMUM(a->len, b->len))) != 0)
 127                         return r;
 128                 return a->len > b->len ? 1 : -1;
 129         } else
 130                 return memcmp(a->blob, b->blob, a->len);
 131 }
 132
 133 struct ssh_krl *
 134 ssh_krl_init(void)
 135 {
 136         struct ssh_krl *krl;
 137
 138         if ((krl = calloc(1, sizeof(*krl))) == NULL)
 139                 return NULL;
 140         RB_INIT(&krl->revoked_keys);
 141         RB_INIT(&krl->revoked_sha1s);
 142         RB_INIT(&krl->revoked_sha256s);
 143         TAILQ_INIT(&krl->revoked_certs);
 144         return krl;
 145 }
 146
 147 static void
 148 revoked_certs_free(struct revoked_certs *rc)
 149 {
 150         struct revoked_serial *rs, *trs;
 151         struct revoked_key_id *rki, *trki;
 152
 153         RB_FOREACH_SAFE(rs, revoked_serial_tree, &rc->revoked_serials, trs) {
 154                 RB_REMOVE(revoked_serial_tree, &rc->revoked_serials, rs);
 155                 free(rs);
 156         }
 157         RB_FOREACH_SAFE(rki, revoked_key_id_tree, &rc->revoked_key_ids, trki) {
 158                 RB_REMOVE(revoked_key_id_tree, &rc->revoked_key_ids, rki);
 159                 free(rki->key_id);
 160                 free(rki);
 161         }
 162         sshkey_free(rc->ca_key);
 163 }
 164
 165 void
 166 ssh_krl_free(struct ssh_krl *krl)
 167 {
 168         struct revoked_blob *rb, *trb;
 169         struct revoked_certs *rc, *trc;
 170
 171         if (krl == NULL)
 172                 return;
 173
 174         free(krl->comment);
 175         RB_FOREACH_SAFE(rb, revoked_blob_tree, &krl->revoked_keys, trb) {
 176                 RB_REMOVE(revoked_blob_tree, &krl->revoked_keys, rb);
 177                 free(rb->blob);
 178                 free(rb);
 179         }
 180         RB_FOREACH_SAFE(rb, revoked_blob_tree, &krl->revoked_sha1s, trb) {
 181                 RB_REMOVE(revoked_blob_tree, &krl->revoked_sha1s, rb);
 182                 free(rb->blob);
 183                 free(rb);
 184         }
 185         RB_FOREACH_SAFE(rb, revoked_blob_tree, &krl->revoked_sha256s, trb) {
 186                 RB_REMOVE(revoked_blob_tree, &krl->revoked_sha256s, rb);
 187                 free(rb->blob);
 188                 free(rb);
 189         }
 190         TAILQ_FOREACH_SAFE(rc, &krl->revoked_certs, entry, trc) {
 191                 TAILQ_REMOVE(&krl->revoked_certs, rc, entry);
 192                 revoked_certs_free(rc);
 193         }
 194         free(krl);
 195 }
 196
 197 void
 198 ssh_krl_set_version(struct ssh_krl *krl, u_int64_t version)
 199 {
 200         krl->krl_version = version;
 201 }
 202
 203 int
 204 ssh_krl_set_comment(struct ssh_krl *krl, const char *comment)
 205 {
 206         free(krl->comment);
 207         if ((krl->comment = strdup(comment)) == NULL)
 208                 return SSH_ERR_ALLOC_FAIL;
 209         return 0;
 210 }
 211
 212 /*
 213  * Find the revoked_certs struct for a CA key. If allow_create is set then
 214  * create a new one in the tree if one did not exist already.
 215  */
 216 static int
 217 revoked_certs_for_ca_key(struct ssh_krl *krl, const struct sshkey *ca_key,
 218     struct revoked_certs **rcp, int allow_create)
 219 {
 220         struct revoked_certs *rc;
 221         int r;
 222
 223         *rcp = NULL;
 224         TAILQ_FOREACH(rc, &krl->revoked_certs, entry) {
 225                 if ((ca_key == NULL && rc->ca_key == NULL) ||
 226                     sshkey_equal(rc->ca_key, ca_key)) {
 227                         *rcp = rc;
 228                         return 0;
 229                 }
 230         }
 231         if (!allow_create)
 232                 return 0;
 233         /* If this CA doesn't exist in the list then add it now */
 234         if ((rc = calloc(1, sizeof(*rc))) == NULL)
 235                 return SSH_ERR_ALLOC_FAIL;
 236         if (ca_key == NULL)
 237                 rc->ca_key = NULL;
 238         else if ((r = sshkey_from_private(ca_key, &rc->ca_key)) != 0) {
 239                 free(rc);
 240                 return r;
 241         }
 242         RB_INIT(&rc->revoked_serials);
 243         RB_INIT(&rc->revoked_key_ids);
 244         TAILQ_INSERT_TAIL(&krl->revoked_certs, rc, entry);
 245         KRL_DBG(("new CA %s", ca_key == NULL ? "*" : sshkey_type(ca_key)));
 246         *rcp = rc;
 247         return 0;
 248 }
 249
 250 static int
 251 insert_serial_range(struct revoked_serial_tree *rt, u_int64_t lo, u_int64_t hi)
 252 {
 253         struct revoked_serial rs, *ers, *crs, *irs;
 254
 255         KRL_DBG(("insert %llu:%llu", lo, hi));
 256         memset(&rs, 0, sizeof(rs));
 257         rs.lo = lo;
 258         rs.hi = hi;
 259         ers = RB_NFIND(revoked_serial_tree, rt, &rs);
 260         if (ers == NULL || serial_cmp(ers, &rs) != 0) {
 261                 /* No entry matches. Just insert */
 262                 if ((irs = malloc(sizeof(rs))) == NULL)
 263                         return SSH_ERR_ALLOC_FAIL;
 264                 memcpy(irs, &rs, sizeof(*irs));
 265                 ers = RB_INSERT(revoked_serial_tree, rt, irs);
 266                 if (ers != NULL) {
 267                         KRL_DBG(("bad: ers != NULL"));
 268                         /* Shouldn't happen */
 269                         free(irs);
 270                         return SSH_ERR_INTERNAL_ERROR;
 271                 }
 272                 ers = irs;
 273         } else {
 274                 KRL_DBG(("overlap found %llu:%llu", ers->lo, ers->hi));
 275                 /*
 276                  * The inserted entry overlaps an existing one. Grow the
 277                  * existing entry.
 278                  */
 279                 if (ers->lo > lo)
 280                         ers->lo = lo;
 281                 if (ers->hi < hi)
 282                         ers->hi = hi;
 283         }
 284
 285         /*
 286          * The inserted or revised range might overlap or abut adjacent ones;
 287          * coalesce as necessary.
 288          */
 289
 290         /* Check predecessors */
 291         while ((crs = RB_PREV(revoked_serial_tree, rt, ers)) != NULL) {
 292                 KRL_DBG(("pred %llu:%llu", crs->lo, crs->hi));
 293                 if (ers->lo != 0 && crs->hi < ers->lo - 1)
 294                         break;
 295                 /* This entry overlaps. */
 296                 if (crs->lo < ers->lo) {
 297                         ers->lo = crs->lo;
 298                         KRL_DBG(("pred extend %llu:%llu", ers->lo, ers->hi));
 299                 }
 300                 RB_REMOVE(revoked_serial_tree, rt, crs);
 301                 free(crs);
 302         }
 303         /* Check successors */
 304         while ((crs = RB_NEXT(revoked_serial_tree, rt, ers)) != NULL) {
 305                 KRL_DBG(("succ %llu:%llu", crs->lo, crs->hi));
 306                 if (ers->hi != (u_int64_t)-1 && crs->lo > ers->hi + 1)
 307                         break;
 308                 /* This entry overlaps. */
 309                 if (crs->hi > ers->hi) {
 310                         ers->hi = crs->hi;
 311                         KRL_DBG(("succ extend %llu:%llu", ers->lo, ers->hi));
 312                 }
 313                 RB_REMOVE(revoked_serial_tree, rt, crs);
 314                 free(crs);
 315         }
 316         KRL_DBG(("done, final %llu:%llu", ers->lo, ers->hi));
 317         return 0;
 318 }
 319
 320 int
 321 ssh_krl_revoke_cert_by_serial(struct ssh_krl *krl, const struct sshkey *ca_key,
 322     u_int64_t serial)
 323 {
 324         return ssh_krl_revoke_cert_by_serial_range(krl, ca_key, serial, serial);
 325 }
 326
 327 int
 328 ssh_krl_revoke_cert_by_serial_range(struct ssh_krl *krl,
 329     const struct sshkey *ca_key, u_int64_t lo, u_int64_t hi)
 330 {
 331         struct revoked_certs *rc;
 332         int r;
 333
 334         if (lo > hi || lo == 0)
 335                 return SSH_ERR_INVALID_ARGUMENT;
 336         if ((r = revoked_certs_for_ca_key(krl, ca_key, &rc, 1)) != 0)
 337                 return r;
 338         return insert_serial_range(&rc->revoked_serials, lo, hi);
 339 }
 340
 341 int
 342 ssh_krl_revoke_cert_by_key_id(struct ssh_krl *krl, const struct sshkey *ca_key,
 343     const char *key_id)
 344 {
 345         struct revoked_key_id *rki, *erki;
 346         struct revoked_certs *rc;
 347         int r;
 348
 349         if ((r = revoked_certs_for_ca_key(krl, ca_key, &rc, 1)) != 0)
 350                 return r;
 351
 352         KRL_DBG(("revoke %s", key_id));
 353         if ((rki = calloc(1, sizeof(*rki))) == NULL ||
 354             (rki->key_id = strdup(key_id)) == NULL) {
 355                 free(rki);
 356                 return SSH_ERR_ALLOC_FAIL;
 357         }
 358         erki = RB_INSERT(revoked_key_id_tree, &rc->revoked_key_ids, rki);
 359         if (erki != NULL) {
 360                 free(rki->key_id);
 361                 free(rki);
 362         }
 363         return 0;
 364 }
 365
 366 /* Convert "key" to a public key blob without any certificate information */
 367 static int
 368 plain_key_blob(const struct sshkey *key, u_char **blob, size_t *blen)
 369 {
 370         struct sshkey *kcopy;
 371         int r;
 372
 373         if ((r = sshkey_from_private(key, &kcopy)) != 0)
 374                 return r;
 375         if (sshkey_is_cert(kcopy)) {
 376                 if ((r = sshkey_drop_cert(kcopy)) != 0) {
 377                         sshkey_free(kcopy);
 378                         return r;
 379                 }
 380         }
 381         r = sshkey_to_blob(kcopy, blob, blen);
 382         sshkey_free(kcopy);
 383         return r;
 384 }
 385
 386 /* Revoke a key blob. Ownership of blob is transferred to the tree */
 387 static int
 388 revoke_blob(struct revoked_blob_tree *rbt, u_char *blob, size_t len)
 389 {
 390         struct revoked_blob *rb, *erb;
 391
 392         if ((rb = calloc(1, sizeof(*rb))) == NULL)
 393                 return SSH_ERR_ALLOC_FAIL;
 394         rb->blob = blob;
 395         rb->len = len;
 396         erb = RB_INSERT(revoked_blob_tree, rbt, rb);
 397         if (erb != NULL) {
 398                 free(rb->blob);
 399                 free(rb);
 400         }
 401         return 0;
 402 }
 403
 404 int
 405 ssh_krl_revoke_key_explicit(struct ssh_krl *krl, const struct sshkey *key)
 406 {
 407         u_char *blob;
 408         size_t len;
 409         int r;
 410
 411         debug3_f("revoke type %s", sshkey_type(key));
 412         if ((r = plain_key_blob(key, &blob, &len)) != 0)
 413                 return r;
 414         return revoke_blob(&krl->revoked_keys, blob, len);
 415 }
 416
 417 static int
 418 revoke_by_hash(struct revoked_blob_tree *target, const u_char *p, size_t len)
 419 {
 420         u_char *blob;
 421         int r;
 422
 423         /* need to copy hash, as revoke_blob steals ownership */
 424         if ((blob = malloc(len)) == NULL)
 425                 return SSH_ERR_SYSTEM_ERROR;
 426         memcpy(blob, p, len);
 427         if ((r = revoke_blob(target, blob, len)) != 0) {
 428                 free(blob);
 429                 return r;
 430         }
 431         return 0;
 432 }
 433
 434 int
 435 ssh_krl_revoke_key_sha1(struct ssh_krl *krl, const u_char *p, size_t len)
 436 {
 437         debug3_f("revoke by sha1");
 438         if (len != 20)
 439                 return SSH_ERR_INVALID_FORMAT;
 440         return revoke_by_hash(&krl->revoked_sha1s, p, len);
 441 }
 442
 443 int
 444 ssh_krl_revoke_key_sha256(struct ssh_krl *krl, const u_char *p, size_t len)
 445 {
 446         debug3_f("revoke by sha256");
 447         if (len != 32)
 448                 return SSH_ERR_INVALID_FORMAT;
 449         return revoke_by_hash(&krl->revoked_sha256s, p, len);
 450 }
 451
 452 int
 453 ssh_krl_revoke_key(struct ssh_krl *krl, const struct sshkey *key)
 454 {
 455         /* XXX replace with SHA256? */
 456         if (!sshkey_is_cert(key))
 457                 return ssh_krl_revoke_key_explicit(krl, key);
 458
 459         if (key->cert->serial == 0) {
 460                 return ssh_krl_revoke_cert_by_key_id(krl,
 461                     key->cert->signature_key,
 462                     key->cert->key_id);
 463         } else {
 464                 return ssh_krl_revoke_cert_by_serial(krl,
 465                     key->cert->signature_key,
 466                     key->cert->serial);
 467         }
 468 }
 469
 470 /*
 471  * Select the most compact section type to emit next in a KRL based on
 472  * the current section type, the run length of contiguous revoked serial
 473  * numbers and the gaps from the last and to the next revoked serial.
 474  * Applies a mostly-accurate bit cost model to select the section type
 475  * that will minimise the size of the resultant KRL.
 476  */
 477 static int
 478 choose_next_state(int current_state, u_int64_t contig, int final,
 479     u_int64_t last_gap, u_int64_t next_gap, int *force_new_section)
 480 {
 481         int new_state;
 482         u_int64_t cost, cost_list, cost_range, cost_bitmap, cost_bitmap_restart;
 483
 484         /*
 485          * Avoid unsigned overflows.
 486          * The limits are high enough to avoid confusing the calculations.
 487          */
 488         contig = MINIMUM(contig, 1ULL<<31);
 489         last_gap = MINIMUM(last_gap, 1ULL<<31);
 490         next_gap = MINIMUM(next_gap, 1ULL<<31);
 491
 492         /*
 493          * Calculate the cost to switch from the current state to candidates.
 494          * NB. range sections only ever contain a single range, so their
 495          * switching cost is independent of the current_state.
 496          */
 497         cost_list = cost_bitmap = cost_bitmap_restart = 0;
 498         cost_range = 8;
 499         switch (current_state) {
 500         case KRL_SECTION_CERT_SERIAL_LIST:
 501                 cost_bitmap_restart = cost_bitmap = 8 + 64;
 502                 break;
 503         case KRL_SECTION_CERT_SERIAL_BITMAP:
 504                 cost_list = 8;
 505                 cost_bitmap_restart = 8 + 64;
 506                 break;
 507         case KRL_SECTION_CERT_SERIAL_RANGE:
 508         case 0:
 509                 cost_bitmap_restart = cost_bitmap = 8 + 64;
 510                 cost_list = 8;
 511         }
 512
 513         /* Estimate base cost in bits of each section type */
 514         cost_list += 64 * contig + (final ? 0 : 8+64);
 515         cost_range += (2 * 64) + (final ? 0 : 8+64);
 516         cost_bitmap += last_gap + contig + (final ? 0 : MINIMUM(next_gap, 8+64));
 517         cost_bitmap_restart += contig + (final ? 0 : MINIMUM(next_gap, 8+64));
 518
 519         /* Convert to byte costs for actual comparison */
 520         cost_list = (cost_list + 7) / 8;
 521         cost_bitmap = (cost_bitmap + 7) / 8;
 522         cost_bitmap_restart = (cost_bitmap_restart + 7) / 8;
 523         cost_range = (cost_range + 7) / 8;
 524
 525         /* Now pick the best choice */
 526         *force_new_section = 0;
 527         new_state = KRL_SECTION_CERT_SERIAL_BITMAP;
 528         cost = cost_bitmap;
 529         if (cost_range < cost) {
 530                 new_state = KRL_SECTION_CERT_SERIAL_RANGE;
 531                 cost = cost_range;
 532         }
 533         if (cost_list < cost) {
 534                 new_state = KRL_SECTION_CERT_SERIAL_LIST;
 535                 cost = cost_list;
 536         }
 537         if (cost_bitmap_restart < cost) {
 538                 new_state = KRL_SECTION_CERT_SERIAL_BITMAP;
 539                 *force_new_section = 1;
 540                 cost = cost_bitmap_restart;
 541         }
 542         KRL_DBG(("contig %llu last_gap %llu next_gap %llu final %d, costs:"
 543             "list %llu range %llu bitmap %llu new bitmap %llu, "
 544             "selected 0x%02x%s", (long long unsigned)contig,
 545             (long long unsigned)last_gap, (long long unsigned)next_gap, final,
 546             (long long unsigned)cost_list, (long long unsigned)cost_range,
 547             (long long unsigned)cost_bitmap,
 548             (long long unsigned)cost_bitmap_restart, new_state,
 549             *force_new_section ? " restart" : ""));
 550         return new_state;
 551 }
 552
 553 static int
 554 put_bitmap(struct sshbuf *buf, struct bitmap *bitmap)
 555 {
 556         size_t len;
 557         u_char *blob;
 558         int r;
 559
 560         len = bitmap_nbytes(bitmap);
 561         if ((blob = malloc(len)) == NULL)
 562                 return SSH_ERR_ALLOC_FAIL;
 563         if (bitmap_to_string(bitmap, blob, len) != 0) {
 564                 free(blob);
 565                 return SSH_ERR_INTERNAL_ERROR;
 566         }
 567         r = sshbuf_put_bignum2_bytes(buf, blob, len);
 568         free(blob);
 569         return r;
 570 }
 571
 572 /* Generate a KRL_SECTION_CERTIFICATES KRL section */
 573 static int
 574 revoked_certs_generate(struct revoked_certs *rc, struct sshbuf *buf)
 575 {
 576         int final, force_new_sect, r = SSH_ERR_INTERNAL_ERROR;
 577         u_int64_t i, contig, gap, last = 0, bitmap_start = 0;
 578         struct revoked_serial *rs, *nrs;
 579         struct revoked_key_id *rki;
 580         int next_state, state = 0;
 581         struct sshbuf *sect;
 582         struct bitmap *bitmap = NULL;
 583
 584         if ((sect = sshbuf_new()) == NULL)
 585                 return SSH_ERR_ALLOC_FAIL;
 586
 587         /* Store the header: optional CA scope key, reserved */
 588         if (rc->ca_key == NULL) {
 589                 if ((r = sshbuf_put_string(buf, NULL, 0)) != 0)
 590                         goto out;
 591         } else {
 592                 if ((r = sshkey_puts(rc->ca_key, buf)) != 0)
 593                         goto out;
 594         }
 595         if ((r = sshbuf_put_string(buf, NULL, 0)) != 0)
 596                 goto out;
 597
 598         /* Store the revoked serials.  */
 599         for (rs = RB_MIN(revoked_serial_tree, &rc->revoked_serials);
 600              rs != NULL;
 601              rs = RB_NEXT(revoked_serial_tree, &rc->revoked_serials, rs)) {
 602                 KRL_DBG(("serial %llu:%llu state 0x%02x",
 603                     (long long unsigned)rs->lo, (long long unsigned)rs->hi,
 604                     state));
 605
 606                 /* Check contiguous length and gap to next section (if any) */
 607                 nrs = RB_NEXT(revoked_serial_tree, &rc->revoked_serials, rs);
 608                 final = nrs == NULL;
 609                 gap = nrs == NULL ? 0 : nrs->lo - rs->hi;
 610                 contig = 1 + (rs->hi - rs->lo);
 611
 612                 /* Choose next state based on these */
 613                 next_state = choose_next_state(state, contig, final,
 614                     state == 0 ? 0 : rs->lo - last, gap, &force_new_sect);
 615
 616                 /*
 617                  * If the current section is a range section or has a different
 618                  * type to the next section, then finish it off now.
 619                  */
 620                 if (state != 0 && (force_new_sect || next_state != state ||
 621                     state == KRL_SECTION_CERT_SERIAL_RANGE)) {
 622                         KRL_DBG(("finish state 0x%02x", state));
 623                         switch (state) {
 624                         case KRL_SECTION_CERT_SERIAL_LIST:
 625                         case KRL_SECTION_CERT_SERIAL_RANGE:
 626                                 break;
 627                         case KRL_SECTION_CERT_SERIAL_BITMAP:
 628                                 if ((r = put_bitmap(sect, bitmap)) != 0)
 629                                         goto out;
 630                                 bitmap_free(bitmap);
 631                                 bitmap = NULL;
 632                                 break;
 633                         }
 634                         if ((r = sshbuf_put_u8(buf, state)) != 0 ||
 635                             (r = sshbuf_put_stringb(buf, sect)) != 0)
 636                                 goto out;
 637                         sshbuf_reset(sect);
 638                 }
 639
 640                 /* If we are starting a new section then prepare it now */
 641                 if (next_state != state || force_new_sect) {
 642                         KRL_DBG(("start state 0x%02x",
 643                             next_state));
 644                         state = next_state;
 645                         sshbuf_reset(sect);
 646                         switch (state) {
 647                         case KRL_SECTION_CERT_SERIAL_LIST:
 648                         case KRL_SECTION_CERT_SERIAL_RANGE:
 649                                 break;
 650                         case KRL_SECTION_CERT_SERIAL_BITMAP:
 651                                 if ((bitmap = bitmap_new()) == NULL) {
 652                                         r = SSH_ERR_ALLOC_FAIL;
 653                                         goto out;
 654                                 }
 655                                 bitmap_start = rs->lo;
 656                                 if ((r = sshbuf_put_u64(sect,
 657                                     bitmap_start)) != 0)
 658                                         goto out;
 659                                 break;
 660                         }
 661                 }
 662
 663                 /* Perform section-specific processing */
 664                 switch (state) {
 665                 case KRL_SECTION_CERT_SERIAL_LIST:
 666                         for (i = 0; i < contig; i++) {
 667                                 if ((r = sshbuf_put_u64(sect, rs->lo + i)) != 0)
 668                                         goto out;
 669                         }
 670                         break;
 671                 case KRL_SECTION_CERT_SERIAL_RANGE:
 672                         if ((r = sshbuf_put_u64(sect, rs->lo)) != 0 ||
 673                             (r = sshbuf_put_u64(sect, rs->hi)) != 0)
 674                                 goto out;
 675                         break;
 676                 case KRL_SECTION_CERT_SERIAL_BITMAP:
 677                         if (rs->lo - bitmap_start > INT_MAX) {
 678                                 error_f("insane bitmap gap");
 679                                 goto out;
 680                         }
 681                         for (i = 0; i < contig; i++) {
 682                                 if (bitmap_set_bit(bitmap,
 683                                     rs->lo + i - bitmap_start) != 0) {
 684                                         r = SSH_ERR_ALLOC_FAIL;
 685                                         goto out;
 686                                 }
 687                         }
 688                         break;
 689                 }
 690                 last = rs->hi;
 691         }
 692         /* Flush the remaining section, if any */
 693         if (state != 0) {
 694                 KRL_DBG(("serial final flush for state 0x%02x", state));
 695                 switch (state) {
 696                 case KRL_SECTION_CERT_SERIAL_LIST:
 697                 case KRL_SECTION_CERT_SERIAL_RANGE:
 698                         break;
 699                 case KRL_SECTION_CERT_SERIAL_BITMAP:
 700                         if ((r = put_bitmap(sect, bitmap)) != 0)
 701                                 goto out;
 702                         bitmap_free(bitmap);
 703                         bitmap = NULL;
 704                         break;
 705                 }
 706                 if ((r = sshbuf_put_u8(buf, state)) != 0 ||
 707                     (r = sshbuf_put_stringb(buf, sect)) != 0)
 708                         goto out;
 709         }
 710         KRL_DBG(("serial done "));
 711
 712         /* Now output a section for any revocations by key ID */
 713         sshbuf_reset(sect);
 714         RB_FOREACH(rki, revoked_key_id_tree, &rc->revoked_key_ids) {
 715                 KRL_DBG(("key ID %s", rki->key_id));
 716                 if ((r = sshbuf_put_cstring(sect, rki->key_id)) != 0)
 717                         goto out;
 718         }
 719         if (sshbuf_len(sect) != 0) {
 720                 if ((r = sshbuf_put_u8(buf, KRL_SECTION_CERT_KEY_ID)) != 0 ||
 721                     (r = sshbuf_put_stringb(buf, sect)) != 0)
 722                         goto out;
 723         }
 724         r = 0;
 725  out:
 726         bitmap_free(bitmap);
 727         sshbuf_free(sect);
 728         return r;
 729 }
 730
 731 int
 732 ssh_krl_to_blob(struct ssh_krl *krl, struct sshbuf *buf,
 733     struct sshkey **sign_keys, u_int nsign_keys)
 734 {
 735         int r = SSH_ERR_INTERNAL_ERROR;
 736         struct revoked_certs *rc;
 737         struct revoked_blob *rb;
 738         struct sshbuf *sect;
 739         u_char *sblob = NULL;
 740         size_t slen, i;
 741
 742         if (krl->generated_date == 0)
 743                 krl->generated_date = time(NULL);
 744
 745         if ((sect = sshbuf_new()) == NULL)
 746                 return SSH_ERR_ALLOC_FAIL;
 747
 748         /* Store the header */
 749         if ((r = sshbuf_put(buf, KRL_MAGIC, sizeof(KRL_MAGIC) - 1)) != 0 ||
 750             (r = sshbuf_put_u32(buf, KRL_FORMAT_VERSION)) != 0 ||
 751             (r = sshbuf_put_u64(buf, krl->krl_version)) != 0 ||
 752             (r = sshbuf_put_u64(buf, krl->generated_date)) != 0 ||
 753             (r = sshbuf_put_u64(buf, krl->flags)) != 0 ||
 754             (r = sshbuf_put_string(buf, NULL, 0)) != 0 ||
 755             (r = sshbuf_put_cstring(buf, krl->comment)) != 0)
 756                 goto out;
 757
 758         /* Store sections for revoked certificates */
 759         TAILQ_FOREACH(rc, &krl->revoked_certs, entry) {
 760                 sshbuf_reset(sect);
 761                 if ((r = revoked_certs_generate(rc, sect)) != 0)
 762                         goto out;
 763                 if ((r = sshbuf_put_u8(buf, KRL_SECTION_CERTIFICATES)) != 0 ||
 764                     (r = sshbuf_put_stringb(buf, sect)) != 0)
 765                         goto out;
 766         }
 767
 768         /* Finally, output sections for revocations by public key/hash */
 769         sshbuf_reset(sect);
 770         RB_FOREACH(rb, revoked_blob_tree, &krl->revoked_keys) {
 771                 KRL_DBG(("key len %zu ", rb->len));
 772                 if ((r = sshbuf_put_string(sect, rb->blob, rb->len)) != 0)
 773                         goto out;
 774         }
 775         if (sshbuf_len(sect) != 0) {
 776                 if ((r = sshbuf_put_u8(buf, KRL_SECTION_EXPLICIT_KEY)) != 0 ||
 777                     (r = sshbuf_put_stringb(buf, sect)) != 0)
 778                         goto out;
 779         }
 780         sshbuf_reset(sect);
 781         RB_FOREACH(rb, revoked_blob_tree, &krl->revoked_sha1s) {
 782                 KRL_DBG(("hash len %zu ", rb->len));
 783                 if ((r = sshbuf_put_string(sect, rb->blob, rb->len)) != 0)
 784                         goto out;
 785         }
 786         if (sshbuf_len(sect) != 0) {
 787                 if ((r = sshbuf_put_u8(buf,
 788                     KRL_SECTION_FINGERPRINT_SHA1)) != 0 ||
 789                     (r = sshbuf_put_stringb(buf, sect)) != 0)
 790                         goto out;
 791         }
 792         sshbuf_reset(sect);
 793         RB_FOREACH(rb, revoked_blob_tree, &krl->revoked_sha256s) {
 794                 KRL_DBG(("hash len %zu ", rb->len));
 795                 if ((r = sshbuf_put_string(sect, rb->blob, rb->len)) != 0)
 796                         goto out;
 797         }
 798         if (sshbuf_len(sect) != 0) {
 799                 if ((r = sshbuf_put_u8(buf,
 800                     KRL_SECTION_FINGERPRINT_SHA256)) != 0 ||
 801                     (r = sshbuf_put_stringb(buf, sect)) != 0)
 802                         goto out;
 803         }
 804
 805         for (i = 0; i < nsign_keys; i++) {
 806                 KRL_DBG(("sig key %s", sshkey_ssh_name(sign_keys[i])));
 807                 if ((r = sshbuf_put_u8(buf, KRL_SECTION_SIGNATURE)) != 0 ||
 808                     (r = sshkey_puts(sign_keys[i], buf)) != 0)
 809                         goto out;
 810                 /* XXX support sk-* keys */
 811                 if ((r = sshkey_sign(sign_keys[i], &sblob, &slen,
 812                     sshbuf_ptr(buf), sshbuf_len(buf), NULL, NULL,
 813                     NULL, 0)) != 0)
 814                         goto out;
 815                 KRL_DBG(("signature sig len %zu", slen));
 816                 if ((r = sshbuf_put_string(buf, sblob, slen)) != 0)
 817                         goto out;
 818         }
 819
 820         r = 0;
 821  out:
 822         free(sblob);
 823         sshbuf_free(sect);
 824         return r;
 825 }
 826
 827 static void
 828 format_timestamp(u_int64_t timestamp, char *ts, size_t nts)
 829 {
 830         time_t t;
 831         struct tm *tm;
 832
 833         t = timestamp;
 834         tm = localtime(&t);
 835         if (tm == NULL)
 836                 strlcpy(ts, "<INVALID>", nts);
 837         else {
 838                 *ts = '\0';
 839                 strftime(ts, nts, "%Y%m%dT%H%M%S", tm);
 840         }
 841 }
 842
 843 static int
 844 parse_revoked_certs(struct sshbuf *buf, struct ssh_krl *krl)
 845 {
 846         int r = SSH_ERR_INTERNAL_ERROR;
 847         u_char type;
 848         const u_char *blob;
 849         size_t blen, nbits;
 850         struct sshbuf *subsect = NULL;
 851         u_int64_t serial, serial_lo, serial_hi;
 852         struct bitmap *bitmap = NULL;
 853         char *key_id = NULL;
 854         struct sshkey *ca_key = NULL;
 855
 856         if ((subsect = sshbuf_new()) == NULL)
 857                 return SSH_ERR_ALLOC_FAIL;
 858
 859         /* Header: key, reserved */
 860         if ((r = sshbuf_get_string_direct(buf, &blob, &blen)) != 0 ||
 861             (r = sshbuf_skip_string(buf)) != 0)
 862                 goto out;
 863         if (blen != 0 && (r = sshkey_from_blob(blob, blen, &ca_key)) != 0)
 864                 goto out;
 865
 866         while (sshbuf_len(buf) > 0) {
 867                 sshbuf_free(subsect);
 868                 subsect = NULL;
 869                 if ((r = sshbuf_get_u8(buf, &type)) != 0 ||
 870                     (r = sshbuf_froms(buf, &subsect)) != 0)
 871                         goto out;
 872                 KRL_DBG(("subsection type 0x%02x", type));
 873                 /* sshbuf_dump(subsect, stderr); */
 874
 875                 switch (type) {
 876                 case KRL_SECTION_CERT_SERIAL_LIST:
 877                         while (sshbuf_len(subsect) > 0) {
 878                                 if ((r = sshbuf_get_u64(subsect, &serial)) != 0)
 879                                         goto out;
 880                                 if ((r = ssh_krl_revoke_cert_by_serial(krl,
 881                                     ca_key, serial)) != 0)
 882                                         goto out;
 883                         }
 884                         break;
 885                 case KRL_SECTION_CERT_SERIAL_RANGE:
 886                         if ((r = sshbuf_get_u64(subsect, &serial_lo)) != 0 ||
 887                             (r = sshbuf_get_u64(subsect, &serial_hi)) != 0)
 888                                 goto out;
 889                         if ((r = ssh_krl_revoke_cert_by_serial_range(krl,
 890                             ca_key, serial_lo, serial_hi)) != 0)
 891                                 goto out;
 892                         break;
 893                 case KRL_SECTION_CERT_SERIAL_BITMAP:
 894                         if ((bitmap = bitmap_new()) == NULL) {
 895                                 r = SSH_ERR_ALLOC_FAIL;
 896                                 goto out;
 897                         }
 898                         if ((r = sshbuf_get_u64(subsect, &serial_lo)) != 0 ||
 899                             (r = sshbuf_get_bignum2_bytes_direct(subsect,
 900                             &blob, &blen)) != 0)
 901                                 goto out;
 902                         if (bitmap_from_string(bitmap, blob, blen) != 0) {
 903                                 r = SSH_ERR_INVALID_FORMAT;
 904                                 goto out;
 905                         }
 906                         nbits = bitmap_nbits(bitmap);
 907                         for (serial = 0; serial < (u_int64_t)nbits; serial++) {
 908                                 if (serial > 0 && serial_lo + serial == 0) {
 909                                         error_f("bitmap wraps u64");
 910                                         r = SSH_ERR_INVALID_FORMAT;
 911                                         goto out;
 912                                 }
 913                                 if (!bitmap_test_bit(bitmap, serial))
 914                                         continue;
 915                                 if ((r = ssh_krl_revoke_cert_by_serial(krl,
 916                                     ca_key, serial_lo + serial)) != 0)
 917                                         goto out;
 918                         }
 919                         bitmap_free(bitmap);
 920                         bitmap = NULL;
 921                         break;
 922                 case KRL_SECTION_CERT_KEY_ID:
 923                         while (sshbuf_len(subsect) > 0) {
 924                                 if ((r = sshbuf_get_cstring(subsect,
 925                                     &key_id, NULL)) != 0)
 926                                         goto out;
 927                                 if ((r = ssh_krl_revoke_cert_by_key_id(krl,
 928                                     ca_key, key_id)) != 0)
 929                                         goto out;
 930                                 free(key_id);
 931                                 key_id = NULL;
 932                         }
 933                         break;
 934                 default:
 935                         error("Unsupported KRL certificate section %u", type);
 936                         r = SSH_ERR_INVALID_FORMAT;
 937                         goto out;
 938                 }
 939                 if (sshbuf_len(subsect) > 0) {
 940                         error("KRL certificate section contains unparsed data");
 941                         r = SSH_ERR_INVALID_FORMAT;
 942                         goto out;
 943                 }
 944         }
 945
 946         r = 0;
 947  out:
 948         if (bitmap != NULL)
 949                 bitmap_free(bitmap);
 950         free(key_id);
 951         sshkey_free(ca_key);
 952         sshbuf_free(subsect);
 953         return r;
 954 }
 955
 956 static int
 957 blob_section(struct sshbuf *sect, struct revoked_blob_tree *target_tree,
 958     size_t expected_len)
 959 {
 960         u_char *rdata = NULL;
 961         size_t rlen = 0;
 962         int r;
 963
 964         while (sshbuf_len(sect) > 0) {
 965                 if ((r = sshbuf_get_string(sect, &rdata, &rlen)) != 0)
 966                         return r;
 967                 if (expected_len != 0 && rlen != expected_len) {
 968                         error_f("bad length");
 969                         free(rdata);
 970                         return SSH_ERR_INVALID_FORMAT;
 971                 }
 972                 if ((r = revoke_blob(target_tree, rdata, rlen)) != 0) {
 973                         free(rdata);
 974                         return r;
 975                 }
 976         }
 977         return 0;
 978 }
 979
 980 /* Attempt to parse a KRL, checking its signature (if any) with sign_ca_keys. */
 981 int
 982 ssh_krl_from_blob(struct sshbuf *buf, struct ssh_krl **krlp,
 983     const struct sshkey **sign_ca_keys, size_t nsign_ca_keys)
 984 {
 985         struct sshbuf *copy = NULL, *sect = NULL;
 986         struct ssh_krl *krl = NULL;
 987         char timestamp[64];
 988         int r = SSH_ERR_INTERNAL_ERROR, sig_seen;
 989         struct sshkey *key = NULL, **ca_used = NULL, **tmp_ca_used;
 990         u_char type;
 991         const u_char *blob;
 992         size_t i, j, sig_off, sects_off, blen, nca_used;
 993         u_int format_version;
 994
 995         nca_used = 0;
 996         *krlp = NULL;
 997         if (sshbuf_len(buf) < sizeof(KRL_MAGIC) - 1 ||
 998             memcmp(sshbuf_ptr(buf), KRL_MAGIC, sizeof(KRL_MAGIC) - 1) != 0) {
 999                 debug3_f("not a KRL");
1000                 return SSH_ERR_KRL_BAD_MAGIC;
1001         }
1002
1003         /* Take a copy of the KRL buffer so we can verify its signature later */
1004         if ((copy = sshbuf_fromb(buf)) == NULL) {
1005                 r = SSH_ERR_ALLOC_FAIL;
1006                 goto out;
1007         }
1008         if ((r = sshbuf_consume(copy, sizeof(KRL_MAGIC) - 1)) != 0)
1009                 goto out;
1010
1011         if ((krl = ssh_krl_init()) == NULL) {
1012                 error_f("alloc failed");
1013                 goto out;
1014         }
1015
1016         if ((r = sshbuf_get_u32(copy, &format_version)) != 0)
1017                 goto out;
1018         if (format_version != KRL_FORMAT_VERSION) {
1019                 r = SSH_ERR_INVALID_FORMAT;
1020                 goto out;
1021         }
1022         if ((r = sshbuf_get_u64(copy, &krl->krl_version)) != 0 ||
1023             (r = sshbuf_get_u64(copy, &krl->generated_date)) != 0 ||
1024             (r = sshbuf_get_u64(copy, &krl->flags)) != 0 ||
1025             (r = sshbuf_skip_string(copy)) != 0 ||
1026             (r = sshbuf_get_cstring(copy, &krl->comment, NULL)) != 0)
1027                 goto out;
1028
1029         format_timestamp(krl->generated_date, timestamp, sizeof(timestamp));
1030         debug("KRL version %llu generated at %s%s%s",
1031             (long long unsigned)krl->krl_version, timestamp,
1032             *krl->comment ? ": " : "", krl->comment);
1033
1034         /*
1035          * 1st pass: verify signatures, if any. This is done to avoid
1036          * detailed parsing of data whose provenance is unverified.
1037          */
1038         sig_seen = 0;
1039         if (sshbuf_len(buf) < sshbuf_len(copy)) {
1040                 /* Shouldn't happen */
1041                 r = SSH_ERR_INTERNAL_ERROR;
1042                 goto out;
1043         }
1044         sects_off = sshbuf_len(buf) - sshbuf_len(copy);
1045         while (sshbuf_len(copy) > 0) {
1046                 if ((r = sshbuf_get_u8(copy, &type)) != 0 ||
1047                     (r = sshbuf_get_string_direct(copy, &blob, &blen)) != 0)
1048                         goto out;
1049                 KRL_DBG(("first pass, section 0x%02x", type));
1050                 if (type != KRL_SECTION_SIGNATURE) {
1051                         if (sig_seen) {
1052                                 error("KRL contains non-signature section "
1053                                     "after signature");
1054                                 r = SSH_ERR_INVALID_FORMAT;
1055                                 goto out;
1056                         }
1057                         /* Not interested for now. */
1058                         continue;
1059                 }
1060                 sig_seen = 1;
1061                 /* First string component is the signing key */
1062                 if ((r = sshkey_from_blob(blob, blen, &key)) != 0) {
1063                         r = SSH_ERR_INVALID_FORMAT;
1064                         goto out;
1065                 }
1066                 if (sshbuf_len(buf) < sshbuf_len(copy)) {
1067                         /* Shouldn't happen */
1068                         r = SSH_ERR_INTERNAL_ERROR;
1069                         goto out;
1070                 }
1071                 sig_off = sshbuf_len(buf) - sshbuf_len(copy);
1072                 /* Second string component is the signature itself */
1073                 if ((r = sshbuf_get_string_direct(copy, &blob, &blen)) != 0) {
1074                         r = SSH_ERR_INVALID_FORMAT;
1075                         goto out;
1076                 }
1077                 /* Check signature over entire KRL up to this point */
1078                 if ((r = sshkey_verify(key, blob, blen,
1079                     sshbuf_ptr(buf), sig_off, NULL, 0, NULL)) != 0)
1080                         goto out;
1081                 /* Check if this key has already signed this KRL */
1082                 for (i = 0; i < nca_used; i++) {
1083                         if (sshkey_equal(ca_used[i], key)) {
1084                                 error("KRL signed more than once with "
1085                                     "the same key");
1086                                 r = SSH_ERR_INVALID_FORMAT;
1087                                 goto out;
1088                         }
1089                 }
1090                 /* Record keys used to sign the KRL */
1091                 tmp_ca_used = recallocarray(ca_used, nca_used, nca_used + 1,
1092                     sizeof(*ca_used));
1093                 if (tmp_ca_used == NULL) {
1094                         r = SSH_ERR_ALLOC_FAIL;
1095                         goto out;
1096                 }
1097                 ca_used = tmp_ca_used;
1098                 ca_used[nca_used++] = key;
1099                 key = NULL;
1100         }
1101
1102         if (sshbuf_len(copy) != 0) {
1103                 /* Shouldn't happen */
1104                 r = SSH_ERR_INTERNAL_ERROR;
1105                 goto out;
1106         }
1107
1108         /*
1109          * 2nd pass: parse and load the KRL, skipping the header to the point
1110          * where the section start.
1111          */
1112         sshbuf_free(copy);
1113         if ((copy = sshbuf_fromb(buf)) == NULL) {
1114                 r = SSH_ERR_ALLOC_FAIL;
1115                 goto out;
1116         }
1117         if ((r = sshbuf_consume(copy, sects_off)) != 0)
1118                 goto out;
1119         while (sshbuf_len(copy) > 0) {
1120                 sshbuf_free(sect);
1121                 sect = NULL;
1122                 if ((r = sshbuf_get_u8(copy, &type)) != 0 ||
1123                     (r = sshbuf_froms(copy, &sect)) != 0)
1124                         goto out;
1125                 KRL_DBG(("second pass, section 0x%02x", type));
1126
1127                 switch (type) {
1128                 case KRL_SECTION_CERTIFICATES:
1129                         if ((r = parse_revoked_certs(sect, krl)) != 0)
1130                                 goto out;
1131                         break;
1132                 case KRL_SECTION_EXPLICIT_KEY:
1133                         if ((r = blob_section(sect,
1134                             &krl->revoked_keys, 0)) != 0)
1135                                 goto out;
1136                         break;
1137                 case KRL_SECTION_FINGERPRINT_SHA1:
1138                         if ((r = blob_section(sect,
1139                             &krl->revoked_sha1s, 20)) != 0)
1140                                 goto out;
1141                         break;
1142                 case KRL_SECTION_FINGERPRINT_SHA256:
1143                         if ((r = blob_section(sect,
1144                             &krl->revoked_sha256s, 32)) != 0)
1145                                 goto out;
1146                         break;
1147                 case KRL_SECTION_SIGNATURE:
1148                         /* Handled above, but still need to stay in synch */
1149                         sshbuf_free(sect);
1150                         sect = NULL;
1151                         if ((r = sshbuf_skip_string(copy)) != 0)
1152                                 goto out;
1153                         break;
1154                 default:
1155                         error("Unsupported KRL section %u", type);
1156                         r = SSH_ERR_INVALID_FORMAT;
1157                         goto out;
1158                 }
1159                 if (sect != NULL && sshbuf_len(sect) > 0) {
1160                         error("KRL section contains unparsed data");
1161                         r = SSH_ERR_INVALID_FORMAT;
1162                         goto out;
1163                 }
1164         }
1165
1166         /* Check that the key(s) used to sign the KRL weren't revoked */
1167         sig_seen = 0;
1168         for (i = 0; i < nca_used; i++) {
1169                 if (ssh_krl_check_key(krl, ca_used[i]) == 0)
1170                         sig_seen = 1;
1171                 else {
1172                         sshkey_free(ca_used[i]);
1173                         ca_used[i] = NULL;
1174                 }
1175         }
1176         if (nca_used && !sig_seen) {
1177                 error("All keys used to sign KRL were revoked");
1178                 r = SSH_ERR_KEY_REVOKED;
1179                 goto out;
1180         }
1181
1182         /* If we have CA keys, then verify that one was used to sign the KRL */
1183         if (sig_seen && nsign_ca_keys != 0) {
1184                 sig_seen = 0;
1185                 for (i = 0; !sig_seen && i < nsign_ca_keys; i++) {
1186                         for (j = 0; j < nca_used; j++) {
1187                                 if (ca_used[j] == NULL)
1188                                         continue;
1189                                 if (sshkey_equal(ca_used[j], sign_ca_keys[i])) {
1190                                         sig_seen = 1;
1191                                         break;
1192                                 }
1193                         }
1194                 }
1195                 if (!sig_seen) {
1196                         r = SSH_ERR_SIGNATURE_INVALID;
1197                         error("KRL not signed with any trusted key");
1198                         goto out;
1199                 }
1200         }
1201
1202         *krlp = krl;
1203         r = 0;
1204  out:
1205         if (r != 0)
1206                 ssh_krl_free(krl);
1207         for (i = 0; i < nca_used; i++)
1208                 sshkey_free(ca_used[i]);
1209         free(ca_used);
1210         sshkey_free(key);
1211         sshbuf_free(copy);
1212         sshbuf_free(sect);
1213         return r;
1214 }
1215
1216 /* Checks certificate serial number and key ID revocation */
1217 static int
1218 is_cert_revoked(const struct sshkey *key, struct revoked_certs *rc)
1219 {
1220         struct revoked_serial rs, *ers;
1221         struct revoked_key_id rki, *erki;
1222
1223         /* Check revocation by cert key ID */
1224         memset(&rki, 0, sizeof(rki));
1225         rki.key_id = key->cert->key_id;
1226         erki = RB_FIND(revoked_key_id_tree, &rc->revoked_key_ids, &rki);
1227         if (erki != NULL) {
1228                 KRL_DBG(("revoked by key ID"));
1229                 return SSH_ERR_KEY_REVOKED;
1230         }
1231
1232         /*
1233          * Zero serials numbers are ignored (it's the default when the
1234          * CA doesn't specify one).
1235          */
1236         if (key->cert->serial == 0)
1237                 return 0;
1238
1239         memset(&rs, 0, sizeof(rs));
1240         rs.lo = rs.hi = key->cert->serial;
1241         ers = RB_FIND(revoked_serial_tree, &rc->revoked_serials, &rs);
1242         if (ers != NULL) {
1243                 KRL_DBG(("revoked serial %llu matched %llu:%llu",
1244                     key->cert->serial, ers->lo, ers->hi));
1245                 return SSH_ERR_KEY_REVOKED;
1246         }
1247         return 0;
1248 }
1249
1250 /* Checks whether a given key/cert is revoked. Does not check its CA */
1251 static int
1252 is_key_revoked(struct ssh_krl *krl, const struct sshkey *key)
1253 {
1254         struct revoked_blob rb, *erb;
1255         struct revoked_certs *rc;
1256         int r;
1257
1258         /* Check explicitly revoked hashes first */
1259         memset(&rb, 0, sizeof(rb));
1260         if ((r = sshkey_fingerprint_raw(key, SSH_DIGEST_SHA1,
1261             &rb.blob, &rb.len)) != 0)
1262                 return r;
1263         erb = RB_FIND(revoked_blob_tree, &krl->revoked_sha1s, &rb);
1264         free(rb.blob);
1265         if (erb != NULL) {
1266                 KRL_DBG(("revoked by key SHA1"));
1267                 return SSH_ERR_KEY_REVOKED;
1268         }
1269         memset(&rb, 0, sizeof(rb));
1270         if ((r = sshkey_fingerprint_raw(key, SSH_DIGEST_SHA256,
1271             &rb.blob, &rb.len)) != 0)
1272                 return r;
1273         erb = RB_FIND(revoked_blob_tree, &krl->revoked_sha256s, &rb);
1274         free(rb.blob);
1275         if (erb != NULL) {
1276                 KRL_DBG(("revoked by key SHA256"));
1277                 return SSH_ERR_KEY_REVOKED;
1278         }
1279
1280         /* Next, explicit keys */
1281         memset(&rb, 0, sizeof(rb));
1282         if ((r = plain_key_blob(key, &rb.blob, &rb.len)) != 0)
1283                 return r;
1284         erb = RB_FIND(revoked_blob_tree, &krl->revoked_keys, &rb);
1285         free(rb.blob);
1286         if (erb != NULL) {
1287                 KRL_DBG(("revoked by explicit key"));
1288                 return SSH_ERR_KEY_REVOKED;
1289         }
1290
1291         if (!sshkey_is_cert(key))
1292                 return 0;
1293
1294         /* Check cert revocation for the specified CA */
1295         if ((r = revoked_certs_for_ca_key(krl, key->cert->signature_key,
1296             &rc, 0)) != 0)
1297                 return r;
1298         if (rc != NULL) {
1299                 if ((r = is_cert_revoked(key, rc)) != 0)
1300                         return r;
1301         }
1302         /* Check cert revocation for the wildcard CA */
1303         if ((r = revoked_certs_for_ca_key(krl, NULL, &rc, 0)) != 0)
1304                 return r;
1305         if (rc != NULL) {
1306                 if ((r = is_cert_revoked(key, rc)) != 0)
1307                         return r;
1308         }
1309
1310         KRL_DBG(("%llu no match", key->cert->serial));
1311         return 0;
1312 }
1313
1314 int
1315 ssh_krl_check_key(struct ssh_krl *krl, const struct sshkey *key)
1316 {
1317         int r;
1318
1319         KRL_DBG(("checking key"));
1320         if ((r = is_key_revoked(krl, key)) != 0)
1321                 return r;
1322         if (sshkey_is_cert(key)) {
1323                 debug2_f("checking CA key");
1324                 if ((r = is_key_revoked(krl, key->cert->signature_key)) != 0)
1325                         return r;
1326         }
1327         KRL_DBG(("key okay"));
1328         return 0;
1329 }
1330
1331 int
1332 ssh_krl_file_contains_key(const char *path, const struct sshkey *key)
1333 {
1334         struct sshbuf *krlbuf = NULL;
1335         struct ssh_krl *krl = NULL;
1336         int oerrno = 0, r;
1337
1338         if (path == NULL)
1339                 return 0;
1340         if ((r = sshbuf_load_file(path, &krlbuf)) != 0) {
1341                 oerrno = errno;
1342                 goto out;
1343         }
1344         if ((r = ssh_krl_from_blob(krlbuf, &krl, NULL, 0)) != 0)
1345                 goto out;
1346         debug2_f("checking KRL %s", path);
1347         r = ssh_krl_check_key(krl, key);
1348  out:
1349         sshbuf_free(krlbuf);
1350         ssh_krl_free(krl);
1351         if (r != 0)
1352                 errno = oerrno;
1353         return r;
1354 }
1355
1356 int
1357 krl_dump(struct ssh_krl *krl, FILE *f)
1358 {
1359         struct sshkey *key = NULL;
1360         struct revoked_blob *rb;
1361         struct revoked_certs *rc;
1362         struct revoked_serial *rs;
1363         struct revoked_key_id *rki;
1364         int r, ret = 0;
1365         char *fp, timestamp[64];
1366
1367         /* Try to print in a KRL spec-compatible format */
1368         format_timestamp(krl->generated_date, timestamp, sizeof(timestamp));
1369         fprintf(f, "# KRL version %llu\n",
1370             (unsigned long long)krl->krl_version);
1371         fprintf(f, "# Generated at %s\n", timestamp);
1372         if (krl->comment != NULL && *krl->comment != '\0') {
1373                 r = INT_MAX;
1374                 asmprintf(&fp, INT_MAX, &r, "%s", krl->comment);
1375                 fprintf(f, "# Comment: %s\n", fp);
1376                 free(fp);
1377         }
1378         fputc('\n', f);
1379
1380         RB_FOREACH(rb, revoked_blob_tree, &krl->revoked_keys) {
1381                 if ((r = sshkey_from_blob(rb->blob, rb->len, &key)) != 0) {
1382                         ret = SSH_ERR_INVALID_FORMAT;
1383                         error_r(r, "parse KRL key");
1384                         continue;
1385                 }
1386                 if ((fp = sshkey_fingerprint(key, SSH_FP_HASH_DEFAULT,
1387                     SSH_FP_DEFAULT)) == NULL) {
1388                         ret = SSH_ERR_INVALID_FORMAT;
1389                         error("sshkey_fingerprint failed");
1390                         continue;
1391                 }
1392                 fprintf(f, "hash: %s # %s\n", fp, sshkey_ssh_name(key));
1393                 free(fp);
1394                 free(key);
1395         }
1396         RB_FOREACH(rb, revoked_blob_tree, &krl->revoked_sha256s) {
1397                 fp = tohex(rb->blob, rb->len);
1398                 fprintf(f, "hash: SHA256:%s\n", fp);
1399                 free(fp);
1400         }
1401         RB_FOREACH(rb, revoked_blob_tree, &krl->revoked_sha1s) {
1402                 /*
1403                  * There is not KRL spec keyword for raw SHA1 hashes, so
1404                  * print them as comments.
1405                  */
1406                 fp = tohex(rb->blob, rb->len);
1407                 fprintf(f, "# hash SHA1:%s\n", fp);
1408                 free(fp);
1409         }
1410
1411         TAILQ_FOREACH(rc, &krl->revoked_certs, entry) {
1412                 fputc('\n', f);
1413                 if (rc->ca_key == NULL)
1414                         fprintf(f, "# Wildcard CA\n");
1415                 else {
1416                         if ((fp = sshkey_fingerprint(rc->ca_key,
1417                             SSH_FP_HASH_DEFAULT, SSH_FP_DEFAULT)) == NULL) {
1418                                 ret = SSH_ERR_INVALID_FORMAT;
1419                                 error("sshkey_fingerprint failed");
1420                                 continue;
1421                         }
1422                         fprintf(f, "# CA key %s %s\n",
1423                             sshkey_ssh_name(rc->ca_key), fp);
1424                         free(fp);
1425                 }
1426                 RB_FOREACH(rs, revoked_serial_tree, &rc->revoked_serials) {
1427                         if (rs->lo == rs->hi) {
1428                                 fprintf(f, "serial: %llu\n",
1429                                     (unsigned long long)rs->lo);
1430                         } else {
1431                                 fprintf(f, "serial: %llu-%llu\n",
1432                                     (unsigned long long)rs->lo,
1433                                     (unsigned long long)rs->hi);
1434                         }
1435                 }
1436                 RB_FOREACH(rki, revoked_key_id_tree, &rc->revoked_key_ids) {
1437                         /*
1438                          * We don't want key IDs with embedded newlines to
1439                          * mess up the display.
1440                          */
1441                         r = INT_MAX;
1442                         asmprintf(&fp, INT_MAX, &r, "%s", rki->key_id);
1443                         fprintf(f, "id: %s\n", fp);
1444                         free(fp);
1445                 }
1446         }
1447         return ret;
1448 }