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 9ee5f67..0d79c90 100644 (file)
--- 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 4279cd3..1609363 100644 (file)
--- 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 4c7d23b..9fc4156 100644 (file)
--- 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 c1247e1..5c7762a 100644 (file)
--- 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 e70a0ec..f2f4d76 100644 (file)
--- 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 97ca2db..7efe7fa 100644 (file)
--- 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 63809ae..d372ced 100644 (file)
--- 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 d2adc13..43895dd 100644 (file)
--- 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 6439a74..a8e197b 100644 (file)
--- 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 7de75b9..8f0efb2 100644 (file)
--- 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 524566f..7569e23 100644 (file)
--- 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 4398e52..c14dfca 100644 (file)
--- 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 284006b..088a524 100644 (file)
--- 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 af31d06..78e7eeb 100644 (file)
--- 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 79832dc..166b8b2 100644 (file)
--- 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 5e785b3..2c01322 100644 (file)
--- 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 17dd39e..fe7d23e 100644 (file)
--- 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 a144636..b6c4fc8 100644 (file)
--- 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 560609c..f9e31c1 100644 (file)
--- 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 10de2d4..b7093e1 100644 (file)
--- 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 (file)
index 0000000..469c74a
--- /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 <http://creativecommons.org/publicdomain/zero/1.0/>. */
+
+#include <stdint.h>
+
+#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);
+}