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