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.53 2021/06/04 06:19:07 djm 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 }
 195
 196 void
 197 ssh_krl_set_version(struct ssh_krl *krl, u_int64_t version)
 198 {
 199         krl->krl_version = version;
 200 }
 201
 202 int
 203 ssh_krl_set_comment(struct ssh_krl *krl, const char *comment)
 204 {
 205         free(krl->comment);
 206         if ((krl->comment = strdup(comment)) == NULL)
 207                 return SSH_ERR_ALLOC_FAIL;
 208         return 0;
 209 }
 210
 211 /*
 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.
 214  */
 215 static int
 216 revoked_certs_for_ca_key(struct ssh_krl *krl, const struct sshkey *ca_key,
 217     struct revoked_certs **rcp, int allow_create)
 218 {
 219         struct revoked_certs *rc;
 220         int r;
 221
 222         *rcp = NULL;
 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)) {
 226                         *rcp = rc;
 227                         return 0;
 228                 }
 229         }
 230         if (!allow_create)
 231                 return 0;
 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;
 235         if (ca_key == NULL)
 236                 rc->ca_key = NULL;
 237         else if ((r = sshkey_from_private(ca_key, &rc->ca_key)) != 0) {
 238                 free(rc);
 239                 return r;
 240         }
 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)));
 245         *rcp = rc;
 246         return 0;
 247 }
 248
 249 static int
 250 insert_serial_range(struct revoked_serial_tree *rt, u_int64_t lo, u_int64_t hi)
 251 {
 252         struct revoked_serial rs, *ers, *crs, *irs;
 253
 254         KRL_DBG(("insert %llu:%llu", lo, hi));
 255         memset(&rs, 0, sizeof(rs));
 256         rs.lo = lo;
 257         rs.hi = hi;
 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);
 265                 if (ers != NULL) {
 266                         KRL_DBG(("bad: ers != NULL"));
 267                         /* Shouldn't happen */
 268                         free(irs);
 269                         return SSH_ERR_INTERNAL_ERROR;
 270                 }
 271                 ers = irs;
 272         } else {
 273                 KRL_DBG(("overlap found %llu:%llu", ers->lo, ers->hi));
 274                 /*
 275                  * The inserted entry overlaps an existing one. Grow the
 276                  * existing entry.
 277                  */
 278                 if (ers->lo > lo)
 279                         ers->lo = lo;
 280                 if (ers->hi < hi)
 281                         ers->hi = hi;
 282         }
 283
 284         /*
 285          * The inserted or revised range might overlap or abut adjacent ones;
 286          * coalesce as necessary.
 287          */
 288
 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)
 293                         break;
 294                 /* This entry overlaps. */
 295                 if (crs->lo < ers->lo) {
 296                         ers->lo = crs->lo;
 297                         KRL_DBG(("pred extend %llu:%llu", ers->lo, ers->hi));
 298                 }
 299                 RB_REMOVE(revoked_serial_tree, rt, crs);
 300                 free(crs);
 301         }
 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)
 306                         break;
 307                 /* This entry overlaps. */
 308                 if (crs->hi > ers->hi) {
 309                         ers->hi = crs->hi;
 310                         KRL_DBG(("succ extend %llu:%llu", ers->lo, ers->hi));
 311                 }
 312                 RB_REMOVE(revoked_serial_tree, rt, crs);
 313                 free(crs);
 314         }
 315         KRL_DBG(("done, final %llu:%llu", ers->lo, ers->hi));
 316         return 0;
 317 }
 318
 319 int
 320 ssh_krl_revoke_cert_by_serial(struct ssh_krl *krl, const struct sshkey *ca_key,
 321     u_int64_t serial)
 322 {
 323         return ssh_krl_revoke_cert_by_serial_range(krl, ca_key, serial, serial);
 324 }
 325
 326 int
 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)
 329 {
 330         struct revoked_certs *rc;
 331         int r;
 332
 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)
 336                 return r;
 337         return insert_serial_range(&rc->revoked_serials, lo, hi);
 338 }
 339
 340 int
 341 ssh_krl_revoke_cert_by_key_id(struct ssh_krl *krl, const struct sshkey *ca_key,
 342     const char *key_id)
 343 {
 344         struct revoked_key_id *rki, *erki;
 345         struct revoked_certs *rc;
 346         int r;
 347
 348         if ((r = revoked_certs_for_ca_key(krl, ca_key, &rc, 1)) != 0)
 349                 return r;
 350
 351         KRL_DBG(("revoke %s", key_id));
 352         if ((rki = calloc(1, sizeof(*rki))) == NULL ||
 353             (rki->key_id = strdup(key_id)) == NULL) {
 354                 free(rki);
 355                 return SSH_ERR_ALLOC_FAIL;
 356         }
 357         erki = RB_INSERT(revoked_key_id_tree, &rc->revoked_key_ids, rki);
 358         if (erki != NULL) {
 359                 free(rki->key_id);
 360                 free(rki);
 361         }
 362         return 0;
 363 }
 364
 365 /* Convert "key" to a public key blob without any certificate information */
 366 static int
 367 plain_key_blob(const struct sshkey *key, u_char **blob, size_t *blen)
 368 {
 369         struct sshkey *kcopy;
 370         int r;
 371
 372         if ((r = sshkey_from_private(key, &kcopy)) != 0)
 373                 return r;
 374         if (sshkey_is_cert(kcopy)) {
 375                 if ((r = sshkey_drop_cert(kcopy)) != 0) {
 376                         sshkey_free(kcopy);
 377                         return r;
 378                 }
 379         }
 380         r = sshkey_to_blob(kcopy, blob, blen);
 381         sshkey_free(kcopy);
 382         return r;
 383 }
 384
 385 /* Revoke a key blob. Ownership of blob is transferred to the tree */
 386 static int
 387 revoke_blob(struct revoked_blob_tree *rbt, u_char *blob, size_t len)
 388 {
 389         struct revoked_blob *rb, *erb;
 390
 391         if ((rb = calloc(1, sizeof(*rb))) == NULL)
 392                 return SSH_ERR_ALLOC_FAIL;
 393         rb->blob = blob;
 394         rb->len = len;
 395         erb = RB_INSERT(revoked_blob_tree, rbt, rb);
 396         if (erb != NULL) {
 397                 free(rb->blob);
 398                 free(rb);
 399         }
 400         return 0;
 401 }
 402
 403 int
 404 ssh_krl_revoke_key_explicit(struct ssh_krl *krl, const struct sshkey *key)
 405 {
 406         u_char *blob;
 407         size_t len;
 408         int r;
 409
 410         debug3_f("revoke type %s", sshkey_type(key));
 411         if ((r = plain_key_blob(key, &blob, &len)) != 0)
 412                 return r;
 413         return revoke_blob(&krl->revoked_keys, blob, len);
 414 }
 415
 416 static int
 417 revoke_by_hash(struct revoked_blob_tree *target, const u_char *p, size_t len)
 418 {
 419         u_char *blob;
 420         int r;
 421
 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) {
 427                 free(blob);
 428                 return r;
 429         }
 430         return 0;
 431 }
 432
 433 int
 434 ssh_krl_revoke_key_sha1(struct ssh_krl *krl, const u_char *p, size_t len)
 435 {
 436         debug3_f("revoke by sha1");
 437         if (len != 20)
 438                 return SSH_ERR_INVALID_FORMAT;
 439         return revoke_by_hash(&krl->revoked_sha1s, p, len);
 440 }
 441
 442 int
 443 ssh_krl_revoke_key_sha256(struct ssh_krl *krl, const u_char *p, size_t len)
 444 {
 445         debug3_f("revoke by sha256");
 446         if (len != 32)
 447                 return SSH_ERR_INVALID_FORMAT;
 448         return revoke_by_hash(&krl->revoked_sha256s, p, len);
 449 }
 450
 451 int
 452 ssh_krl_revoke_key(struct ssh_krl *krl, const struct sshkey *key)
 453 {
 454         /* XXX replace with SHA256? */
 455         if (!sshkey_is_cert(key))
 456                 return ssh_krl_revoke_key_explicit(krl, key);
 457
 458         if (key->cert->serial == 0) {
 459                 return ssh_krl_revoke_cert_by_key_id(krl,
 460                     key->cert->signature_key,
 461                     key->cert->key_id);
 462         } else {
 463                 return ssh_krl_revoke_cert_by_serial(krl,
 464                     key->cert->signature_key,
 465                     key->cert->serial);
 466         }
 467 }
 468
 469 /*
 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.
 475  */
 476 static int
 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)
 479 {
 480         int new_state;
 481         u_int64_t cost, cost_list, cost_range, cost_bitmap, cost_bitmap_restart;
 482
 483         /*
 484          * Avoid unsigned overflows.
 485          * The limits are high enough to avoid confusing the calculations.
 486          */
 487         contig = MINIMUM(contig, 1ULL<<31);
 488         last_gap = MINIMUM(last_gap, 1ULL<<31);
 489         next_gap = MINIMUM(next_gap, 1ULL<<31);
 490
 491         /*
 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.
 495          */
 496         cost_list = cost_bitmap = cost_bitmap_restart = 0;
 497         cost_range = 8;
 498         switch (current_state) {
 499         case KRL_SECTION_CERT_SERIAL_LIST:
 500                 cost_bitmap_restart = cost_bitmap = 8 + 64;
 501                 break;
 502         case KRL_SECTION_CERT_SERIAL_BITMAP:
 503                 cost_list = 8;
 504                 cost_bitmap_restart = 8 + 64;
 505                 break;
 506         case KRL_SECTION_CERT_SERIAL_RANGE:
 507         case 0:
 508                 cost_bitmap_restart = cost_bitmap = 8 + 64;
 509                 cost_list = 8;
 510         }
 511
 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));
 517
 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;
 523
 524         /* Now pick the best choice */
 525         *force_new_section = 0;
 526         new_state = KRL_SECTION_CERT_SERIAL_BITMAP;
 527         cost = cost_bitmap;
 528         if (cost_range < cost) {
 529                 new_state = KRL_SECTION_CERT_SERIAL_RANGE;
 530                 cost = cost_range;
 531         }
 532         if (cost_list < cost) {
 533                 new_state = KRL_SECTION_CERT_SERIAL_LIST;
 534                 cost = cost_list;
 535         }
 536         if (cost_bitmap_restart < cost) {
 537                 new_state = KRL_SECTION_CERT_SERIAL_BITMAP;
 538                 *force_new_section = 1;
 539                 cost = cost_bitmap_restart;
 540         }
 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" : ""));
 549         return new_state;
 550 }
 551
 552 static int
 553 put_bitmap(struct sshbuf *buf, struct bitmap *bitmap)
 554 {
 555         size_t len;
 556         u_char *blob;
 557         int r;
 558
 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) {
 563                 free(blob);
 564                 return SSH_ERR_INTERNAL_ERROR;
 565         }
 566         r = sshbuf_put_bignum2_bytes(buf, blob, len);
 567         free(blob);
 568         return r;
 569 }
 570
 571 /* Generate a KRL_SECTION_CERTIFICATES KRL section */
 572 static int
 573 revoked_certs_generate(struct revoked_certs *rc, struct sshbuf *buf)
 574 {
 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;
 580         struct sshbuf *sect;
 581         struct bitmap *bitmap = NULL;
 582
 583         if ((sect = sshbuf_new()) == NULL)
 584                 return SSH_ERR_ALLOC_FAIL;
 585
 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)
 589                         goto out;
 590         } else {
 591                 if ((r = sshkey_puts(rc->ca_key, buf)) != 0)
 592                         goto out;
 593         }
 594         if ((r = sshbuf_put_string(buf, NULL, 0)) != 0)
 595                 goto out;
 596
 597         /* Store the revoked serials.  */
 598         for (rs = RB_MIN(revoked_serial_tree, &rc->revoked_serials);
 599              rs != NULL;
 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,
 603                     state));
 604
 605                 /* Check contiguous length and gap to next section (if any) */
 606                 nrs = RB_NEXT(revoked_serial_tree, &rc->revoked_serials, rs);
 607                 final = nrs == NULL;
 608                 gap = nrs == NULL ? 0 : nrs->lo - rs->hi;
 609                 contig = 1 + (rs->hi - rs->lo);
 610
 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);
 614
 615                 /*
 616                  * If the current section is a range section or has a different
 617                  * type to the next section, then finish it off now.
 618                  */
 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));
 622                         switch (state) {
 623                         case KRL_SECTION_CERT_SERIAL_LIST:
 624                         case KRL_SECTION_CERT_SERIAL_RANGE:
 625                                 break;
 626                         case KRL_SECTION_CERT_SERIAL_BITMAP:
 627                                 if ((r = put_bitmap(sect, bitmap)) != 0)
 628                                         goto out;
 629                                 bitmap_free(bitmap);
 630                                 bitmap = NULL;
 631                                 break;
 632                         }
 633                         if ((r = sshbuf_put_u8(buf, state)) != 0 ||
 634                             (r = sshbuf_put_stringb(buf, sect)) != 0)
 635                                 goto out;
 636                         sshbuf_reset(sect);
 637                 }
 638
 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",
 642                             next_state));
 643                         state = next_state;
 644                         sshbuf_reset(sect);
 645                         switch (state) {
 646                         case KRL_SECTION_CERT_SERIAL_LIST:
 647                         case KRL_SECTION_CERT_SERIAL_RANGE:
 648                                 break;
 649                         case KRL_SECTION_CERT_SERIAL_BITMAP:
 650                                 if ((bitmap = bitmap_new()) == NULL) {
 651                                         r = SSH_ERR_ALLOC_FAIL;
 652                                         goto out;
 653                                 }
 654                                 bitmap_start = rs->lo;
 655                                 if ((r = sshbuf_put_u64(sect,
 656                                     bitmap_start)) != 0)
 657                                         goto out;
 658                                 break;
 659                         }
 660                 }
 661
 662                 /* Perform section-specific processing */
 663                 switch (state) {
 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)
 667                                         goto out;
 668                         }
 669                         break;
 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)
 673                                 goto out;
 674                         break;
 675                 case KRL_SECTION_CERT_SERIAL_BITMAP:
 676                         if (rs->lo - bitmap_start > INT_MAX) {
 677                                 error_f("insane bitmap gap");
 678                                 goto out;
 679                         }
 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;
 684                                         goto out;
 685                                 }
 686                         }
 687                         break;
 688                 }
 689                 last = rs->hi;
 690         }
 691         /* Flush the remaining section, if any */
 692         if (state != 0) {
 693                 KRL_DBG(("serial final flush for state 0x%02x", state));
 694                 switch (state) {
 695                 case KRL_SECTION_CERT_SERIAL_LIST:
 696                 case KRL_SECTION_CERT_SERIAL_RANGE:
 697                         break;
 698                 case KRL_SECTION_CERT_SERIAL_BITMAP:
 699                         if ((r = put_bitmap(sect, bitmap)) != 0)
 700                                 goto out;
 701                         bitmap_free(bitmap);
 702                         bitmap = NULL;
 703                         break;
 704                 }
 705                 if ((r = sshbuf_put_u8(buf, state)) != 0 ||
 706                     (r = sshbuf_put_stringb(buf, sect)) != 0)
 707                         goto out;
 708         }
 709         KRL_DBG(("serial done "));
 710
 711         /* Now output a section for any revocations by key ID */
 712         sshbuf_reset(sect);
 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)
 716                         goto out;
 717         }
 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)
 721                         goto out;
 722         }
 723         r = 0;
 724  out:
 725         bitmap_free(bitmap);
 726         sshbuf_free(sect);
 727         return r;
 728 }
 729
 730 int
 731 ssh_krl_to_blob(struct ssh_krl *krl, struct sshbuf *buf,
 732     struct sshkey **sign_keys, u_int nsign_keys)
 733 {
 734         int r = SSH_ERR_INTERNAL_ERROR;
 735         struct revoked_certs *rc;
 736         struct revoked_blob *rb;
 737         struct sshbuf *sect;
 738         u_char *sblob = NULL;
 739         size_t slen, i;
 740
 741         if (krl->generated_date == 0)
 742                 krl->generated_date = time(NULL);
 743
 744         if ((sect = sshbuf_new()) == NULL)
 745                 return SSH_ERR_ALLOC_FAIL;
 746
 747         /* Store the header */
 748         if ((r = sshbuf_put(buf, KRL_MAGIC, sizeof(KRL_MAGIC) - 1)) != 0 ||
 749             (r = sshbuf_put_u32(buf, KRL_FORMAT_VERSION)) != 0 ||
 750             (r = sshbuf_put_u64(buf, krl->krl_version)) != 0 ||
 751             (r = sshbuf_put_u64(buf, krl->generated_date)) != 0 ||
 752             (r = sshbuf_put_u64(buf, krl->flags)) != 0 ||
 753             (r = sshbuf_put_string(buf, NULL, 0)) != 0 ||
 754             (r = sshbuf_put_cstring(buf, krl->comment)) != 0)
 755                 goto out;
 756
 757         /* Store sections for revoked certificates */
 758         TAILQ_FOREACH(rc, &krl->revoked_certs, entry) {
 759                 sshbuf_reset(sect);
 760                 if ((r = revoked_certs_generate(rc, sect)) != 0)
 761                         goto out;
 762                 if ((r = sshbuf_put_u8(buf, KRL_SECTION_CERTIFICATES)) != 0 ||
 763                     (r = sshbuf_put_stringb(buf, sect)) != 0)
 764                         goto out;
 765         }
 766
 767         /* Finally, output sections for revocations by public key/hash */
 768         sshbuf_reset(sect);
 769         RB_FOREACH(rb, revoked_blob_tree, &krl->revoked_keys) {
 770                 KRL_DBG(("key len %zu ", rb->len));
 771                 if ((r = sshbuf_put_string(sect, rb->blob, rb->len)) != 0)
 772                         goto out;
 773         }
 774         if (sshbuf_len(sect) != 0) {
 775                 if ((r = sshbuf_put_u8(buf, KRL_SECTION_EXPLICIT_KEY)) != 0 ||
 776                     (r = sshbuf_put_stringb(buf, sect)) != 0)
 777                         goto out;
 778         }
 779         sshbuf_reset(sect);
 780         RB_FOREACH(rb, revoked_blob_tree, &krl->revoked_sha1s) {
 781                 KRL_DBG(("hash len %zu ", rb->len));
 782                 if ((r = sshbuf_put_string(sect, rb->blob, rb->len)) != 0)
 783                         goto out;
 784         }
 785         if (sshbuf_len(sect) != 0) {
 786                 if ((r = sshbuf_put_u8(buf,
 787                     KRL_SECTION_FINGERPRINT_SHA1)) != 0 ||
 788                     (r = sshbuf_put_stringb(buf, sect)) != 0)
 789                         goto out;
 790         }
 791         sshbuf_reset(sect);
 792         RB_FOREACH(rb, revoked_blob_tree, &krl->revoked_sha256s) {
 793                 KRL_DBG(("hash len %zu ", rb->len));
 794                 if ((r = sshbuf_put_string(sect, rb->blob, rb->len)) != 0)
 795                         goto out;
 796         }
 797         if (sshbuf_len(sect) != 0) {
 798                 if ((r = sshbuf_put_u8(buf,
 799                     KRL_SECTION_FINGERPRINT_SHA256)) != 0 ||
 800                     (r = sshbuf_put_stringb(buf, sect)) != 0)
 801                         goto out;
 802         }
 803
 804         for (i = 0; i < nsign_keys; i++) {
 805                 KRL_DBG(("sig key %s", sshkey_ssh_name(sign_keys[i])));
 806                 if ((r = sshbuf_put_u8(buf, KRL_SECTION_SIGNATURE)) != 0 ||
 807                     (r = sshkey_puts(sign_keys[i], buf)) != 0)
 808                         goto out;
 809                 /* XXX support sk-* keys */
 810                 if ((r = sshkey_sign(sign_keys[i], &sblob, &slen,
 811                     sshbuf_ptr(buf), sshbuf_len(buf), NULL, NULL,
 812                     NULL, 0)) != 0)
 813                         goto out;
 814                 KRL_DBG(("signature sig len %zu", slen));
 815                 if ((r = sshbuf_put_string(buf, sblob, slen)) != 0)
 816                         goto out;
 817         }
 818
 819         r = 0;
 820  out:
 821         free(sblob);
 822         sshbuf_free(sect);
 823         return r;
 824 }
 825
 826 static void
 827 format_timestamp(u_int64_t timestamp, char *ts, size_t nts)
 828 {
 829         time_t t;
 830         struct tm *tm;
 831
 832         t = timestamp;
 833         tm = localtime(&t);
 834         if (tm == NULL)
 835                 strlcpy(ts, "<INVALID>", nts);
 836         else {
 837                 *ts = '\0';
 838                 strftime(ts, nts, "%Y%m%dT%H%M%S", tm);
 839         }
 840 }
 841
 842 static int
 843 parse_revoked_certs(struct sshbuf *buf, struct ssh_krl *krl)
 844 {
 845         int r = SSH_ERR_INTERNAL_ERROR;
 846         u_char type;
 847         const u_char *blob;
 848         size_t blen, nbits;
 849         struct sshbuf *subsect = NULL;
 850         u_int64_t serial, serial_lo, serial_hi;
 851         struct bitmap *bitmap = NULL;
 852         char *key_id = NULL;
 853         struct sshkey *ca_key = NULL;
 854
 855         if ((subsect = sshbuf_new()) == NULL)
 856                 return SSH_ERR_ALLOC_FAIL;
 857
 858         /* Header: key, reserved */
 859         if ((r = sshbuf_get_string_direct(buf, &blob, &blen)) != 0 ||
 860             (r = sshbuf_skip_string(buf)) != 0)
 861                 goto out;
 862         if (blen != 0 && (r = sshkey_from_blob(blob, blen, &ca_key)) != 0)
 863                 goto out;
 864
 865         while (sshbuf_len(buf) > 0) {
 866                 sshbuf_free(subsect);
 867                 subsect = NULL;
 868                 if ((r = sshbuf_get_u8(buf, &type)) != 0 ||
 869                     (r = sshbuf_froms(buf, &subsect)) != 0)
 870                         goto out;
 871                 KRL_DBG(("subsection type 0x%02x", type));
 872                 /* sshbuf_dump(subsect, stderr); */
 873
 874                 switch (type) {
 875                 case KRL_SECTION_CERT_SERIAL_LIST:
 876                         while (sshbuf_len(subsect) > 0) {
 877                                 if ((r = sshbuf_get_u64(subsect, &serial)) != 0)
 878                                         goto out;
 879                                 if ((r = ssh_krl_revoke_cert_by_serial(krl,
 880                                     ca_key, serial)) != 0)
 881                                         goto out;
 882                         }
 883                         break;
 884                 case KRL_SECTION_CERT_SERIAL_RANGE:
 885                         if ((r = sshbuf_get_u64(subsect, &serial_lo)) != 0 ||
 886                             (r = sshbuf_get_u64(subsect, &serial_hi)) != 0)
 887                                 goto out;
 888                         if ((r = ssh_krl_revoke_cert_by_serial_range(krl,
 889                             ca_key, serial_lo, serial_hi)) != 0)
 890                                 goto out;
 891                         break;
 892                 case KRL_SECTION_CERT_SERIAL_BITMAP:
 893                         if ((bitmap = bitmap_new()) == NULL) {
 894                                 r = SSH_ERR_ALLOC_FAIL;
 895                                 goto out;
 896                         }
 897                         if ((r = sshbuf_get_u64(subsect, &serial_lo)) != 0 ||
 898                             (r = sshbuf_get_bignum2_bytes_direct(subsect,
 899                             &blob, &blen)) != 0)
 900                                 goto out;
 901                         if (bitmap_from_string(bitmap, blob, blen) != 0) {
 902                                 r = SSH_ERR_INVALID_FORMAT;
 903                                 goto out;
 904                         }
 905                         nbits = bitmap_nbits(bitmap);
 906                         for (serial = 0; serial < (u_int64_t)nbits; serial++) {
 907                                 if (serial > 0 && serial_lo + serial == 0) {
 908                                         error_f("bitmap wraps u64");
 909                                         r = SSH_ERR_INVALID_FORMAT;
 910                                         goto out;
 911                                 }
 912                                 if (!bitmap_test_bit(bitmap, serial))
 913                                         continue;
 914                                 if ((r = ssh_krl_revoke_cert_by_serial(krl,
 915                                     ca_key, serial_lo + serial)) != 0)
 916                                         goto out;
 917                         }
 918                         bitmap_free(bitmap);
 919                         bitmap = NULL;
 920                         break;
 921                 case KRL_SECTION_CERT_KEY_ID:
 922                         while (sshbuf_len(subsect) > 0) {
 923                                 if ((r = sshbuf_get_cstring(subsect,
 924                                     &key_id, NULL)) != 0)
 925                                         goto out;
 926                                 if ((r = ssh_krl_revoke_cert_by_key_id(krl,
 927                                     ca_key, key_id)) != 0)
 928                                         goto out;
 929                                 free(key_id);
 930                                 key_id = NULL;
 931                         }
 932                         break;
 933                 default:
 934                         error("Unsupported KRL certificate section %u", type);
 935                         r = SSH_ERR_INVALID_FORMAT;
 936                         goto out;
 937                 }
 938                 if (sshbuf_len(subsect) > 0) {
 939                         error("KRL certificate section contains unparsed data");
 940                         r = SSH_ERR_INVALID_FORMAT;
 941                         goto out;
 942                 }
 943         }
 944
 945         r = 0;
 946  out:
 947         if (bitmap != NULL)
 948                 bitmap_free(bitmap);
 949         free(key_id);
 950         sshkey_free(ca_key);
 951         sshbuf_free(subsect);
 952         return r;
 953 }
 954
 955 static int
 956 blob_section(struct sshbuf *sect, struct revoked_blob_tree *target_tree,
 957     size_t expected_len)
 958 {
 959         u_char *rdata = NULL;
 960         size_t rlen = 0;
 961         int r;
 962
 963         while (sshbuf_len(sect) > 0) {
 964                 if ((r = sshbuf_get_string(sect, &rdata, &rlen)) != 0)
 965                         return r;
 966                 if (expected_len != 0 && rlen != expected_len) {
 967                         error_f("bad length");
 968                         free(rdata);
 969                         return SSH_ERR_INVALID_FORMAT;
 970                 }
 971                 if ((r = revoke_blob(target_tree, rdata, rlen)) != 0) {
 972                         free(rdata);
 973                         return r;
 974                 }
 975         }
 976         return 0;
 977 }
 978
 979 /* Attempt to parse a KRL, checking its signature (if any) with sign_ca_keys. */
 980 int
 981 ssh_krl_from_blob(struct sshbuf *buf, struct ssh_krl **krlp,
 982     const struct sshkey **sign_ca_keys, size_t nsign_ca_keys)
 983 {
 984         struct sshbuf *copy = NULL, *sect = NULL;
 985         struct ssh_krl *krl = NULL;
 986         char timestamp[64];
 987         int r = SSH_ERR_INTERNAL_ERROR, sig_seen;
 988         struct sshkey *key = NULL, **ca_used = NULL, **tmp_ca_used;
 989         u_char type;
 990         const u_char *blob;
 991         size_t i, j, sig_off, sects_off, blen, nca_used;
 992         u_int format_version;
 993
 994         nca_used = 0;
 995         *krlp = NULL;
 996         if (sshbuf_len(buf) < sizeof(KRL_MAGIC) - 1 ||
 997             memcmp(sshbuf_ptr(buf), KRL_MAGIC, sizeof(KRL_MAGIC) - 1) != 0) {
 998                 debug3_f("not a KRL");
 999                 return SSH_ERR_KRL_BAD_MAGIC;
1000         }
1001
1002         /* Take a copy of the KRL buffer so we can verify its signature later */
1003         if ((copy = sshbuf_fromb(buf)) == NULL) {
1004                 r = SSH_ERR_ALLOC_FAIL;
1005                 goto out;
1006         }
1007         if ((r = sshbuf_consume(copy, sizeof(KRL_MAGIC) - 1)) != 0)
1008                 goto out;
1009
1010         if ((krl = ssh_krl_init()) == NULL) {
1011                 error_f("alloc failed");
1012                 goto out;
1013         }
1014
1015         if ((r = sshbuf_get_u32(copy, &format_version)) != 0)
1016                 goto out;
1017         if (format_version != KRL_FORMAT_VERSION) {
1018                 r = SSH_ERR_INVALID_FORMAT;
1019                 goto out;
1020         }
1021         if ((r = sshbuf_get_u64(copy, &krl->krl_version)) != 0 ||
1022             (r = sshbuf_get_u64(copy, &krl->generated_date)) != 0 ||
1023             (r = sshbuf_get_u64(copy, &krl->flags)) != 0 ||
1024             (r = sshbuf_skip_string(copy)) != 0 ||
1025             (r = sshbuf_get_cstring(copy, &krl->comment, NULL)) != 0)
1026                 goto out;
1027
1028         format_timestamp(krl->generated_date, timestamp, sizeof(timestamp));
1029         debug("KRL version %llu generated at %s%s%s",
1030             (long long unsigned)krl->krl_version, timestamp,
1031             *krl->comment ? ": " : "", krl->comment);
1032
1033         /*
1034          * 1st pass: verify signatures, if any. This is done to avoid
1035          * detailed parsing of data whose provenance is unverified.
1036          */
1037         sig_seen = 0;
1038         if (sshbuf_len(buf) < sshbuf_len(copy)) {
1039                 /* Shouldn't happen */
1040                 r = SSH_ERR_INTERNAL_ERROR;
1041                 goto out;
1042         }
1043         sects_off = sshbuf_len(buf) - sshbuf_len(copy);
1044         while (sshbuf_len(copy) > 0) {
1045                 if ((r = sshbuf_get_u8(copy, &type)) != 0 ||
1046                     (r = sshbuf_get_string_direct(copy, &blob, &blen)) != 0)
1047                         goto out;
1048                 KRL_DBG(("first pass, section 0x%02x", type));
1049                 if (type != KRL_SECTION_SIGNATURE) {
1050                         if (sig_seen) {
1051                                 error("KRL contains non-signature section "
1052                                     "after signature");
1053                                 r = SSH_ERR_INVALID_FORMAT;
1054                                 goto out;
1055                         }
1056                         /* Not interested for now. */
1057                         continue;
1058                 }
1059                 sig_seen = 1;
1060                 /* First string component is the signing key */
1061                 if ((r = sshkey_from_blob(blob, blen, &key)) != 0) {
1062                         r = SSH_ERR_INVALID_FORMAT;
1063                         goto out;
1064                 }
1065                 if (sshbuf_len(buf) < sshbuf_len(copy)) {
1066                         /* Shouldn't happen */
1067                         r = SSH_ERR_INTERNAL_ERROR;
1068                         goto out;
1069                 }
1070                 sig_off = sshbuf_len(buf) - sshbuf_len(copy);
1071                 /* Second string component is the signature itself */
1072                 if ((r = sshbuf_get_string_direct(copy, &blob, &blen)) != 0) {
1073                         r = SSH_ERR_INVALID_FORMAT;
1074                         goto out;
1075                 }
1076                 /* Check signature over entire KRL up to this point */
1077                 if ((r = sshkey_verify(key, blob, blen,
1078                     sshbuf_ptr(buf), sig_off, NULL, 0, NULL)) != 0)
1079                         goto out;
1080                 /* Check if this key has already signed this KRL */
1081                 for (i = 0; i < nca_used; i++) {
1082                         if (sshkey_equal(ca_used[i], key)) {
1083                                 error("KRL signed more than once with "
1084                                     "the same key");
1085                                 r = SSH_ERR_INVALID_FORMAT;
1086                                 goto out;
1087                         }
1088                 }
1089                 /* Record keys used to sign the KRL */
1090                 tmp_ca_used = recallocarray(ca_used, nca_used, nca_used + 1,
1091                     sizeof(*ca_used));
1092                 if (tmp_ca_used == NULL) {
1093                         r = SSH_ERR_ALLOC_FAIL;
1094                         goto out;
1095                 }
1096                 ca_used = tmp_ca_used;
1097                 ca_used[nca_used++] = key;
1098                 key = NULL;
1099         }
1100
1101         if (sshbuf_len(copy) != 0) {
1102                 /* Shouldn't happen */
1103                 r = SSH_ERR_INTERNAL_ERROR;
1104                 goto out;
1105         }
1106
1107         /*
1108          * 2nd pass: parse and load the KRL, skipping the header to the point
1109          * where the section start.
1110          */
1111         sshbuf_free(copy);
1112         if ((copy = sshbuf_fromb(buf)) == NULL) {
1113                 r = SSH_ERR_ALLOC_FAIL;
1114                 goto out;
1115         }
1116         if ((r = sshbuf_consume(copy, sects_off)) != 0)
1117                 goto out;
1118         while (sshbuf_len(copy) > 0) {
1119                 sshbuf_free(sect);
1120                 sect = NULL;
1121                 if ((r = sshbuf_get_u8(copy, &type)) != 0 ||
1122                     (r = sshbuf_froms(copy, &sect)) != 0)
1123                         goto out;
1124                 KRL_DBG(("second pass, section 0x%02x", type));
1125
1126                 switch (type) {
1127                 case KRL_SECTION_CERTIFICATES:
1128                         if ((r = parse_revoked_certs(sect, krl)) != 0)
1129                                 goto out;
1130                         break;
1131                 case KRL_SECTION_EXPLICIT_KEY:
1132                         if ((r = blob_section(sect,
1133                             &krl->revoked_keys, 0)) != 0)
1134                                 goto out;
1135                         break;
1136                 case KRL_SECTION_FINGERPRINT_SHA1:
1137                         if ((r = blob_section(sect,
1138                             &krl->revoked_sha1s, 20)) != 0)
1139                                 goto out;
1140                         break;
1141                 case KRL_SECTION_FINGERPRINT_SHA256:
1142                         if ((r = blob_section(sect,
1143                             &krl->revoked_sha256s, 32)) != 0)
1144                                 goto out;
1145                         break;
1146                 case KRL_SECTION_SIGNATURE:
1147                         /* Handled above, but still need to stay in synch */
1148                         sshbuf_free(sect);
1149                         sect = NULL;
1150                         if ((r = sshbuf_skip_string(copy)) != 0)
1151                                 goto out;
1152                         break;
1153                 default:
1154                         error("Unsupported KRL section %u", type);
1155                         r = SSH_ERR_INVALID_FORMAT;
1156                         goto out;
1157                 }
1158                 if (sect != NULL && sshbuf_len(sect) > 0) {
1159                         error("KRL section contains unparsed data");
1160                         r = SSH_ERR_INVALID_FORMAT;
1161                         goto out;
1162                 }
1163         }
1164
1165         /* Check that the key(s) used to sign the KRL weren't revoked */
1166         sig_seen = 0;
1167         for (i = 0; i < nca_used; i++) {
1168                 if (ssh_krl_check_key(krl, ca_used[i]) == 0)
1169                         sig_seen = 1;
1170                 else {
1171                         sshkey_free(ca_used[i]);
1172                         ca_used[i] = NULL;
1173                 }
1174         }
1175         if (nca_used && !sig_seen) {
1176                 error("All keys used to sign KRL were revoked");
1177                 r = SSH_ERR_KEY_REVOKED;
1178                 goto out;
1179         }
1180
1181         /* If we have CA keys, then verify that one was used to sign the KRL */
1182         if (sig_seen && nsign_ca_keys != 0) {
1183                 sig_seen = 0;
1184                 for (i = 0; !sig_seen && i < nsign_ca_keys; i++) {
1185                         for (j = 0; j < nca_used; j++) {
1186                                 if (ca_used[j] == NULL)
1187                                         continue;
1188                                 if (sshkey_equal(ca_used[j], sign_ca_keys[i])) {
1189                                         sig_seen = 1;
1190                                         break;
1191                                 }
1192                         }
1193                 }
1194                 if (!sig_seen) {
1195                         r = SSH_ERR_SIGNATURE_INVALID;
1196                         error("KRL not signed with any trusted key");
1197                         goto out;
1198                 }
1199         }
1200
1201         *krlp = krl;
1202         r = 0;
1203  out:
1204         if (r != 0)
1205                 ssh_krl_free(krl);
1206         for (i = 0; i < nca_used; i++)
1207                 sshkey_free(ca_used[i]);
1208         free(ca_used);
1209         sshkey_free(key);
1210         sshbuf_free(copy);
1211         sshbuf_free(sect);
1212         return r;
1213 }
1214
1215 /* Checks certificate serial number and key ID revocation */
1216 static int
1217 is_cert_revoked(const struct sshkey *key, struct revoked_certs *rc)
1218 {
1219         struct revoked_serial rs, *ers;
1220         struct revoked_key_id rki, *erki;
1221
1222         /* Check revocation by cert key ID */
1223         memset(&rki, 0, sizeof(rki));
1224         rki.key_id = key->cert->key_id;
1225         erki = RB_FIND(revoked_key_id_tree, &rc->revoked_key_ids, &rki);
1226         if (erki != NULL) {
1227                 KRL_DBG(("revoked by key ID"));
1228                 return SSH_ERR_KEY_REVOKED;
1229         }
1230
1231         /*
1232          * Zero serials numbers are ignored (it's the default when the
1233          * CA doesn't specify one).
1234          */
1235         if (key->cert->serial == 0)
1236                 return 0;
1237
1238         memset(&rs, 0, sizeof(rs));
1239         rs.lo = rs.hi = key->cert->serial;
1240         ers = RB_FIND(revoked_serial_tree, &rc->revoked_serials, &rs);
1241         if (ers != NULL) {
1242                 KRL_DBG(("revoked serial %llu matched %llu:%llu",
1243                     key->cert->serial, ers->lo, ers->hi));
1244                 return SSH_ERR_KEY_REVOKED;
1245         }
1246         return 0;
1247 }
1248
1249 /* Checks whether a given key/cert is revoked. Does not check its CA */
1250 static int
1251 is_key_revoked(struct ssh_krl *krl, const struct sshkey *key)
1252 {
1253         struct revoked_blob rb, *erb;
1254         struct revoked_certs *rc;
1255         int r;
1256
1257         /* Check explicitly revoked hashes first */
1258         memset(&rb, 0, sizeof(rb));
1259         if ((r = sshkey_fingerprint_raw(key, SSH_DIGEST_SHA1,
1260             &rb.blob, &rb.len)) != 0)
1261                 return r;
1262         erb = RB_FIND(revoked_blob_tree, &krl->revoked_sha1s, &rb);
1263         free(rb.blob);
1264         if (erb != NULL) {
1265                 KRL_DBG(("revoked by key SHA1"));
1266                 return SSH_ERR_KEY_REVOKED;
1267         }
1268         memset(&rb, 0, sizeof(rb));
1269         if ((r = sshkey_fingerprint_raw(key, SSH_DIGEST_SHA256,
1270             &rb.blob, &rb.len)) != 0)
1271                 return r;
1272         erb = RB_FIND(revoked_blob_tree, &krl->revoked_sha256s, &rb);
1273         free(rb.blob);
1274         if (erb != NULL) {
1275                 KRL_DBG(("revoked by key SHA256"));
1276                 return SSH_ERR_KEY_REVOKED;
1277         }
1278
1279         /* Next, explicit keys */
1280         memset(&rb, 0, sizeof(rb));
1281         if ((r = plain_key_blob(key, &rb.blob, &rb.len)) != 0)
1282                 return r;
1283         erb = RB_FIND(revoked_blob_tree, &krl->revoked_keys, &rb);
1284         free(rb.blob);
1285         if (erb != NULL) {
1286                 KRL_DBG(("revoked by explicit key"));
1287                 return SSH_ERR_KEY_REVOKED;
1288         }
1289
1290         if (!sshkey_is_cert(key))
1291                 return 0;
1292
1293         /* Check cert revocation for the specified CA */
1294         if ((r = revoked_certs_for_ca_key(krl, key->cert->signature_key,
1295             &rc, 0)) != 0)
1296                 return r;
1297         if (rc != NULL) {
1298                 if ((r = is_cert_revoked(key, rc)) != 0)
1299                         return r;
1300         }
1301         /* Check cert revocation for the wildcard CA */
1302         if ((r = revoked_certs_for_ca_key(krl, NULL, &rc, 0)) != 0)
1303                 return r;
1304         if (rc != NULL) {
1305                 if ((r = is_cert_revoked(key, rc)) != 0)
1306                         return r;
1307         }
1308
1309         KRL_DBG(("%llu no match", key->cert->serial));
1310         return 0;
1311 }
1312
1313 int
1314 ssh_krl_check_key(struct ssh_krl *krl, const struct sshkey *key)
1315 {
1316         int r;
1317
1318         KRL_DBG(("checking key"));
1319         if ((r = is_key_revoked(krl, key)) != 0)
1320                 return r;
1321         if (sshkey_is_cert(key)) {
1322                 debug2_f("checking CA key");
1323                 if ((r = is_key_revoked(krl, key->cert->signature_key)) != 0)
1324                         return r;
1325         }
1326         KRL_DBG(("key okay"));
1327         return 0;
1328 }
1329
1330 int
1331 ssh_krl_file_contains_key(const char *path, const struct sshkey *key)
1332 {
1333         struct sshbuf *krlbuf = NULL;
1334         struct ssh_krl *krl = NULL;
1335         int oerrno = 0, r;
1336
1337         if (path == NULL)
1338                 return 0;
1339         if ((r = sshbuf_load_file(path, &krlbuf)) != 0) {
1340                 oerrno = errno;
1341                 goto out;
1342         }
1343         if ((r = ssh_krl_from_blob(krlbuf, &krl, NULL, 0)) != 0)
1344                 goto out;
1345         debug2_f("checking KRL %s", path);
1346         r = ssh_krl_check_key(krl, key);
1347  out:
1348         sshbuf_free(krlbuf);
1349         ssh_krl_free(krl);
1350         if (r != 0)
1351                 errno = oerrno;
1352         return r;
1353 }
1354
1355 int
1356 krl_dump(struct ssh_krl *krl, FILE *f)
1357 {
1358         struct sshkey *key = NULL;
1359         struct revoked_blob *rb;
1360         struct revoked_certs *rc;
1361         struct revoked_serial *rs;
1362         struct revoked_key_id *rki;
1363         int r, ret = 0;
1364         char *fp, timestamp[64];
1365
1366         /* Try to print in a KRL spec-compatible format */
1367         format_timestamp(krl->generated_date, timestamp, sizeof(timestamp));
1368         fprintf(f, "# KRL version %llu\n",
1369             (unsigned long long)krl->krl_version);
1370         fprintf(f, "# Generated at %s\n", timestamp);
1371         if (krl->comment != NULL && *krl->comment != '\0') {
1372                 r = INT_MAX;
1373                 asmprintf(&fp, INT_MAX, &r, "%s", krl->comment);
1374                 fprintf(f, "# Comment: %s\n", fp);
1375                 free(fp);
1376         }
1377         fputc('\n', f);
1378
1379         RB_FOREACH(rb, revoked_blob_tree, &krl->revoked_keys) {
1380                 if ((r = sshkey_from_blob(rb->blob, rb->len, &key)) != 0) {
1381                         ret = SSH_ERR_INVALID_FORMAT;
1382                         error_r(r, "parse KRL key");
1383                         continue;
1384                 }
1385                 if ((fp = sshkey_fingerprint(key, SSH_FP_HASH_DEFAULT,
1386                     SSH_FP_DEFAULT)) == NULL) {
1387                         ret = SSH_ERR_INVALID_FORMAT;
1388                         error("sshkey_fingerprint failed");
1389                         continue;
1390                 }
1391                 fprintf(f, "hash: SHA256:%s # %s\n", fp, sshkey_ssh_name(key));
1392                 free(fp);
1393                 free(key);
1394         }
1395         RB_FOREACH(rb, revoked_blob_tree, &krl->revoked_sha256s) {
1396                 fp = tohex(rb->blob, rb->len);
1397                 fprintf(f, "hash: SHA256:%s\n", fp);
1398                 free(fp);
1399         }
1400         RB_FOREACH(rb, revoked_blob_tree, &krl->revoked_sha1s) {
1401                 /*
1402                  * There is not KRL spec keyword for raw SHA1 hashes, so
1403                  * print them as comments.
1404                  */
1405                 fp = tohex(rb->blob, rb->len);
1406                 fprintf(f, "# hash SHA1:%s\n", fp);
1407                 free(fp);
1408         }
1409
1410         TAILQ_FOREACH(rc, &krl->revoked_certs, entry) {
1411                 fputc('\n', f);
1412                 if (rc->ca_key == NULL)
1413                         fprintf(f, "# Wildcard CA\n");
1414                 else {
1415                         if ((fp = sshkey_fingerprint(rc->ca_key,
1416                             SSH_FP_HASH_DEFAULT, SSH_FP_DEFAULT)) == NULL) {
1417                                 ret = SSH_ERR_INVALID_FORMAT;
1418                                 error("sshkey_fingerprint failed");
1419                                 continue;
1420                         }
1421                         fprintf(f, "# CA key %s %s\n",
1422                             sshkey_ssh_name(rc->ca_key), fp);
1423                         free(fp);
1424                 }
1425                 RB_FOREACH(rs, revoked_serial_tree, &rc->revoked_serials) {
1426                         if (rs->lo == rs->hi) {
1427                                 fprintf(f, "serial: %llu\n",
1428                                     (unsigned long long)rs->lo);
1429                         } else {
1430                                 fprintf(f, "serial: %llu-%llu\n",
1431                                     (unsigned long long)rs->lo,
1432                                     (unsigned long long)rs->hi);
1433                         }
1434                 }
1435                 RB_FOREACH(rki, revoked_key_id_tree, &rc->revoked_key_ids) {
1436                         /*
1437                          * We don't want key IDs with embedded newlines to
1438                          * mess up the display.
1439                          */
1440                         r = INT_MAX;
1441                         asmprintf(&fp, INT_MAX, &r, "%s", rki->key_id);
1442                         fprintf(f, "id: %s\n", fp);
1443                         free(fp);
1444                 }
1445         }
1446         return ret;
1447 }