src/or/keypin.c

   1 /* Copyright (c) 2014, The Tor Project, Inc. */
   2 /* See LICENSE for licensing information */
   3
   4 #define KEYPIN_PRIVATE
   5
   6 #include "orconfig.h"
   7 #include "compat.h"
   8 #include "crypto.h"
   9 #include "crypto_format.h"
  10 #include "di_ops.h"
  11 #include "ht.h"
  12 #include "keypin.h"
  13 #include "siphash.h"
  14 #include "torint.h"
  15 #include "torlog.h"
  16 #include "util.h"
  17 #include "util_format.h"
  18
  19 #ifdef HAVE_UNISTD_H
  20 #include <unistd.h>
  21 #endif
  22 #ifdef HAVE_FCNTL_H
  23 #include <fcntl.h>
  24 #endif
  25
  26 #ifdef _WIN32
  27 #include <io.h>
  28 #endif
  29
  30 /**
  31  * @file keypin.c
  32  * @brief Key-pinning for RSA and Ed25519 identity keys at directory
  33  *  authorities.
  34  *
  35  * This module implements a key-pinning mechanism to ensure that it's safe
  36  * to use RSA keys as identitifers even as we migrate to Ed25519 keys.  It
  37  * remembers, for every Ed25519 key we've seen, what the associated Ed25519
  38  * key is.  This way, if we see a different Ed25519 key with that RSA key,
  39  * we'll know that there's a mismatch.
  40  *
  41  * We persist these entries to disk using a simple format, where each line
  42  * has a base64-encoded RSA SHA1 hash, then a base64-endoded Ed25519 key.
  43  * Empty lines, misformed lines, and lines beginning with # are
  44  * ignored. Lines beginning with @ are reserved for future extensions.
  45  */
  46
  47 static int keypin_journal_append_entry(const uint8_t *rsa_id_digest,
  48                                        const uint8_t *ed25519_id_key);
  49 static int keypin_check_and_add_impl(const uint8_t *rsa_id_digest,
  50                                      const uint8_t *ed25519_id_key,
  51                                      int do_not_add);
  52
  53 static HT_HEAD(rsamap, keypin_ent_st) the_rsa_map = HT_INITIALIZER();
  54 static HT_HEAD(edmap, keypin_ent_st) the_ed_map = HT_INITIALIZER();
  55
  56 /** Hashtable helper: compare two keypin table entries and return true iff
  57  * they have the same RSA key IDs. */
  58 static INLINE int
  59 keypin_ents_eq_rsa(const keypin_ent_t *a, const keypin_ent_t *b)
  60 {
  61   return tor_memeq(a->rsa_id, b->rsa_id, sizeof(a->rsa_id));
  62 }
  63
  64 /** Hashtable helper: hash a keypin table entries based on its RSA key ID */
  65 static INLINE unsigned
  66 keypin_ent_hash_rsa(const keypin_ent_t *a)
  67 {
  68 return (unsigned) siphash24g(a->rsa_id, sizeof(a->rsa_id));
  69 }
  70
  71 /** Hashtable helper: compare two keypin table entries and return true iff
  72  * they have the same ed25519 keys */
  73 static INLINE int
  74 keypin_ents_eq_ed(const keypin_ent_t *a, const keypin_ent_t *b)
  75 {
  76   return tor_memeq(a->ed25519_key, b->ed25519_key, sizeof(a->ed25519_key));
  77 }
  78
  79 /** Hashtable helper: hash a keypin table entries based on its ed25519 key */
  80 static INLINE unsigned
  81 keypin_ent_hash_ed(const keypin_ent_t *a)
  82 {
  83 return (unsigned) siphash24g(a->ed25519_key, sizeof(a->ed25519_key));
  84 }
  85
  86 HT_PROTOTYPE(rsamap, keypin_ent_st, rsamap_node, keypin_ent_hash_rsa,
  87                keypin_ents_eq_rsa);
  88 HT_GENERATE2(rsamap, keypin_ent_st, rsamap_node, keypin_ent_hash_rsa,
  89                keypin_ents_eq_rsa, 0.6, tor_reallocarray, tor_free_);
  90
  91 HT_PROTOTYPE(edmap, keypin_ent_st, edmap_node, keypin_ent_hash_ed,
  92                keypin_ents_eq_ed);
  93 HT_GENERATE2(edmap, keypin_ent_st, edmap_node, keypin_ent_hash_ed,
  94                keypin_ents_eq_ed, 0.6, tor_reallocarray, tor_free_);
  95
  96 /**
  97  * Check whether we already have an entry in the key pinning table for a
  98  * router with RSA ID digest <b>rsa_id_digest</b> or for ed25519 key
  99  * <b>ed25519_id_key</b>.  If we have an entry that matches both keys,
 100  * return KEYPIN_FOUND. If we find an entry that matches one key but
 101  * not the other, return KEYPIN_MISMATCH.  If we have no entry for either
 102  * key, add such an entry to the table and return KEYPIN_ADDED.
 103  */
 104 int
 105 keypin_check_and_add(const uint8_t *rsa_id_digest,
 106                      const uint8_t *ed25519_id_key)
 107 {
 108   return keypin_check_and_add_impl(rsa_id_digest, ed25519_id_key, 0);
 109 }
 110
 111 /**
 112  * As keypin_check_and_add, but do not add.  Return KEYPIN_NOT_FOUND if
 113  * we would add.
 114  */
 115 int
 116 keypin_check(const uint8_t *rsa_id_digest,
 117              const uint8_t *ed25519_id_key)
 118 {
 119   return keypin_check_and_add_impl(rsa_id_digest, ed25519_id_key, 1);
 120 }
 121
 122 /**
 123  * Helper: implements keypin_check and keypin_check_and_add.
 124  */
 125 static int
 126 keypin_check_and_add_impl(const uint8_t *rsa_id_digest,
 127                           const uint8_t *ed25519_id_key,
 128                           int do_not_add)
 129 {
 130   keypin_ent_t search, *ent;
 131   memset(&search, 0, sizeof(search));
 132   memcpy(search.rsa_id, rsa_id_digest, sizeof(search.rsa_id));
 133   memcpy(search.ed25519_key, ed25519_id_key, sizeof(search.ed25519_key));
 134
 135   /* Search by RSA key digest first */
 136   ent = HT_FIND(rsamap, &the_rsa_map, &search);
 137   if (ent) {
 138     tor_assert(fast_memeq(ent->rsa_id, rsa_id_digest, sizeof(ent->rsa_id)));
 139     if (tor_memeq(ent->ed25519_key, ed25519_id_key,sizeof(ent->ed25519_key))) {
 140       return KEYPIN_FOUND; /* Match on both keys. Great. */
 141     } else {
 142       return KEYPIN_MISMATCH; /* Found RSA with different Ed key */
 143     }
 144   }
 145
 146   /* See if we know a different RSA key for this ed key */
 147   ent = HT_FIND(edmap, &the_ed_map, &search);
 148   if (ent) {
 149     /* If we got here, then the ed key matches and the RSA doesn't */
 150     tor_assert(fast_memeq(ent->ed25519_key, ed25519_id_key,
 151                           sizeof(ent->ed25519_key)));
 152     tor_assert(fast_memneq(ent->rsa_id, rsa_id_digest, sizeof(ent->rsa_id)));
 153     return KEYPIN_MISMATCH;
 154   }
 155
 156   /* Okay, this one is new to us. */
 157   if (do_not_add)
 158     return KEYPIN_NOT_FOUND;
 159
 160   ent = tor_memdup(&search, sizeof(search));
 161   keypin_add_entry_to_map(ent);
 162   keypin_journal_append_entry(rsa_id_digest, ed25519_id_key);
 163   return KEYPIN_ADDED;
 164 }
 165
 166 /**
 167  * Helper: add <b>ent</b> to the hash tables.
 168  */
 169 MOCK_IMPL(STATIC void,
 170 keypin_add_entry_to_map, (keypin_ent_t *ent))
 171 {
 172   HT_INSERT(rsamap, &the_rsa_map, ent);
 173   HT_INSERT(edmap, &the_ed_map, ent);
 174 }
 175
 176 /**
 177  * Check whether we already have an entry in the key pinning table for a
 178  * router with RSA ID digest <b>rsa_id_digest</b>.  If we have no such entry,
 179  * return KEYPIN_NOT_FOUND.  If we find an entry that matches the RSA key but
 180  * which has an ed25519 key, return KEYPIN_MISMATCH.
 181  */
 182 int
 183 keypin_check_lone_rsa(const uint8_t *rsa_id_digest)
 184 {
 185   keypin_ent_t search, *ent;
 186   memset(&search, 0, sizeof(search));
 187   memcpy(search.rsa_id, rsa_id_digest, sizeof(search.rsa_id));
 188
 189   /* Search by RSA key digest first */
 190   ent = HT_FIND(rsamap, &the_rsa_map, &search);
 191   if (ent) {
 192     return KEYPIN_MISMATCH;
 193   } else {
 194     return KEYPIN_NOT_FOUND;
 195   }
 196 }
 197
 198 /** Open fd to the keypinning journal file. */
 199 static int keypin_journal_fd = -1;
 200
 201 /** Open the key-pinning journal to append to <b>fname</b>.  Return 0 on
 202  * success, -1 on failure. */
 203 int
 204 keypin_open_journal(const char *fname)
 205 {
 206   /* O_SYNC ??*/
 207   int fd = tor_open_cloexec(fname, O_WRONLY|O_CREAT|O_BINARY, 0600);
 208   if (fd < 0)
 209     goto err;
 210
 211   if (tor_fd_seekend(fd) < 0)
 212     goto err;
 213
 214   /* Add a newline in case the last line was only partially written */
 215   if (write(fd, "\n", 1) < 1)
 216     goto err;
 217
 218   /* Add something about when we opened this file. */
 219   char buf[80];
 220   char tbuf[ISO_TIME_LEN+1];
 221   format_iso_time(tbuf, approx_time());
 222   tor_snprintf(buf, sizeof(buf), "@opened-at %s\n", tbuf);
 223   if (write_all(fd, buf, strlen(buf), 0) < 0)
 224     goto err;
 225
 226   keypin_journal_fd = fd;
 227   return 0;
 228  err:
 229   if (fd >= 0)
 230     close(fd);
 231   return -1;
 232 }
 233
 234 /** Close the keypinning journal file. */
 235 int
 236 keypin_close_journal(void)
 237 {
 238   if (keypin_journal_fd >= 0)
 239     close(keypin_journal_fd);
 240   keypin_journal_fd = -1;
 241   return 0;
 242 }
 243
 244 /** Length of a keypinning journal line, including terminating newline. */
 245 #define JOURNAL_LINE_LEN (BASE64_DIGEST_LEN + BASE64_DIGEST256_LEN + 2)
 246
 247 /** Add an entry to the keypinning journal to map <b>rsa_id_digest</b> and
 248  * <b>ed25519_id_key</b>. */
 249 static int
 250 keypin_journal_append_entry(const uint8_t *rsa_id_digest,
 251                             const uint8_t *ed25519_id_key)
 252 {
 253   if (keypin_journal_fd == -1)
 254     return -1;
 255   char line[JOURNAL_LINE_LEN];
 256   digest_to_base64(line, (const char*)rsa_id_digest);
 257   line[BASE64_DIGEST_LEN] = ' ';
 258   digest256_to_base64(line + BASE64_DIGEST_LEN + 1,
 259                       (const char*)ed25519_id_key);
 260   line[BASE64_DIGEST_LEN+1+BASE64_DIGEST256_LEN] = '\n';
 261
 262   if (write_all(keypin_journal_fd, line, JOURNAL_LINE_LEN, 0)<0) {
 263     log_warn(LD_DIRSERV, "Error while adding a line to the key-pinning "
 264              "journal: %s", strerror(errno));
 265     keypin_close_journal();
 266     return -1;
 267   }
 268
 269   return 0;
 270 }
 271
 272 /** Load a journal from the <b>size</b>-byte region at <b>data</b>.  Return 0
 273  * on success, -1 on failure. */
 274 STATIC int
 275 keypin_load_journal_impl(const char *data, size_t size)
 276 {
 277   const char *start = data, *end = data + size, *next;
 278
 279   int n_corrupt_lines = 0;
 280   int n_entries = 0;
 281   int n_duplicates = 0;
 282   int n_conflicts = 0;
 283
 284   for (const char *cp = start; cp < end; cp = next) {
 285     const char *eol = memchr(cp, '\n', end-cp);
 286     const char *eos = eol ? eol : end;
 287     const size_t len = eos - cp;
 288
 289     next = eol ? eol + 1 : end;
 290
 291     if (len == 0) {
 292       continue;
 293     }
 294
 295     if (*cp == '@') {
 296       /* Lines that start with @ are reserved. Ignore for now. */
 297       continue;
 298     }
 299     if (*cp == '#') {
 300       /* Lines that start with # are comments. */
 301       continue;
 302     }
 303
 304     /* Is it the right length?  (The -1 here is for the newline.) */
 305     if (len != JOURNAL_LINE_LEN - 1) {
 306       /* Lines with a bad length are corrupt unless they are empty.
 307        * Ignore them either way */
 308       for (const char *s = cp; s < eos; ++s) {
 309         if (! TOR_ISSPACE(*s)) {
 310           ++n_corrupt_lines;
 311           break;
 312         }
 313       }
 314       continue;
 315     }
 316
 317     keypin_ent_t *ent = keypin_parse_journal_line(cp);
 318
 319     if (ent == NULL) {
 320       ++n_corrupt_lines;
 321       continue;
 322     }
 323
 324     keypin_ent_t *ent2 = HT_FIND(rsamap, &the_rsa_map, ent);
 325     keypin_ent_t *ent3 = HT_FIND(edmap, &the_ed_map, ent);
 326     if (ent2 &&
 327         fast_memeq(ent2->ed25519_key, ent->ed25519_key, DIGEST256_LEN)) {
 328       /* We already have this mapping stored. Ignore it. */
 329       tor_free(ent);
 330       ++n_duplicates;
 331       continue;
 332     } else if (ent2 || ent3) {
 333       /* We have a conflict. (If we had no entry, we would have ent2 == ent3
 334        * == NULL. If we had a non-conflicting duplicate, we would have found
 335        * it above.)
 336        *
 337        * We respond by having this entry (ent) supersede all entries that it
 338        * contradicts (ent2 and/or ent3). In other words, if we receive
 339        * <rsa,ed>, we remove all <rsa,ed'> and all <rsa',ed>, for rsa'!=rsa
 340        * and ed'!= ed.
 341        */
 342       const keypin_ent_t *t;
 343       if (ent2) {
 344         t = HT_REMOVE(rsamap, &the_rsa_map, ent2);
 345         tor_assert(ent2 == t);
 346         t = HT_REMOVE(edmap, &the_ed_map, ent2);
 347         tor_assert(ent2 == t);
 348       }
 349       if (ent3 && ent2 != ent3) {
 350         t = HT_REMOVE(rsamap, &the_rsa_map, ent3);
 351         tor_assert(ent3 == t);
 352         t = HT_REMOVE(edmap, &the_ed_map, ent3);
 353         tor_assert(ent3 == t);
 354         tor_free(ent3);
 355       }
 356       tor_free(ent2);
 357       ++n_conflicts;
 358       /* Fall through */
 359     }
 360
 361     keypin_add_entry_to_map(ent);
 362     ++n_entries;
 363   }
 364
 365   int severity = (n_corrupt_lines || n_duplicates) ? LOG_WARN : LOG_INFO;
 366   tor_log(severity, LD_DIRSERV,
 367           "Loaded %d entries from keypin journal. "
 368           "Found %d corrupt lines, %d duplicates, and %d conflicts.",
 369           n_entries, n_corrupt_lines, n_duplicates, n_conflicts);
 370
 371   return 0;
 372 }
 373
 374 /**
 375  * Load a journal from the file called <b>fname</b>. Return 0 on success,
 376  * -1 on failure.
 377  */
 378 int
 379 keypin_load_journal(const char *fname)
 380 {
 381   tor_mmap_t *map = tor_mmap_file(fname);
 382   if (!map) {
 383     if (errno == ENOENT)
 384       return 0;
 385     else
 386       return -1;
 387   }
 388   int r = keypin_load_journal_impl(map->data, map->size);
 389   tor_munmap_file(map);
 390   return r;
 391 }
 392
 393 /** Parse a single keypinning journal line entry from <b>cp</b>.  The input
 394  * does not need to be NUL-terminated, but it <em>does</em> need to have
 395  * KEYPIN_JOURNAL_LINE_LEN -1 bytes available to read.  Return a new entry
 396  * on success, and NULL on failure.
 397  */
 398 STATIC keypin_ent_t *
 399 keypin_parse_journal_line(const char *cp)
 400 {
 401   /* XXXX assumes !USE_OPENSSL_BASE64 */
 402   keypin_ent_t *ent = tor_malloc_zero(sizeof(keypin_ent_t));
 403
 404   if (base64_decode((char*)ent->rsa_id, sizeof(ent->rsa_id),
 405              cp, BASE64_DIGEST_LEN) != DIGEST_LEN ||
 406       cp[BASE64_DIGEST_LEN] != ' ' ||
 407       base64_decode((char*)ent->ed25519_key, sizeof(ent->ed25519_key),
 408              cp+BASE64_DIGEST_LEN+1, BASE64_DIGEST256_LEN) != DIGEST256_LEN) {
 409     tor_free(ent);
 410     return NULL;
 411   } else {
 412     return ent;
 413   }
 414 }
 415
 416 /** Remove all entries from the keypinning table.*/
 417 void
 418 keypin_clear(void)
 419 {
 420   int bad_entries = 0;
 421   {
 422     keypin_ent_t **ent, **next, *this;
 423     for (ent = HT_START(rsamap, &the_rsa_map); ent != NULL; ent = next) {
 424       this = *ent;
 425       next = HT_NEXT_RMV(rsamap, &the_rsa_map, ent);
 426
 427       keypin_ent_t *other_ent = HT_REMOVE(edmap, &the_ed_map, this);
 428       bad_entries += (other_ent != this);
 429
 430       tor_free(this);
 431     }
 432   }
 433   bad_entries += HT_SIZE(&the_ed_map);
 434
 435   HT_CLEAR(edmap,&the_ed_map);
 436   HT_CLEAR(rsamap,&the_rsa_map);
 437
 438   if (bad_entries) {
 439     log_warn(LD_BUG, "Found %d discrepencies in the the keypin database.",
 440              bad_entries);
 441   }
 442 }
 443