1248613Sdes/* 2248613Sdes * Copyright (c) 2012 Damien Miller <djm@mindrot.org> 3248613Sdes * 4248613Sdes * Permission to use, copy, modify, and distribute this software for any 5248613Sdes * purpose with or without fee is hereby granted, provided that the above 6248613Sdes * copyright notice and this permission notice appear in all copies. 7248613Sdes * 8248613Sdes * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES 9248613Sdes * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF 10248613Sdes * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR 11248613Sdes * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES 12248613Sdes * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN 13248613Sdes * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF 14248613Sdes * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE. 15248613Sdes */ 16248613Sdes 17296781Sdes/* $OpenBSD: krl.c,v 1.37 2015/12/31 00:33:52 djm Exp $ */ 18248613Sdes 19248613Sdes#include "includes.h" 20248613Sdes 21295367Sdes#include <sys/param.h> /* MIN */ 22248613Sdes#include <sys/types.h> 23248613Sdes#include <openbsd-compat/sys-tree.h> 24248613Sdes#include <openbsd-compat/sys-queue.h> 25248613Sdes 26248613Sdes#include <errno.h> 27248613Sdes#include <fcntl.h> 28248613Sdes#include <limits.h> 29248613Sdes#include <string.h> 30248613Sdes#include <time.h> 31248613Sdes#include <unistd.h> 32248613Sdes 33295367Sdes#include "sshbuf.h" 34295367Sdes#include "ssherr.h" 35295367Sdes#include "sshkey.h" 36248613Sdes#include "authfile.h" 37248613Sdes#include "misc.h" 38248613Sdes#include "log.h" 39295367Sdes#include "digest.h" 40295367Sdes#include "bitmap.h" 41248613Sdes 42248613Sdes#include "krl.h" 43248613Sdes 44248613Sdes/* #define DEBUG_KRL */ 45248613Sdes#ifdef DEBUG_KRL 46248613Sdes# define KRL_DBG(x) debug3 x 47248613Sdes#else 48248613Sdes# define KRL_DBG(x) 49248613Sdes#endif 50248613Sdes 51248613Sdes/* 52248613Sdes * Trees of revoked serial numbers, key IDs and keys. This allows 53248613Sdes * quick searching, querying and producing lists in canonical order. 54248613Sdes */ 55248613Sdes 56248613Sdes/* Tree of serial numbers. XXX make smarter: really need a real sparse bitmap */ 57248613Sdesstruct revoked_serial { 58248613Sdes u_int64_t lo, hi; 59248613Sdes RB_ENTRY(revoked_serial) tree_entry; 60248613Sdes}; 61248613Sdesstatic int serial_cmp(struct revoked_serial *a, struct revoked_serial *b); 62248613SdesRB_HEAD(revoked_serial_tree, revoked_serial); 63248613SdesRB_GENERATE_STATIC(revoked_serial_tree, revoked_serial, tree_entry, serial_cmp); 64248613Sdes 65248613Sdes/* Tree of key IDs */ 66248613Sdesstruct revoked_key_id { 67248613Sdes char *key_id; 68248613Sdes RB_ENTRY(revoked_key_id) tree_entry; 69248613Sdes}; 70248613Sdesstatic int key_id_cmp(struct revoked_key_id *a, struct revoked_key_id *b); 71248613SdesRB_HEAD(revoked_key_id_tree, revoked_key_id); 72248613SdesRB_GENERATE_STATIC(revoked_key_id_tree, revoked_key_id, tree_entry, key_id_cmp); 73248613Sdes 74248613Sdes/* Tree of blobs (used for keys and fingerprints) */ 75248613Sdesstruct revoked_blob { 76248613Sdes u_char *blob; 77295367Sdes size_t len; 78248613Sdes RB_ENTRY(revoked_blob) tree_entry; 79248613Sdes}; 80248613Sdesstatic int blob_cmp(struct revoked_blob *a, struct revoked_blob *b); 81248613SdesRB_HEAD(revoked_blob_tree, revoked_blob); 82248613SdesRB_GENERATE_STATIC(revoked_blob_tree, revoked_blob, tree_entry, blob_cmp); 83248613Sdes 84248613Sdes/* Tracks revoked certs for a single CA */ 85248613Sdesstruct revoked_certs { 86295367Sdes struct sshkey *ca_key; 87248613Sdes struct revoked_serial_tree revoked_serials; 88248613Sdes struct revoked_key_id_tree revoked_key_ids; 89248613Sdes TAILQ_ENTRY(revoked_certs) entry; 90248613Sdes}; 91248613SdesTAILQ_HEAD(revoked_certs_list, revoked_certs); 92248613Sdes 93248613Sdesstruct ssh_krl { 94248613Sdes u_int64_t krl_version; 95248613Sdes u_int64_t generated_date; 96248613Sdes u_int64_t flags; 97248613Sdes char *comment; 98248613Sdes struct revoked_blob_tree revoked_keys; 99248613Sdes struct revoked_blob_tree revoked_sha1s; 100248613Sdes struct revoked_certs_list revoked_certs; 101248613Sdes}; 102248613Sdes 103248613Sdes/* Return equal if a and b overlap */ 104248613Sdesstatic int 105248613Sdesserial_cmp(struct revoked_serial *a, struct revoked_serial *b) 106248613Sdes{ 107248613Sdes if (a->hi >= b->lo && a->lo <= b->hi) 108248613Sdes return 0; 109248613Sdes return a->lo < b->lo ? -1 : 1; 110248613Sdes} 111248613Sdes 112248613Sdesstatic int 113248613Sdeskey_id_cmp(struct revoked_key_id *a, struct revoked_key_id *b) 114248613Sdes{ 115248613Sdes return strcmp(a->key_id, b->key_id); 116248613Sdes} 117248613Sdes 118248613Sdesstatic int 119248613Sdesblob_cmp(struct revoked_blob *a, struct revoked_blob *b) 120248613Sdes{ 121248613Sdes int r; 122248613Sdes 123248613Sdes if (a->len != b->len) { 124248613Sdes if ((r = memcmp(a->blob, b->blob, MIN(a->len, b->len))) != 0) 125248613Sdes return r; 126248613Sdes return a->len > b->len ? 1 : -1; 127248613Sdes } else 128248613Sdes return memcmp(a->blob, b->blob, a->len); 129248613Sdes} 130248613Sdes 131248613Sdesstruct ssh_krl * 132248613Sdesssh_krl_init(void) 133248613Sdes{ 134248613Sdes struct ssh_krl *krl; 135248613Sdes 136248613Sdes if ((krl = calloc(1, sizeof(*krl))) == NULL) 137248613Sdes return NULL; 138248613Sdes RB_INIT(&krl->revoked_keys); 139248613Sdes RB_INIT(&krl->revoked_sha1s); 140248613Sdes TAILQ_INIT(&krl->revoked_certs); 141248613Sdes return krl; 142248613Sdes} 143248613Sdes 144248613Sdesstatic void 145248613Sdesrevoked_certs_free(struct revoked_certs *rc) 146248613Sdes{ 147248613Sdes struct revoked_serial *rs, *trs; 148248613Sdes struct revoked_key_id *rki, *trki; 149248613Sdes 150248613Sdes RB_FOREACH_SAFE(rs, revoked_serial_tree, &rc->revoked_serials, trs) { 151248613Sdes RB_REMOVE(revoked_serial_tree, &rc->revoked_serials, rs); 152248613Sdes free(rs); 153248613Sdes } 154248613Sdes RB_FOREACH_SAFE(rki, revoked_key_id_tree, &rc->revoked_key_ids, trki) { 155248613Sdes RB_REMOVE(revoked_key_id_tree, &rc->revoked_key_ids, rki); 156248613Sdes free(rki->key_id); 157248613Sdes free(rki); 158248613Sdes } 159295367Sdes sshkey_free(rc->ca_key); 160248613Sdes} 161248613Sdes 162248613Sdesvoid 163248613Sdesssh_krl_free(struct ssh_krl *krl) 164248613Sdes{ 165248613Sdes struct revoked_blob *rb, *trb; 166248613Sdes struct revoked_certs *rc, *trc; 167248613Sdes 168248613Sdes if (krl == NULL) 169248613Sdes return; 170248613Sdes 171248613Sdes free(krl->comment); 172248613Sdes RB_FOREACH_SAFE(rb, revoked_blob_tree, &krl->revoked_keys, trb) { 173248613Sdes RB_REMOVE(revoked_blob_tree, &krl->revoked_keys, rb); 174248613Sdes free(rb->blob); 175248613Sdes free(rb); 176248613Sdes } 177248613Sdes RB_FOREACH_SAFE(rb, revoked_blob_tree, &krl->revoked_sha1s, trb) { 178248613Sdes RB_REMOVE(revoked_blob_tree, &krl->revoked_sha1s, rb); 179248613Sdes free(rb->blob); 180248613Sdes free(rb); 181248613Sdes } 182248613Sdes TAILQ_FOREACH_SAFE(rc, &krl->revoked_certs, entry, trc) { 183248613Sdes TAILQ_REMOVE(&krl->revoked_certs, rc, entry); 184248613Sdes revoked_certs_free(rc); 185248613Sdes } 186248613Sdes} 187248613Sdes 188248613Sdesvoid 189248613Sdesssh_krl_set_version(struct ssh_krl *krl, u_int64_t version) 190248613Sdes{ 191248613Sdes krl->krl_version = version; 192248613Sdes} 193248613Sdes 194295367Sdesint 195248613Sdesssh_krl_set_comment(struct ssh_krl *krl, const char *comment) 196248613Sdes{ 197248613Sdes free(krl->comment); 198248613Sdes if ((krl->comment = strdup(comment)) == NULL) 199295367Sdes return SSH_ERR_ALLOC_FAIL; 200295367Sdes return 0; 201248613Sdes} 202248613Sdes 203248613Sdes/* 204248613Sdes * Find the revoked_certs struct for a CA key. If allow_create is set then 205248613Sdes * create a new one in the tree if one did not exist already. 206248613Sdes */ 207248613Sdesstatic int 208295367Sdesrevoked_certs_for_ca_key(struct ssh_krl *krl, const struct sshkey *ca_key, 209248613Sdes struct revoked_certs **rcp, int allow_create) 210248613Sdes{ 211248613Sdes struct revoked_certs *rc; 212295367Sdes int r; 213248613Sdes 214248613Sdes *rcp = NULL; 215248613Sdes TAILQ_FOREACH(rc, &krl->revoked_certs, entry) { 216295367Sdes if ((ca_key == NULL && rc->ca_key == NULL) || 217295367Sdes sshkey_equal(rc->ca_key, ca_key)) { 218248613Sdes *rcp = rc; 219248613Sdes return 0; 220248613Sdes } 221248613Sdes } 222248613Sdes if (!allow_create) 223248613Sdes return 0; 224248613Sdes /* If this CA doesn't exist in the list then add it now */ 225248613Sdes if ((rc = calloc(1, sizeof(*rc))) == NULL) 226295367Sdes return SSH_ERR_ALLOC_FAIL; 227295367Sdes if (ca_key == NULL) 228295367Sdes rc->ca_key = NULL; 229295367Sdes else if ((r = sshkey_from_private(ca_key, &rc->ca_key)) != 0) { 230248613Sdes free(rc); 231295367Sdes return r; 232248613Sdes } 233248613Sdes RB_INIT(&rc->revoked_serials); 234248613Sdes RB_INIT(&rc->revoked_key_ids); 235248613Sdes TAILQ_INSERT_TAIL(&krl->revoked_certs, rc, entry); 236295367Sdes KRL_DBG(("%s: new CA %s", __func__, 237295367Sdes ca_key == NULL ? "*" : sshkey_type(ca_key))); 238248613Sdes *rcp = rc; 239248613Sdes return 0; 240248613Sdes} 241248613Sdes 242248613Sdesstatic int 243248613Sdesinsert_serial_range(struct revoked_serial_tree *rt, u_int64_t lo, u_int64_t hi) 244248613Sdes{ 245248613Sdes struct revoked_serial rs, *ers, *crs, *irs; 246248613Sdes 247248613Sdes KRL_DBG(("%s: insert %llu:%llu", __func__, lo, hi)); 248264377Sdes memset(&rs, 0, sizeof(rs)); 249248613Sdes rs.lo = lo; 250248613Sdes rs.hi = hi; 251248613Sdes ers = RB_NFIND(revoked_serial_tree, rt, &rs); 252248613Sdes if (ers == NULL || serial_cmp(ers, &rs) != 0) { 253248613Sdes /* No entry matches. Just insert */ 254248613Sdes if ((irs = malloc(sizeof(rs))) == NULL) 255295367Sdes return SSH_ERR_ALLOC_FAIL; 256248613Sdes memcpy(irs, &rs, sizeof(*irs)); 257248613Sdes ers = RB_INSERT(revoked_serial_tree, rt, irs); 258248613Sdes if (ers != NULL) { 259248613Sdes KRL_DBG(("%s: bad: ers != NULL", __func__)); 260248613Sdes /* Shouldn't happen */ 261248613Sdes free(irs); 262295367Sdes return SSH_ERR_INTERNAL_ERROR; 263248613Sdes } 264248613Sdes ers = irs; 265248613Sdes } else { 266248613Sdes KRL_DBG(("%s: overlap found %llu:%llu", __func__, 267248613Sdes ers->lo, ers->hi)); 268248613Sdes /* 269248613Sdes * The inserted entry overlaps an existing one. Grow the 270248613Sdes * existing entry. 271248613Sdes */ 272248613Sdes if (ers->lo > lo) 273248613Sdes ers->lo = lo; 274248613Sdes if (ers->hi < hi) 275248613Sdes ers->hi = hi; 276248613Sdes } 277295367Sdes 278248613Sdes /* 279248613Sdes * The inserted or revised range might overlap or abut adjacent ones; 280248613Sdes * coalesce as necessary. 281248613Sdes */ 282248613Sdes 283248613Sdes /* Check predecessors */ 284248613Sdes while ((crs = RB_PREV(revoked_serial_tree, rt, ers)) != NULL) { 285248613Sdes KRL_DBG(("%s: pred %llu:%llu", __func__, crs->lo, crs->hi)); 286248613Sdes if (ers->lo != 0 && crs->hi < ers->lo - 1) 287248613Sdes break; 288248613Sdes /* This entry overlaps. */ 289248613Sdes if (crs->lo < ers->lo) { 290248613Sdes ers->lo = crs->lo; 291248613Sdes KRL_DBG(("%s: pred extend %llu:%llu", __func__, 292248613Sdes ers->lo, ers->hi)); 293248613Sdes } 294248613Sdes RB_REMOVE(revoked_serial_tree, rt, crs); 295248613Sdes free(crs); 296248613Sdes } 297248613Sdes /* Check successors */ 298248613Sdes while ((crs = RB_NEXT(revoked_serial_tree, rt, ers)) != NULL) { 299248613Sdes KRL_DBG(("%s: succ %llu:%llu", __func__, crs->lo, crs->hi)); 300248613Sdes if (ers->hi != (u_int64_t)-1 && crs->lo > ers->hi + 1) 301248613Sdes break; 302248613Sdes /* This entry overlaps. */ 303248613Sdes if (crs->hi > ers->hi) { 304248613Sdes ers->hi = crs->hi; 305248613Sdes KRL_DBG(("%s: succ extend %llu:%llu", __func__, 306248613Sdes ers->lo, ers->hi)); 307248613Sdes } 308248613Sdes RB_REMOVE(revoked_serial_tree, rt, crs); 309248613Sdes free(crs); 310248613Sdes } 311248613Sdes KRL_DBG(("%s: done, final %llu:%llu", __func__, ers->lo, ers->hi)); 312248613Sdes return 0; 313248613Sdes} 314248613Sdes 315248613Sdesint 316295367Sdesssh_krl_revoke_cert_by_serial(struct ssh_krl *krl, const struct sshkey *ca_key, 317248613Sdes u_int64_t serial) 318248613Sdes{ 319248613Sdes return ssh_krl_revoke_cert_by_serial_range(krl, ca_key, serial, serial); 320248613Sdes} 321248613Sdes 322248613Sdesint 323295367Sdesssh_krl_revoke_cert_by_serial_range(struct ssh_krl *krl, 324295367Sdes const struct sshkey *ca_key, u_int64_t lo, u_int64_t hi) 325248613Sdes{ 326248613Sdes struct revoked_certs *rc; 327295367Sdes int r; 328248613Sdes 329248613Sdes if (lo > hi || lo == 0) 330295367Sdes return SSH_ERR_INVALID_ARGUMENT; 331295367Sdes if ((r = revoked_certs_for_ca_key(krl, ca_key, &rc, 1)) != 0) 332295367Sdes return r; 333248613Sdes return insert_serial_range(&rc->revoked_serials, lo, hi); 334248613Sdes} 335248613Sdes 336248613Sdesint 337295367Sdesssh_krl_revoke_cert_by_key_id(struct ssh_krl *krl, const struct sshkey *ca_key, 338248613Sdes const char *key_id) 339248613Sdes{ 340248613Sdes struct revoked_key_id *rki, *erki; 341248613Sdes struct revoked_certs *rc; 342295367Sdes int r; 343248613Sdes 344295367Sdes if ((r = revoked_certs_for_ca_key(krl, ca_key, &rc, 1)) != 0) 345295367Sdes return r; 346248613Sdes 347295367Sdes KRL_DBG(("%s: revoke %s", __func__, key_id)); 348248613Sdes if ((rki = calloc(1, sizeof(*rki))) == NULL || 349248613Sdes (rki->key_id = strdup(key_id)) == NULL) { 350248613Sdes free(rki); 351295367Sdes return SSH_ERR_ALLOC_FAIL; 352248613Sdes } 353248613Sdes erki = RB_INSERT(revoked_key_id_tree, &rc->revoked_key_ids, rki); 354248613Sdes if (erki != NULL) { 355248613Sdes free(rki->key_id); 356248613Sdes free(rki); 357248613Sdes } 358248613Sdes return 0; 359248613Sdes} 360248613Sdes 361248613Sdes/* Convert "key" to a public key blob without any certificate information */ 362248613Sdesstatic int 363295367Sdesplain_key_blob(const struct sshkey *key, u_char **blob, size_t *blen) 364248613Sdes{ 365295367Sdes struct sshkey *kcopy; 366248613Sdes int r; 367248613Sdes 368295367Sdes if ((r = sshkey_from_private(key, &kcopy)) != 0) 369295367Sdes return r; 370295367Sdes if (sshkey_is_cert(kcopy)) { 371295367Sdes if ((r = sshkey_drop_cert(kcopy)) != 0) { 372295367Sdes sshkey_free(kcopy); 373295367Sdes return r; 374248613Sdes } 375248613Sdes } 376295367Sdes r = sshkey_to_blob(kcopy, blob, blen); 377295367Sdes sshkey_free(kcopy); 378295367Sdes return r; 379248613Sdes} 380248613Sdes 381248613Sdes/* Revoke a key blob. Ownership of blob is transferred to the tree */ 382248613Sdesstatic int 383295367Sdesrevoke_blob(struct revoked_blob_tree *rbt, u_char *blob, size_t len) 384248613Sdes{ 385248613Sdes struct revoked_blob *rb, *erb; 386248613Sdes 387248613Sdes if ((rb = calloc(1, sizeof(*rb))) == NULL) 388295367Sdes return SSH_ERR_ALLOC_FAIL; 389248613Sdes rb->blob = blob; 390248613Sdes rb->len = len; 391248613Sdes erb = RB_INSERT(revoked_blob_tree, rbt, rb); 392248613Sdes if (erb != NULL) { 393248613Sdes free(rb->blob); 394248613Sdes free(rb); 395248613Sdes } 396248613Sdes return 0; 397248613Sdes} 398248613Sdes 399248613Sdesint 400295367Sdesssh_krl_revoke_key_explicit(struct ssh_krl *krl, const struct sshkey *key) 401248613Sdes{ 402248613Sdes u_char *blob; 403295367Sdes size_t len; 404295367Sdes int r; 405248613Sdes 406295367Sdes debug3("%s: revoke type %s", __func__, sshkey_type(key)); 407295367Sdes if ((r = plain_key_blob(key, &blob, &len)) != 0) 408295367Sdes return r; 409248613Sdes return revoke_blob(&krl->revoked_keys, blob, len); 410248613Sdes} 411248613Sdes 412248613Sdesint 413295367Sdesssh_krl_revoke_key_sha1(struct ssh_krl *krl, const struct sshkey *key) 414248613Sdes{ 415248613Sdes u_char *blob; 416295367Sdes size_t len; 417295367Sdes int r; 418248613Sdes 419295367Sdes debug3("%s: revoke type %s by sha1", __func__, sshkey_type(key)); 420295367Sdes if ((r = sshkey_fingerprint_raw(key, SSH_DIGEST_SHA1, 421295367Sdes &blob, &len)) != 0) 422295367Sdes return r; 423248613Sdes return revoke_blob(&krl->revoked_sha1s, blob, len); 424248613Sdes} 425248613Sdes 426248613Sdesint 427295367Sdesssh_krl_revoke_key(struct ssh_krl *krl, const struct sshkey *key) 428248613Sdes{ 429295367Sdes if (!sshkey_is_cert(key)) 430248613Sdes return ssh_krl_revoke_key_sha1(krl, key); 431248613Sdes 432295367Sdes if (key->cert->serial == 0) { 433248613Sdes return ssh_krl_revoke_cert_by_key_id(krl, 434248613Sdes key->cert->signature_key, 435248613Sdes key->cert->key_id); 436248613Sdes } else { 437248613Sdes return ssh_krl_revoke_cert_by_serial(krl, 438248613Sdes key->cert->signature_key, 439248613Sdes key->cert->serial); 440248613Sdes } 441248613Sdes} 442248613Sdes 443248613Sdes/* 444295367Sdes * Select the most compact section type to emit next in a KRL based on 445295367Sdes * the current section type, the run length of contiguous revoked serial 446248613Sdes * numbers and the gaps from the last and to the next revoked serial. 447248613Sdes * Applies a mostly-accurate bit cost model to select the section type 448248613Sdes * that will minimise the size of the resultant KRL. 449248613Sdes */ 450248613Sdesstatic int 451248613Sdeschoose_next_state(int current_state, u_int64_t contig, int final, 452248613Sdes u_int64_t last_gap, u_int64_t next_gap, int *force_new_section) 453248613Sdes{ 454248613Sdes int new_state; 455248613Sdes u_int64_t cost, cost_list, cost_range, cost_bitmap, cost_bitmap_restart; 456248613Sdes 457248613Sdes /* 458248613Sdes * Avoid unsigned overflows. 459248613Sdes * The limits are high enough to avoid confusing the calculations. 460248613Sdes */ 461248613Sdes contig = MIN(contig, 1ULL<<31); 462248613Sdes last_gap = MIN(last_gap, 1ULL<<31); 463248613Sdes next_gap = MIN(next_gap, 1ULL<<31); 464248613Sdes 465248613Sdes /* 466248613Sdes * Calculate the cost to switch from the current state to candidates. 467248613Sdes * NB. range sections only ever contain a single range, so their 468248613Sdes * switching cost is independent of the current_state. 469248613Sdes */ 470248613Sdes cost_list = cost_bitmap = cost_bitmap_restart = 0; 471248613Sdes cost_range = 8; 472248613Sdes switch (current_state) { 473248613Sdes case KRL_SECTION_CERT_SERIAL_LIST: 474248613Sdes cost_bitmap_restart = cost_bitmap = 8 + 64; 475248613Sdes break; 476248613Sdes case KRL_SECTION_CERT_SERIAL_BITMAP: 477248613Sdes cost_list = 8; 478248613Sdes cost_bitmap_restart = 8 + 64; 479248613Sdes break; 480248613Sdes case KRL_SECTION_CERT_SERIAL_RANGE: 481248613Sdes case 0: 482248613Sdes cost_bitmap_restart = cost_bitmap = 8 + 64; 483248613Sdes cost_list = 8; 484248613Sdes } 485248613Sdes 486248613Sdes /* Estimate base cost in bits of each section type */ 487248613Sdes cost_list += 64 * contig + (final ? 0 : 8+64); 488248613Sdes cost_range += (2 * 64) + (final ? 0 : 8+64); 489248613Sdes cost_bitmap += last_gap + contig + (final ? 0 : MIN(next_gap, 8+64)); 490248613Sdes cost_bitmap_restart += contig + (final ? 0 : MIN(next_gap, 8+64)); 491248613Sdes 492248613Sdes /* Convert to byte costs for actual comparison */ 493248613Sdes cost_list = (cost_list + 7) / 8; 494248613Sdes cost_bitmap = (cost_bitmap + 7) / 8; 495248613Sdes cost_bitmap_restart = (cost_bitmap_restart + 7) / 8; 496248613Sdes cost_range = (cost_range + 7) / 8; 497248613Sdes 498248613Sdes /* Now pick the best choice */ 499248613Sdes *force_new_section = 0; 500248613Sdes new_state = KRL_SECTION_CERT_SERIAL_BITMAP; 501248613Sdes cost = cost_bitmap; 502248613Sdes if (cost_range < cost) { 503248613Sdes new_state = KRL_SECTION_CERT_SERIAL_RANGE; 504248613Sdes cost = cost_range; 505248613Sdes } 506248613Sdes if (cost_list < cost) { 507248613Sdes new_state = KRL_SECTION_CERT_SERIAL_LIST; 508248613Sdes cost = cost_list; 509248613Sdes } 510248613Sdes if (cost_bitmap_restart < cost) { 511248613Sdes new_state = KRL_SECTION_CERT_SERIAL_BITMAP; 512248613Sdes *force_new_section = 1; 513248613Sdes cost = cost_bitmap_restart; 514248613Sdes } 515295367Sdes KRL_DBG(("%s: contig %llu last_gap %llu next_gap %llu final %d, costs:" 516248613Sdes "list %llu range %llu bitmap %llu new bitmap %llu, " 517255767Sdes "selected 0x%02x%s", __func__, (long long unsigned)contig, 518255767Sdes (long long unsigned)last_gap, (long long unsigned)next_gap, final, 519255767Sdes (long long unsigned)cost_list, (long long unsigned)cost_range, 520255767Sdes (long long unsigned)cost_bitmap, 521255767Sdes (long long unsigned)cost_bitmap_restart, new_state, 522295367Sdes *force_new_section ? " restart" : "")); 523248613Sdes return new_state; 524248613Sdes} 525248613Sdes 526295367Sdesstatic int 527295367Sdesput_bitmap(struct sshbuf *buf, struct bitmap *bitmap) 528295367Sdes{ 529295367Sdes size_t len; 530295367Sdes u_char *blob; 531295367Sdes int r; 532295367Sdes 533295367Sdes len = bitmap_nbytes(bitmap); 534295367Sdes if ((blob = malloc(len)) == NULL) 535295367Sdes return SSH_ERR_ALLOC_FAIL; 536295367Sdes if (bitmap_to_string(bitmap, blob, len) != 0) { 537295367Sdes free(blob); 538295367Sdes return SSH_ERR_INTERNAL_ERROR; 539295367Sdes } 540295367Sdes r = sshbuf_put_bignum2_bytes(buf, blob, len); 541295367Sdes free(blob); 542295367Sdes return r; 543295367Sdes} 544295367Sdes 545248613Sdes/* Generate a KRL_SECTION_CERTIFICATES KRL section */ 546248613Sdesstatic int 547295367Sdesrevoked_certs_generate(struct revoked_certs *rc, struct sshbuf *buf) 548248613Sdes{ 549295367Sdes int final, force_new_sect, r = SSH_ERR_INTERNAL_ERROR; 550248613Sdes u_int64_t i, contig, gap, last = 0, bitmap_start = 0; 551248613Sdes struct revoked_serial *rs, *nrs; 552248613Sdes struct revoked_key_id *rki; 553248613Sdes int next_state, state = 0; 554295367Sdes struct sshbuf *sect; 555295367Sdes struct bitmap *bitmap = NULL; 556248613Sdes 557295367Sdes if ((sect = sshbuf_new()) == NULL) 558295367Sdes return SSH_ERR_ALLOC_FAIL; 559248613Sdes 560295367Sdes /* Store the header: optional CA scope key, reserved */ 561295367Sdes if (rc->ca_key == NULL) { 562295367Sdes if ((r = sshbuf_put_string(buf, NULL, 0)) != 0) 563295367Sdes goto out; 564295367Sdes } else { 565295367Sdes if ((r = sshkey_puts(rc->ca_key, buf)) != 0) 566295367Sdes goto out; 567295367Sdes } 568295367Sdes if ((r = sshbuf_put_string(buf, NULL, 0)) != 0) 569295367Sdes goto out; 570248613Sdes 571248613Sdes /* Store the revoked serials. */ 572248613Sdes for (rs = RB_MIN(revoked_serial_tree, &rc->revoked_serials); 573248613Sdes rs != NULL; 574248613Sdes rs = RB_NEXT(revoked_serial_tree, &rc->revoked_serials, rs)) { 575295367Sdes KRL_DBG(("%s: serial %llu:%llu state 0x%02x", __func__, 576255767Sdes (long long unsigned)rs->lo, (long long unsigned)rs->hi, 577295367Sdes state)); 578248613Sdes 579248613Sdes /* Check contiguous length and gap to next section (if any) */ 580248613Sdes nrs = RB_NEXT(revoked_serial_tree, &rc->revoked_serials, rs); 581248613Sdes final = nrs == NULL; 582248613Sdes gap = nrs == NULL ? 0 : nrs->lo - rs->hi; 583248613Sdes contig = 1 + (rs->hi - rs->lo); 584248613Sdes 585248613Sdes /* Choose next state based on these */ 586248613Sdes next_state = choose_next_state(state, contig, final, 587248613Sdes state == 0 ? 0 : rs->lo - last, gap, &force_new_sect); 588248613Sdes 589248613Sdes /* 590248613Sdes * If the current section is a range section or has a different 591248613Sdes * type to the next section, then finish it off now. 592248613Sdes */ 593248613Sdes if (state != 0 && (force_new_sect || next_state != state || 594248613Sdes state == KRL_SECTION_CERT_SERIAL_RANGE)) { 595295367Sdes KRL_DBG(("%s: finish state 0x%02x", __func__, state)); 596248613Sdes switch (state) { 597248613Sdes case KRL_SECTION_CERT_SERIAL_LIST: 598248613Sdes case KRL_SECTION_CERT_SERIAL_RANGE: 599248613Sdes break; 600248613Sdes case KRL_SECTION_CERT_SERIAL_BITMAP: 601295367Sdes if ((r = put_bitmap(sect, bitmap)) != 0) 602295367Sdes goto out; 603295367Sdes bitmap_free(bitmap); 604248613Sdes bitmap = NULL; 605248613Sdes break; 606248613Sdes } 607295367Sdes if ((r = sshbuf_put_u8(buf, state)) != 0 || 608295367Sdes (r = sshbuf_put_stringb(buf, sect)) != 0) 609295367Sdes goto out; 610295367Sdes sshbuf_reset(sect); 611248613Sdes } 612248613Sdes 613248613Sdes /* If we are starting a new section then prepare it now */ 614248613Sdes if (next_state != state || force_new_sect) { 615295367Sdes KRL_DBG(("%s: start state 0x%02x", __func__, 616295367Sdes next_state)); 617248613Sdes state = next_state; 618295367Sdes sshbuf_reset(sect); 619248613Sdes switch (state) { 620248613Sdes case KRL_SECTION_CERT_SERIAL_LIST: 621248613Sdes case KRL_SECTION_CERT_SERIAL_RANGE: 622248613Sdes break; 623248613Sdes case KRL_SECTION_CERT_SERIAL_BITMAP: 624295367Sdes if ((bitmap = bitmap_new()) == NULL) { 625295367Sdes r = SSH_ERR_ALLOC_FAIL; 626248613Sdes goto out; 627295367Sdes } 628248613Sdes bitmap_start = rs->lo; 629295367Sdes if ((r = sshbuf_put_u64(sect, 630295367Sdes bitmap_start)) != 0) 631295367Sdes goto out; 632248613Sdes break; 633248613Sdes } 634248613Sdes } 635248613Sdes 636248613Sdes /* Perform section-specific processing */ 637248613Sdes switch (state) { 638248613Sdes case KRL_SECTION_CERT_SERIAL_LIST: 639295367Sdes for (i = 0; i < contig; i++) { 640295367Sdes if ((r = sshbuf_put_u64(sect, rs->lo + i)) != 0) 641295367Sdes goto out; 642295367Sdes } 643248613Sdes break; 644248613Sdes case KRL_SECTION_CERT_SERIAL_RANGE: 645295367Sdes if ((r = sshbuf_put_u64(sect, rs->lo)) != 0 || 646295367Sdes (r = sshbuf_put_u64(sect, rs->hi)) != 0) 647295367Sdes goto out; 648248613Sdes break; 649248613Sdes case KRL_SECTION_CERT_SERIAL_BITMAP: 650248613Sdes if (rs->lo - bitmap_start > INT_MAX) { 651248613Sdes error("%s: insane bitmap gap", __func__); 652248613Sdes goto out; 653248613Sdes } 654248613Sdes for (i = 0; i < contig; i++) { 655295367Sdes if (bitmap_set_bit(bitmap, 656295367Sdes rs->lo + i - bitmap_start) != 0) { 657295367Sdes r = SSH_ERR_ALLOC_FAIL; 658248613Sdes goto out; 659295367Sdes } 660248613Sdes } 661248613Sdes break; 662248613Sdes } 663248613Sdes last = rs->hi; 664248613Sdes } 665248613Sdes /* Flush the remaining section, if any */ 666248613Sdes if (state != 0) { 667295367Sdes KRL_DBG(("%s: serial final flush for state 0x%02x", 668295367Sdes __func__, state)); 669248613Sdes switch (state) { 670248613Sdes case KRL_SECTION_CERT_SERIAL_LIST: 671248613Sdes case KRL_SECTION_CERT_SERIAL_RANGE: 672248613Sdes break; 673248613Sdes case KRL_SECTION_CERT_SERIAL_BITMAP: 674295367Sdes if ((r = put_bitmap(sect, bitmap)) != 0) 675295367Sdes goto out; 676295367Sdes bitmap_free(bitmap); 677248613Sdes bitmap = NULL; 678248613Sdes break; 679248613Sdes } 680295367Sdes if ((r = sshbuf_put_u8(buf, state)) != 0 || 681295367Sdes (r = sshbuf_put_stringb(buf, sect)) != 0) 682295367Sdes goto out; 683248613Sdes } 684295367Sdes KRL_DBG(("%s: serial done ", __func__)); 685248613Sdes 686248613Sdes /* Now output a section for any revocations by key ID */ 687295367Sdes sshbuf_reset(sect); 688248613Sdes RB_FOREACH(rki, revoked_key_id_tree, &rc->revoked_key_ids) { 689295367Sdes KRL_DBG(("%s: key ID %s", __func__, rki->key_id)); 690295367Sdes if ((r = sshbuf_put_cstring(sect, rki->key_id)) != 0) 691295367Sdes goto out; 692248613Sdes } 693295367Sdes if (sshbuf_len(sect) != 0) { 694295367Sdes if ((r = sshbuf_put_u8(buf, KRL_SECTION_CERT_KEY_ID)) != 0 || 695295367Sdes (r = sshbuf_put_stringb(buf, sect)) != 0) 696295367Sdes goto out; 697248613Sdes } 698248613Sdes r = 0; 699248613Sdes out: 700295367Sdes bitmap_free(bitmap); 701295367Sdes sshbuf_free(sect); 702248613Sdes return r; 703248613Sdes} 704248613Sdes 705248613Sdesint 706295367Sdesssh_krl_to_blob(struct ssh_krl *krl, struct sshbuf *buf, 707295367Sdes const struct sshkey **sign_keys, u_int nsign_keys) 708248613Sdes{ 709295367Sdes int r = SSH_ERR_INTERNAL_ERROR; 710248613Sdes struct revoked_certs *rc; 711248613Sdes struct revoked_blob *rb; 712295367Sdes struct sshbuf *sect; 713295367Sdes u_char *sblob = NULL; 714295367Sdes size_t slen, i; 715248613Sdes 716248613Sdes if (krl->generated_date == 0) 717248613Sdes krl->generated_date = time(NULL); 718248613Sdes 719295367Sdes if ((sect = sshbuf_new()) == NULL) 720295367Sdes return SSH_ERR_ALLOC_FAIL; 721248613Sdes 722248613Sdes /* Store the header */ 723295367Sdes if ((r = sshbuf_put(buf, KRL_MAGIC, sizeof(KRL_MAGIC) - 1)) != 0 || 724295367Sdes (r = sshbuf_put_u32(buf, KRL_FORMAT_VERSION)) != 0 || 725295367Sdes (r = sshbuf_put_u64(buf, krl->krl_version)) != 0 || 726296781Sdes (r = sshbuf_put_u64(buf, krl->generated_date)) != 0 || 727295367Sdes (r = sshbuf_put_u64(buf, krl->flags)) != 0 || 728295367Sdes (r = sshbuf_put_string(buf, NULL, 0)) != 0 || 729295367Sdes (r = sshbuf_put_cstring(buf, krl->comment)) != 0) 730295367Sdes goto out; 731248613Sdes 732248613Sdes /* Store sections for revoked certificates */ 733248613Sdes TAILQ_FOREACH(rc, &krl->revoked_certs, entry) { 734295367Sdes sshbuf_reset(sect); 735295367Sdes if ((r = revoked_certs_generate(rc, sect)) != 0) 736248613Sdes goto out; 737295367Sdes if ((r = sshbuf_put_u8(buf, KRL_SECTION_CERTIFICATES)) != 0 || 738295367Sdes (r = sshbuf_put_stringb(buf, sect)) != 0) 739295367Sdes goto out; 740248613Sdes } 741248613Sdes 742248613Sdes /* Finally, output sections for revocations by public key/hash */ 743295367Sdes sshbuf_reset(sect); 744248613Sdes RB_FOREACH(rb, revoked_blob_tree, &krl->revoked_keys) { 745295367Sdes KRL_DBG(("%s: key len %zu ", __func__, rb->len)); 746295367Sdes if ((r = sshbuf_put_string(sect, rb->blob, rb->len)) != 0) 747295367Sdes goto out; 748248613Sdes } 749295367Sdes if (sshbuf_len(sect) != 0) { 750295367Sdes if ((r = sshbuf_put_u8(buf, KRL_SECTION_EXPLICIT_KEY)) != 0 || 751295367Sdes (r = sshbuf_put_stringb(buf, sect)) != 0) 752295367Sdes goto out; 753248613Sdes } 754295367Sdes sshbuf_reset(sect); 755248613Sdes RB_FOREACH(rb, revoked_blob_tree, &krl->revoked_sha1s) { 756295367Sdes KRL_DBG(("%s: hash len %zu ", __func__, rb->len)); 757295367Sdes if ((r = sshbuf_put_string(sect, rb->blob, rb->len)) != 0) 758295367Sdes goto out; 759248613Sdes } 760295367Sdes if (sshbuf_len(sect) != 0) { 761295367Sdes if ((r = sshbuf_put_u8(buf, 762295367Sdes KRL_SECTION_FINGERPRINT_SHA1)) != 0 || 763295367Sdes (r = sshbuf_put_stringb(buf, sect)) != 0) 764295367Sdes goto out; 765248613Sdes } 766248613Sdes 767248613Sdes for (i = 0; i < nsign_keys; i++) { 768295367Sdes KRL_DBG(("%s: signature key %s", __func__, 769295367Sdes sshkey_ssh_name(sign_keys[i]))); 770295367Sdes if ((r = sshbuf_put_u8(buf, KRL_SECTION_SIGNATURE)) != 0 || 771295367Sdes (r = sshkey_puts(sign_keys[i], buf)) != 0) 772248613Sdes goto out; 773248613Sdes 774295367Sdes if ((r = sshkey_sign(sign_keys[i], &sblob, &slen, 775296781Sdes sshbuf_ptr(buf), sshbuf_len(buf), NULL, 0)) != 0) 776248613Sdes goto out; 777295367Sdes KRL_DBG(("%s: signature sig len %zu", __func__, slen)); 778295367Sdes if ((r = sshbuf_put_string(buf, sblob, slen)) != 0) 779295367Sdes goto out; 780248613Sdes } 781248613Sdes 782248613Sdes r = 0; 783248613Sdes out: 784248613Sdes free(sblob); 785295367Sdes sshbuf_free(sect); 786248613Sdes return r; 787248613Sdes} 788248613Sdes 789248613Sdesstatic void 790248613Sdesformat_timestamp(u_int64_t timestamp, char *ts, size_t nts) 791248613Sdes{ 792248613Sdes time_t t; 793248613Sdes struct tm *tm; 794248613Sdes 795248613Sdes t = timestamp; 796248613Sdes tm = localtime(&t); 797295367Sdes if (tm == NULL) 798295367Sdes strlcpy(ts, "<INVALID>", nts); 799295367Sdes else { 800295367Sdes *ts = '\0'; 801295367Sdes strftime(ts, nts, "%Y%m%dT%H%M%S", tm); 802295367Sdes } 803248613Sdes} 804248613Sdes 805248613Sdesstatic int 806295367Sdesparse_revoked_certs(struct sshbuf *buf, struct ssh_krl *krl) 807248613Sdes{ 808295367Sdes int r = SSH_ERR_INTERNAL_ERROR; 809295367Sdes u_char type; 810295367Sdes const u_char *blob; 811295367Sdes size_t blen, nbits; 812295367Sdes struct sshbuf *subsect = NULL; 813248613Sdes u_int64_t serial, serial_lo, serial_hi; 814295367Sdes struct bitmap *bitmap = NULL; 815248613Sdes char *key_id = NULL; 816295367Sdes struct sshkey *ca_key = NULL; 817248613Sdes 818295367Sdes if ((subsect = sshbuf_new()) == NULL) 819295367Sdes return SSH_ERR_ALLOC_FAIL; 820248613Sdes 821295367Sdes /* Header: key, reserved */ 822295367Sdes if ((r = sshbuf_get_string_direct(buf, &blob, &blen)) != 0 || 823295367Sdes (r = sshbuf_skip_string(buf)) != 0) 824248613Sdes goto out; 825295367Sdes if (blen != 0 && (r = sshkey_from_blob(blob, blen, &ca_key)) != 0) 826248613Sdes goto out; 827248613Sdes 828295367Sdes while (sshbuf_len(buf) > 0) { 829296781Sdes sshbuf_free(subsect); 830296781Sdes subsect = NULL; 831295367Sdes if ((r = sshbuf_get_u8(buf, &type)) != 0 || 832295367Sdes (r = sshbuf_froms(buf, &subsect)) != 0) 833248613Sdes goto out; 834295367Sdes KRL_DBG(("%s: subsection type 0x%02x", __func__, type)); 835295367Sdes /* sshbuf_dump(subsect, stderr); */ 836248613Sdes 837248613Sdes switch (type) { 838248613Sdes case KRL_SECTION_CERT_SERIAL_LIST: 839295367Sdes while (sshbuf_len(subsect) > 0) { 840295367Sdes if ((r = sshbuf_get_u64(subsect, &serial)) != 0) 841248613Sdes goto out; 842295367Sdes if ((r = ssh_krl_revoke_cert_by_serial(krl, 843295367Sdes ca_key, serial)) != 0) 844248613Sdes goto out; 845248613Sdes } 846248613Sdes break; 847248613Sdes case KRL_SECTION_CERT_SERIAL_RANGE: 848295367Sdes if ((r = sshbuf_get_u64(subsect, &serial_lo)) != 0 || 849295367Sdes (r = sshbuf_get_u64(subsect, &serial_hi)) != 0) 850248613Sdes goto out; 851295367Sdes if ((r = ssh_krl_revoke_cert_by_serial_range(krl, 852295367Sdes ca_key, serial_lo, serial_hi)) != 0) 853248613Sdes goto out; 854248613Sdes break; 855248613Sdes case KRL_SECTION_CERT_SERIAL_BITMAP: 856295367Sdes if ((bitmap = bitmap_new()) == NULL) { 857295367Sdes r = SSH_ERR_ALLOC_FAIL; 858248613Sdes goto out; 859248613Sdes } 860295367Sdes if ((r = sshbuf_get_u64(subsect, &serial_lo)) != 0 || 861295367Sdes (r = sshbuf_get_bignum2_bytes_direct(subsect, 862295367Sdes &blob, &blen)) != 0) 863248613Sdes goto out; 864295367Sdes if (bitmap_from_string(bitmap, blob, blen) != 0) { 865295367Sdes r = SSH_ERR_INVALID_FORMAT; 866248613Sdes goto out; 867248613Sdes } 868295367Sdes nbits = bitmap_nbits(bitmap); 869295367Sdes for (serial = 0; serial < (u_int64_t)nbits; serial++) { 870248613Sdes if (serial > 0 && serial_lo + serial == 0) { 871248613Sdes error("%s: bitmap wraps u64", __func__); 872295367Sdes r = SSH_ERR_INVALID_FORMAT; 873248613Sdes goto out; 874248613Sdes } 875295367Sdes if (!bitmap_test_bit(bitmap, serial)) 876248613Sdes continue; 877295367Sdes if ((r = ssh_krl_revoke_cert_by_serial(krl, 878295367Sdes ca_key, serial_lo + serial)) != 0) 879248613Sdes goto out; 880248613Sdes } 881295367Sdes bitmap_free(bitmap); 882248613Sdes bitmap = NULL; 883248613Sdes break; 884248613Sdes case KRL_SECTION_CERT_KEY_ID: 885295367Sdes while (sshbuf_len(subsect) > 0) { 886295367Sdes if ((r = sshbuf_get_cstring(subsect, 887295367Sdes &key_id, NULL)) != 0) 888248613Sdes goto out; 889295367Sdes if ((r = ssh_krl_revoke_cert_by_key_id(krl, 890295367Sdes ca_key, key_id)) != 0) 891248613Sdes goto out; 892248613Sdes free(key_id); 893248613Sdes key_id = NULL; 894248613Sdes } 895248613Sdes break; 896248613Sdes default: 897248613Sdes error("Unsupported KRL certificate section %u", type); 898295367Sdes r = SSH_ERR_INVALID_FORMAT; 899248613Sdes goto out; 900248613Sdes } 901295367Sdes if (sshbuf_len(subsect) > 0) { 902248613Sdes error("KRL certificate section contains unparsed data"); 903295367Sdes r = SSH_ERR_INVALID_FORMAT; 904248613Sdes goto out; 905248613Sdes } 906248613Sdes } 907248613Sdes 908295367Sdes r = 0; 909248613Sdes out: 910248613Sdes if (bitmap != NULL) 911295367Sdes bitmap_free(bitmap); 912248613Sdes free(key_id); 913295367Sdes sshkey_free(ca_key); 914295367Sdes sshbuf_free(subsect); 915295367Sdes return r; 916248613Sdes} 917248613Sdes 918248613Sdes 919248613Sdes/* Attempt to parse a KRL, checking its signature (if any) with sign_ca_keys. */ 920248613Sdesint 921295367Sdesssh_krl_from_blob(struct sshbuf *buf, struct ssh_krl **krlp, 922295367Sdes const struct sshkey **sign_ca_keys, size_t nsign_ca_keys) 923248613Sdes{ 924295367Sdes struct sshbuf *copy = NULL, *sect = NULL; 925295367Sdes struct ssh_krl *krl = NULL; 926248613Sdes char timestamp[64]; 927295367Sdes int r = SSH_ERR_INTERNAL_ERROR, sig_seen; 928295367Sdes struct sshkey *key = NULL, **ca_used = NULL, **tmp_ca_used; 929295367Sdes u_char type, *rdata = NULL; 930295367Sdes const u_char *blob; 931295367Sdes size_t i, j, sig_off, sects_off, rlen, blen, nca_used; 932295367Sdes u_int format_version; 933248613Sdes 934255767Sdes nca_used = 0; 935248613Sdes *krlp = NULL; 936295367Sdes if (sshbuf_len(buf) < sizeof(KRL_MAGIC) - 1 || 937295367Sdes memcmp(sshbuf_ptr(buf), KRL_MAGIC, sizeof(KRL_MAGIC) - 1) != 0) { 938248613Sdes debug3("%s: not a KRL", __func__); 939295367Sdes return SSH_ERR_KRL_BAD_MAGIC; 940248613Sdes } 941248613Sdes 942248613Sdes /* Take a copy of the KRL buffer so we can verify its signature later */ 943295367Sdes if ((copy = sshbuf_fromb(buf)) == NULL) { 944295367Sdes r = SSH_ERR_ALLOC_FAIL; 945295367Sdes goto out; 946295367Sdes } 947295367Sdes if ((r = sshbuf_consume(copy, sizeof(KRL_MAGIC) - 1)) != 0) 948295367Sdes goto out; 949248613Sdes 950248613Sdes if ((krl = ssh_krl_init()) == NULL) { 951248613Sdes error("%s: alloc failed", __func__); 952248613Sdes goto out; 953248613Sdes } 954248613Sdes 955295367Sdes if ((r = sshbuf_get_u32(copy, &format_version)) != 0) 956248613Sdes goto out; 957248613Sdes if (format_version != KRL_FORMAT_VERSION) { 958295367Sdes r = SSH_ERR_INVALID_FORMAT; 959248613Sdes goto out; 960248613Sdes } 961295367Sdes if ((r = sshbuf_get_u64(copy, &krl->krl_version)) != 0 || 962295367Sdes (r = sshbuf_get_u64(copy, &krl->generated_date)) != 0 || 963295367Sdes (r = sshbuf_get_u64(copy, &krl->flags)) != 0 || 964295367Sdes (r = sshbuf_skip_string(copy)) != 0 || 965295367Sdes (r = sshbuf_get_cstring(copy, &krl->comment, NULL)) != 0) 966248613Sdes goto out; 967248613Sdes 968248613Sdes format_timestamp(krl->generated_date, timestamp, sizeof(timestamp)); 969249015Sdes debug("KRL version %llu generated at %s%s%s", 970255767Sdes (long long unsigned)krl->krl_version, timestamp, 971249015Sdes *krl->comment ? ": " : "", krl->comment); 972248613Sdes 973248613Sdes /* 974248613Sdes * 1st pass: verify signatures, if any. This is done to avoid 975248613Sdes * detailed parsing of data whose provenance is unverified. 976248613Sdes */ 977248613Sdes sig_seen = 0; 978295367Sdes if (sshbuf_len(buf) < sshbuf_len(copy)) { 979295367Sdes /* Shouldn't happen */ 980295367Sdes r = SSH_ERR_INTERNAL_ERROR; 981295367Sdes goto out; 982295367Sdes } 983295367Sdes sects_off = sshbuf_len(buf) - sshbuf_len(copy); 984295367Sdes while (sshbuf_len(copy) > 0) { 985295367Sdes if ((r = sshbuf_get_u8(copy, &type)) != 0 || 986295367Sdes (r = sshbuf_get_string_direct(copy, &blob, &blen)) != 0) 987248613Sdes goto out; 988295367Sdes KRL_DBG(("%s: first pass, section 0x%02x", __func__, type)); 989248613Sdes if (type != KRL_SECTION_SIGNATURE) { 990248613Sdes if (sig_seen) { 991248613Sdes error("KRL contains non-signature section " 992248613Sdes "after signature"); 993295367Sdes r = SSH_ERR_INVALID_FORMAT; 994248613Sdes goto out; 995248613Sdes } 996248613Sdes /* Not interested for now. */ 997248613Sdes continue; 998248613Sdes } 999248613Sdes sig_seen = 1; 1000248613Sdes /* First string component is the signing key */ 1001295367Sdes if ((r = sshkey_from_blob(blob, blen, &key)) != 0) { 1002295367Sdes r = SSH_ERR_INVALID_FORMAT; 1003248613Sdes goto out; 1004248613Sdes } 1005295367Sdes if (sshbuf_len(buf) < sshbuf_len(copy)) { 1006295367Sdes /* Shouldn't happen */ 1007295367Sdes r = SSH_ERR_INTERNAL_ERROR; 1008295367Sdes goto out; 1009295367Sdes } 1010295367Sdes sig_off = sshbuf_len(buf) - sshbuf_len(copy); 1011248613Sdes /* Second string component is the signature itself */ 1012295367Sdes if ((r = sshbuf_get_string_direct(copy, &blob, &blen)) != 0) { 1013295367Sdes r = SSH_ERR_INVALID_FORMAT; 1014248613Sdes goto out; 1015248613Sdes } 1016248613Sdes /* Check signature over entire KRL up to this point */ 1017295367Sdes if ((r = sshkey_verify(key, blob, blen, 1018296781Sdes sshbuf_ptr(buf), sig_off, 0)) != 0) 1019248613Sdes goto out; 1020248613Sdes /* Check if this key has already signed this KRL */ 1021248613Sdes for (i = 0; i < nca_used; i++) { 1022295367Sdes if (sshkey_equal(ca_used[i], key)) { 1023248613Sdes error("KRL signed more than once with " 1024248613Sdes "the same key"); 1025295367Sdes r = SSH_ERR_INVALID_FORMAT; 1026248613Sdes goto out; 1027248613Sdes } 1028248613Sdes } 1029248613Sdes /* Record keys used to sign the KRL */ 1030295367Sdes tmp_ca_used = reallocarray(ca_used, nca_used + 1, 1031295367Sdes sizeof(*ca_used)); 1032295367Sdes if (tmp_ca_used == NULL) { 1033295367Sdes r = SSH_ERR_ALLOC_FAIL; 1034295367Sdes goto out; 1035295367Sdes } 1036295367Sdes ca_used = tmp_ca_used; 1037248613Sdes ca_used[nca_used++] = key; 1038248613Sdes key = NULL; 1039248613Sdes } 1040248613Sdes 1041295367Sdes if (sshbuf_len(copy) != 0) { 1042295367Sdes /* Shouldn't happen */ 1043295367Sdes r = SSH_ERR_INTERNAL_ERROR; 1044295367Sdes goto out; 1045295367Sdes } 1046295367Sdes 1047248613Sdes /* 1048248613Sdes * 2nd pass: parse and load the KRL, skipping the header to the point 1049248613Sdes * where the section start. 1050248613Sdes */ 1051295367Sdes sshbuf_free(copy); 1052295367Sdes if ((copy = sshbuf_fromb(buf)) == NULL) { 1053295367Sdes r = SSH_ERR_ALLOC_FAIL; 1054295367Sdes goto out; 1055295367Sdes } 1056295367Sdes if ((r = sshbuf_consume(copy, sects_off)) != 0) 1057295367Sdes goto out; 1058295367Sdes while (sshbuf_len(copy) > 0) { 1059296781Sdes sshbuf_free(sect); 1060296781Sdes sect = NULL; 1061295367Sdes if ((r = sshbuf_get_u8(copy, &type)) != 0 || 1062295367Sdes (r = sshbuf_froms(copy, §)) != 0) 1063248613Sdes goto out; 1064295367Sdes KRL_DBG(("%s: second pass, section 0x%02x", __func__, type)); 1065248613Sdes 1066248613Sdes switch (type) { 1067248613Sdes case KRL_SECTION_CERTIFICATES: 1068295367Sdes if ((r = parse_revoked_certs(sect, krl)) != 0) 1069248613Sdes goto out; 1070248613Sdes break; 1071248613Sdes case KRL_SECTION_EXPLICIT_KEY: 1072248613Sdes case KRL_SECTION_FINGERPRINT_SHA1: 1073295367Sdes while (sshbuf_len(sect) > 0) { 1074295367Sdes if ((r = sshbuf_get_string(sect, 1075295367Sdes &rdata, &rlen)) != 0) 1076248613Sdes goto out; 1077248613Sdes if (type == KRL_SECTION_FINGERPRINT_SHA1 && 1078255767Sdes rlen != 20) { 1079248613Sdes error("%s: bad SHA1 length", __func__); 1080295367Sdes r = SSH_ERR_INVALID_FORMAT; 1081248613Sdes goto out; 1082248613Sdes } 1083295367Sdes if ((r = revoke_blob( 1084248613Sdes type == KRL_SECTION_EXPLICIT_KEY ? 1085248613Sdes &krl->revoked_keys : &krl->revoked_sha1s, 1086295367Sdes rdata, rlen)) != 0) 1087255767Sdes goto out; 1088295367Sdes rdata = NULL; /* revoke_blob frees rdata */ 1089248613Sdes } 1090248613Sdes break; 1091248613Sdes case KRL_SECTION_SIGNATURE: 1092248613Sdes /* Handled above, but still need to stay in synch */ 1093295367Sdes sshbuf_reset(sect); 1094295367Sdes sect = NULL; 1095295367Sdes if ((r = sshbuf_skip_string(copy)) != 0) 1096248613Sdes goto out; 1097248613Sdes break; 1098248613Sdes default: 1099248613Sdes error("Unsupported KRL section %u", type); 1100295367Sdes r = SSH_ERR_INVALID_FORMAT; 1101248613Sdes goto out; 1102248613Sdes } 1103296781Sdes if (sect != NULL && sshbuf_len(sect) > 0) { 1104248613Sdes error("KRL section contains unparsed data"); 1105295367Sdes r = SSH_ERR_INVALID_FORMAT; 1106248613Sdes goto out; 1107248613Sdes } 1108248613Sdes } 1109248613Sdes 1110248613Sdes /* Check that the key(s) used to sign the KRL weren't revoked */ 1111248613Sdes sig_seen = 0; 1112248613Sdes for (i = 0; i < nca_used; i++) { 1113248613Sdes if (ssh_krl_check_key(krl, ca_used[i]) == 0) 1114248613Sdes sig_seen = 1; 1115248613Sdes else { 1116295367Sdes sshkey_free(ca_used[i]); 1117248613Sdes ca_used[i] = NULL; 1118248613Sdes } 1119248613Sdes } 1120248613Sdes if (nca_used && !sig_seen) { 1121248613Sdes error("All keys used to sign KRL were revoked"); 1122295367Sdes r = SSH_ERR_KEY_REVOKED; 1123248613Sdes goto out; 1124248613Sdes } 1125248613Sdes 1126248613Sdes /* If we have CA keys, then verify that one was used to sign the KRL */ 1127248613Sdes if (sig_seen && nsign_ca_keys != 0) { 1128248613Sdes sig_seen = 0; 1129248613Sdes for (i = 0; !sig_seen && i < nsign_ca_keys; i++) { 1130248613Sdes for (j = 0; j < nca_used; j++) { 1131248613Sdes if (ca_used[j] == NULL) 1132248613Sdes continue; 1133295367Sdes if (sshkey_equal(ca_used[j], sign_ca_keys[i])) { 1134248613Sdes sig_seen = 1; 1135248613Sdes break; 1136248613Sdes } 1137248613Sdes } 1138248613Sdes } 1139248613Sdes if (!sig_seen) { 1140295367Sdes r = SSH_ERR_SIGNATURE_INVALID; 1141248613Sdes error("KRL not signed with any trusted key"); 1142248613Sdes goto out; 1143248613Sdes } 1144248613Sdes } 1145248613Sdes 1146248613Sdes *krlp = krl; 1147295367Sdes r = 0; 1148248613Sdes out: 1149295367Sdes if (r != 0) 1150248613Sdes ssh_krl_free(krl); 1151295367Sdes for (i = 0; i < nca_used; i++) 1152295367Sdes sshkey_free(ca_used[i]); 1153248613Sdes free(ca_used); 1154255767Sdes free(rdata); 1155295367Sdes sshkey_free(key); 1156295367Sdes sshbuf_free(copy); 1157295367Sdes sshbuf_free(sect); 1158295367Sdes return r; 1159248613Sdes} 1160248613Sdes 1161295367Sdes/* Checks certificate serial number and key ID revocation */ 1162295367Sdesstatic int 1163295367Sdesis_cert_revoked(const struct sshkey *key, struct revoked_certs *rc) 1164295367Sdes{ 1165295367Sdes struct revoked_serial rs, *ers; 1166295367Sdes struct revoked_key_id rki, *erki; 1167295367Sdes 1168295367Sdes /* Check revocation by cert key ID */ 1169295367Sdes memset(&rki, 0, sizeof(rki)); 1170295367Sdes rki.key_id = key->cert->key_id; 1171295367Sdes erki = RB_FIND(revoked_key_id_tree, &rc->revoked_key_ids, &rki); 1172295367Sdes if (erki != NULL) { 1173295367Sdes KRL_DBG(("%s: revoked by key ID", __func__)); 1174295367Sdes return SSH_ERR_KEY_REVOKED; 1175295367Sdes } 1176295367Sdes 1177295367Sdes /* 1178295367Sdes * Zero serials numbers are ignored (it's the default when the 1179295367Sdes * CA doesn't specify one). 1180295367Sdes */ 1181295367Sdes if (key->cert->serial == 0) 1182295367Sdes return 0; 1183295367Sdes 1184295367Sdes memset(&rs, 0, sizeof(rs)); 1185295367Sdes rs.lo = rs.hi = key->cert->serial; 1186295367Sdes ers = RB_FIND(revoked_serial_tree, &rc->revoked_serials, &rs); 1187295367Sdes if (ers != NULL) { 1188295367Sdes KRL_DBG(("%s: revoked serial %llu matched %llu:%llu", __func__, 1189295367Sdes key->cert->serial, ers->lo, ers->hi)); 1190295367Sdes return SSH_ERR_KEY_REVOKED; 1191295367Sdes } 1192295367Sdes return 0; 1193295367Sdes} 1194295367Sdes 1195248613Sdes/* Checks whether a given key/cert is revoked. Does not check its CA */ 1196248613Sdesstatic int 1197295367Sdesis_key_revoked(struct ssh_krl *krl, const struct sshkey *key) 1198248613Sdes{ 1199248613Sdes struct revoked_blob rb, *erb; 1200248613Sdes struct revoked_certs *rc; 1201295367Sdes int r; 1202248613Sdes 1203248613Sdes /* Check explicitly revoked hashes first */ 1204264377Sdes memset(&rb, 0, sizeof(rb)); 1205295367Sdes if ((r = sshkey_fingerprint_raw(key, SSH_DIGEST_SHA1, 1206295367Sdes &rb.blob, &rb.len)) != 0) 1207295367Sdes return r; 1208248613Sdes erb = RB_FIND(revoked_blob_tree, &krl->revoked_sha1s, &rb); 1209248613Sdes free(rb.blob); 1210248613Sdes if (erb != NULL) { 1211295367Sdes KRL_DBG(("%s: revoked by key SHA1", __func__)); 1212295367Sdes return SSH_ERR_KEY_REVOKED; 1213248613Sdes } 1214248613Sdes 1215248613Sdes /* Next, explicit keys */ 1216264377Sdes memset(&rb, 0, sizeof(rb)); 1217295367Sdes if ((r = plain_key_blob(key, &rb.blob, &rb.len)) != 0) 1218295367Sdes return r; 1219248613Sdes erb = RB_FIND(revoked_blob_tree, &krl->revoked_keys, &rb); 1220248613Sdes free(rb.blob); 1221248613Sdes if (erb != NULL) { 1222295367Sdes KRL_DBG(("%s: revoked by explicit key", __func__)); 1223295367Sdes return SSH_ERR_KEY_REVOKED; 1224248613Sdes } 1225248613Sdes 1226295367Sdes if (!sshkey_is_cert(key)) 1227248613Sdes return 0; 1228248613Sdes 1229295367Sdes /* Check cert revocation for the specified CA */ 1230295367Sdes if ((r = revoked_certs_for_ca_key(krl, key->cert->signature_key, 1231295367Sdes &rc, 0)) != 0) 1232295367Sdes return r; 1233295367Sdes if (rc != NULL) { 1234295367Sdes if ((r = is_cert_revoked(key, rc)) != 0) 1235295367Sdes return r; 1236248613Sdes } 1237295367Sdes /* Check cert revocation for the wildcard CA */ 1238295367Sdes if ((r = revoked_certs_for_ca_key(krl, NULL, &rc, 0)) != 0) 1239295367Sdes return r; 1240295367Sdes if (rc != NULL) { 1241295367Sdes if ((r = is_cert_revoked(key, rc)) != 0) 1242295367Sdes return r; 1243295367Sdes } 1244248613Sdes 1245248613Sdes KRL_DBG(("%s: %llu no match", __func__, key->cert->serial)); 1246248613Sdes return 0; 1247248613Sdes} 1248248613Sdes 1249248613Sdesint 1250295367Sdesssh_krl_check_key(struct ssh_krl *krl, const struct sshkey *key) 1251248613Sdes{ 1252248613Sdes int r; 1253248613Sdes 1254295367Sdes KRL_DBG(("%s: checking key", __func__)); 1255248613Sdes if ((r = is_key_revoked(krl, key)) != 0) 1256248613Sdes return r; 1257295367Sdes if (sshkey_is_cert(key)) { 1258248613Sdes debug2("%s: checking CA key", __func__); 1259248613Sdes if ((r = is_key_revoked(krl, key->cert->signature_key)) != 0) 1260248613Sdes return r; 1261248613Sdes } 1262295367Sdes KRL_DBG(("%s: key okay", __func__)); 1263248613Sdes return 0; 1264248613Sdes} 1265248613Sdes 1266248613Sdesint 1267295367Sdesssh_krl_file_contains_key(const char *path, const struct sshkey *key) 1268248613Sdes{ 1269295367Sdes struct sshbuf *krlbuf = NULL; 1270295367Sdes struct ssh_krl *krl = NULL; 1271295367Sdes int oerrno = 0, r, fd; 1272248613Sdes 1273248613Sdes if (path == NULL) 1274248613Sdes return 0; 1275248613Sdes 1276295367Sdes if ((krlbuf = sshbuf_new()) == NULL) 1277295367Sdes return SSH_ERR_ALLOC_FAIL; 1278248613Sdes if ((fd = open(path, O_RDONLY)) == -1) { 1279295367Sdes r = SSH_ERR_SYSTEM_ERROR; 1280295367Sdes oerrno = errno; 1281295367Sdes goto out; 1282248613Sdes } 1283295367Sdes if ((r = sshkey_load_file(fd, krlbuf)) != 0) { 1284295367Sdes oerrno = errno; 1285295367Sdes goto out; 1286248613Sdes } 1287295367Sdes if ((r = ssh_krl_from_blob(krlbuf, &krl, NULL, 0)) != 0) 1288295367Sdes goto out; 1289295367Sdes debug2("%s: checking KRL %s", __func__, path); 1290295367Sdes r = ssh_krl_check_key(krl, key); 1291295367Sdes out: 1292248613Sdes close(fd); 1293295367Sdes sshbuf_free(krlbuf); 1294248613Sdes ssh_krl_free(krl); 1295295367Sdes if (r != 0) 1296295367Sdes errno = oerrno; 1297295367Sdes return r; 1298248613Sdes} 1299