[tz] [PROPOSED 4/7] Improve randomness of zic temp file names

[Paul Eggert]

* private.h (HAVE_GETRANDOM): New macro.
* zic.c [HAVE_GETRANDOM]: Include <sys/random.h>.
(get_rand_u64): New function with more randomness,
by using getrandom and/or clock_gettime if available.
Use simpler test for initialization.
(random_dirent): Use it.  Avoid slightly biasing the output of the
random number generator.
---
 Makefile  |  1 +
 private.h |  5 ++++
 zic.c     | 87 ++++++++++++++++++++++++++++++++++++++++++++++++++-----
 3 files changed, 86 insertions(+), 7 deletions(-)

diff --git a/Makefile b/Makefile
index 8a2856f..6f8b2f9 100644
--- a/Makefile
+++ b/Makefile
@@ -210,6 +210,7 @@ LDLIBS=
 #  -DHAVE_DECL_ENVIRON if <unistd.h> declares 'environ'
 #  -DHAVE_DIRECT_H if mkdir needs <direct.h> (MS-Windows)
 #  -DHAVE_GENERIC=0 if _Generic does not work
+#  -DHAVE_GETRANDOM if getgrandom works (e.g., GNU/Linux)*
 #  -DHAVE_GETTEXT if 'gettext' works (e.g., GNU/Linux, FreeBSD, Solaris)*
 #  -DHAVE_INCOMPATIBLE_CTIME_R if your system's time.h declares
 #	ctime_r and asctime_r incompatibly with the POSIX standard
diff --git a/private.h b/private.h
index 5624abc..8024df5 100644
--- a/private.h
+++ b/private.h
@@ -62,6 +62,11 @@
 # define HAVE_GENERIC (201112 <= __STDC_VERSION__)
 #endif
 
+#ifndef HAVE_GETRANDOM
+# define HAVE_GETRANDOM HAS_INCLUDE(<sys/random.h>, \
+				    (2 < __GLIBC__ + (25 <= __GLIBC_MINOR__)))
+#endif
+
 #ifndef HAVE_GETTEXT
 # define HAVE_GETTEXT HAS_INCLUDE(<libintl.h>, false)
 #endif
diff --git a/zic.c b/zic.c
index 38a65eb..ddfdc79 100644
--- a/zic.c
+++ b/zic.c
@@ -38,6 +38,10 @@ typedef int_fast64_t	zic_t;
 # define mkdir(name, mode) _mkdir(name)
 #endif
 
+#if HAVE_GETRANDOM
+# include <sys/random.h>
+#endif
+
 #if HAVE_SYS_STAT_H
 # include <sys/stat.h>
 #endif
@@ -1037,6 +1041,63 @@ namecheck(const char *name)
 	return componentcheck(name, component, cp);
 }
 
+/* Return a random uint_fast64_t.  */
+static uint_fast64_t
+get_rand_u64(void)
+{
+#if HAVE_GETRANDOM
+  static uint_fast64_t entropy_buffer[max(1, 256 / sizeof (uint_fast64_t))];
+  static int nwords;
+  if (!nwords) {
+    ssize_t s;
+    do
+      s = getrandom(entropy_buffer, sizeof entropy_buffer, 0);
+    while (s < 0 && errno == EINTR);
+
+    nwords = s < 0 ? -1 : s / sizeof *entropy_buffer;
+  }
+  if (0 < nwords)
+    return entropy_buffer[--nwords];
+#endif
+
+  /* getrandom didn't work, so fall back on portable code that is
+     not the best because the seed doesn't necessarily have enough bits,
+     the seed isn't cryptographically random on platforms lacking
+     getrandom, and 'rand' might not be cryptographically secure.  */
+  {
+    static bool initialized;
+    if (!initialized) {
+      unsigned seed;
+#ifdef CLOCK_REALTIME
+      struct timespec now;
+      clock_gettime (CLOCK_REALTIME, &now);
+      seed = now.tv_sec ^ now.tv_nsec;
+#else
+      seed = time(NULL);
+#endif
+      srand(seed);
+      initialized = true;
+    }
+  }
+
+  /* Return a random number if rand() yields a random number and in
+     the typical case where RAND_MAX is one less than a power of two.
+     In other cases this code yields a sort-of-random number.  */
+  {
+    uint_fast64_t
+      rand_max = RAND_MAX,
+      multiplier = rand_max + 1, /* It's OK if this overflows to 0.  */
+      r = 0, rmax = 0;
+    do {
+      uint_fast64_t rmax1 = rmax * multiplier + rand_max;
+      r = r * multiplier + rand();
+      rmax = rmax < rmax1 ? rmax1 : UINT_FAST64_MAX;
+    } while (rmax < UINT_FAST64_MAX);
+
+    return r;
+  }
+}
+
 /* Generate a randomish name in the same directory as *NAME.  If
    *NAMEALLOC, put the name into *NAMEALLOC which is assumed to be
    that returned by a previous call and is thus already almost set up
@@ -1056,8 +1117,19 @@ random_dirent(char const **name, char **namealloc)
   int suffixlen = 6;
   char const *lastslash = strrchr(src, '/');
   ptrdiff_t dirlen = lastslash ? lastslash + 1 - src : 0;
-  static unsigned short initialized;
   int i;
+  uint_fast64_t r;
+  uint_fast64_t base = alphabetlen;
+
+  /* BASE**6 */
+  uint_fast64_t base__6 = base * base * base * base * base * base;
+
+  /* The largest uintmax_t that is a multiple of BASE**6.  Any random
+     uintmax_t value that is this value or greater, yields a biased
+     remainder when divided by BASE**6.  UNFAIR_MIN equals the
+     mathematical value of ((UINTMAX_MAX + 1) - (UINTMAX_MAX + 1) % BASE**6)
+     computed without overflow.  */
+  uint_fast64_t unfair_min = - ((UINTMAX_MAX % base__6 + 1) % base__6);
 
   if (!dst) {
     dst = emalloc(dirlen + prefixlen + suffixlen + 1);
@@ -1067,13 +1139,14 @@ random_dirent(char const **name, char **namealloc)
     *name = *namealloc = dst;
   }
 
-  /* This randomization is not the best, but is portable to C89.  */
-  if (!initialized++) {
-    unsigned now = time(NULL);
-    srand(rand() ^ now);
+  do
+    r = get_rand_u64();
+  while (unfair_min <= r);
+
+  for (i = 0; i < suffixlen; i++) {
+    dst[dirlen + prefixlen + i] = alphabet[r % alphabetlen];
+    r /= alphabetlen;
   }
-  for (i = 0; i < suffixlen; i++)
-    dst[dirlen + prefixlen + i] = alphabet[rand() % alphabetlen];
 }
 
 /* Prepare to write to the file *OUTNAME, using *TEMPNAME to store the
-- 
2.37.3