From 55a78da4e0b496fc599704473f41d5ea52669737 Mon Sep 17 00:00:00 2001 From: Etienne Dechamps Date: Sun, 21 Sep 2014 18:17:02 +0100 Subject: [PATCH] Introduce node IDs. This introduces a new type of identifier for nodes, which complements node names: node IDs. Node IDs are defined as the first 6 bytes of the SHA-256 hash of the node name. They will be used in future code in lieu of node names as unique node identifiers in contexts where space is at a premium (such as VPN packets). The semantics of node IDs is that they are supposed to be unique in a tinc graph; i.e. two different nodes that are part of the same graph should not have the same ID, otherwise things could break. This solution provides this guarantee based on realistic probabilities: indeed, according to the birthday problem, with a 48-bit hash, the probability of at least one collision is 1e-13 with 10 nodes, 1e-11 with 100 nodes, 1e-9 with 1000 nodes and 1e-7 with 10000 nodes. Things only start getting hairy with more than 1 million nodes, as the probability gets over 0.2%. --- src/info.c | 6 ++++-- src/net.h | 4 ++++ src/node.c | 36 +++++++++++++++++++++++++++++++++--- src/node.h | 2 ++ src/tincctl.c | 9 +++++---- 5 files changed, 48 insertions(+), 9 deletions(-) diff --git a/src/info.c b/src/info.c index c9b00946..b9a6fcf9 100644 --- a/src/info.c +++ b/src/info.c @@ -50,6 +50,7 @@ static int info_node(int fd, const char *item) { char line[4096]; char node[4096]; + char id[4096]; char from[4096]; char to[4096]; char subnet[4096]; @@ -68,12 +69,12 @@ static int info_node(int fd, const char *item) { long int last_state_change; while(recvline(fd, line, sizeof line)) { - int n = sscanf(line, "%d %d %s %s port %s %d %d %d %d %x %"PRIx32" %s %s %d %hd %hd %hd %ld", &code, &req, node, host, port, &cipher, &digest, &maclength, &compression, &options, &status_union.raw, nexthop, via, &distance, &pmtu, &minmtu, &maxmtu, &last_state_change); + int n = sscanf(line, "%d %d %s %s %s port %s %d %d %d %d %x %"PRIx32" %s %s %d %hd %hd %hd %ld", &code, &req, node, id, host, port, &cipher, &digest, &maclength, &compression, &options, &status_union.raw, nexthop, via, &distance, &pmtu, &minmtu, &maxmtu, &last_state_change); if(n == 2) break; - if(n != 18) { + if(n != 19) { fprintf(stderr, "Unable to parse node dump from tincd.\n"); return 1; } @@ -95,6 +96,7 @@ static int info_node(int fd, const char *item) { } printf("Node: %s\n", item); + printf("Node ID: %s\n", id); printf("Address: %s port %s\n", host, port); char timestr[32] = "never"; diff --git a/src/net.h b/src/net.h index d8aa64cd..6e575d45 100644 --- a/src/net.h +++ b/src/net.h @@ -52,6 +52,10 @@ typedef struct ipv6_t { uint16_t x[8]; } ipv6_t; +typedef struct node_id_t { + uint8_t x[6]; +} node_id_t; + typedef short length_t; #define AF_UNKNOWN 255 diff --git a/src/node.c b/src/node.c index 0cb24454..80da6769 100644 --- a/src/node.c +++ b/src/node.c @@ -30,7 +30,10 @@ #include "utils.h" #include "xalloc.h" +static digest_t *sha256; + splay_tree_t *node_tree; +static splay_tree_t *node_id_tree; static hash_t *node_udp_cache; node_t *myself; @@ -39,14 +42,24 @@ static int node_compare(const node_t *a, const node_t *b) { return strcmp(a->name, b->name); } +static int node_id_compare(const node_t *a, const node_t *b) { + return memcmp(&a->id, &b->id, sizeof(node_id_t)); +} + void init_nodes(void) { + sha256 = digest_open_by_name("sha256", sizeof(node_id_t)); + node_tree = splay_alloc_tree((splay_compare_t) node_compare, (splay_action_t) free_node); + node_id_tree = splay_alloc_tree((splay_compare_t) node_id_compare, NULL); node_udp_cache = hash_alloc(0x100, sizeof(sockaddr_t)); } void exit_nodes(void) { hash_free(node_udp_cache); + splay_delete_tree(node_id_tree); splay_delete_tree(node_tree); + + digest_close(sha256); } node_t *new_node(void) { @@ -93,7 +106,10 @@ void free_node(node_t *n) { } void node_add(node_t *n) { + digest_create(sha256, n->name, strlen(n->name), &n->id); + splay_insert(node_tree, n); + splay_insert(node_id_tree, n); } void node_del(node_t *n) { @@ -103,6 +119,7 @@ void node_del(node_t *n) { for splay_each(edge_t, e, n->edge_tree) edge_del(e); + splay_delete(node_id_tree, n); splay_delete(node_tree, n); } @@ -114,6 +131,14 @@ node_t *lookup_node(char *name) { return splay_search(node_tree, &n); } +node_t *lookup_node_id(const node_id_t *id) { + node_t n = {NULL}; + + n.id = *id; + + return splay_search(node_id_tree, &n); +} + node_t *lookup_node_udp(const sockaddr_t *sa) { return hash_search(node_udp_cache, sa); } @@ -150,12 +175,17 @@ void update_node_udp(node_t *n, const sockaddr_t *sa) { } bool dump_nodes(connection_t *c) { - for splay_each(node_t, n, node_tree) - send_request(c, "%d %d %s %s %d %d %d %d %x %x %s %s %d %hd %hd %hd %ld", CONTROL, REQ_DUMP_NODES, - n->name, n->hostname ?: "unknown port unknown", cipher_get_nid(n->outcipher), + for splay_each(node_t, n, node_tree) { + char id[2 * sizeof n->id + 1]; + for (size_t c = 0; c < sizeof n->id; ++c) + sprintf(id + 2 * c, "%02hhx", n->id.x[c]); + id[sizeof id - 1] = 0; + send_request(c, "%d %d %s %s %s %d %d %d %d %x %x %s %s %d %hd %hd %hd %ld", CONTROL, REQ_DUMP_NODES, + n->name, id, n->hostname ?: "unknown port unknown", cipher_get_nid(n->outcipher), digest_get_nid(n->outdigest), (int)digest_length(n->outdigest), n->outcompression, n->options, bitfield_to_int(&n->status, sizeof n->status), n->nexthop ? n->nexthop->name : "-", n->via ? n->via->name ?: "-" : "-", n->distance, n->mtu, n->minmtu, n->maxmtu, (long)n->last_state_change); + } return send_request(c, "%d %d", CONTROL, REQ_DUMP_NODES); } diff --git a/src/node.h b/src/node.h index 605477e5..b6db18b3 100644 --- a/src/node.h +++ b/src/node.h @@ -43,6 +43,7 @@ typedef struct node_status_t { typedef struct node_t { char *name; /* name of this node */ + node_id_t id; /* unique node ID (name hash) */ uint32_t options; /* options turned on for this node */ int sock; /* Socket to use for outgoing UDP packets */ @@ -111,6 +112,7 @@ extern void free_node(node_t *); extern void node_add(node_t *); extern void node_del(node_t *); extern node_t *lookup_node(char *); +extern node_t *lookup_node_id(const node_id_t *); extern node_t *lookup_node_udp(const sockaddr_t *); extern bool dump_nodes(struct connection_t *); extern bool dump_traffic(struct connection_t *); diff --git a/src/tincctl.c b/src/tincctl.c index b15676c8..b287467d 100644 --- a/src/tincctl.c +++ b/src/tincctl.c @@ -1002,6 +1002,7 @@ static int cmd_dump(int argc, char *argv[]) { break; char node[4096]; + char id[4096]; char from[4096]; char to[4096]; char subnet[4096]; @@ -1019,8 +1020,8 @@ static int cmd_dump(int argc, char *argv[]) { switch(req) { case REQ_DUMP_NODES: { - int n = sscanf(line, "%*d %*d %s %s port %s %d %d %d %d %x %x %s %s %d %hd %hd %hd %ld", node, host, port, &cipher, &digest, &maclength, &compression, &options, &status_int, nexthop, via, &distance, &pmtu, &minmtu, &maxmtu, &last_state_change); - if(n != 16) { + int n = sscanf(line, "%*d %*d %s %s %s port %s %d %d %d %d %x %x %s %s %d %hd %hd %hd %ld", node, id, host, port, &cipher, &digest, &maclength, &compression, &options, &status_int, nexthop, via, &distance, &pmtu, &minmtu, &maxmtu, &last_state_change); + if(n != 17) { fprintf(stderr, "Unable to parse node dump from tincd: %s\n", line); return 1; } @@ -1043,8 +1044,8 @@ static int cmd_dump(int argc, char *argv[]) { } else { if(only_reachable && !status.reachable) continue; - printf("%s at %s port %s cipher %d digest %d maclength %d compression %d options %x status %04x nexthop %s via %s distance %d pmtu %hd (min %hd max %hd)\n", - node, host, port, cipher, digest, maclength, compression, options, status_int, nexthop, via, distance, pmtu, minmtu, maxmtu); + printf("%s id %s at %s port %s cipher %d digest %d maclength %d compression %d options %x status %04x nexthop %s via %s distance %d pmtu %hd (min %hd max %hd)\n", + node, id, host, port, cipher, digest, maclength, compression, options, status_int, nexthop, via, distance, pmtu, minmtu, maxmtu); } } break; -- 2.20.1