Tor  0.4.4.0-alpha-dev
keypin.c
Go to the documentation of this file.
1 /* Copyright (c) 2014-2020, The Tor Project, Inc. */
2 /* See LICENSE for licensing information */
3 
4 /**
5  * \file keypin.c
6  *
7  * \brief Functions and structures for associating routers' RSA key
8  * fingerprints with their ED25519 keys.
9  */
10 
11 #define KEYPIN_PRIVATE
12 
13 #include "orconfig.h"
14 
15 #include "lib/cc/torint.h"
18 #include "lib/ctime/di_ops.h"
19 #include "lib/encoding/binascii.h"
20 #include "lib/encoding/time_fmt.h"
21 #include "lib/fdio/fdio.h"
22 #include "lib/fs/files.h"
23 #include "lib/fs/mmap.h"
24 #include "lib/log/log.h"
25 #include "lib/log/util_bug.h"
27 #include "lib/string/printf.h"
29 
30 #include "ht.h"
31 #include "feature/dirauth/keypin.h"
32 
33 #include "siphash.h"
34 
35 #ifdef HAVE_UNISTD_H
36 #include <unistd.h>
37 #endif
38 #ifdef HAVE_FCNTL_H
39 #include <fcntl.h>
40 #endif
41 
42 #ifdef _WIN32
43 #include <io.h>
44 #endif
45 
46 #include <errno.h>
47 #include <string.h>
48 #include <stdlib.h>
49 
50 /**
51  * @file keypin.c
52  * @brief Key-pinning for RSA and Ed25519 identity keys at directory
53  * authorities.
54  *
55  * Many older clients, and many internal interfaces, still refer to relays by
56  * their RSA1024 identity keys. We can make this more secure, however:
57  * authorities use this module to track which RSA keys have been used along
58  * with which Ed25519 keys, and force such associations to be permanent.
59  *
60  * This module implements a key-pinning mechanism to ensure that it's safe
61  * to use RSA keys as identitifers even as we migrate to Ed25519 keys. It
62  * remembers, for every Ed25519 key we've seen, what the associated Ed25519
63  * key is. This way, if we see a different Ed25519 key with that RSA key,
64  * we'll know that there's a mismatch.
65  *
66  * (As of this writing, these key associations are advisory only, mostly
67  * because some relay operators kept mishandling their Ed25519 keys during
68  * the initial Ed25519 rollout. We should fix this problem, and then toggle
69  * the AuthDirPinKeys option.)
70  *
71  * We persist these entries to disk using a simple format, where each line
72  * has a base64-encoded RSA SHA1 hash, then a base64-endoded Ed25519 key.
73  * Empty lines, misformed lines, and lines beginning with # are
74  * ignored. Lines beginning with @ are reserved for future extensions.
75  *
76  * The dirserv.c module is the main user of these functions.
77  */
78 
79 static int keypin_journal_append_entry(const uint8_t *rsa_id_digest,
80  const uint8_t *ed25519_id_key);
81 static int keypin_check_and_add_impl(const uint8_t *rsa_id_digest,
82  const uint8_t *ed25519_id_key,
83  const int do_not_add,
84  const int replace);
85 static int keypin_add_or_replace_entry_in_map(keypin_ent_t *ent);
86 
87 static HT_HEAD(rsamap, keypin_ent_st) the_rsa_map = HT_INITIALIZER();
88 static HT_HEAD(edmap, keypin_ent_st) the_ed_map = HT_INITIALIZER();
89 
90 /** Hashtable helper: compare two keypin table entries and return true iff
91  * they have the same RSA key IDs. */
92 static inline int
93 keypin_ents_eq_rsa(const keypin_ent_t *a, const keypin_ent_t *b)
94 {
95  return tor_memeq(a->rsa_id, b->rsa_id, sizeof(a->rsa_id));
96 }
97 
98 /** Hashtable helper: hash a keypin table entries based on its RSA key ID */
99 static inline unsigned
100 keypin_ent_hash_rsa(const keypin_ent_t *a)
101 {
102 return (unsigned) siphash24g(a->rsa_id, sizeof(a->rsa_id));
103 }
104 
105 /** Hashtable helper: compare two keypin table entries and return true iff
106  * they have the same ed25519 keys */
107 static inline int
108 keypin_ents_eq_ed(const keypin_ent_t *a, const keypin_ent_t *b)
109 {
110  return tor_memeq(a->ed25519_key, b->ed25519_key, sizeof(a->ed25519_key));
111 }
112 
113 /** Hashtable helper: hash a keypin table entries based on its ed25519 key */
114 static inline unsigned
115 keypin_ent_hash_ed(const keypin_ent_t *a)
116 {
117 return (unsigned) siphash24g(a->ed25519_key, sizeof(a->ed25519_key));
118 }
119 
120 HT_PROTOTYPE(rsamap, keypin_ent_st, rsamap_node, keypin_ent_hash_rsa,
121  keypin_ents_eq_rsa)
122 HT_GENERATE2(rsamap, keypin_ent_st, rsamap_node, keypin_ent_hash_rsa,
123  keypin_ents_eq_rsa, 0.6, tor_reallocarray, tor_free_)
124 
125 HT_PROTOTYPE(edmap, keypin_ent_st, edmap_node, keypin_ent_hash_ed,
127 HT_GENERATE2(edmap, keypin_ent_st, edmap_node, keypin_ent_hash_ed,
128  keypin_ents_eq_ed, 0.6, tor_reallocarray, tor_free_)
129 
130 /**
131  * Check whether we already have an entry in the key pinning table for a
132  * router with RSA ID digest <b>rsa_id_digest</b> or for ed25519 key
133  * <b>ed25519_id_key</b>. If we have an entry that matches both keys,
134  * return KEYPIN_FOUND. If we find an entry that matches one key but
135  * not the other, return KEYPIN_MISMATCH. If we have no entry for either
136  * key, add such an entry to the table and return KEYPIN_ADDED.
137  *
138  * If <b>replace_existing_entry</b> is true, then any time we would have said
139  * KEYPIN_FOUND, we instead add this entry anyway and return KEYPIN_ADDED.
140  */
141 int
142 keypin_check_and_add(const uint8_t *rsa_id_digest,
143  const uint8_t *ed25519_id_key,
144  const int replace_existing_entry)
145 {
146  return keypin_check_and_add_impl(rsa_id_digest, ed25519_id_key, 0,
147  replace_existing_entry);
148 }
149 
150 /**
151  * As keypin_check_and_add, but do not add. Return KEYPIN_NOT_FOUND if
152  * we would add.
153  */
154 int
155 keypin_check(const uint8_t *rsa_id_digest,
156  const uint8_t *ed25519_id_key)
157 {
158  return keypin_check_and_add_impl(rsa_id_digest, ed25519_id_key, 1, 0);
159 }
160 
161 /**
162  * Helper: implements keypin_check and keypin_check_and_add.
163  */
164 static int
165 keypin_check_and_add_impl(const uint8_t *rsa_id_digest,
166  const uint8_t *ed25519_id_key,
167  const int do_not_add,
168  const int replace)
169 {
170  keypin_ent_t search, *ent;
171  memset(&search, 0, sizeof(search));
172  memcpy(search.rsa_id, rsa_id_digest, sizeof(search.rsa_id));
173  memcpy(search.ed25519_key, ed25519_id_key, sizeof(search.ed25519_key));
174 
175  /* Search by RSA key digest first */
176  ent = HT_FIND(rsamap, &the_rsa_map, &search);
177  if (ent) {
178  tor_assert(fast_memeq(ent->rsa_id, rsa_id_digest, sizeof(ent->rsa_id)));
179  if (tor_memeq(ent->ed25519_key, ed25519_id_key,sizeof(ent->ed25519_key))) {
180  return KEYPIN_FOUND; /* Match on both keys. Great. */
181  } else {
182  if (!replace)
183  return KEYPIN_MISMATCH; /* Found RSA with different Ed key */
184  }
185  }
186 
187  /* See if we know a different RSA key for this ed key */
188  if (! replace) {
189  ent = HT_FIND(edmap, &the_ed_map, &search);
190  if (ent) {
191  /* If we got here, then the ed key matches and the RSA doesn't */
192  tor_assert(fast_memeq(ent->ed25519_key, ed25519_id_key,
193  sizeof(ent->ed25519_key)));
194  tor_assert(fast_memneq(ent->rsa_id, rsa_id_digest, sizeof(ent->rsa_id)));
195  return KEYPIN_MISMATCH;
196  }
197  }
198 
199  /* Okay, this one is new to us. */
200  if (do_not_add)
201  return KEYPIN_NOT_FOUND;
202 
203  ent = tor_memdup(&search, sizeof(search));
205  if (! replace) {
206  tor_assert(r == 1);
207  } else {
208  tor_assert(r != 0);
209  }
210  keypin_journal_append_entry(rsa_id_digest, ed25519_id_key);
211  return KEYPIN_ADDED;
212 }
213 
214 /**
215  * Helper: add <b>ent</b> to the hash tables.
216  */
217 MOCK_IMPL(STATIC void,
218 keypin_add_entry_to_map, (keypin_ent_t *ent))
219 {
220  HT_INSERT(rsamap, &the_rsa_map, ent);
221  HT_INSERT(edmap, &the_ed_map, ent);
222 }
223 
224 /**
225  * Helper: add 'ent' to the maps, replacing any entries that contradict it.
226  * Take ownership of 'ent', freeing it if needed.
227  *
228  * Return 0 if the entry was a duplicate, -1 if there was a conflict,
229  * and 1 if there was no conflict.
230  */
231 static int
233 {
234  int r = 1;
235  keypin_ent_t *ent2 = HT_FIND(rsamap, &the_rsa_map, ent);
236  keypin_ent_t *ent3 = HT_FIND(edmap, &the_ed_map, ent);
237  if (ent2 &&
238  fast_memeq(ent2->ed25519_key, ent->ed25519_key, DIGEST256_LEN)) {
239  /* We already have this mapping stored. Ignore it. */
240  tor_free(ent);
241  return 0;
242  } else if (ent2 || ent3) {
243  /* We have a conflict. (If we had no entry, we would have ent2 == ent3
244  * == NULL. If we had a non-conflicting duplicate, we would have found
245  * it above.)
246  *
247  * We respond by having this entry (ent) supersede all entries that it
248  * contradicts (ent2 and/or ent3). In other words, if we receive
249  * <rsa,ed>, we remove all <rsa,ed'> and all <rsa',ed>, for rsa'!=rsa
250  * and ed'!= ed.
251  */
252  const keypin_ent_t *t;
253  if (ent2) {
254  t = HT_REMOVE(rsamap, &the_rsa_map, ent2);
255  tor_assert(ent2 == t);
256  t = HT_REMOVE(edmap, &the_ed_map, ent2);
257  tor_assert(ent2 == t);
258  }
259  if (ent3 && ent2 != ent3) {
260  t = HT_REMOVE(rsamap, &the_rsa_map, ent3);
261  tor_assert(ent3 == t);
262  t = HT_REMOVE(edmap, &the_ed_map, ent3);
263  tor_assert(ent3 == t);
264  tor_free(ent3);
265  }
266  tor_free(ent2);
267  r = -1;
268  /* Fall through */
269  }
270 
272  return r;
273 }
274 
275 /**
276  * Check whether we already have an entry in the key pinning table for a
277  * router with RSA ID digest <b>rsa_id_digest</b>. If we have no such entry,
278  * return KEYPIN_NOT_FOUND. If we find an entry that matches the RSA key but
279  * which has an ed25519 key, return KEYPIN_MISMATCH.
280  */
281 int
282 keypin_check_lone_rsa(const uint8_t *rsa_id_digest)
283 {
284  keypin_ent_t search, *ent;
285  memset(&search, 0, sizeof(search));
286  memcpy(search.rsa_id, rsa_id_digest, sizeof(search.rsa_id));
287 
288  /* Search by RSA key digest first */
289  ent = HT_FIND(rsamap, &the_rsa_map, &search);
290  if (ent) {
291  return KEYPIN_MISMATCH;
292  } else {
293  return KEYPIN_NOT_FOUND;
294  }
295 }
296 
297 /** Open fd to the keypinning journal file. */
298 static int keypin_journal_fd = -1;
299 
300 /** Open the key-pinning journal to append to <b>fname</b>. Return 0 on
301  * success, -1 on failure. */
302 int
303 keypin_open_journal(const char *fname)
304 {
305 #ifndef O_SYNC
306 #define O_SYNC 0
307 #endif
308  int fd = tor_open_cloexec(fname, O_WRONLY|O_CREAT|O_BINARY|O_SYNC, 0600);
309  if (fd < 0)
310  goto err;
311 
312  if (tor_fd_seekend(fd) < 0)
313  goto err;
314 
315  /* Add a newline in case the last line was only partially written */
316  if (write(fd, "\n", 1) < 1)
317  goto err;
318 
319  /* Add something about when we opened this file. */
320  char buf[80];
321  char tbuf[ISO_TIME_LEN+1];
322  format_iso_time(tbuf, approx_time());
323  tor_snprintf(buf, sizeof(buf), "@opened-at %s\n", tbuf);
324  if (write_all_to_fd(fd, buf, strlen(buf)) < 0)
325  goto err;
326 
327  keypin_journal_fd = fd;
328  return 0;
329  err:
330  if (fd >= 0)
331  close(fd);
332  return -1;
333 }
334 
335 /** Close the keypinning journal file. */
336 int
338 {
339  if (keypin_journal_fd >= 0)
340  close(keypin_journal_fd);
341  keypin_journal_fd = -1;
342  return 0;
343 }
344 
345 /** Length of a keypinning journal line, including terminating newline. */
346 #define JOURNAL_LINE_LEN (BASE64_DIGEST_LEN + BASE64_DIGEST256_LEN + 2)
347 
348 /** Add an entry to the keypinning journal to map <b>rsa_id_digest</b> and
349  * <b>ed25519_id_key</b>. */
350 static int
351 keypin_journal_append_entry(const uint8_t *rsa_id_digest,
352  const uint8_t *ed25519_id_key)
353 {
354  if (keypin_journal_fd == -1)
355  return -1;
356  char line[JOURNAL_LINE_LEN];
357  digest_to_base64(line, (const char*)rsa_id_digest);
358  line[BASE64_DIGEST_LEN] = ' ';
360  (const char*)ed25519_id_key);
362 
364  log_warn(LD_DIRSERV, "Error while adding a line to the key-pinning "
365  "journal: %s", strerror(errno));
367  return -1;
368  }
369 
370  return 0;
371 }
372 
373 /** Load a journal from the <b>size</b>-byte region at <b>data</b>. Return 0
374  * on success, -1 on failure. */
375 STATIC int
376 keypin_load_journal_impl(const char *data, size_t size)
377 {
378  const char *start = data, *end = data + size, *next;
379 
380  int n_corrupt_lines = 0;
381  int n_entries = 0;
382  int n_duplicates = 0;
383  int n_conflicts = 0;
384 
385  for (const char *cp = start; cp < end; cp = next) {
386  const char *eol = memchr(cp, '\n', end-cp);
387  const char *eos = eol ? eol : end;
388  const size_t len = eos - cp;
389 
390  next = eol ? eol + 1 : end;
391 
392  if (len == 0) {
393  continue;
394  }
395 
396  if (*cp == '@') {
397  /* Lines that start with @ are reserved. Ignore for now. */
398  continue;
399  }
400  if (*cp == '#') {
401  /* Lines that start with # are comments. */
402  continue;
403  }
404 
405  /* Is it the right length? (The -1 here is for the newline.) */
406  if (len != JOURNAL_LINE_LEN - 1) {
407  /* Lines with a bad length are corrupt unless they are empty.
408  * Ignore them either way */
409  for (const char *s = cp; s < eos; ++s) {
410  if (! TOR_ISSPACE(*s)) {
411  ++n_corrupt_lines;
412  break;
413  }
414  }
415  continue;
416  }
417 
418  keypin_ent_t *ent = keypin_parse_journal_line(cp);
419 
420  if (ent == NULL) {
421  ++n_corrupt_lines;
422  continue;
423  }
424 
425  const int r = keypin_add_or_replace_entry_in_map(ent);
426  if (r == 0) {
427  ++n_duplicates;
428  } else if (r == -1) {
429  ++n_conflicts;
430  }
431 
432  ++n_entries;
433  }
434 
435  int severity = (n_corrupt_lines || n_duplicates) ? LOG_NOTICE : LOG_INFO;
436  tor_log(severity, LD_DIRSERV,
437  "Loaded %d entries from keypin journal. "
438  "Found %d corrupt lines (ignored), %d duplicates (harmless), "
439  "and %d conflicts (resolved in favor of more recent entry).",
440  n_entries, n_corrupt_lines, n_duplicates, n_conflicts);
441 
442  return 0;
443 }
444 
445 /**
446  * Load a journal from the file called <b>fname</b>. Return 0 on success,
447  * -1 on failure.
448  */
449 int
450 keypin_load_journal(const char *fname)
451 {
452  tor_mmap_t *map = tor_mmap_file(fname);
453  if (!map) {
454  if (errno == ENOENT)
455  return 0;
456  else
457  return -1;
458  }
459  int r = keypin_load_journal_impl(map->data, map->size);
460  tor_munmap_file(map);
461  return r;
462 }
463 
464 /** Parse a single keypinning journal line entry from <b>cp</b>. The input
465  * does not need to be NUL-terminated, but it <em>does</em> need to have
466  * KEYPIN_JOURNAL_LINE_LEN -1 bytes available to read. Return a new entry
467  * on success, and NULL on failure.
468  */
469 STATIC keypin_ent_t *
471 {
472  /* XXXX assumes !USE_OPENSSL_BASE64 */
473  keypin_ent_t *ent = tor_malloc_zero(sizeof(keypin_ent_t));
474 
475  if (base64_decode((char*)ent->rsa_id, sizeof(ent->rsa_id),
476  cp, BASE64_DIGEST_LEN) != DIGEST_LEN ||
477  cp[BASE64_DIGEST_LEN] != ' ' ||
478  base64_decode((char*)ent->ed25519_key, sizeof(ent->ed25519_key),
480  tor_free(ent);
481  return NULL;
482  } else {
483  return ent;
484  }
485 }
486 
487 /** Remove all entries from the keypinning table.*/
488 void
490 {
491  int bad_entries = 0;
492  {
493  keypin_ent_t **ent, **next, *this;
494  for (ent = HT_START(rsamap, &the_rsa_map); ent != NULL; ent = next) {
495  this = *ent;
496  next = HT_NEXT_RMV(rsamap, &the_rsa_map, ent);
497 
498  keypin_ent_t *other_ent = HT_REMOVE(edmap, &the_ed_map, this);
499  bad_entries += (other_ent != this);
500 
501  tor_free(this);
502  }
503  }
504  bad_entries += HT_SIZE(&the_ed_map);
505 
506  HT_CLEAR(edmap,&the_ed_map);
507  HT_CLEAR(rsamap,&the_rsa_map);
508 
509  if (bad_entries) {
510  log_warn(LD_BUG, "Found %d discrepencies in the keypin database.",
511  bad_entries);
512  }
513 }
static int keypin_add_or_replace_entry_in_map(keypin_ent_t *ent)
Definition: keypin.c:232
static int keypin_journal_append_entry(const uint8_t *rsa_id_digest, const uint8_t *ed25519_id_key)
Definition: keypin.c:351
Header for printf.c.
int tor_open_cloexec(const char *path, int flags, unsigned mode)
Definition: files.c:54
Headers for di_ops.c.
#define MOCK_IMPL(rv, funcname, arglist)
Definition: testsupport.h:133
int tor_fd_seekend(int fd)
Definition: fdio.c:61
static int keypin_check_and_add_impl(const uint8_t *rsa_id_digest, const uint8_t *ed25519_id_key, const int do_not_add, const int replace)
Definition: keypin.c:165
#define LOG_INFO
Definition: log.h:45
static unsigned keypin_ent_hash_ed(const keypin_ent_t *a)
Definition: keypin.c:115
Header for fdio.c.
void tor_log(int severity, log_domain_mask_t domain, const char *format,...)
Definition: log.c:628
ssize_t write_all_to_fd(int fd, const char *buf, size_t count)
Definition: files.c:162
STATIC int keypin_load_journal_impl(const char *data, size_t size)
Definition: keypin.c:376
static unsigned keypin_ent_hash_rsa(const keypin_ent_t *a)
Definition: keypin.c:100
void digest_to_base64(char *d64, const char *digest)
#define tor_assert(expr)
Definition: util_bug.h:102
Header for mmap.c.
Header for keypin.c.
static int keypin_journal_fd
Definition: keypin.c:298
Header for time_fmt.c.
#define tor_free(p)
Definition: malloc.h:52
void keypin_clear(void)
Definition: keypin.c:489
#define LOG_NOTICE
Definition: log.h:50
Integer definitions used throughout Tor.
int keypin_check(const uint8_t *rsa_id_digest, const uint8_t *ed25519_id_key)
Definition: keypin.c:155
#define STATIC
Definition: testsupport.h:32
int keypin_load_journal(const char *fname)
Definition: keypin.c:450
#define DIGEST256_LEN
Definition: digest_sizes.h:23
STATIC void keypin_add_entry_to_map(keypin_ent_t *ent)
Definition: keypin.c:218
Header for crypto_format.c.
int tor_memeq(const void *a, const void *b, size_t sz)
Definition: di_ops.c:107
int keypin_close_journal(void)
Definition: keypin.c:337
STATIC keypin_ent_t * keypin_parse_journal_line(const char *cp)
Definition: keypin.c:470
#define DIGEST_LEN
Definition: digest_sizes.h:20
#define LD_DIRSERV
Definition: log.h:90
HT_GENERATE2(cdm_diff_ht, cdm_diff_t, node, cdm_diff_hash, cdm_diff_eq, 0.6, tor_reallocarray, tor_free_) static void cdm_diff_free_(cdm_diff_t *diff)
Definition: consdiffmgr.c:222
int keypin_open_journal(const char *fname)
Definition: keypin.c:303
#define fast_memneq(a, b, c)
Definition: di_ops.h:42
const char * data
Definition: mmap.h:26
Header for binascii.c.
Header for approx_time.c.
void tor_free_(void *mem)
Definition: malloc.c:227
void digest256_to_base64(char *d64, const char *digest)
Headers for crypto_digest.c.
int tor_snprintf(char *str, size_t size, const char *format,...)
Definition: printf.c:27
void format_iso_time(char *buf, time_t t)
Definition: time_fmt.c:295
int keypin_check_lone_rsa(const uint8_t *rsa_id_digest)
Definition: keypin.c:282
int base64_decode(char *dest, size_t destlen, const char *src, size_t srclen)
Definition: binascii.c:396
HT_PROTOTYPE(HT_GENERATE2(channel_gid_map, HT_GENERATE2(channel_t, HT_GENERATE2(gidmap_node, HT_GENERATE2(channel_id_hash, HT_GENERATE2(channel_id_eq)
Definition: channel.c:121
Locale-independent character-type inspection (header)
typedef HT_HEAD(hs_service_ht, hs_service_t) hs_service_ht
#define BASE64_DIGEST_LEN
Definition: crypto_digest.h:26
Wrappers for reading and writing data to files on disk.
time_t approx_time(void)
Definition: approx_time.c:32
#define BASE64_DIGEST256_LEN
Definition: crypto_digest.h:29
#define JOURNAL_LINE_LEN
Definition: keypin.c:346
size_t size
Definition: mmap.h:27
static int keypin_ents_eq_ed(const keypin_ent_t *a, const keypin_ent_t *b)
Definition: keypin.c:108
Headers for log.c.
Macros to manage assertions, fatal and non-fatal.
#define LD_BUG
Definition: log.h:86
#define fast_memeq(a, b, c)
Definition: di_ops.h:35