crypto/openssh/krl.c

   1 /* $OpenBSD: krl.c,v 1.59 2023/07/17 05:22:30 djm Exp $ */
   2 /*
   3  * Copyright (c) 2012 Damien Miller <djm@mindrot.org>
   4  *
   5  * Permission to use, copy, modify, and distribute this software for any
   6  * purpose with or without fee is hereby granted, provided that the above
   7  * copyright notice and this permission notice appear in all copies.
   8  *
   9  * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
  10  * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
  11  * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
  12  * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
  13  * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
  14  * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
  15  * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
  16  */
  17
  18 #include "includes.h"
  19
  20 #include <sys/types.h>
  21 #include <openbsd-compat/sys-tree.h>
  22 #include <openbsd-compat/sys-queue.h>
  23
  24 #include <errno.h>
  25 #include <fcntl.h>
  26 #include <limits.h>
  27 #include <stdlib.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 #include "utf8.h"
  41
  42 #include "krl.h"
  43
  44 /* #define DEBUG_KRL */
  45 #ifdef DEBUG_KRL
  46 # define KRL_DBG(x) debug3_f x
  47 #else
  48 # define KRL_DBG(x)
  49 #endif
  50
  51 /*
  52  * Trees of revoked serial numbers, key IDs and keys. This allows
  53  * quick searching, querying and producing lists in canonical order.
  54  */
  55
  56 /* Tree of serial numbers. XXX make smarter: really need a real sparse bitmap */
  57 struct revoked_serial {
  58         u_int64_t lo, hi;
  59         RB_ENTRY(revoked_serial) tree_entry;
  60 };
  61 static int serial_cmp(struct revoked_serial *a, struct revoked_serial *b);
  62 RB_HEAD(revoked_serial_tree, revoked_serial);
  63 RB_GENERATE_STATIC(revoked_serial_tree, revoked_serial, tree_entry, serial_cmp)
  64
  65 /* Tree of key IDs */
  66 struct revoked_key_id {
  67         char *key_id;
  68         RB_ENTRY(revoked_key_id) tree_entry;
  69 };
  70 static int key_id_cmp(struct revoked_key_id *a, struct revoked_key_id *b);
  71 RB_HEAD(revoked_key_id_tree, revoked_key_id);
  72 RB_GENERATE_STATIC(revoked_key_id_tree, revoked_key_id, tree_entry, key_id_cmp)
  73
  74 /* Tree of blobs (used for keys and fingerprints) */
  75 struct revoked_blob {
  76         u_char *blob;
  77         size_t len;
  78         RB_ENTRY(revoked_blob) tree_entry;
  79 };
  80 static int blob_cmp(struct revoked_blob *a, struct revoked_blob *b);
  81 RB_HEAD(revoked_blob_tree, revoked_blob);
  82 RB_GENERATE_STATIC(revoked_blob_tree, revoked_blob, tree_entry, blob_cmp)
  83
  84 /* Tracks revoked certs for a single CA */
  85 struct revoked_certs {
  86         struct sshkey *ca_key;
  87         struct revoked_serial_tree revoked_serials;
  88         struct revoked_key_id_tree revoked_key_ids;
  89         TAILQ_ENTRY(revoked_certs) entry;
  90 };
  91 TAILQ_HEAD(revoked_certs_list, revoked_certs);
  92
  93 struct ssh_krl {
  94         u_int64_t krl_version;
  95         u_int64_t generated_date;
  96         u_int64_t flags;
  97         char *comment;
  98         struct revoked_blob_tree revoked_keys;
  99         struct revoked_blob_tree revoked_sha1s;
 100         struct revoked_blob_tree revoked_sha256s;
 101         struct revoked_certs_list revoked_certs;
 102 };
 103
 104 /* Return equal if a and b overlap */
 105 static int
 106 serial_cmp(struct revoked_serial *a, struct revoked_serial *b)
 107 {
 108         if (a->hi >= b->lo && a->lo <= b->hi)
 109                 return 0;
 110         return a->lo < b->lo ? -1 : 1;
 111 }
 112
 113 static int
 114 key_id_cmp(struct revoked_key_id *a, struct revoked_key_id *b)
 115 {
 116         return strcmp(a->key_id, b->key_id);
 117 }
 118
 119 static int
 120 blob_cmp(struct revoked_blob *a, struct revoked_blob *b)
 121 {
 122         int r;
 123
 124         if (a->len != b->len) {
 125                 if ((r = memcmp(a->blob, b->blob, MINIMUM(a->len, b->len))) != 0)
 126                         return r;
 127                 return a->len > b->len ? 1 : -1;
 128         } else
 129                 return memcmp(a->blob, b->blob, a->len);
 130 }
 131
 132 struct ssh_krl *
 133 ssh_krl_init(void)
 134 {
 135         struct ssh_krl *krl;
 136
 137         if ((krl = calloc(1, sizeof(*krl))) == NULL)
 138                 return NULL;
 139         RB_INIT(&krl->revoked_keys);
 140         RB_INIT(&krl->revoked_sha1s);
 141         RB_INIT(&krl->revoked_sha256s);
 142         TAILQ_INIT(&krl->revoked_certs);
 143         return krl;
 144 }
 145
 146 static void
 147 revoked_certs_free(struct revoked_certs *rc)
 148 {
 149         struct revoked_serial *rs, *trs;
 150         struct revoked_key_id *rki, *trki;
 151
 152         RB_FOREACH_SAFE(rs, revoked_serial_tree, &rc->revoked_serials, trs) {
 153                 RB_REMOVE(revoked_serial_tree, &rc->revoked_serials, rs);
 154                 free(rs);
 155         }
 156         RB_FOREACH_SAFE(rki, revoked_key_id_tree, &rc->revoked_key_ids, trki) {
 157                 RB_REMOVE(revoked_key_id_tree, &rc->revoked_key_ids, rki);
 158                 free(rki->key_id);
 159                 free(rki);
 160         }
 161         sshkey_free(rc->ca_key);
 162 }
 163
 164 void
 165 ssh_krl_free(struct ssh_krl *krl)
 166 {
 167         struct revoked_blob *rb, *trb;
 168         struct revoked_certs *rc, *trc;
 169
 170         if (krl == NULL)
 171                 return;
 172
 173         free(krl->comment);
 174         RB_FOREACH_SAFE(rb, revoked_blob_tree, &krl->revoked_keys, trb) {
 175                 RB_REMOVE(revoked_blob_tree, &krl->revoked_keys, rb);
 176                 free(rb->blob);
 177                 free(rb);
 178         }
 179         RB_FOREACH_SAFE(rb, revoked_blob_tree, &krl->revoked_sha1s, trb) {
 180                 RB_REMOVE(revoked_blob_tree, &krl->revoked_sha1s, rb);
 181                 free(rb->blob);
 182                 free(rb);
 183         }
 184         RB_FOREACH_SAFE(rb, revoked_blob_tree, &krl->revoked_sha256s, trb) {
 185                 RB_REMOVE(revoked_blob_tree, &krl->revoked_sha256s, rb);
 186                 free(rb->blob);
 187                 free(rb);
 188         }
 189         TAILQ_FOREACH_SAFE(rc, &krl->revoked_certs, entry, trc) {
 190                 TAILQ_REMOVE(&krl->revoked_certs, rc, entry);
 191                 revoked_certs_free(rc);
 192         }
 193         free(krl);
 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 {
 733         int r = SSH_ERR_INTERNAL_ERROR;
 734         struct revoked_certs *rc;
 735         struct revoked_blob *rb;
 736         struct sshbuf *sect;
 737         u_char *sblob = NULL;
 738
 739         if (krl->generated_date == 0)
 740                 krl->generated_date = time(NULL);
 741
 742         if ((sect = sshbuf_new()) == NULL)
 743                 return SSH_ERR_ALLOC_FAIL;
 744
 745         /* Store the header */
 746         if ((r = sshbuf_put(buf, KRL_MAGIC, sizeof(KRL_MAGIC) - 1)) != 0 ||
 747             (r = sshbuf_put_u32(buf, KRL_FORMAT_VERSION)) != 0 ||
 748             (r = sshbuf_put_u64(buf, krl->krl_version)) != 0 ||
 749             (r = sshbuf_put_u64(buf, krl->generated_date)) != 0 ||
 750             (r = sshbuf_put_u64(buf, krl->flags)) != 0 ||
 751             (r = sshbuf_put_string(buf, NULL, 0)) != 0 ||
 752             (r = sshbuf_put_cstring(buf, krl->comment)) != 0)
 753                 goto out;
 754
 755         /* Store sections for revoked certificates */
 756         TAILQ_FOREACH(rc, &krl->revoked_certs, entry) {
 757                 sshbuf_reset(sect);
 758                 if ((r = revoked_certs_generate(rc, sect)) != 0)
 759                         goto out;
 760                 if ((r = sshbuf_put_u8(buf, KRL_SECTION_CERTIFICATES)) != 0 ||
 761                     (r = sshbuf_put_stringb(buf, sect)) != 0)
 762                         goto out;
 763         }
 764
 765         /* Finally, output sections for revocations by public key/hash */
 766         sshbuf_reset(sect);
 767         RB_FOREACH(rb, revoked_blob_tree, &krl->revoked_keys) {
 768                 KRL_DBG(("key len %zu ", rb->len));
 769                 if ((r = sshbuf_put_string(sect, rb->blob, rb->len)) != 0)
 770                         goto out;
 771         }
 772         if (sshbuf_len(sect) != 0) {
 773                 if ((r = sshbuf_put_u8(buf, KRL_SECTION_EXPLICIT_KEY)) != 0 ||
 774                     (r = sshbuf_put_stringb(buf, sect)) != 0)
 775                         goto out;
 776         }
 777         sshbuf_reset(sect);
 778         RB_FOREACH(rb, revoked_blob_tree, &krl->revoked_sha1s) {
 779                 KRL_DBG(("hash len %zu ", rb->len));
 780                 if ((r = sshbuf_put_string(sect, rb->blob, rb->len)) != 0)
 781                         goto out;
 782         }
 783         if (sshbuf_len(sect) != 0) {
 784                 if ((r = sshbuf_put_u8(buf,
 785                     KRL_SECTION_FINGERPRINT_SHA1)) != 0 ||
 786                     (r = sshbuf_put_stringb(buf, sect)) != 0)
 787                         goto out;
 788         }
 789         sshbuf_reset(sect);
 790         RB_FOREACH(rb, revoked_blob_tree, &krl->revoked_sha256s) {
 791                 KRL_DBG(("hash len %zu ", rb->len));
 792                 if ((r = sshbuf_put_string(sect, rb->blob, rb->len)) != 0)
 793                         goto out;
 794         }
 795         if (sshbuf_len(sect) != 0) {
 796                 if ((r = sshbuf_put_u8(buf,
 797                     KRL_SECTION_FINGERPRINT_SHA256)) != 0 ||
 798                     (r = sshbuf_put_stringb(buf, sect)) != 0)
 799                         goto out;
 800         }
 801         /* success */
 802         r = 0;
 803  out:
 804         free(sblob);
 805         sshbuf_free(sect);
 806         return r;
 807 }
 808
 809 static void
 810 format_timestamp(u_int64_t timestamp, char *ts, size_t nts)
 811 {
 812         time_t t;
 813         struct tm *tm;
 814
 815         t = timestamp;
 816         tm = localtime(&t);
 817         if (tm == NULL)
 818                 strlcpy(ts, "<INVALID>", nts);
 819         else {
 820                 *ts = '\0';
 821                 strftime(ts, nts, "%Y%m%dT%H%M%S", tm);
 822         }
 823 }
 824
 825 static int
 826 cert_extension_subsection(struct sshbuf *subsect, struct ssh_krl *krl)
 827 {
 828         int r = SSH_ERR_INTERNAL_ERROR;
 829         u_char critical = 1;
 830         struct sshbuf *value = NULL;
 831         char *name = NULL;
 832
 833         if ((r = sshbuf_get_cstring(subsect, &name, NULL)) != 0 ||
 834             (r = sshbuf_get_u8(subsect, &critical)) != 0 ||
 835             (r = sshbuf_froms(subsect, &value)) != 0) {
 836                 debug_fr(r, "parse");
 837                 error("KRL has invalid certificate extension subsection");
 838                 r = SSH_ERR_INVALID_FORMAT;
 839                 goto out;
 840         }
 841         if (sshbuf_len(subsect) != 0) {
 842                 error("KRL has invalid certificate extension subsection: "
 843                     "trailing data");
 844                 r = SSH_ERR_INVALID_FORMAT;
 845                 goto out;
 846         }
 847         debug_f("cert extension %s critical %u len %zu",
 848             name, critical, sshbuf_len(value));
 849         /* no extensions are currently supported */
 850         if (critical) {
 851                 error("KRL contains unsupported critical certificate "
 852                     "subsection \"%s\"", name);
 853                 r = SSH_ERR_FEATURE_UNSUPPORTED;
 854                 goto out;
 855         }
 856         /* success */
 857         r = 0;
 858  out:
 859         free(name);
 860         sshbuf_free(value);
 861         return r;
 862 }
 863
 864 static int
 865 parse_revoked_certs(struct sshbuf *buf, struct ssh_krl *krl)
 866 {
 867         int r = SSH_ERR_INTERNAL_ERROR;
 868         u_char type;
 869         const u_char *blob;
 870         size_t blen, nbits;
 871         struct sshbuf *subsect = NULL;
 872         u_int64_t serial, serial_lo, serial_hi;
 873         struct bitmap *bitmap = NULL;
 874         char *key_id = NULL;
 875         struct sshkey *ca_key = NULL;
 876
 877         if ((subsect = sshbuf_new()) == NULL)
 878                 return SSH_ERR_ALLOC_FAIL;
 879
 880         /* Header: key, reserved */
 881         if ((r = sshbuf_get_string_direct(buf, &blob, &blen)) != 0 ||
 882             (r = sshbuf_skip_string(buf)) != 0)
 883                 goto out;
 884         if (blen != 0 && (r = sshkey_from_blob(blob, blen, &ca_key)) != 0)
 885                 goto out;
 886
 887         while (sshbuf_len(buf) > 0) {
 888                 sshbuf_free(subsect);
 889                 subsect = NULL;
 890                 if ((r = sshbuf_get_u8(buf, &type)) != 0 ||
 891                     (r = sshbuf_froms(buf, &subsect)) != 0)
 892                         goto out;
 893                 KRL_DBG(("subsection type 0x%02x", type));
 894                 /* sshbuf_dump(subsect, stderr); */
 895
 896                 switch (type) {
 897                 case KRL_SECTION_CERT_SERIAL_LIST:
 898                         while (sshbuf_len(subsect) > 0) {
 899                                 if ((r = sshbuf_get_u64(subsect, &serial)) != 0)
 900                                         goto out;
 901                                 if ((r = ssh_krl_revoke_cert_by_serial(krl,
 902                                     ca_key, serial)) != 0)
 903                                         goto out;
 904                         }
 905                         break;
 906                 case KRL_SECTION_CERT_SERIAL_RANGE:
 907                         if ((r = sshbuf_get_u64(subsect, &serial_lo)) != 0 ||
 908                             (r = sshbuf_get_u64(subsect, &serial_hi)) != 0)
 909                                 goto out;
 910                         if ((r = ssh_krl_revoke_cert_by_serial_range(krl,
 911                             ca_key, serial_lo, serial_hi)) != 0)
 912                                 goto out;
 913                         break;
 914                 case KRL_SECTION_CERT_SERIAL_BITMAP:
 915                         if ((bitmap = bitmap_new()) == NULL) {
 916                                 r = SSH_ERR_ALLOC_FAIL;
 917                                 goto out;
 918                         }
 919                         if ((r = sshbuf_get_u64(subsect, &serial_lo)) != 0 ||
 920                             (r = sshbuf_get_bignum2_bytes_direct(subsect,
 921                             &blob, &blen)) != 0)
 922                                 goto out;
 923                         if (bitmap_from_string(bitmap, blob, blen) != 0) {
 924                                 r = SSH_ERR_INVALID_FORMAT;
 925                                 goto out;
 926                         }
 927                         nbits = bitmap_nbits(bitmap);
 928                         for (serial = 0; serial < (u_int64_t)nbits; serial++) {
 929                                 if (serial > 0 && serial_lo + serial == 0) {
 930                                         error_f("bitmap wraps u64");
 931                                         r = SSH_ERR_INVALID_FORMAT;
 932                                         goto out;
 933                                 }
 934                                 if (!bitmap_test_bit(bitmap, serial))
 935                                         continue;
 936                                 if ((r = ssh_krl_revoke_cert_by_serial(krl,
 937                                     ca_key, serial_lo + serial)) != 0)
 938                                         goto out;
 939                         }
 940                         bitmap_free(bitmap);
 941                         bitmap = NULL;
 942                         break;
 943                 case KRL_SECTION_CERT_KEY_ID:
 944                         while (sshbuf_len(subsect) > 0) {
 945                                 if ((r = sshbuf_get_cstring(subsect,
 946                                     &key_id, NULL)) != 0)
 947                                         goto out;
 948                                 if ((r = ssh_krl_revoke_cert_by_key_id(krl,
 949                                     ca_key, key_id)) != 0)
 950                                         goto out;
 951                                 free(key_id);
 952                                 key_id = NULL;
 953                         }
 954                         break;
 955                 case KRL_SECTION_CERT_EXTENSION:
 956                         if ((r = cert_extension_subsection(subsect, krl)) != 0)
 957                                 goto out;
 958                         break;
 959                 default:
 960                         error("Unsupported KRL certificate section %u", type);
 961                         r = SSH_ERR_INVALID_FORMAT;
 962                         goto out;
 963                 }
 964                 if (sshbuf_len(subsect) > 0) {
 965                         error("KRL certificate section contains unparsed data");
 966                         r = SSH_ERR_INVALID_FORMAT;
 967                         goto out;
 968                 }
 969         }
 970
 971         r = 0;
 972  out:
 973         if (bitmap != NULL)
 974                 bitmap_free(bitmap);
 975         free(key_id);
 976         sshkey_free(ca_key);
 977         sshbuf_free(subsect);
 978         return r;
 979 }
 980
 981 static int
 982 blob_section(struct sshbuf *sect, struct revoked_blob_tree *target_tree,
 983     size_t expected_len)
 984 {
 985         u_char *rdata = NULL;
 986         size_t rlen = 0;
 987         int r;
 988
 989         while (sshbuf_len(sect) > 0) {
 990                 if ((r = sshbuf_get_string(sect, &rdata, &rlen)) != 0)
 991                         return r;
 992                 if (expected_len != 0 && rlen != expected_len) {
 993                         error_f("bad length");
 994                         free(rdata);
 995                         return SSH_ERR_INVALID_FORMAT;
 996                 }
 997                 if ((r = revoke_blob(target_tree, rdata, rlen)) != 0) {
 998                         free(rdata);
 999                         return r;
1000                 }
1001         }
1002         return 0;
1003 }
1004
1005 static int
1006 extension_section(struct sshbuf *sect, struct ssh_krl *krl)
1007 {
1008         int r = SSH_ERR_INTERNAL_ERROR;
1009         u_char critical = 1;
1010         struct sshbuf *value = NULL;
1011         char *name = NULL;
1012
1013         if ((r = sshbuf_get_cstring(sect, &name, NULL)) != 0 ||
1014             (r = sshbuf_get_u8(sect, &critical)) != 0 ||
1015             (r = sshbuf_froms(sect, &value)) != 0) {
1016                 debug_fr(r, "parse");
1017                 error("KRL has invalid extension section");
1018                 r = SSH_ERR_INVALID_FORMAT;
1019                 goto out;
1020         }
1021         if (sshbuf_len(sect) != 0) {
1022                 error("KRL has invalid extension section: trailing data");
1023                 r = SSH_ERR_INVALID_FORMAT;
1024                 goto out;
1025         }
1026         debug_f("extension %s critical %u len %zu",
1027             name, critical, sshbuf_len(value));
1028         /* no extensions are currently supported */
1029         if (critical) {
1030                 error("KRL contains unsupported critical section \"%s\"", name);
1031                 r = SSH_ERR_FEATURE_UNSUPPORTED;
1032                 goto out;
1033         }
1034         /* success */
1035         r = 0;
1036  out:
1037         free(name);
1038         sshbuf_free(value);
1039         return r;
1040 }
1041
1042 /* Attempt to parse a KRL */
1043 int
1044 ssh_krl_from_blob(struct sshbuf *buf, struct ssh_krl **krlp)
1045 {
1046         struct sshbuf *copy = NULL, *sect = NULL;
1047         struct ssh_krl *krl = NULL;
1048         char timestamp[64];
1049         int r = SSH_ERR_INTERNAL_ERROR;
1050         u_char type;
1051         u_int format_version;
1052
1053         *krlp = NULL;
1054
1055         /* KRL must begin with magic string */
1056         if ((r = sshbuf_cmp(buf, 0, KRL_MAGIC, sizeof(KRL_MAGIC) - 1)) != 0) {
1057                 debug2_f("bad KRL magic header");
1058                 return SSH_ERR_KRL_BAD_MAGIC;
1059         }
1060
1061         if ((krl = ssh_krl_init()) == NULL) {
1062                 error_f("alloc failed");
1063                 goto out;
1064         }
1065         /* Don't modify buffer */
1066         if ((copy = sshbuf_fromb(buf)) == NULL) {
1067                 r = SSH_ERR_ALLOC_FAIL;
1068                 goto out;
1069         }
1070         if ((r = sshbuf_consume(copy, sizeof(KRL_MAGIC) - 1)) != 0 ||
1071             (r = sshbuf_get_u32(copy, &format_version)) != 0)
1072                 goto out;
1073         if (format_version != KRL_FORMAT_VERSION) {
1074                 error_f("unsupported KRL format version %u", format_version);
1075                 r = SSH_ERR_INVALID_FORMAT;
1076                 goto out;
1077         }
1078         if ((r = sshbuf_get_u64(copy, &krl->krl_version)) != 0 ||
1079             (r = sshbuf_get_u64(copy, &krl->generated_date)) != 0 ||
1080             (r = sshbuf_get_u64(copy, &krl->flags)) != 0 ||
1081             (r = sshbuf_skip_string(copy)) != 0 ||
1082             (r = sshbuf_get_cstring(copy, &krl->comment, NULL)) != 0) {
1083                 error_fr(r, "parse KRL header");
1084                 goto out;
1085         }
1086         format_timestamp(krl->generated_date, timestamp, sizeof(timestamp));
1087         debug("KRL version %llu generated at %s%s%s",
1088             (long long unsigned)krl->krl_version, timestamp,
1089             *krl->comment ? ": " : "", krl->comment);
1090
1091         /* Parse and load the KRL sections. */
1092         while (sshbuf_len(copy) > 0) {
1093                 sshbuf_free(sect);
1094                 sect = NULL;
1095                 if ((r = sshbuf_get_u8(copy, &type)) != 0 ||
1096                     (r = sshbuf_froms(copy, &sect)) != 0)
1097                         goto out;
1098                 KRL_DBG(("section 0x%02x", type));
1099
1100                 switch (type) {
1101                 case KRL_SECTION_CERTIFICATES:
1102                         if ((r = parse_revoked_certs(sect, krl)) != 0)
1103                                 goto out;
1104                         break;
1105                 case KRL_SECTION_EXPLICIT_KEY:
1106                         if ((r = blob_section(sect,
1107                             &krl->revoked_keys, 0)) != 0)
1108                                 goto out;
1109                         break;
1110                 case KRL_SECTION_FINGERPRINT_SHA1:
1111                         if ((r = blob_section(sect,
1112                             &krl->revoked_sha1s, 20)) != 0)
1113                                 goto out;
1114                         break;
1115                 case KRL_SECTION_FINGERPRINT_SHA256:
1116                         if ((r = blob_section(sect,
1117                             &krl->revoked_sha256s, 32)) != 0)
1118                                 goto out;
1119                         break;
1120                 case KRL_SECTION_EXTENSION:
1121                         if ((r = extension_section(sect, krl)) != 0)
1122                                 goto out;
1123                         break;
1124                 case KRL_SECTION_SIGNATURE:
1125                         /* Handled above, but still need to stay in synch */
1126                         sshbuf_free(sect);
1127                         sect = NULL;
1128                         if ((r = sshbuf_skip_string(copy)) != 0)
1129                                 goto out;
1130                         break;
1131                 default:
1132                         error("Unsupported KRL section %u", type);
1133                         r = SSH_ERR_INVALID_FORMAT;
1134                         goto out;
1135                 }
1136                 if (sect != NULL && sshbuf_len(sect) > 0) {
1137                         error("KRL section contains unparsed data");
1138                         r = SSH_ERR_INVALID_FORMAT;
1139                         goto out;
1140                 }
1141         }
1142
1143         /* Success */
1144         *krlp = krl;
1145         r = 0;
1146  out:
1147         if (r != 0)
1148                 ssh_krl_free(krl);
1149         sshbuf_free(copy);
1150         sshbuf_free(sect);
1151         return r;
1152 }
1153
1154 /* Checks certificate serial number and key ID revocation */
1155 static int
1156 is_cert_revoked(const struct sshkey *key, struct revoked_certs *rc)
1157 {
1158         struct revoked_serial rs, *ers;
1159         struct revoked_key_id rki, *erki;
1160
1161         /* Check revocation by cert key ID */
1162         memset(&rki, 0, sizeof(rki));
1163         rki.key_id = key->cert->key_id;
1164         erki = RB_FIND(revoked_key_id_tree, &rc->revoked_key_ids, &rki);
1165         if (erki != NULL) {
1166                 KRL_DBG(("revoked by key ID"));
1167                 return SSH_ERR_KEY_REVOKED;
1168         }
1169
1170         /*
1171          * Zero serials numbers are ignored (it's the default when the
1172          * CA doesn't specify one).
1173          */
1174         if (key->cert->serial == 0)
1175                 return 0;
1176
1177         memset(&rs, 0, sizeof(rs));
1178         rs.lo = rs.hi = key->cert->serial;
1179         ers = RB_FIND(revoked_serial_tree, &rc->revoked_serials, &rs);
1180         if (ers != NULL) {
1181                 KRL_DBG(("revoked serial %llu matched %llu:%llu",
1182                     key->cert->serial, ers->lo, ers->hi));
1183                 return SSH_ERR_KEY_REVOKED;
1184         }
1185         return 0;
1186 }
1187
1188 /* Checks whether a given key/cert is revoked. Does not check its CA */
1189 static int
1190 is_key_revoked(struct ssh_krl *krl, const struct sshkey *key)
1191 {
1192         struct revoked_blob rb, *erb;
1193         struct revoked_certs *rc;
1194         int r;
1195
1196         /* Check explicitly revoked hashes first */
1197         memset(&rb, 0, sizeof(rb));
1198         if ((r = sshkey_fingerprint_raw(key, SSH_DIGEST_SHA1,
1199             &rb.blob, &rb.len)) != 0)
1200                 return r;
1201         erb = RB_FIND(revoked_blob_tree, &krl->revoked_sha1s, &rb);
1202         free(rb.blob);
1203         if (erb != NULL) {
1204                 KRL_DBG(("revoked by key SHA1"));
1205                 return SSH_ERR_KEY_REVOKED;
1206         }
1207         memset(&rb, 0, sizeof(rb));
1208         if ((r = sshkey_fingerprint_raw(key, SSH_DIGEST_SHA256,
1209             &rb.blob, &rb.len)) != 0)
1210                 return r;
1211         erb = RB_FIND(revoked_blob_tree, &krl->revoked_sha256s, &rb);
1212         free(rb.blob);
1213         if (erb != NULL) {
1214                 KRL_DBG(("revoked by key SHA256"));
1215                 return SSH_ERR_KEY_REVOKED;
1216         }
1217
1218         /* Next, explicit keys */
1219         memset(&rb, 0, sizeof(rb));
1220         if ((r = plain_key_blob(key, &rb.blob, &rb.len)) != 0)
1221                 return r;
1222         erb = RB_FIND(revoked_blob_tree, &krl->revoked_keys, &rb);
1223         free(rb.blob);
1224         if (erb != NULL) {
1225                 KRL_DBG(("revoked by explicit key"));
1226                 return SSH_ERR_KEY_REVOKED;
1227         }
1228
1229         if (!sshkey_is_cert(key))
1230                 return 0;
1231
1232         /* Check cert revocation for the specified CA */
1233         if ((r = revoked_certs_for_ca_key(krl, key->cert->signature_key,
1234             &rc, 0)) != 0)
1235                 return r;
1236         if (rc != NULL) {
1237                 if ((r = is_cert_revoked(key, rc)) != 0)
1238                         return r;
1239         }
1240         /* Check cert revocation for the wildcard CA */
1241         if ((r = revoked_certs_for_ca_key(krl, NULL, &rc, 0)) != 0)
1242                 return r;
1243         if (rc != NULL) {
1244                 if ((r = is_cert_revoked(key, rc)) != 0)
1245                         return r;
1246         }
1247
1248         KRL_DBG(("%llu no match", key->cert->serial));
1249         return 0;
1250 }
1251
1252 int
1253 ssh_krl_check_key(struct ssh_krl *krl, const struct sshkey *key)
1254 {
1255         int r;
1256
1257         KRL_DBG(("checking key"));
1258         if ((r = is_key_revoked(krl, key)) != 0)
1259                 return r;
1260         if (sshkey_is_cert(key)) {
1261                 debug2_f("checking CA key");
1262                 if ((r = is_key_revoked(krl, key->cert->signature_key)) != 0)
1263                         return r;
1264         }
1265         KRL_DBG(("key okay"));
1266         return 0;
1267 }
1268
1269 int
1270 ssh_krl_file_contains_key(const char *path, const struct sshkey *key)
1271 {
1272         struct sshbuf *krlbuf = NULL;
1273         struct ssh_krl *krl = NULL;
1274         int oerrno = 0, r;
1275
1276         if (path == NULL)
1277                 return 0;
1278         if ((r = sshbuf_load_file(path, &krlbuf)) != 0) {
1279                 oerrno = errno;
1280                 goto out;
1281         }
1282         if ((r = ssh_krl_from_blob(krlbuf, &krl)) != 0)
1283                 goto out;
1284         debug2_f("checking KRL %s", path);
1285         r = ssh_krl_check_key(krl, key);
1286  out:
1287         sshbuf_free(krlbuf);
1288         ssh_krl_free(krl);
1289         if (r != 0)
1290                 errno = oerrno;
1291         return r;
1292 }
1293
1294 int
1295 krl_dump(struct ssh_krl *krl, FILE *f)
1296 {
1297         struct sshkey *key = NULL;
1298         struct revoked_blob *rb;
1299         struct revoked_certs *rc;
1300         struct revoked_serial *rs;
1301         struct revoked_key_id *rki;
1302         int r, ret = 0;
1303         char *fp, timestamp[64];
1304
1305         /* Try to print in a KRL spec-compatible format */
1306         format_timestamp(krl->generated_date, timestamp, sizeof(timestamp));
1307         fprintf(f, "# KRL version %llu\n",
1308             (unsigned long long)krl->krl_version);
1309         fprintf(f, "# Generated at %s\n", timestamp);
1310         if (krl->comment != NULL && *krl->comment != '\0') {
1311                 r = INT_MAX;
1312                 asmprintf(&fp, INT_MAX, &r, "%s", krl->comment);
1313                 fprintf(f, "# Comment: %s\n", fp);
1314                 free(fp);
1315         }
1316         fputc('\n', f);
1317
1318         RB_FOREACH(rb, revoked_blob_tree, &krl->revoked_keys) {
1319                 if ((r = sshkey_from_blob(rb->blob, rb->len, &key)) != 0) {
1320                         ret = SSH_ERR_INVALID_FORMAT;
1321                         error_r(r, "parse KRL key");
1322                         continue;
1323                 }
1324                 if ((fp = sshkey_fingerprint(key, SSH_FP_HASH_DEFAULT,
1325                     SSH_FP_DEFAULT)) == NULL) {
1326                         ret = SSH_ERR_INVALID_FORMAT;
1327                         error("sshkey_fingerprint failed");
1328                         continue;
1329                 }
1330                 fprintf(f, "hash: %s # %s\n", fp, sshkey_ssh_name(key));
1331                 free(fp);
1332                 free(key);
1333         }
1334         RB_FOREACH(rb, revoked_blob_tree, &krl->revoked_sha256s) {
1335                 fp = tohex(rb->blob, rb->len);
1336                 fprintf(f, "hash: SHA256:%s\n", fp);
1337                 free(fp);
1338         }
1339         RB_FOREACH(rb, revoked_blob_tree, &krl->revoked_sha1s) {
1340                 /*
1341                  * There is not KRL spec keyword for raw SHA1 hashes, so
1342                  * print them as comments.
1343                  */
1344                 fp = tohex(rb->blob, rb->len);
1345                 fprintf(f, "# hash SHA1:%s\n", fp);
1346                 free(fp);
1347         }
1348
1349         TAILQ_FOREACH(rc, &krl->revoked_certs, entry) {
1350                 fputc('\n', f);
1351                 if (rc->ca_key == NULL)
1352                         fprintf(f, "# Wildcard CA\n");
1353                 else {
1354                         if ((fp = sshkey_fingerprint(rc->ca_key,
1355                             SSH_FP_HASH_DEFAULT, SSH_FP_DEFAULT)) == NULL) {
1356                                 ret = SSH_ERR_INVALID_FORMAT;
1357                                 error("sshkey_fingerprint failed");
1358                                 continue;
1359                         }
1360                         fprintf(f, "# CA key %s %s\n",
1361                             sshkey_ssh_name(rc->ca_key), fp);
1362                         free(fp);
1363                 }
1364                 RB_FOREACH(rs, revoked_serial_tree, &rc->revoked_serials) {
1365                         if (rs->lo == rs->hi) {
1366                                 fprintf(f, "serial: %llu\n",
1367                                     (unsigned long long)rs->lo);
1368                         } else {
1369                                 fprintf(f, "serial: %llu-%llu\n",
1370                                     (unsigned long long)rs->lo,
1371                                     (unsigned long long)rs->hi);
1372                         }
1373                 }
1374                 RB_FOREACH(rki, revoked_key_id_tree, &rc->revoked_key_ids) {
1375                         /*
1376                          * We don't want key IDs with embedded newlines to
1377                          * mess up the display.
1378                          */
1379                         r = INT_MAX;
1380                         asmprintf(&fp, INT_MAX, &r, "%s", rki->key_id);
1381                         fprintf(f, "id: %s\n", fp);
1382                         free(fp);
1383                 }
1384         }
1385         return ret;
1386 }