From 99ba29bc52f640ec9c2cbb331ffdeceff2f0f26f Mon Sep 17 00:00:00 2001 From: =?utf8?q?Ond=C5=99ej=20Sur=C3=BD?= Date: Mon, 28 May 2018 15:22:23 +0200 Subject: [PATCH] Change isc_random() to be just PRNG, and add isc_nonce_buf() that uses CSPRNG This commit reverts the previous change to use system provided entropy, as (SYS_)getrandom is very slow on Linux because it is a syscall. The change introduced in this commit adds a new call isc_nonce_buf that uses CSPRNG from cryptographic library provider to generate secure data that can be and must be used for generating nonces. Example usage would be DNS cookies. The isc_random() API has been changed to use fast PRNG that is not cryptographically secure, but runs entirely in user space. Two contestants have been considered xoroshiro family of the functions by Villa&Blackman and PCG by O'Neill. After a consideration the xoshiro128starstar function has been used as uint32_t random number provider because it is very fast and has good enough properties for our usage pattern. The other change introduced in the commit is the more extensive usage of isc_random_uniform in places where the usage pattern was isc_random() % n to prevent modulo bias. For usage patterns where only 16 or 8 bits are needed (DNS Message ID), the isc_random() functions has been renamed to isc_random32(), and isc_random16() and isc_random8() functions have been introduced by &-ing the isc_random32() output with 0xffff and 0xff. Please note that the functions that uses stripped down bit count doesn't pass our NIST SP 800-22 based random test. --- bin/dig/dighost.c | 10 +- bin/named/controlconf.c | 3 +- bin/named/server.c | 10 +- bin/nsupdate/nsupdate.c | 12 +- bin/rndc/rndc.c | 2 +- bin/tests/system/tkey/keycreate.c | 3 +- bin/tools/mdig.c | 3 +- lib/dns/adb.c | 2 +- lib/dns/dispatch.c | 5 +- lib/dns/hmac_link.c | 13 +- lib/dns/openssldsa_link.c | 3 +- lib/dns/rbtdb.c | 6 +- lib/dns/rdataset.c | 6 +- lib/dns/resolver.c | 2 +- lib/dns/tests/rbt_serialize_test.c | 6 +- lib/dns/tests/rbt_test.c | 14 +- lib/dns/tkey.c | 5 +- lib/dns/xfrin.c | 2 +- lib/dns/zone.c | 3 +- lib/isc/Makefile.in | 10 +- lib/isc/entropy.c | 40 +++++ lib/isc/entropy_private.h | 36 ++++ lib/isc/hash.c | 2 +- lib/isc/include/isc/Makefile.in | 2 +- lib/isc/include/isc/nonce.h | 32 ++++ lib/isc/include/isc/random.h | 39 +++-- lib/isc/nonce.c | 21 +++ lib/isc/pool.c | 3 +- lib/isc/random.c | 172 ++++++------------- lib/isc/taskpool.c | 3 +- lib/isc/tests/random_test.c | 254 ++++++++++++++++++++++------- lib/isc/unix/file.c | 6 +- lib/isc/win32/file.c | 4 +- lib/isc/xoshiro128starstar.c | 58 +++++++ lib/ns/client.c | 3 +- lib/ns/tests/nstest.c | 4 +- util/copyrights | 6 + 37 files changed, 540 insertions(+), 265 deletions(-) create mode 100644 lib/isc/entropy.c create mode 100644 lib/isc/entropy_private.h create mode 100644 lib/isc/include/isc/nonce.h create mode 100644 lib/isc/nonce.c create mode 100644 lib/isc/xoshiro128starstar.c diff --git a/bin/dig/dighost.c b/bin/dig/dighost.c index e980bd3c88a..5928392a679 100644 --- a/bin/dig/dighost.c +++ b/bin/dig/dighost.c @@ -63,6 +63,7 @@ #include #include #include +#include #include #include #include @@ -1315,7 +1316,7 @@ setup_system(isc_boolean_t ipv4only, isc_boolean_t ipv6only) { else if (keysecret[0] != 0) setup_text_key(); - isc_random_buf(cookie_secret, sizeof(cookie_secret)); + isc_nonce_buf(cookie_secret, sizeof(cookie_secret)); } /*% @@ -1870,8 +1871,7 @@ followup_lookup(dns_message_t *msg, dig_query_t *query, dns_section_t section) srv != NULL; srv = ISC_LIST_HEAD(lookup->my_server_list)) { INSIST(i > 0); - j = isc_random(); - j %= i; + j = isc_random_uniform(i); next = ISC_LIST_NEXT(srv, link); while (j-- > 0 && next != NULL) { srv = next; @@ -2023,7 +2023,6 @@ compute_cookie(unsigned char *clientcookie, size_t len) { isc_boolean_t setup_lookup(dig_lookup_t *lookup) { isc_result_t result; - isc_uint32_t id; unsigned int len; dig_server_t *serv; dig_query_t *query; @@ -2198,8 +2197,7 @@ setup_lookup(dig_lookup_t *lookup) { dighost_trying(store, lookup); INSIST(dns_name_isabsolute(lookup->name)); - id = isc_random(); - lookup->sendmsg->id = (unsigned short)id & 0xFFFF; + lookup->sendmsg->id = (dns_messageid_t)isc_random16(); lookup->sendmsg->opcode = lookup->opcode; lookup->msgcounter = 0; /* diff --git a/bin/named/controlconf.c b/bin/named/controlconf.c index 029420b2ecd..36602d3e18b 100644 --- a/bin/named/controlconf.c +++ b/bin/named/controlconf.c @@ -20,6 +20,7 @@ #include #include #include +#include #include #include #include @@ -457,7 +458,7 @@ control_recvmessage(isc_task_t *task, isc_event_t *event) { */ if (conn->nonce == 0) { while (conn->nonce == 0) { - isc_random_buf(&conn->nonce, sizeof(conn->nonce)); + isc_nonce_buf(&conn->nonce, sizeof(conn->nonce)); } eresult = ISC_R_SUCCESS; } else diff --git a/bin/named/server.c b/bin/named/server.c index 9e1aa022e83..1f827a8700c 100644 --- a/bin/named/server.c +++ b/bin/named/server.c @@ -32,11 +32,11 @@ #include #include #include +#include #include #include #include #include -#include #include #include #include @@ -5670,7 +5670,7 @@ create_view(const cfg_obj_t *vconfig, dns_viewlist_t *viewlist, if (result != ISC_R_SUCCESS) return (result); - isc_random_buf(view->secret, sizeof(view->secret)); + isc_nonce_buf(view->secret, sizeof(view->secret)); ISC_LIST_APPEND(*viewlist, view, link); dns_view_attach(view, viewp); @@ -8845,8 +8845,8 @@ load_configuration(const char *filename, named_server_t *server, } } } else { - isc_random_buf(server->sctx->secret, - sizeof(server->sctx->secret)); + isc_nonce_buf(server->sctx->secret, + sizeof(server->sctx->secret)); } /* @@ -13513,7 +13513,7 @@ generate_salt(unsigned char *salt, size_t saltlen) { if (saltlen > 256U) return (ISC_R_RANGE); - isc_random_buf(salt, saltlen); + isc_nonce_buf(salt, saltlen); r.base = salt; r.length = (unsigned int) saltlen; diff --git a/bin/nsupdate/nsupdate.c b/bin/nsupdate/nsupdate.c index 426b4f02db7..fcd30494bb3 100644 --- a/bin/nsupdate/nsupdate.c +++ b/bin/nsupdate/nsupdate.c @@ -29,6 +29,7 @@ #include #include #include +#include #include #include #include @@ -2829,14 +2830,16 @@ start_gssrequest(dns_name_t *master) { fatal("out of memory"); } - memmove(kserver, &master_servers[master_inuse], sizeof(isc_sockaddr_t)); + memmove(kserver, &master_servers[master_inuse], + sizeof(isc_sockaddr_t)); servname = dns_fixedname_initname(&fname); if (realm == NULL) get_ticket_realm(gmctx); - result = snprintf(servicename, sizeof(servicename), "DNS/%s%s", namestr, realm ? realm : ""); + result = snprintf(servicename, sizeof(servicename), "DNS/%s%s", + namestr, realm ? realm : ""); RUNTIME_CHECK(result < sizeof(servicename)); isc_buffer_init(&buf, servicename, strlen(servicename)); isc_buffer_add(&buf, strlen(servicename)); @@ -2848,9 +2851,10 @@ start_gssrequest(dns_name_t *master) { keyname = dns_fixedname_initname(&fkname); - val = isc_random(); + isc_nonce_buf(&val, sizeof(val)); - result = snprintf(mykeystr, sizeof(mykeystr), "%u.sig-%s", val, namestr); + result = snprintf(mykeystr, sizeof(mykeystr), "%u.sig-%s", val, + namestr); RUNTIME_CHECK(result <= sizeof(mykeystr)); isc_buffer_init(&buf, mykeystr, strlen(mykeystr)); diff --git a/bin/rndc/rndc.c b/bin/rndc/rndc.c index d86bdb4eaf1..e6cf1b8f5d9 100644 --- a/bin/rndc/rndc.c +++ b/bin/rndc/rndc.c @@ -930,7 +930,7 @@ main(int argc, char **argv) { if (argc < 1) usage(1); - serial = isc_random(); + serial = isc_random32(); DO("create memory context", isc_mem_create(0, 0, &rndc_mctx)); DO("create socket manager", isc_socketmgr_create(rndc_mctx, &socketmgr)); diff --git a/bin/tests/system/tkey/keycreate.c b/bin/tests/system/tkey/keycreate.c index 0619f381596..e6ab6445c26 100644 --- a/bin/tests/system/tkey/keycreate.c +++ b/bin/tests/system/tkey/keycreate.c @@ -20,6 +20,7 @@ #include #include #include +#include #include #include #include @@ -295,7 +296,7 @@ main(int argc, char *argv[]) { CHECK("dst_key_fromnamedfile", result); isc_buffer_init(&nonce, noncedata, sizeof(noncedata)); - isc_random_buf(noncedata, sizeof(noncedata)); + isc_nonce_buf(noncedata, sizeof(noncedata)); isc_buffer_add(&nonce, sizeof(noncedata)); (void)isc_app_run(); diff --git a/bin/tools/mdig.c b/bin/tools/mdig.c index 9fd980de8b7..a5ec672cb04 100644 --- a/bin/tools/mdig.c +++ b/bin/tools/mdig.c @@ -22,6 +22,7 @@ #include #include #include +#include #include #include #include @@ -1917,7 +1918,7 @@ main(int argc, char *argv[]) { RUNCHECK(isc_log_create(mctx, &lctx, &lcfg)); RUNCHECK(dst_lib_init(mctx, NULL)); - isc_random_buf(cookie_secret, sizeof(cookie_secret)); + isc_nonce_buf(cookie_secret, sizeof(cookie_secret)); ISC_LIST_INIT(queries); parse_args(ISC_FALSE, argc, argv); diff --git a/lib/dns/adb.c b/lib/dns/adb.c index 4c79df71b98..044c9a90929 100644 --- a/lib/dns/adb.c +++ b/lib/dns/adb.c @@ -1834,7 +1834,7 @@ new_adbentry(dns_adb_t *adb) { e->to512 = 0; e->cookie = NULL; e->cookielen = 0; - e->srtt = (isc_random() & 0x1f) + 1; + e->srtt = (isc_random_uniform(0x1f)) + 1; e->lastage = 0; e->expires = 0; e->active = 0; diff --git a/lib/dns/dispatch.c b/lib/dns/dispatch.c index 0bcbabe5fcf..76a22530586 100644 --- a/lib/dns/dispatch.c +++ b/lib/dns/dispatch.c @@ -693,7 +693,8 @@ get_dispsocket(dns_dispatch_t *disp, const isc_sockaddr_t *dest, dispsock->resp = NULL; dispsock->portentry = NULL; dispsock->task = NULL; - isc_task_attach(disp->task[isc_random() % disp->ntasks], &dispsock->task); + isc_task_attach(disp->task[isc_random_uniform(disp->ntasks)], + &dispsock->task); ISC_LINK_INIT(dispsock, link); ISC_LINK_INIT(dispsock, blink); dispsock->magic = DISPSOCK_MAGIC; @@ -3169,7 +3170,7 @@ dns_dispatch_addresponse(dns_dispatch_t *disp, unsigned int options, if ((options & DNS_DISPATCHOPT_FIXEDID) != 0) { id = *idp; } else { - isc_random_buf(&id, sizeof(id)); + id = (dns_messageid_t)isc_random16(); } ok = ISC_FALSE; i = 0; diff --git a/lib/dns/hmac_link.c b/lib/dns/hmac_link.c index 0e817c4c4f9..2c324100dab 100644 --- a/lib/dns/hmac_link.c +++ b/lib/dns/hmac_link.c @@ -29,6 +29,7 @@ #include #include #include +#include #include #include #include @@ -161,7 +162,7 @@ hmacmd5_generate(dst_key_t *key, int pseudorandom_ok, void (*callback)(int)) } memset(data, 0, ISC_MD5_BLOCK_LENGTH); - isc_random_buf(data, bytes); + isc_nonce_buf(data, bytes); isc_buffer_init(&b, data, bytes); isc_buffer_add(&b, bytes); @@ -468,7 +469,7 @@ hmacsha1_generate(dst_key_t *key, int pseudorandom_ok, void (*callback)(int)) } memset(data, 0, ISC_SHA1_BLOCK_LENGTH); - isc_random_buf(data, bytes); + isc_nonce_buf(data, bytes); isc_buffer_init(&b, data, bytes); isc_buffer_add(&b, bytes); @@ -758,7 +759,7 @@ hmacsha224_generate(dst_key_t *key, int pseudorandom_ok, void (*callback)(int)) } memset(data, 0, ISC_SHA224_BLOCK_LENGTH); - isc_random_buf(data, bytes); + isc_nonce_buf(data, bytes); isc_buffer_init(&b, data, bytes); isc_buffer_add(&b, bytes); @@ -1042,7 +1043,7 @@ hmacsha256_generate(dst_key_t *key, int pseudorandom_ok, void (*callback)(int)) } memset(data, 0, ISC_SHA256_BLOCK_LENGTH); - isc_random_buf(data, bytes); + isc_nonce_buf(data, bytes); isc_buffer_init(&b, data, bytes); isc_buffer_add(&b, bytes); @@ -1326,7 +1327,7 @@ hmacsha384_generate(dst_key_t *key, int pseudorandom_ok, void (*callback)(int)) } memset(data, 0, ISC_SHA384_BLOCK_LENGTH); - isc_random_buf(data, bytes); + isc_nonce_buf(data, bytes); isc_buffer_init(&b, data, bytes); isc_buffer_add(&b, bytes); @@ -1610,7 +1611,7 @@ hmacsha512_generate(dst_key_t *key, int pseudorandom_ok, void (*callback)(int)) } memset(data, 0, ISC_SHA512_BLOCK_LENGTH); - isc_random_buf(data, bytes); + isc_nonce_buf(data, bytes); isc_buffer_init(&b, data, bytes); isc_buffer_add(&b, bytes); diff --git a/lib/dns/openssldsa_link.c b/lib/dns/openssldsa_link.c index cd5a60e82ce..000d262168b 100644 --- a/lib/dns/openssldsa_link.c +++ b/lib/dns/openssldsa_link.c @@ -34,6 +34,7 @@ #include #include +#include #include #include #include @@ -351,7 +352,7 @@ openssldsa_generate(dst_key_t *key, int unused, void (*callback)(int)) { UNUSED(unused); - isc_random_buf(rand_array, sizeof(rand_array)); + isc_nonce_buf(rand_array, sizeof(rand_array)); dsa = DSA_new(); if (dsa == NULL) diff --git a/lib/dns/rbtdb.c b/lib/dns/rbtdb.c index 3fef55841a4..ab586dab7b0 100644 --- a/lib/dns/rbtdb.c +++ b/lib/dns/rbtdb.c @@ -5415,12 +5415,12 @@ expirenode(dns_db_t *db, dns_dbnode_t *node, isc_stdtime_t now) { isc_stdtime_get(&now); if (isc_mem_isovermem(rbtdb->common.mctx)) { - isc_uint32_t val = isc_random(); - /* + * Force expire with 25% probability. * XXXDCL Could stand to have a better policy, like LRU. */ - force_expire = ISC_TF(rbtnode->down == NULL && val % 4 == 0); + force_expire = ISC_TF(rbtnode->down == NULL && + (isc_random32() % 4) == 0); /* * Note that 'log' can be true IFF overmem is also true. diff --git a/lib/dns/rdataset.c b/lib/dns/rdataset.c index 21bcff658f2..aad094ef494 100644 --- a/lib/dns/rdataset.c +++ b/lib/dns/rdataset.c @@ -410,9 +410,9 @@ towiresorted(dns_rdataset_t *rdataset, const dns_name_t *owner_name, * 'Random' order. */ for (i = 0; i < count; i++) { - isc_uint32_t val = isc_random(); + isc_uint32_t val = isc_random32(); - choice = i + (val % (count - i)); + choice = i + val % (count - i); rdata = in[i]; in[i] = in[choice]; in[choice] = rdata; @@ -432,7 +432,7 @@ towiresorted(dns_rdataset_t *rdataset, const dns_name_t *owner_name, val = rdataset->count; if (val == ISC_UINT32_MAX) { - val = isc_random(); + val = isc_random32(); } j = val % count; for (i = 0; i < count; i++) { diff --git a/lib/dns/resolver.c b/lib/dns/resolver.c index a959876f8d8..3c11ff2ee19 100644 --- a/lib/dns/resolver.c +++ b/lib/dns/resolver.c @@ -1182,7 +1182,7 @@ fctx_cancelquery(resquery_t **queryp, dns_dispatchevent_t **deventp, * slow. We don't know. Increase the RTT. */ INSIST(no_response); - value = isc_random(); + value = isc_random32(); if (query->addrinfo->srtt > 800000) mask = 0x3fff; else if (query->addrinfo->srtt > 400000) diff --git a/lib/dns/tests/rbt_serialize_test.c b/lib/dns/tests/rbt_serialize_test.c index f52efaa2863..c84b705235a 100644 --- a/lib/dns/tests/rbt_serialize_test.c +++ b/lib/dns/tests/rbt_serialize_test.c @@ -387,11 +387,11 @@ ATF_TC_BODY(deserialize_corrupt, tc) { close(fd); /* Randomly fuzz a portion of the memory */ - p = base + (isc_random() % filesize); + p = base + (isc_random_uniform(filesize)); q = base + filesize; - q -= (isc_random() % (q - p)); + q -= (isc_random_uniform(q - p)); while (p++ < q) { - *p = isc_random() & 0xff; + *p = isc_random8(); } result = dns_rbt_deserialize_tree(base, filesize, 0, mctx, diff --git a/lib/dns/tests/rbt_test.c b/lib/dns/tests/rbt_test.c index a957db2ea49..3eb135acf6e 100644 --- a/lib/dns/tests/rbt_test.c +++ b/lib/dns/tests/rbt_test.c @@ -368,8 +368,8 @@ ATF_TC_BODY(rbt_check_distance_random, tc) { dns_name_t *name; for (j = 0; j < 32; j++) { - isc_uint32_t v = isc_random(); - namebuf[j] = 'a' + (v % 26); + isc_uint32_t v = isc_random_uniform(26); + namebuf[j] = 'a' + v; } namebuf[32] = '.'; namebuf[33] = 0; @@ -894,8 +894,8 @@ insert_nodes(dns_rbt_t *mytree, char **names, isc_result_t result; for (j = 0; j < 32; j++) { - isc_uint32_t v = isc_random(); - namebuf[j] = 'a' + (v % 26); + isc_uint32_t v = isc_random_uniform(26); + namebuf[j] = 'a' + v; } namebuf[32] = '.'; namebuf[33] = 0; @@ -1019,9 +1019,8 @@ ATF_TC_BODY(rbt_insert_and_remove, tc) { for (i = 0; i < 4096; i++) { isc_uint32_t num_names; - num_names = isc_random(); if (names_count < 1024) { - num_names %= 1024 - names_count; + num_names = isc_random_uniform(1024 - names_count); num_names++; } else { num_names = 0; @@ -1030,9 +1029,8 @@ ATF_TC_BODY(rbt_insert_and_remove, tc) { insert_nodes(mytree, names, &names_count, num_names); check_tree(mytree, names, names_count, __LINE__); - num_names = isc_random(); if (names_count > 0) { - num_names %= names_count; + num_names = isc_random_uniform(names_count); num_names++; } else { num_names = 0; diff --git a/lib/dns/tkey.c b/lib/dns/tkey.c index 91437a6bc1e..e31611f4d08 100644 --- a/lib/dns/tkey.c +++ b/lib/dns/tkey.c @@ -15,6 +15,7 @@ #include #include #include +#include #include #include #include @@ -411,7 +412,7 @@ process_dhtkey(dns_message_t *msg, dns_name_t *signer, dns_name_t *name, if (randomdata == NULL) goto failure; - isc_random_buf(randomdata, TKEY_RANDOM_AMOUNT); + isc_nonce_buf(randomdata, TKEY_RANDOM_AMOUNT); r.base = randomdata; r.length = TKEY_RANDOM_AMOUNT; @@ -766,7 +767,7 @@ dns_tkey_processquery(dns_message_t *msg, dns_tkeyctx_t *tctx, isc_buffer_t b; unsigned int i, j; - isc_random_buf(randomdata, sizeof(randomdata)); + isc_nonce_buf(randomdata, sizeof(randomdata)); for (i = 0, j = 0; i < sizeof(randomdata); i++) { unsigned char val = randomdata[i]; diff --git a/lib/dns/xfrin.c b/lib/dns/xfrin.c index 960212bf017..b3186bc67e2 100644 --- a/lib/dns/xfrin.c +++ b/lib/dns/xfrin.c @@ -805,7 +805,7 @@ xfrin_create(isc_mem_t *mctx, dns_name_init(&xfr->name, NULL); xfr->rdclass = rdclass; xfr->checkid = ISC_TRUE; - xfr->id = (isc_uint16_t)(isc_random() & 0xffff); + xfr->id = (dns_messageid_t)isc_random16(); xfr->reqtype = reqtype; xfr->dscp = dscp; diff --git a/lib/dns/zone.c b/lib/dns/zone.c index 8681b76f07c..227b9de56aa 100644 --- a/lib/dns/zone.c +++ b/lib/dns/zone.c @@ -3576,8 +3576,7 @@ set_resigntime(dns_zone_t *zone) { resign = rdataset.resign - zone->sigresigninginterval; dns_rdataset_disassociate(&rdataset); - nanosecs = isc_random(); - nanosecs %= 1000000000; + nanosecs = isc_random_uniform(1000000000); isc_time_set(&zone->resigntime, resign, nanosecs); cleanup: dns_db_detach(&db); diff --git a/lib/isc/Makefile.in b/lib/isc/Makefile.in index 64f5f4c9110..5edc5635b6e 100644 --- a/lib/isc/Makefile.in +++ b/lib/isc/Makefile.in @@ -51,12 +51,12 @@ WIN32OBJS = win32/condition.@O@ win32/dir.@O@ win32/errno.@O@ \ OBJS = @ISC_EXTRA_OBJS@ @ISC_PK11_O@ @ISC_PK11_RESULT_O@ \ aes.@O@ assertions.@O@ backtrace.@O@ base32.@O@ base64.@O@ \ bind9.@O@ buffer.@O@ bufferlist.@O@ \ - commandline.@O@ counter.@O@ crc64.@O@ error.@O@ event.@O@ \ - hash.@O@ ht.@O@ heap.@O@ hex.@O@ hmacmd5.@O@ \ + commandline.@O@ counter.@O@ crc64.@O@ error.@O@ entropy.@O@ \ + event.@O@ hash.@O@ ht.@O@ heap.@O@ hex.@O@ hmacmd5.@O@ \ hmacsha.@O@ httpd.@O@ iterated_hash.@O@ \ lex.@O@ lfsr.@O@ lib.@O@ log.@O@ \ md5.@O@ mem.@O@ mutexblock.@O@ \ - netaddr.@O@ netscope.@O@ pool.@O@ \ + netaddr.@O@ netscope.@O@ nonce.@O@ pool.@O@ \ parseint.@O@ portset.@O@ quota.@O@ radix.@O@ random.@O@ \ ratelimiter.@O@ refcount.@O@ region.@O@ regex.@O@ result.@O@ \ rwlock.@O@ \ @@ -70,11 +70,11 @@ SYMTBLOBJS = backtrace-emptytbl.@O@ SRCS = @ISC_EXTRA_SRCS@ @ISC_PK11_C@ @ISC_PK11_RESULT_C@ \ aes.c assertions.c backtrace.c base32.c base64.c bind9.c \ buffer.c bufferlist.c commandline.c counter.c crc64.c \ - error.c event.c hash.c ht.c heap.c hex.c hmacmd5.c \ + entropy.c error.c event.c hash.c ht.c heap.c hex.c hmacmd5.c \ hmacsha.c httpd.c iterated_hash.c \ lex.c lfsr.c lib.c log.c \ md5.c mem.c mutexblock.c \ - netaddr.c netscope.c pool.c \ + netaddr.c netscope.c nonce.c pool.c \ parseint.c portset.c quota.c radix.c random.c \ ratelimiter.c refcount.c region.c regex.c result.c rwlock.c \ safe.c serial.c sha1.c sha2.c sockaddr.c stats.c string.c \ diff --git a/lib/isc/entropy.c b/lib/isc/entropy.c new file mode 100644 index 00000000000..949a3065814 --- /dev/null +++ b/lib/isc/entropy.c @@ -0,0 +1,40 @@ +/* + * Copyright (C) Internet Systems Consortium, Inc. ("ISC") + * + * This Source Code Form is subject to the terms of the Mozilla Public + * License, v. 2.0. If a copy of the MPL was not distributed with this + * file, You can obtain one at http://mozilla.org/MPL/2.0/. + * + * See the COPYRIGHT file distributed with this work for additional + * information regarding copyright ownership. + */ + +#include + +#include + +#include "entropy_private.h" + +#if HAVE_OPENSSL +#include +#include + +void +isc_entropy_get(void *buf, size_t buflen) { + if (RAND_bytes(buf, buflen) < 1) { + FATAL_ERROR(__FILE__, + __LINE__, + "RAND_bytes(): %s", + ERR_error_string(ERR_get_error(), NULL)); + } +} + +#elif HAVE_PKCS11 +#include + +void +isc_entropy_get(void *buf, size_t buflen) { + RUNTIME_CHECK(pk11_rand_bytes(buf, buflen) == ISC_R_SUCCESS); +} + +#endif /* if HAVE_PKCS11 */ diff --git a/lib/isc/entropy_private.h b/lib/isc/entropy_private.h new file mode 100644 index 00000000000..5ca72133a30 --- /dev/null +++ b/lib/isc/entropy_private.h @@ -0,0 +1,36 @@ +/* + * Copyright (C) Internet Systems Consortium, Inc. ("ISC") + * + * This Source Code Form is subject to the terms of the Mozilla Public + * License, v. 2.0. If a copy of the MPL was not distributed with this + * file, You can obtain one at http://mozilla.org/MPL/2.0/. + * + * See the COPYRIGHT file distributed with this work for additional + * information regarding copyright ownership. + */ + +#pragma once + +#include +#include + +#include + +/*! \file isc/entropy.h + * \brief Implements wrapper around CSPRNG cryptographic library calls + * for getting cryptographically secure pseudo-random numbers. + * + * - If OpenSSL is used, it uses RAND_bytes() + * - If PKCS#11 is used, it uses pkcs_C_GenerateRandom() + * + */ + +ISC_LANG_BEGINDECLS + +void +isc_entropy_get(void *buf, size_t buflen); +/*!< + * \brief Get cryptographically-secure pseudo-random data. + */ + +ISC_LANG_ENDDECLS diff --git a/lib/isc/hash.c b/lib/isc/hash.c index 4d1add960f4..1158513c0bd 100644 --- a/lib/isc/hash.c +++ b/lib/isc/hash.c @@ -70,7 +70,7 @@ fnv_initialize(void) { * again, it should not change fnv_offset_basis. */ while (fnv_offset_basis == 0) { - fnv_offset_basis = isc_random(); + fnv_offset_basis = isc_random32(); } fnv_initialized = ISC_TRUE; diff --git a/lib/isc/include/isc/Makefile.in b/lib/isc/include/isc/Makefile.in index 11682cd06d6..5ae75d2e265 100644 --- a/lib/isc/include/isc/Makefile.in +++ b/lib/isc/include/isc/Makefile.in @@ -27,7 +27,7 @@ HEADERS = aes.h app.h assertions.h backtrace.h base32.h base64.h \ interfaceiter.h @ISC_IPV6_H@ iterated_hash.h \ json.h lang.h lex.h lfsr.h lib.h likely.h list.h log.h \ magic.h md5.h mem.h meminfo.h msgcat.h msgs.h mutexblock.h \ - netaddr.h netscope.h os.h parseint.h \ + netaddr.h netscope.h nonce.h os.h parseint.h \ pool.h portset.h print.h queue.h quota.h \ radix.h random.h ratelimiter.h refcount.h regex.h \ region.h resource.h result.h resultclass.h rwlock.h \ diff --git a/lib/isc/include/isc/nonce.h b/lib/isc/include/isc/nonce.h new file mode 100644 index 00000000000..d01096940ed --- /dev/null +++ b/lib/isc/include/isc/nonce.h @@ -0,0 +1,32 @@ +/* + * Copyright (C) Internet Systems Consortium, Inc. ("ISC") + * + * This Source Code Form is subject to the terms of the Mozilla Public + * License, v. 2.0. If a copy of the MPL was not distributed with this + * file, You can obtain one at http://mozilla.org/MPL/2.0/. + * + * See the COPYRIGHT file distributed with this work for additional + * information regarding copyright ownership. + */ + +#pragma once + +#include +#include + +#include + +/*! \file isc/nonce.h + * \brief Provides a function for generating an arbitrarily long nonce. + */ + +ISC_LANG_BEGINDECLS + +void +isc_nonce_buf(void *buf, size_t buflen); +/*!< + * Fill 'buf', up to 'buflen' bytes, with random data from the + * crypto provider's random function. + */ + +ISC_LANG_ENDDECLS diff --git a/lib/isc/include/isc/random.h b/lib/isc/include/isc/random.h index 0648706f27d..6fe2da068cc 100644 --- a/lib/isc/include/isc/random.h +++ b/lib/isc/include/isc/random.h @@ -17,31 +17,46 @@ #include /*! \file isc/random.h - * \brief Implements wrapper around system provider pseudo-random data - * generators. - * - * The system providers used: - * - On Linux - getrandom() glibc call or syscall - * - On BSDs - arc4random() - * - * If neither is available, the crypto library provider is used: - * - If OpenSSL is used - RAND_bytes() - * - If PKCS#11 is used - pkcs_C_GenerateRandom() + * \brief Implements wrapper around a non-cryptographically secure + * pseudo-random number generator. * */ ISC_LANG_BEGINDECLS +uint8_t +isc_random8(void); +/*!< + * \brief Returns a single 8-bit random value. + */ + +uint16_t +isc_random16(void); +/*!< + * \brief Returns a single 16-bit random value. + */ + uint32_t -isc_random(void); +isc_random32(void); +/*!< + * \brief Returns a single 32-bit random value. + */ void isc_random_buf(void *buf, size_t buflen); /*!< - * \brief Get random data. + * \brief Fills the region buf of length buflen with random data. */ uint32_t isc_random_uniform(uint32_t upper_bound); +/*!< + * \brief Will return a single 32-bit value, uniformly distributed but + * less than upper_bound. This is recommended over + * constructions like ``isc_random() % upper_bound'' as it + * avoids "modulo bias" when the upper bound is not a power of + * two. In the worst case, this function may require multiple + * iterations to ensure uniformity. + */ ISC_LANG_ENDDECLS diff --git a/lib/isc/nonce.c b/lib/isc/nonce.c new file mode 100644 index 00000000000..512caafabd9 --- /dev/null +++ b/lib/isc/nonce.c @@ -0,0 +1,21 @@ +/* + * Copyright (C) Internet Systems Consortium, Inc. ("ISC") + * + * This Source Code Form is subject to the terms of the Mozilla Public + * License, v. 2.0. If a copy of the MPL was not distributed with this + * file, You can obtain one at http://mozilla.org/MPL/2.0/. + * + * See the COPYRIGHT file distributed with this work for additional + * information regarding copyright ownership. + */ + +#include + +#include + +#include "entropy_private.h" + +inline void +isc_nonce_buf(void *buf, size_t buflen) { + return (isc_entropy_get(buf, buflen)); +} diff --git a/lib/isc/pool.c b/lib/isc/pool.c index 853e54d6e85..5c693a6eea7 100644 --- a/lib/isc/pool.c +++ b/lib/isc/pool.c @@ -98,8 +98,7 @@ isc_pool_create(isc_mem_t *mctx, unsigned int count, void * isc_pool_get(isc_pool_t *pool) { - isc_uint32_t i = isc_random(); - return (pool->pool[i % pool->count]); + return (pool->pool[isc_random_uniform(pool->count)]); } int diff --git a/lib/isc/random.c b/lib/isc/random.c index c6ed6823e23..d88431d6d0e 100644 --- a/lib/isc/random.c +++ b/lib/isc/random.c @@ -32,162 +32,95 @@ #include #include +#include #include -#if HAVE_OPENSSL -#include -#include -#endif /* ifdef HAVE_OPENSSL */ - -#if HAVE_PKCS11 -#include -#endif /* if HAVE_PKCS11 */ - -#if defined(__linux__) -# include -# ifdef HAVE_GETRANDOM -# include -# else /* HAVE_GETRANDOM */ -# include -# endif /* HAVE_GETRANDOM */ -#endif /* defined(__linux__) */ - #include #include #include #include -#if defined(_WIN32) || defined(_WIN64) #include -#endif - -#if defined(__linux__) -# ifdef HAVE_GETRANDOM -# define have_getrandom() 1 -# else /* ifdef HAVE_GETRANDOM */ -# undef getrandom -# if defined(SYS_getrandom) -# define getrandom(dst,s,flags) syscall(SYS_getrandom, \ - (void*)dst, \ - (size_t)s, \ - (unsigned int)flags) - -static unsigned -have_getrandom(void) { - uint16_t buf; - ssize_t ret; - ret = getrandom(&buf, sizeof(buf), 1 /*GRND_NONBLOCK*/); - return (ret == sizeof(buf) || - (ret == -1 && errno == EAGAIN)); -} -# else /* defined(SYS_getrandom) */ -# define have_getrandom() 0 -# define getrandom(dst,s,flags) -1 -# endif /* defined(SYS_getrandom) */ -# endif /* ifdef HAVE_GETRANDOM */ - -static int -getrandom_buf(void *buf, size_t buflen) { - size_t left = buflen; - ssize_t ret; - uint8_t *p = buf; - - while (left > 0) { - ret = getrandom(p, left, 0); - if (ret == -1 && errno == EINTR) { - continue; - } - - RUNTIME_CHECK(ret >= 0); - - if (ret > 0) { - left -= ret; - p += ret; - } - } +#include "entropy_private.h" - return(0); -} -#endif /* __linux__ */ +/* + * The specific implementation for PRNG is included as a C file + * that has to provide a static variable named seed, and a function + * uint32_t next(void) that provides next random number. + * + * The implementation must be thread-safe. + */ -#if defined(_WIN32) || defined(_WIN64) +/* + * Two contestants have been considered: the xoroshiro family of the + * functions by Villa&Blackman, and PCG by O'Neill. After + * consideration, the xoshiro128starstar function has been chosen as + * the uint32_t random number provider because it is very fast and has + * good enough properties for our usage pattern. + */ +#include "xoshiro128starstar.c" static isc_once_t isc_random_once = ISC_ONCE_INIT; -static HCRYPTPROV isc_random_hcryptprov; +static void +isc_random_initialize(void) { + isc_entropy_get(seed, sizeof(seed)); +} -static void isc_random_initialize(void) { - RUNTIME_CHECK(CryptAcquireContext(&isc_random_hcryptprov, - NULL, NULL, PROV_RSA_FULL, - CRYPT_VERIFYCONTEXT|CRYPT_SILENT)); +uint8_t +isc_random8(void) { + RUNTIME_CHECK(isc_once_do(&isc_random_once, + isc_random_initialize) == ISC_R_SUCCESS); + return (next() & 0xff); } -#endif /* defined(_WIN32) || defined(_WIN64) */ +uint16_t +isc_random16(void) { + RUNTIME_CHECK(isc_once_do(&isc_random_once, + isc_random_initialize) == ISC_R_SUCCESS); + return (next() & 0xffff); +} uint32_t -isc_random(void) { -#if defined(HAVE_ARC4RANDOM) - return(arc4random()); -#else /* HAVE_ARC4RANDOM */ - uint32_t ret; - isc_random_buf(&ret, sizeof(ret)); - return (ret); -#endif /* HAVE_ARC4RANDOM */ +isc_random32(void) { + RUNTIME_CHECK(isc_once_do(&isc_random_once, + isc_random_initialize) == ISC_R_SUCCESS); + return (next()); } -/* - * Fill the region buf of length buflen with random data. - */ void isc_random_buf(void *buf, size_t buflen) { REQUIRE(buf); REQUIRE(buflen > 0); -#if defined(_WIN32) || defined(_WIN64) RUNTIME_CHECK(isc_once_do(&isc_random_once, isc_random_initialize) == ISC_R_SUCCESS); - RUNTIME_CHECK(CryptGenRandom(isc_random_hcryptprov, - (DWORD)buflen, buf)); - return; -#elif defined(HAVE_ARC4RANDOM_BUF) - arc4random_buf(buf, buflen); - return; -#else -# if defined(__linux__) - /* - * We need to check the availability of the SYS_getrandom - * syscall at runtime and fall back to crypto library provider - * if not available - */ - if (have_getrandom()) { - getrandom_buf(buf, buflen); - return; - } + int i; + uint32_t r; -# endif /* defined(__linux__) */ - -/* Use crypto library as fallback when no other CSPRNG is available */ -# if HAVE_OPENSSL - if (RAND_bytes(buf, buflen) < 1) { - FATAL_ERROR(__FILE__, __LINE__, "RAND_bytes(): %s", ERR_error_string(ERR_get_error(), NULL)); + for (i = 0; i + sizeof(r) <= buflen; i += sizeof(r)) { + r = next(); + memmove((uint8_t *)buf + i, &r, sizeof(r)); /* Buffers cannot + * really overlap + * here */ } -# elif HAVE_PKCS11 - RUNTIME_CHECK(pk11_rand_bytes(buf, buflen) == ISC_R_SUCCESS); -# endif /* if defined(HAVE_ARC4RANDOM_BUF) */ - -#endif + r = next(); + memmove((uint8_t *)buf + i, &r, buflen % sizeof(r)); /* Buffer cannot + * really overlap + * here */ + return; } uint32_t isc_random_uniform(uint32_t upper_bound) { -#if defined(HAVE_ARC4RANDOM_UNIFORM) - return(arc4random_uniform(upper_bound)); -#else /* if defined(HAVE_ARC4RANDOM_UNIFORM) */ /* Copy of arc4random_uniform from OpenBSD */ uint32_t r, min; + RUNTIME_CHECK(isc_once_do(&isc_random_once, + isc_random_initialize) == ISC_R_SUCCESS); + if (upper_bound < 2) { return (0); } @@ -211,12 +144,11 @@ isc_random_uniform(uint32_t upper_bound) { * to re-roll. */ for (;;) { - r = isc_random(); + r = next(); if (r >= min) { break; } } return (r % upper_bound); -#endif /* if defined(HAVE_ARC4RANDOM_UNIFORM) */ } diff --git a/lib/isc/taskpool.c b/lib/isc/taskpool.c index 706b1b1b691..c21bd280a70 100644 --- a/lib/isc/taskpool.c +++ b/lib/isc/taskpool.c @@ -95,8 +95,7 @@ isc_taskpool_create(isc_taskmgr_t *tmgr, isc_mem_t *mctx, void isc_taskpool_gettask(isc_taskpool_t *pool, isc_task_t **targetp) { - isc_uint32_t i = isc_random(); - isc_task_attach(pool->tasks[i % pool->ntasks], targetp); + isc_task_attach(pool->tasks[isc_random_uniform(pool->ntasks)], targetp); } int diff --git a/lib/isc/tests/random_test.c b/lib/isc/tests/random_test.c index 6d52bbe6ab0..b04cfb826f0 100644 --- a/lib/isc/tests/random_test.c +++ b/lib/isc/tests/random_test.c @@ -21,6 +21,7 @@ #include #include #include +#include #include #include @@ -53,6 +54,15 @@ static double biginv = 2.22044604925031308085e-16; static double igamc(double a, double x); static double igam(double a, double x); +typedef enum { + ISC_RANDOM8, + ISC_RANDOM16, + ISC_RANDOM32, + ISC_RANDOM_BYTES, + ISC_RANDOM_UNIFORM, + ISC_NONCE_BYTES +} isc_random_func; + static double igamc(double a, double x) { double ans, ax, c, yc, r, t, y, z; @@ -250,7 +260,7 @@ matrix_binaryrank(isc_uint32_t *bits, size_t rows, size_t cols) { } static void -random_test(pvalue_func_t *func, isc_boolean_t word_sized) { +random_test(pvalue_func_t *func, isc_random_func test_func) { isc_mem_t *mctx = NULL; isc_result_t result; isc_uint32_t m; @@ -274,18 +284,48 @@ random_test(pvalue_func_t *func, isc_boolean_t word_sized) { for (j = 0; j < m; j++) { isc_uint32_t i; - isc_uint16_t values[REPS]; + isc_uint32_t values[REPS]; + isc_uint16_t *uniform_values; double p_value; - if (word_sized) { - for (i = 0; i < REPS; i++) { - isc_random_buf(&values[i], sizeof(values[i])); + switch (test_func) { + case ISC_RANDOM8: + for (i = 0; i < (sizeof(values) / sizeof(*values)); i++) + { + values[i] = isc_random8(); } - } else { + break; + case ISC_RANDOM16: + for (i = 0; i < (sizeof(values) / sizeof(*values)); i++) + { + values[i] = isc_random16(); + } + break; + case ISC_RANDOM32: + for (i = 0; i < (sizeof(values) / sizeof(*values)); i++) + { + values[i] = isc_random32(); + } + break; + case ISC_RANDOM_BYTES: isc_random_buf(values, sizeof(values)); + break; + case ISC_RANDOM_UNIFORM: + uniform_values = (isc_uint16_t *)values; + for (i = 0; + i < (sizeof(values) / sizeof(*uniform_values)); + i++) + { + uniform_values[i] = + isc_random_uniform(ISC_UINT16_MAX); + } + break; + case ISC_NONCE_BYTES: + isc_nonce_buf(values, sizeof(values)); + break; } - p_value = (*func)(mctx, values, REPS); + p_value = (*func)(mctx, (uint16_t *)values, REPS * 2); if (p_value >= 0.01) { passed++; } @@ -364,7 +404,7 @@ monobit(isc_mem_t *mctx, isc_uint16_t *values, size_t length) { UNUSED(mctx); - numbits = length * 16; + numbits = length * sizeof(*values) * 8; scount = 0; for (i = 0; i < length; i++) @@ -403,10 +443,10 @@ runs(isc_mem_t *mctx, isc_uint16_t *values, size_t length) { UNUSED(mctx); - numbits = length * 16; + numbits = length * sizeof(*values) * 8; bcount = 0; - for (i = 0; i < REPS; i++) + for (i = 0; i < length; i++) bcount += bitcounts_table[values[i]]; /* Debug message, not displayed when running via atf-run */ @@ -472,7 +512,7 @@ blockfrequency(isc_mem_t *mctx, isc_uint16_t *values, size_t length) { double chi_square; double p_value; - numbits = length * 16; + numbits = length * sizeof(*values) * 8; mbits = 32000; mwords = mbits / 16; numblocks = numbits / mbits; @@ -512,7 +552,7 @@ blockfrequency(isc_mem_t *mctx, isc_uint16_t *values, size_t length) { isc_mem_put(mctx, pi, numblocks * sizeof(double)); /* Debug message, not displayed when running via atf-run */ - printf("chi_square=%f\n", chi_square); +printf("chi_square=%f\n", chi_square); p_value = igamc(numblocks * 0.5, chi_square * 0.5); @@ -605,114 +645,208 @@ binarymatrixrank(isc_mem_t *mctx, isc_uint16_t *values, size_t length) { return (p_value); } -ATF_TC(isc_random_monobit_16); -ATF_TC_HEAD(isc_random_monobit_16, tc) { +/* Tests for isc_random32() function */ + +ATF_TC(isc_random32_monobit); +ATF_TC_HEAD(isc_random32_monobit, tc) { + atf_tc_set_md_var(tc, "descr", "Monobit test for the RANDOM"); +} +ATF_TC_BODY(isc_random32_monobit, tc) { + UNUSED(tc); + + random_test(monobit, ISC_RANDOM32); +} + +ATF_TC(isc_random32_runs); +ATF_TC_HEAD(isc_random32_runs, tc) { + atf_tc_set_md_var(tc, "descr", "Runs test for the RANDOM"); +} +ATF_TC_BODY(isc_random32_runs, tc) { + UNUSED(tc); + + random_test(runs, ISC_RANDOM32); +} + +ATF_TC(isc_random32_blockfrequency); +ATF_TC_HEAD(isc_random32_blockfrequency, tc) { + atf_tc_set_md_var(tc, "descr", "Block frequency test for the RANDOM"); +} +ATF_TC_BODY(isc_random32_blockfrequency, tc) { + UNUSED(tc); + + random_test(blockfrequency, ISC_RANDOM32); +} + +ATF_TC(isc_random32_binarymatrixrank); +ATF_TC_HEAD(isc_random32_binarymatrixrank, tc) { + atf_tc_set_md_var(tc, "descr", "Binary matrix rank test for the RANDOM"); +} +ATF_TC_BODY(isc_random32_binarymatrixrank, tc) { + UNUSED(tc); + + random_test(binarymatrixrank, ISC_RANDOM32); +} + +/* Tests for isc_random_bytes() function */ + +ATF_TC(isc_random_bytes_monobit); +ATF_TC_HEAD(isc_random_bytes_monobit, tc) { atf_tc_set_md_var(tc, "descr", "Monobit test for the RANDOM"); } -ATF_TC_BODY(isc_random_monobit_16, tc) { +ATF_TC_BODY(isc_random_bytes_monobit, tc) { UNUSED(tc); - random_test(monobit, ISC_TRUE); + random_test(monobit, ISC_RANDOM_BYTES); } -ATF_TC(isc_random_runs_16); -ATF_TC_HEAD(isc_random_runs_16, tc) { +ATF_TC(isc_random_bytes_runs); +ATF_TC_HEAD(isc_random_bytes_runs, tc) { atf_tc_set_md_var(tc, "descr", "Runs test for the RANDOM"); } -ATF_TC_BODY(isc_random_runs_16, tc) { +ATF_TC_BODY(isc_random_bytes_runs, tc) { UNUSED(tc); - random_test(runs, ISC_TRUE); + random_test(runs, ISC_RANDOM_BYTES); } -ATF_TC(isc_random_blockfrequency_16); -ATF_TC_HEAD(isc_random_blockfrequency_16, tc) { +ATF_TC(isc_random_bytes_blockfrequency); +ATF_TC_HEAD(isc_random_bytes_blockfrequency, tc) { atf_tc_set_md_var(tc, "descr", "Block frequency test for the RANDOM"); } -ATF_TC_BODY(isc_random_blockfrequency_16, tc) { +ATF_TC_BODY(isc_random_bytes_blockfrequency, tc) { UNUSED(tc); - random_test(blockfrequency, ISC_TRUE); + random_test(blockfrequency, ISC_RANDOM_BYTES); } -ATF_TC(isc_random_binarymatrixrank_16); -ATF_TC_HEAD(isc_random_binarymatrixrank_16, tc) { +ATF_TC(isc_random_bytes_binarymatrixrank); +ATF_TC_HEAD(isc_random_bytes_binarymatrixrank, tc) { atf_tc_set_md_var(tc, "descr", "Binary matrix rank test for the RANDOM"); } -/* - * This is the binary matrix rank test taken from the NIST SP 800-22 RNG - * test suite. - */ -ATF_TC_BODY(isc_random_binarymatrixrank_16, tc) { +ATF_TC_BODY(isc_random_bytes_binarymatrixrank, tc) { UNUSED(tc); - random_test(binarymatrixrank, ISC_TRUE); + random_test(binarymatrixrank, ISC_RANDOM_BYTES); } -ATF_TC(isc_random_monobit_bytes); -ATF_TC_HEAD(isc_random_monobit_bytes, tc) { + +/* Tests for isc_random_uniform() function */ + +ATF_TC(isc_random_uniform_monobit); +ATF_TC_HEAD(isc_random_uniform_monobit, tc) { atf_tc_set_md_var(tc, "descr", "Monobit test for the RANDOM"); } -ATF_TC_BODY(isc_random_monobit_bytes, tc) { +ATF_TC_BODY(isc_random_uniform_monobit, tc) { UNUSED(tc); - random_test(monobit, ISC_FALSE); + random_test(monobit, ISC_RANDOM_UNIFORM); } -ATF_TC(isc_random_runs_bytes); -ATF_TC_HEAD(isc_random_runs_bytes, tc) { +ATF_TC(isc_random_uniform_runs); +ATF_TC_HEAD(isc_random_uniform_runs, tc) { atf_tc_set_md_var(tc, "descr", "Runs test for the RANDOM"); } -ATF_TC_BODY(isc_random_runs_bytes, tc) { +ATF_TC_BODY(isc_random_uniform_runs, tc) { UNUSED(tc); - random_test(runs, ISC_FALSE); + random_test(runs, ISC_RANDOM_UNIFORM); } -ATF_TC(isc_random_blockfrequency_bytes); -ATF_TC_HEAD(isc_random_blockfrequency_bytes, tc) { +ATF_TC(isc_random_uniform_blockfrequency); +ATF_TC_HEAD(isc_random_uniform_blockfrequency, tc) { atf_tc_set_md_var(tc, "descr", "Block frequency test for the RANDOM"); } -ATF_TC_BODY(isc_random_blockfrequency_bytes, tc) { +ATF_TC_BODY(isc_random_uniform_blockfrequency, tc) { UNUSED(tc); - random_test(blockfrequency, ISC_FALSE); + random_test(blockfrequency, ISC_RANDOM_UNIFORM); } -ATF_TC(isc_random_binarymatrixrank_bytes); -ATF_TC_HEAD(isc_random_binarymatrixrank_bytes, tc) { +ATF_TC(isc_random_uniform_binarymatrixrank); +ATF_TC_HEAD(isc_random_uniform_binarymatrixrank, tc) { atf_tc_set_md_var(tc, "descr", "Binary matrix rank test for the RANDOM"); } -/* - * This is the binary matrix rank test taken from the NIST SP 800-22 RNG - * test suite. - */ -ATF_TC_BODY(isc_random_binarymatrixrank_bytes, tc) { +ATF_TC_BODY(isc_random_uniform_binarymatrixrank, tc) { + UNUSED(tc); + + random_test(binarymatrixrank, ISC_RANDOM_UNIFORM); +} + + +/* Tests for isc_nonce_bytes() function */ + +ATF_TC(isc_nonce_bytes_monobit); +ATF_TC_HEAD(isc_nonce_bytes_monobit, tc) { + atf_tc_set_md_var(tc, "descr", "Monobit test for the RANDOM"); +} + +ATF_TC_BODY(isc_nonce_bytes_monobit, tc) { + UNUSED(tc); + + random_test(monobit, ISC_NONCE_BYTES); +} + +ATF_TC(isc_nonce_bytes_runs); +ATF_TC_HEAD(isc_nonce_bytes_runs, tc) { + atf_tc_set_md_var(tc, "descr", "Runs test for the RANDOM"); +} + +ATF_TC_BODY(isc_nonce_bytes_runs, tc) { + UNUSED(tc); + + random_test(runs, ISC_NONCE_BYTES); +} + +ATF_TC(isc_nonce_bytes_blockfrequency); +ATF_TC_HEAD(isc_nonce_bytes_blockfrequency, tc) { + atf_tc_set_md_var(tc, "descr", "Block frequency test for the RANDOM"); +} + +ATF_TC_BODY(isc_nonce_bytes_blockfrequency, tc) { + UNUSED(tc); + + random_test(blockfrequency, ISC_NONCE_BYTES); +} + +ATF_TC(isc_nonce_bytes_binarymatrixrank); +ATF_TC_HEAD(isc_nonce_bytes_binarymatrixrank, tc) { + atf_tc_set_md_var(tc, "descr", "Binary matrix rank test for the RANDOM"); +} + +ATF_TC_BODY(isc_nonce_bytes_binarymatrixrank, tc) { UNUSED(tc); - random_test(binarymatrixrank, ISC_FALSE); + random_test(binarymatrixrank, ISC_NONCE_BYTES); } /* * Main */ ATF_TP_ADD_TCS(tp) { - ATF_TP_ADD_TC(tp, isc_random_monobit_16); - ATF_TP_ADD_TC(tp, isc_random_runs_16); - ATF_TP_ADD_TC(tp, isc_random_blockfrequency_16); - ATF_TP_ADD_TC(tp, isc_random_binarymatrixrank_16); - ATF_TP_ADD_TC(tp, isc_random_monobit_bytes); - ATF_TP_ADD_TC(tp, isc_random_runs_bytes); - ATF_TP_ADD_TC(tp, isc_random_blockfrequency_bytes); - ATF_TP_ADD_TC(tp, isc_random_binarymatrixrank_bytes); + ATF_TP_ADD_TC(tp, isc_random32_monobit); + ATF_TP_ADD_TC(tp, isc_random32_runs); + ATF_TP_ADD_TC(tp, isc_random32_blockfrequency); + ATF_TP_ADD_TC(tp, isc_random32_binarymatrixrank); + ATF_TP_ADD_TC(tp, isc_random_bytes_monobit); + ATF_TP_ADD_TC(tp, isc_random_bytes_runs); + ATF_TP_ADD_TC(tp, isc_random_bytes_blockfrequency); + ATF_TP_ADD_TC(tp, isc_random_bytes_binarymatrixrank); + ATF_TP_ADD_TC(tp, isc_random_uniform_monobit); + ATF_TP_ADD_TC(tp, isc_random_uniform_runs); + ATF_TP_ADD_TC(tp, isc_random_uniform_blockfrequency); + ATF_TP_ADD_TC(tp, isc_random_uniform_binarymatrixrank); + ATF_TP_ADD_TC(tp, isc_nonce_bytes_monobit); + ATF_TP_ADD_TC(tp, isc_nonce_bytes_runs); + ATF_TP_ADD_TC(tp, isc_nonce_bytes_blockfrequency); + ATF_TP_ADD_TC(tp, isc_nonce_bytes_binarymatrixrank); return (atf_no_error()); } diff --git a/lib/isc/unix/file.c b/lib/isc/unix/file.c index 609ba5035a7..1abf4123830 100644 --- a/lib/isc/unix/file.c +++ b/lib/isc/unix/file.c @@ -272,8 +272,7 @@ isc_file_renameunique(const char *file, char *templet) { x = cp--; while (cp >= templet && *cp == 'X') { - isc_uint32_t which = isc_random(); - *cp = alphnum[which % (sizeof(alphnum) - 1)]; + *cp = alphnum[isc_random_uniform(sizeof(alphnum) - 1)]; x = cp--; } while (link(file, templet) == -1) { @@ -329,8 +328,7 @@ isc_file_openuniquemode(char *templet, int mode, FILE **fp) { x = cp--; while (cp >= templet && *cp == 'X') { - isc_uint32_t which = isc_random(); - *cp = alphnum[which % (sizeof(alphnum) - 1)]; + *cp = alphnum[isc_random_uniform(sizeof(alphnum) - 1)]; x = cp--; } diff --git a/lib/isc/win32/file.c b/lib/isc/win32/file.c index 49dc50605cf..11c57c3f5b3 100644 --- a/lib/isc/win32/file.c +++ b/lib/isc/win32/file.c @@ -56,8 +56,8 @@ gettemp(char *path, isc_boolean_t binary, int *doopen) { trv++; /* extra X's get set to 0's */ while (*--trv == 'X') { - isc_uint32_t which = isc_random(); - *trv = alphnum[which % (sizeof(alphnum) - 1)]; + isc_uint32_t which = isc_random_uniform(sizeof(alphnum) - 1); + *trv = alphnum[which]; } /* * check the target directory; if you have six X's and it diff --git a/lib/isc/xoshiro128starstar.c b/lib/isc/xoshiro128starstar.c new file mode 100644 index 00000000000..f12f5cf52f0 --- /dev/null +++ b/lib/isc/xoshiro128starstar.c @@ -0,0 +1,58 @@ +/* + * Portions Copyright (C) Internet Systems Consortium, Inc. ("ISC") + * + * This Source Code Form is subject to the terms of the Mozilla Public + * License, v. 2.0. If a copy of the MPL was not distributed with this + * file, You can obtain one at http://mozilla.org/MPL/2.0/. + * + * See the COPYRIGHT file distributed with this work for additional + * information regarding copyright ownership. + */ + +/* + * 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 + +/* + * This is xoshiro128** 1.0, our 32-bit all-purpose, rock-solid generator. + * It has excellent (sub-ns) speed, a state size (128 bits) that is large + * enough for mild parallelism, and it passes all tests we are aware of. + * + * For generating just single-precision (i.e., 32-bit) floating-point + * numbers, xoshiro128+ is even faster. + * + * The state must be seeded so that it is not everywhere zero. + */ + +static inline uint32_t rotl(const uint32_t x, int k) { + return (x << k) | (x >> (32 - k)); +} + +static uint32_t seed[4]; + +static inline uint32_t +next(void) { + const uint32_t result_starstar = rotl(seed[0] * 5, 7) * 9; + + const uint32_t t = seed[1] << 9; + + seed[2] ^= seed[0]; + seed[3] ^= seed[1]; + seed[1] ^= seed[2]; + seed[0] ^= seed[3]; + + seed[2] ^= t; + + seed[3] = rotl(seed[3], 11); + + return (result_starstar); +} diff --git a/lib/ns/client.c b/lib/ns/client.c index 8c0a0a7aa93..ad5f492d82d 100644 --- a/lib/ns/client.c +++ b/lib/ns/client.c @@ -17,6 +17,7 @@ #include #include #include +#include #include #include #include @@ -1652,7 +1653,7 @@ ns_client_addopt(ns_client_t *client, dns_message_t *message, isc_buffer_init(&buf, cookie, sizeof(cookie)); isc_stdtime_get(&now); - isc_random_buf(&nonce, sizeof(nonce)); + isc_nonce_buf(&nonce, sizeof(nonce)); compute_cookie(client, now, nonce, client->sctx->secret, &buf); diff --git a/lib/ns/tests/nstest.c b/lib/ns/tests/nstest.c index 16c2dfaf3f0..cd2907bf052 100644 --- a/lib/ns/tests/nstest.c +++ b/lib/ns/tests/nstest.c @@ -534,7 +534,6 @@ attach_query_msg_to_client(ns_client_t *client, const char *qnamestr, isc_buffer_t querybuf; dns_compress_t cctx; isc_result_t result; - isc_uint32_t qid; REQUIRE(client != NULL); REQUIRE(qnamestr != NULL); @@ -550,8 +549,7 @@ attach_query_msg_to_client(ns_client_t *client, const char *qnamestr, /* * Set query ID to a random value. */ - qid = isc_random(); - message->id = (dns_messageid_t)(qid & 0xffff); + message->id = isc_random16(); /* * Set query flags as requested by the caller. diff --git a/util/copyrights b/util/copyrights index 44db4042c13..7ed2fa59f9e 100644 --- a/util/copyrights +++ b/util/copyrights @@ -3482,6 +3482,9 @@ ./lib/isc/commandline.c C.PORTION 1999,2000,2001,2004,2005,2007,2008,2014,2015,2016,2018 ./lib/isc/counter.c C 2014,2016,2018 ./lib/isc/crc64.c C 2013,2016,2018 +./lib/isc/entropy.c C 2018 +./lib/isc/entropy.h C 2018 +./lib/isc/entropy_private.h C 2018 ./lib/isc/error.c C 1998,1999,2000,2001,2004,2005,2007,2015,2016,2018 ./lib/isc/event.c C 1998,1999,2000,2001,2004,2005,2007,2014,2016,2017,2018 ./lib/isc/fsaccess.c C 2000,2001,2004,2005,2007,2016,2017,2018 @@ -3547,6 +3550,7 @@ ./lib/isc/include/isc/mutexblock.h C 1999,2000,2001,2004,2005,2006,2007,2016,2018 ./lib/isc/include/isc/netaddr.h C 1998,1999,2000,2001,2002,2004,2005,2006,2007,2009,2015,2016,2017,2018 ./lib/isc/include/isc/netscope.h C 2002,2004,2005,2006,2007,2009,2016,2018 +./lib/isc/include/isc/nonce.h C 2018 ./lib/isc/include/isc/os.h C 2000,2001,2004,2005,2006,2007,2016,2018 ./lib/isc/include/isc/parseint.h C 2001,2002,2004,2005,2006,2007,2016,2018 ./lib/isc/include/isc/platform.h.in C 1999,2000,2001,2002,2003,2004,2005,2006,2007,2008,2009,2010,2013,2014,2015,2016,2017,2018 @@ -3618,6 +3622,7 @@ ./lib/isc/noatomic/include/Makefile.in MAKE 2007,2012,2016,2018 ./lib/isc/noatomic/include/isc/Makefile.in MAKE 2007,2012,2015,2016,2018 ./lib/isc/noatomic/include/isc/atomic.h C 2005,2007,2016,2018 +./lib/isc/nonce.c C 2018 ./lib/isc/nothreads/Makefile.in MAKE 2000,2001,2004,2007,2009,2010,2012,2013,2016,2018 ./lib/isc/nothreads/condition.c C 2000,2001,2004,2006,2007,2016,2018 ./lib/isc/nothreads/include/Makefile.in MAKE 2000,2001,2004,2007,2012,2016,2018 @@ -3827,6 +3832,7 @@ ./lib/isc/x86_64/include/Makefile.in MAKE 2007,2012,2016,2018 ./lib/isc/x86_64/include/isc/Makefile.in MAKE 2007,2012,2015,2016,2018 ./lib/isc/x86_64/include/isc/atomic.h C 2005,2007,2008,2015,2016,2017,2018 +./lib/isc/xoshiro128starstar.c C.PORTION 2018 ./lib/isccc/Makefile.in MAKE 2001,2003,2004,2007,2009,2011,2012,2014,2015,2016,2017,2018 ./lib/isccc/alist.c C.NOM 2001,2004,2005,2007,2015,2016,2018 ./lib/isccc/api X 2001,2006,2008,2009,2010,2011,2012,2013,2014,2015,2016,2017,2018 -- 2.47.3