From: Guus Sliepen Date: Mon, 16 Aug 2021 21:26:24 +0000 (+0200) Subject: Use xoshiro256** to generate pseudo-random numbers. X-Git-Url: https://tinc-vpn.org/git/browse?p=tinc;a=commitdiff_plain;h=6debc6c79ba385d35f646e0958f84ace5b8f4b4d Use xoshiro256** to generate pseudo-random numbers. Also seed it using /dev/random or whatever equivalent is available. --- diff --git a/src/Makefile.am b/src/Makefile.am index 9ee5f677..0d79c906 100644 --- a/src/Makefile.am +++ b/src/Makefile.am @@ -111,6 +111,7 @@ tincd_SOURCES = \ tincd.c \ utils.c utils.h \ xalloc.h \ + xoshiro.c \ version.c version.h \ ed25519/ecdh.c \ ed25519/ecdsa.c \ @@ -140,6 +141,7 @@ tinc_SOURCES = \ ed25519/ecdh.c \ ed25519/ecdsa.c \ ed25519/ecdsagen.c \ + xoshiro.c \ $(ed25519_SOURCES) \ $(chacha_poly1305_SOURCES) @@ -148,6 +150,7 @@ sptps_test_SOURCES = \ sptps.c sptps.h \ sptps_test.c \ utils.c utils.h \ + xoshiro.c \ ed25519/ecdh.c \ ed25519/ecdsa.c \ $(ed25519_SOURCES) \ diff --git a/src/autoconnect.c b/src/autoconnect.c index 4279cd37..16093633 100644 --- a/src/autoconnect.c +++ b/src/autoconnect.c @@ -20,13 +20,14 @@ #include "system.h" #include "connection.h" +#include "crypto.h" #include "logger.h" #include "node.h" #include "xalloc.h" static void make_new_connection() { /* Select a random node we haven't connected to yet. */ - int count = 0; + uint32_t count = 0; for splay_each(node_t, n, &node_tree) { if(n == myself || n->connection || !(n->status.has_address || n->status.reachable)) { @@ -40,7 +41,7 @@ static void make_new_connection() { return; } - int r = rand() % count; + uint32_t r = prng(count); for splay_each(node_t, n, &node_tree) { if(n == myself || n->connection || !(n->status.has_address || n->status.reachable)) { @@ -80,7 +81,7 @@ static void connect_to_unreachable() { * are only a few reachable nodes, and many unreachable ones, we're * going to try harder to connect to them. */ - unsigned int r = rand() % node_tree.count; + uint32_t r = prng(node_tree.count); for splay_each(node_t, n, &node_tree) { if(r--) { @@ -111,7 +112,7 @@ static void connect_to_unreachable() { static void drop_superfluous_outgoing_connection() { /* Choose a random outgoing connection to a node that has at least one other connection. */ - int count = 0; + uint32_t count = 0; for list_each(connection_t, c, &connection_list) { if(!c->edge || !c->outgoing || !c->node || c->node->edge_tree.count < 2) { @@ -125,7 +126,7 @@ static void drop_superfluous_outgoing_connection() { return; } - int r = rand() % count; + uint32_t r = prng(count); for list_each(connection_t, c, &connection_list) { if(!c->edge || !c->outgoing || !c->node || c->node->edge_tree.count < 2) { @@ -167,7 +168,7 @@ static void drop_superfluous_pending_connections() { void do_autoconnect() { /* Count number of active connections. */ - int nc = 0; + uint32_t nc = 0; for list_each(connection_t, c, &connection_list) { if(c->edge) { diff --git a/src/crypto.h b/src/crypto.h index 4c7d23bf..9fc4156c 100644 --- a/src/crypto.h +++ b/src/crypto.h @@ -24,6 +24,21 @@ extern void crypto_init(void); extern void crypto_exit(void); +extern uint64_t xoshiro(void); +extern void prng_init(void); +extern void prng_randomize(void *buf, size_t buflen); extern void randomize(void *buf, size_t buflen); +static inline uint32_t prng(uint32_t limit) { + uint64_t bins = UINT64_MAX / limit; + uint64_t reject_after = bins * limit; + uint64_t value; + + do { + value = xoshiro(); + } while(value >= reject_after); + + return value / bins; +} + #endif diff --git a/src/fsck.c b/src/fsck.c index c1247e17..5c7762a8 100644 --- a/src/fsck.c +++ b/src/fsck.c @@ -329,7 +329,7 @@ static bool test_rsa_keypair(rsa_t *rsa_priv, rsa_t *rsa_pub, const char *host_f uint8_t *encrypted = xzalloc(len); uint8_t *decrypted = xzalloc(len); - randomize(plaintext, len); + prng_randomize(plaintext, len); plaintext[0] &= 0x7f; if(rsa_public_encrypt(rsa_pub, plaintext, len, encrypted)) { diff --git a/src/invitation.c b/src/invitation.c index e70a0ec8..f2f4d76c 100644 --- a/src/invitation.c +++ b/src/invitation.c @@ -709,7 +709,7 @@ make_names: // Generate a random netname, ask for a better one later. ask_netname = true; - snprintf(temp_netname, sizeof(temp_netname), "join_%x", rand()); + snprintf(temp_netname, sizeof(temp_netname), "join_%x", prng(UINT32_MAX)); netname = temp_netname; goto make_names; } diff --git a/src/net.c b/src/net.c index 97ca2dba..7efe7fa3 100644 --- a/src/net.c +++ b/src/net.c @@ -26,6 +26,7 @@ #include "conf_net.h" #include "conf.h" #include "connection.h" +#include "crypto.h" #include "graph.h" #include "logger.h" #include "meta.h" @@ -256,7 +257,7 @@ static void timeout_handler(void *data) { } timeout_set(data, &(struct timeval) { - 1, rand() % 100000 + 1, jitter() }); } @@ -294,7 +295,7 @@ static void periodic_handler(void *data) { } timeout_set(data, &(struct timeval) { - 5, rand() % 100000 + 5, jitter() }); } @@ -482,7 +483,7 @@ void retry(void) { int main_loop(void) { last_periodic_run_time = now; timeout_add(&pingtimer, timeout_handler, &pingtimer, &(struct timeval) { - pingtimeout, rand() % 100000 + pingtimeout, jitter() }); timeout_add(&periodictimer, periodic_handler, &periodictimer, &(struct timeval) { 0, 0 diff --git a/src/net_packet.c b/src/net_packet.c index 63809aee..d372ced6 100644 --- a/src/net_packet.c +++ b/src/net_packet.c @@ -739,7 +739,7 @@ static void choose_udp_address(const node_t *n, const sockaddr_t **sa, size_t *s So we pick a random edge and a random socket. */ unsigned int i = 0; - unsigned int j = rand() % n->edge_tree.count; + unsigned int j = prng(n->edge_tree.count); edge_t *candidate = NULL; for splay_each(edge_t, e, &n->edge_tree) { @@ -751,7 +751,7 @@ static void choose_udp_address(const node_t *n, const sockaddr_t **sa, size_t *s if(candidate) { *sa = &candidate->address; - *sock = rand() % listen_sockets; + *sock = prng(listen_sockets); } adapt_socket(*sa, sock); @@ -763,7 +763,7 @@ static void choose_local_address(const node_t *n, const sockaddr_t **sa, size_t /* Pick one of the edges from this node at random, then use its local address. */ unsigned int i = 0; - unsigned int j = rand() % n->edge_tree.count; + unsigned int j = prng(n->edge_tree.count); edge_t *candidate = NULL; for splay_each(edge_t, e, &n->edge_tree) { @@ -775,7 +775,7 @@ static void choose_local_address(const node_t *n, const sockaddr_t **sa, size_t if(candidate && candidate->local_address.sa.sa_family) { *sa = &candidate->local_address; - *sock = rand() % listen_sockets; + *sock = prng(listen_sockets); adapt_socket(*sa, sock); } } diff --git a/src/net_setup.c b/src/net_setup.c index d2adc13f..43895dda 100644 --- a/src/net_setup.c +++ b/src/net_setup.c @@ -28,6 +28,7 @@ #include "connection.h" #include "compression.h" #include "control.h" +#include "crypto.h" #include "device.h" #include "digest.h" #include "ecdsa.h" @@ -142,7 +143,7 @@ static timeout_t keyexpire_timeout; static void keyexpire_handler(void *data) { regenerate_key(); timeout_set(data, &(struct timeval) { - keylifetime, rand() % 100000 + keylifetime, jitter() }); } #endif @@ -834,7 +835,7 @@ static bool setup_myself(void) { free(cipher); timeout_add(&keyexpire_timeout, keyexpire_handler, &keyexpire_timeout, &(struct timeval) { - keylifetime, rand() % 100000 + keylifetime, jitter() }); /* Check if we want to use message authentication codes... */ diff --git a/src/net_socket.c b/src/net_socket.c index 6439a743..a8e197b4 100644 --- a/src/net_socket.c +++ b/src/net_socket.c @@ -25,6 +25,7 @@ #include "address_cache.h" #include "conf.h" #include "connection.h" +#include "crypto.h" #include "list.h" #include "logger.h" #include "names.h" @@ -408,7 +409,7 @@ void retry_outgoing(outgoing_t *outgoing) { } timeout_add(&outgoing->ev, retry_outgoing_handler, outgoing, &(struct timeval) { - outgoing->timeout, rand() % 100000 + outgoing->timeout, jitter() }); logger(DEBUG_CONNECTIONS, LOG_NOTICE, "Trying to re-establish outgoing connection in %d seconds", outgoing->timeout); diff --git a/src/protocol.c b/src/protocol.c index 7de75b93..8f0efb2a 100644 --- a/src/protocol.c +++ b/src/protocol.c @@ -22,9 +22,11 @@ #include "conf.h" #include "connection.h" +#include "crypto.h" #include "logger.h" #include "meta.h" #include "protocol.h" +#include "utils.h" #include "xalloc.h" bool tunnelserver = false; @@ -191,7 +193,7 @@ static void age_past_requests(void *data) { if(left) timeout_set(&past_request_timeout, &(struct timeval) { - 10, rand() % 100000 + 10, jitter() }); } @@ -209,7 +211,7 @@ bool seen_request(const char *request) { new->firstseen = now.tv_sec; splay_insert(&past_request_tree, new); timeout_add(&past_request_timeout, age_past_requests, NULL, &(struct timeval) { - 10, rand() % 100000 + 10, jitter() }); return false; } diff --git a/src/protocol_edge.c b/src/protocol_edge.c index 524566f0..7569e231 100644 --- a/src/protocol_edge.c +++ b/src/protocol_edge.c @@ -22,6 +22,7 @@ #include "system.h" #include "conf.h" +#include "crypto.h" #include "connection.h" #include "edge.h" #include "graph.h" @@ -43,13 +44,13 @@ bool send_add_edge(connection_t *c, const edge_t *e) { char *local_address, *local_port; sockaddr2str(&e->local_address, &local_address, &local_port); - x = send_request(c, "%d %x %s %s %s %s %x %d %s %s", ADD_EDGE, rand(), + x = send_request(c, "%d %x %s %s %s %s %x %d %s %s", ADD_EDGE, prng(UINT32_MAX), e->from->name, e->to->name, address, port, e->options, e->weight, local_address, local_port); free(local_address); free(local_port); } else { - x = send_request(c, "%d %x %s %s %s %s %x %d", ADD_EDGE, rand(), + x = send_request(c, "%d %x %s %s %s %s %x %d", ADD_EDGE, prng(UINT32_MAX), e->from->name, e->to->name, address, port, e->options, e->weight); } @@ -218,7 +219,7 @@ bool add_edge_h(connection_t *c, const char *request) { } bool send_del_edge(connection_t *c, const edge_t *e) { - return send_request(c, "%d %x %s %s", DEL_EDGE, rand(), + return send_request(c, "%d %x %s %s", DEL_EDGE, prng(UINT32_MAX), e->from->name, e->to->name); } diff --git a/src/protocol_key.c b/src/protocol_key.c index 4398e528..c14dfcac 100644 --- a/src/protocol_key.c +++ b/src/protocol_key.c @@ -35,7 +35,7 @@ void send_key_changed(void) { #ifndef DISABLE_LEGACY - send_request(everyone, "%d %x %s", KEY_CHANGED, rand(), myself->name); + send_request(everyone, "%d %x %s", KEY_CHANGED, prng(UINT32_MAX), myself->name); /* Immediately send new keys to directly connected nodes to keep UDP mappings alive */ diff --git a/src/protocol_misc.c b/src/protocol_misc.c index 284006bb..088a5242 100644 --- a/src/protocol_misc.c +++ b/src/protocol_misc.c @@ -22,6 +22,7 @@ #include "address_cache.h" #include "connection.h" +#include "crypto.h" #include "logger.h" #include "meta.h" #include "net.h" @@ -73,13 +74,23 @@ bool pong_h(connection_t *c, const char *request) { return true; } +static bool random_early_drop(connection_t *c) { + if(c->outbuf.len > maxoutbufsize / 2) { + if((c->outbuf.len - maxoutbufsize / 2) > prng((maxoutbufsize) / 2)) { + return true; + } + } + + return false; +} + /* Sending and receiving packets via TCP */ bool send_tcppacket(connection_t *c, const vpn_packet_t *packet) { /* If there already is a lot of data in the outbuf buffer, discard this packet. We use a very simple Random Early Drop algorithm. */ - if(2.0 * c->outbuf.len / (float)maxoutbufsize - 1 > (float)rand() / (float)RAND_MAX) { + if(random_early_drop(c)) { return true; } @@ -110,7 +121,7 @@ bool send_sptps_tcppacket(connection_t *c, const void *packet, size_t len) { /* If there already is a lot of data in the outbuf buffer, discard this packet. We use a very simple Random Early Drop algorithm. */ - if(2.0 * c->outbuf.len / (float)maxoutbufsize - 1 > (float)rand() / (float)RAND_MAX) { + if(random_early_drop(c)) { return true; } diff --git a/src/protocol_subnet.c b/src/protocol_subnet.c index af31d064..78e7eebc 100644 --- a/src/protocol_subnet.c +++ b/src/protocol_subnet.c @@ -23,6 +23,7 @@ #include "conf.h" #include "connection.h" +#include "crypto.h" #include "logger.h" #include "node.h" #include "protocol.h" @@ -37,7 +38,7 @@ bool send_add_subnet(connection_t *c, const subnet_t *subnet) { return false; } - return send_request(c, "%d %x %s %s", ADD_SUBNET, rand(), subnet->owner->name, netstr); + return send_request(c, "%d %x %s %s", ADD_SUBNET, prng(UINT32_MAX), subnet->owner->name, netstr); } bool add_subnet_h(connection_t *c, const char *request) { @@ -153,7 +154,7 @@ bool send_del_subnet(connection_t *c, const subnet_t *s) { return false; } - return send_request(c, "%d %x %s %s", DEL_SUBNET, rand(), s->owner->name, netstr); + return send_request(c, "%d %x %s %s", DEL_SUBNET, prng(UINT32_MAX), s->owner->name, netstr); } bool del_subnet_h(connection_t *c, const char *request) { diff --git a/src/route.c b/src/route.c index 79832dca..166b8b24 100644 --- a/src/route.c +++ b/src/route.c @@ -22,6 +22,7 @@ #include "connection.h" #include "control_common.h" +#include "crypto.h" #include "ethernet.h" #include "ipv4.h" #include "ipv6.h" @@ -31,6 +32,7 @@ #include "protocol.h" #include "route.h" #include "subnet.h" +#include "utils.h" rmode_t routing_mode = RMODE_ROUTER; fmode_t forwarding_mode = FMODE_INTERNAL; @@ -515,7 +517,7 @@ static void age_subnets(void *data) { if(left) timeout_set(&age_subnets_timeout, &(struct timeval) { - 10, rand() % 100000 + 10, jitter() }); } @@ -545,7 +547,7 @@ static void learn_mac(mac_t *address) { } timeout_add(&age_subnets_timeout, age_subnets, NULL, &(struct timeval) { - 10, rand() % 100000 + 10, jitter() }); } else { if(subnet->expires) { diff --git a/src/sptps_test.c b/src/sptps_test.c index 5e785b3a..2c013223 100644 --- a/src/sptps_test.c +++ b/src/sptps_test.c @@ -375,8 +375,6 @@ int main(int argc, char *argv[]) { initiator = true; } - srand(getpid()); - #ifdef HAVE_LINUX if(tun) { @@ -494,6 +492,7 @@ int main(int argc, char *argv[]) { } crypto_init(); + prng_init(); FILE *fp = fopen(argv[1], "r"); @@ -647,7 +646,7 @@ int main(int argc, char *argv[]) { fprintf(stderr, "Received %zd bytes of data:\n%s\n", len, hex); } - if(packetloss && (rand() % 100) < packetloss) { + if(packetloss && prng(100) < packetloss) { if(verbose) { fprintf(stderr, "Dropped.\n"); } diff --git a/src/subnet.c b/src/subnet.c index 17dd39e8..fe7d23ef 100644 --- a/src/subnet.c +++ b/src/subnet.c @@ -22,6 +22,7 @@ #include "splay_tree.h" #include "control_common.h" +#include "crypto.h" #include "hash.h" #include "logger.h" #include "net.h" @@ -128,7 +129,7 @@ void subnet_cache_flush_table(subnet_type_t stype) { /* Initialising trees */ void init_subnets(void) { - hash_seed = (uint32_t)rand(); + hash_seed = prng(UINT32_MAX); // tables need to be cleared on startup subnet_cache_flush_tables(); diff --git a/src/tincctl.c b/src/tincctl.c index a1446369..b6c4fc89 100644 --- a/src/tincctl.c +++ b/src/tincctl.c @@ -2127,7 +2127,7 @@ int check_port(const char *name) { fprintf(stderr, "Warning: could not bind to port 655. "); for(int i = 0; i < 100; i++) { - int port = 0x1000 + (rand() & 0x7fff); + uint16_t port = 0x1000 + prng(0x8000); if(try_bind(port)) { char filename[PATH_MAX]; @@ -3302,8 +3302,8 @@ int main(int argc, char *argv[]) { #endif gettimeofday(&now, NULL); - srand(now.tv_sec + now.tv_usec); crypto_init(); + prng_init(); if(optind >= argc) { return cmd_shell(argc, argv); diff --git a/src/tincd.c b/src/tincd.c index 560609c1..f9e31c19 100644 --- a/src/tincd.c +++ b/src/tincd.c @@ -489,9 +489,9 @@ int main(int argc, char **argv) { unsetenv("LISTEN_PID"); #endif - /* Slllluuuuuuurrrrp! */ - + gettimeofday(&now, NULL); crypto_init(); + prng_init(); if(!read_server_config(&config_tree)) { return 1; @@ -544,9 +544,6 @@ int main2(int argc, char **argv) { #endif char *priority = NULL; - gettimeofday(&now, NULL); - srand(now.tv_sec + now.tv_usec); - if(!detach()) { return 1; } diff --git a/src/utils.h b/src/utils.h index 10de2d41..b7093e1e 100644 --- a/src/utils.h +++ b/src/utils.h @@ -23,6 +23,8 @@ #include "system.h" +#include "crypto.h" + #define B64_SIZE(len) ((len) * 4 / 3 + 5) extern size_t hex2bin(const char *src, void *dst, size_t length); @@ -43,6 +45,10 @@ extern const char *winerror(int); #define sockinuse(x) ((x) == WSAEADDRINUSE) #define socknotconn(x) ((x) == WSAENOTCONN) #define sockshutdown(x) ((x) == WSAESHUTDOWN) + +static inline long jitter(void) { + return (long)prng(131072); +} #else #define sockerrno errno #define sockstrerror(x) strerror(x) @@ -51,6 +57,10 @@ extern const char *winerror(int); #define sockinprogress(x) ((x) == EINPROGRESS) #define sockinuse(x) ((x) == EADDRINUSE) #define socknotconn(x) ((x) == ENOTCONN) + +static inline suseconds_t jitter(void) { + return (suseconds_t)prng(131072); +} #endif extern unsigned int bitfield_to_int(const void *bitfield, size_t size); diff --git a/src/xoshiro.c b/src/xoshiro.c new file mode 100644 index 00000000..469c74ab --- /dev/null +++ b/src/xoshiro.c @@ -0,0 +1,70 @@ +/* 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 "crypto.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)); +} + +static uint64_t s[4]; + +uint64_t xoshiro(void) { + 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; +} + +void prng_init(void) { + do { + randomize(s, sizeof(s)); + } while(!s[0] && !s[1] && !s[2] && !s[3]); +} + +void prng_randomize(void *buf, size_t buflen) { + uint8_t *p = buf; + uint64_t value; + + while(buflen > sizeof(value)) { + value = xoshiro(); + memcpy(p, &value, sizeof(value)); + p += sizeof(value); + buflen -= sizeof(value); + } + + if(!buflen) { + return; + } + + value = xoshiro(); + memcpy(p, &value, buflen); +}