keypin.c 15 KB

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