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