From: Guus Sliepen Date: Sat, 5 Oct 2019 17:40:15 +0000 (+0200) Subject: Replace rand() by xoshiro256** with per-mesh state. X-Git-Url: http://git.meshlink.io/?p=meshlink;a=commitdiff_plain;h=ea20fcfcded669ce8fbbda3a1f93f354ed254603 Replace rand() by xoshiro256** with per-mesh state. We need a reasonable fast PRNG that doesn't have to be secure, for things like timer randomization, port number generation and so on. Already some platforms warn about the use of rand(). Also, when calling fork(), both parent and child have the same PRNG seed, which causes some inefficiencies in the test suite. --- diff --git a/src/Makefile.am b/src/Makefile.am index b3c1dd10..8decac75 100644 --- a/src/Makefile.am +++ b/src/Makefile.am @@ -78,6 +78,7 @@ libmeshlink_la_SOURCES = \ system.h \ utils.c utils.h \ xalloc.h \ + xoshiro.c xoshiro.h \ devtools.c devtools.h \ $(ed25519_SOURCES) \ $(chacha_poly1305_SOURCES) \ diff --git a/src/discovery.c b/src/discovery.c index 2af47023..323d22cf 100644 --- a/src/discovery.c +++ b/src/discovery.c @@ -21,11 +21,11 @@ #define MESHLINK_MDNS_NAME_KEY "name" #define MESHLINK_MDNS_FINGERPRINT_KEY "fingerprint" -static void generate_rand_string(char *buffer, size_t size) { +static void generate_rand_string(meshlink_handle_t *mesh, char *buffer, size_t size) { assert(size); for(size_t i = 0; i < (size - 1); ++i) { - buffer[i] = 'a' + (rand() % ('z' - 'a' + 1)); + buffer[i] = 'a' + prng(mesh, 'z' - 'a' + 1); } buffer[size - 1] = '\0'; @@ -141,7 +141,7 @@ static void discovery_server_callback(CattaServer *server, CattaServerState stat case CATTA_SERVER_COLLISION: { /* A host name collision happened. Let's pick a new name for the server */ char hostname[17]; - generate_rand_string(hostname, sizeof(hostname)); + generate_rand_string(mesh, hostname, sizeof(hostname)); pthread_mutex_lock(&(mesh->mesh_mutex)); @@ -379,7 +379,7 @@ static void *discovery_loop(void *userdata) { // generate some unique host name (we actually do not care about it) char hostname[17]; - generate_rand_string(hostname, sizeof(hostname)); + generate_rand_string(mesh, hostname, sizeof(hostname)); // Let's set the host name for this server. CattaServerConfig config; diff --git a/src/meshlink.c b/src/meshlink.c index 5940c70e..f504e5af 100644 --- a/src/meshlink.c +++ b/src/meshlink.c @@ -516,7 +516,7 @@ static bool try_bind(int port) { static int check_port(meshlink_handle_t *mesh) { for(int i = 0; i < 1000; i++) { - int port = 0x1000 + (rand() & 0x7fff); + int port = 0x1000 + prng(mesh, 0x8000); if(try_bind(port)) { free(mesh->myport); @@ -1286,6 +1286,8 @@ meshlink_handle_t *meshlink_open_ex(const meshlink_open_params_t *params) { mesh->log_cb = global_log_cb; mesh->log_level = global_log_level; + randomize(&mesh->prng_state, sizeof(mesh->prng_state)); + memcpy(mesh->dev_class_traits, default_class_traits, sizeof(default_class_traits)); if(usingname) { @@ -3522,9 +3524,6 @@ void handle_network_change(meshlink_handle_t *mesh, bool online) { static void __attribute__((constructor)) meshlink_init(void) { crypto_init(); - unsigned int seed; - randomize(&seed, sizeof(seed)); - srand(seed); } static void __attribute__((destructor)) meshlink_exit(void) { diff --git a/src/meshlink_internal.h b/src/meshlink_internal.h index a8561806..f32e87e6 100644 --- a/src/meshlink_internal.h +++ b/src/meshlink_internal.h @@ -32,6 +32,7 @@ #include "meshlink_queue.h" #include "sockaddr.h" #include "sptps.h" +#include "xoshiro.h" #include @@ -130,6 +131,7 @@ struct meshlink_handle { timeout_t periodictimer; struct connection_t *everyone; + uint64_t prng_state[4]; int next_pit; int pits[10]; @@ -255,4 +257,12 @@ extern meshlink_log_cb_t global_log_cb; extern void handle_duplicate_node(meshlink_handle_t *mesh, struct node_t *n); extern void handle_network_change(meshlink_handle_t *mesh, bool online); +/// Per-instance PRNG +static inline int prng(meshlink_handle_t *mesh, uint64_t max) { + return xoshiro(mesh->prng_state) % max; +} + +/// Fudge value of ~0.1 seconds, in microseconds. +static const unsigned int TIMER_FUDGE = 0x20000; + #endif diff --git a/src/net.c b/src/net.c index 46a2631e..76f88475 100644 --- a/src/net.c +++ b/src/net.c @@ -148,7 +148,7 @@ static void timeout_handler(event_loop_t *loop, void *data) { } timeout_set(&mesh->loop, data, &(struct timeval) { - default_timeout, rand() % 100000 + default_timeout, prng(mesh, TIMER_FUDGE) }); } @@ -610,7 +610,7 @@ static void periodic_handler(event_loop_t *loop, void *data) { } timeout_set(&mesh->loop, data, &(struct timeval) { - timeout, rand() % 100000 + timeout, prng(mesh, TIMER_FUDGE) }); } @@ -698,7 +698,7 @@ void retry(meshlink_handle_t *mesh) { */ int main_loop(meshlink_handle_t *mesh) { timeout_add(&mesh->loop, &mesh->pingtimer, timeout_handler, &mesh->pingtimer, &(struct timeval) { - default_timeout, rand() % 100000 + default_timeout, prng(mesh, TIMER_FUDGE) }); timeout_add(&mesh->loop, &mesh->periodictimer, periodic_handler, &mesh->periodictimer, &(struct timeval) { 0, 0 diff --git a/src/net_packet.c b/src/net_packet.c index 493a38ff..ea363b7f 100644 --- a/src/net_packet.c +++ b/src/net_packet.c @@ -120,7 +120,7 @@ static void send_mtu_probe_handler(event_loop_t *loop, void *data) { } else if(n->maxmtu <= n->minmtu) { len = n->maxmtu; } else { - len = n->minmtu + 1 + rand() % (n->maxmtu - n->minmtu); + len = n->minmtu + 1 + prng(mesh, n->maxmtu - n->minmtu); } if(len < 64) { @@ -143,7 +143,7 @@ static void send_mtu_probe_handler(event_loop_t *loop, void *data) { end: timeout_set(&mesh->loop, &n->mtutimeout, &(struct timeval) { - timeout, rand() % 100000 + timeout, prng(mesh, TIMER_FUDGE) }); } @@ -297,7 +297,7 @@ static void choose_udp_address(meshlink_handle_t *mesh, const node_t *n, const s So we pick a random edge and a random socket. */ int i = 0; - int j = rand() % n->edge_tree->count; + int j = prng(mesh, n->edge_tree->count); edge_t *candidate = NULL; for splay_each(edge_t, e, n->edge_tree) { @@ -309,7 +309,7 @@ static void choose_udp_address(meshlink_handle_t *mesh, const node_t *n, const s if(candidate) { *sa = &candidate->address; - *sock = rand() % mesh->listen_sockets; + *sock = prng(mesh, mesh->listen_sockets); } /* Make sure we have a suitable socket for the chosen address */ @@ -340,7 +340,7 @@ static void choose_broadcast_address(meshlink_handle_t *mesh, const node_t *n, c } }; - *sock = rand() % mesh->listen_sockets; + *sock = prng(mesh, mesh->listen_sockets); if(mesh->listen_socket[*sock].sa.sa.sa_family == AF_INET6) { broadcast_ipv6.in6.sin6_port = n->prevedge->address.in.sin_port; diff --git a/src/protocol.c b/src/protocol.c index 3886e357..fa1dc137 100644 --- a/src/protocol.c +++ b/src/protocol.c @@ -209,7 +209,7 @@ static void age_past_requests(event_loop_t *loop, void *data) { if(left) { timeout_set(&mesh->loop, &mesh->past_request_timeout, &(struct timeval) { - 10, rand() % 100000 + 10, prng(mesh, TIMER_FUDGE) }); } } @@ -230,7 +230,7 @@ bool seen_request(meshlink_handle_t *mesh, const char *request) { if(!mesh->past_request_tree->head) { timeout_set(&mesh->loop, &mesh->past_request_timeout, &(struct timeval) { - 10, rand() % 100000 + 10, prng(mesh, TIMER_FUDGE) }); } diff --git a/src/protocol_edge.c b/src/protocol_edge.c index 8bb70714..e817114b 100644 --- a/src/protocol_edge.c +++ b/src/protocol_edge.c @@ -74,7 +74,7 @@ bool send_add_edge(meshlink_handle_t *mesh, connection_t *c, const edge_t *e, in s = e->to->submesh; } - x = send_request(mesh, c, s, "%d %x %s %d %s %s %s %s %d %s %x %d %d", ADD_EDGE, rand(), + x = send_request(mesh, c, s, "%d %x %s %d %s %s %s %s %d %s %x %d %d", ADD_EDGE, prng(mesh, UINT_MAX), e->from->name, e->from->devclass, from_submesh, e->to->name, address, port, e->to->devclass, to_submesh, OPTION_PMTU_DISCOVERY, e->weight, contradictions); free(address); @@ -273,7 +273,7 @@ bool send_del_edge(meshlink_handle_t *mesh, connection_t *c, const edge_t *e, in s = e->to->submesh; } - return send_request(mesh, c, s, "%d %x %s %s %d", DEL_EDGE, rand(), + return send_request(mesh, c, s, "%d %x %s %s %d", DEL_EDGE, prng(mesh, UINT_MAX), e->from->name, e->to->name, contradictions); } diff --git a/src/protocol_key.c b/src/protocol_key.c index bf6c40a2..9f69d803 100644 --- a/src/protocol_key.c +++ b/src/protocol_key.c @@ -34,7 +34,7 @@ static const int req_key_timeout = 2; void send_key_changed(meshlink_handle_t *mesh) { - send_request(mesh, mesh->everyone, NULL, "%d %x %s", KEY_CHANGED, rand(), mesh->self->name); + send_request(mesh, mesh->everyone, NULL, "%d %x %s", KEY_CHANGED, prng(mesh, UINT_MAX), mesh->self->name); /* Force key exchange for connections using SPTPS */ diff --git a/src/xoshiro.c b/src/xoshiro.c new file mode 100644 index 00000000..c05e9405 --- /dev/null +++ b/src/xoshiro.c @@ -0,0 +1,42 @@ +/* Written in 2018 by David Blackman and Sebastiano Vigna (vigna@acm.org) + +To the extent possible under law, the author has dedicated all copyright +and related and neighboring rights to this software to the public domain +worldwide. This software is distributed without any warranty. + +See . */ + +#include +#include "xoshiro.h" + +/* This is xoshiro256** 1.0, one of our all-purpose, rock-solid + generators. It has excellent (sub-ns) speed, a state (256 bits) that is + large enough for any parallel application, and it passes all tests we + are aware of. + + For generating just floating-point numbers, xoshiro256+ is even faster. + + The state must be seeded so that it is not everywhere zero. If you have + a 64-bit seed, we suggest to seed a splitmix64 generator and use its + output to fill s. */ + +static inline uint64_t rotl(const uint64_t x, int k) { + return (x << k) | (x >> (64 - k)); +} + +uint64_t xoshiro(uint64_t s[4]) { + const uint64_t result = rotl(s[1] * 5, 7) * 9; + + const uint64_t t = s[1] << 17; + + s[2] ^= s[0]; + s[3] ^= s[1]; + s[1] ^= s[2]; + s[0] ^= s[3]; + + s[2] ^= t; + + s[3] = rotl(s[3], 45); + + return result; +} diff --git a/src/xoshiro.h b/src/xoshiro.h new file mode 100644 index 00000000..fcd5192c --- /dev/null +++ b/src/xoshiro.h @@ -0,0 +1,6 @@ +#ifndef MESHLINK_XOSHIRO_H +#define MESHLINK_XOSHIRO_H + +extern uint64_t xoshiro(uint64_t s[4]); + +#endif