keypin.c 15 KB

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