bug#6683: mktemp foo.XXXXXXXXXXX is not sufficiently random

[Paul Eggert]

While looking at the random-number stuff I found a theoretical
randomness bug in mktemp.  The mktemp command currently uses 8 bytes
of randomness to generate a file name, so with an invocation like
this:

$ mktemp foo.XXXXXXXXXXX

the file name is not sufficiently random.  There are 62 possibilities
for each X, so one needs log2(62**11) random bits to generate a random
11-character value for the Xs, which is about 65.5 bits, but we are
generating only 64 bits.  The more Xs, the more randomness is needed,
so the bug gets more "serious" as the number of Xs grows.

Here's a simple patch to fix this.  Should I install this by
generating a new gl/lib/tempname.c.diff by hand, and pushing that?

--- old/tempname.c      2010-07-20 09:41:36.774229000 -0700
+++ new/tempname.c      2010-07-20 10:14:33.391452000 -0700
@@ -245,7 +245,7 @@ gen_tempname_len (char *tmpl, int suffix
   XXXXXX = &tmpl[len - x_suffix_len - suffixlen];
 
   /* Get some more or less random data.  */
-  rand_src = randint_all_new (NULL, 8);
+  rand_src = randint_all_new (NULL, x_suffix_len);
   if (! rand_src)
     return -1;
 

Here's a fancier patch that uses fewer random bits, but on
futher thought I don't think it's worth the extra machine
instructions for a purely-theoretical bug:

--- old/tempname.c      2010-07-20 09:41:36.774229000 -0700
+++ new/tempname.c      2010-07-20 09:45:00.685972000 -0700
@@ -19,6 +19,7 @@
 
 #if !_LIBC
 # include <config.h>
+# include <limits.h>
 # include "tempname.h"
 # include "randint.h"
 #endif
@@ -189,6 +190,17 @@ check_x_suffix (char const *s, size_t le
 static const char letters[] =
 "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789";
 
+/* Upper bound on the number bytes of random information needed to
+   generate N random letters.  There are 62 letters, and 2**6 is 64,
+   so 6N bits = 6N/CHAR_BIT bytes is an upper bound.  Return ceil (6.0
+   * N / CHAR_BIT) without rounding error or overflow.  */
+static size_t
+randomness_bound (size_t n)
+{
+  return ((n / CHAR_BIT) * 6
+         + ((n % CHAR_BIT) * 6 + CHAR_BIT - 1) / CHAR_BIT);
+}
+
 /* Generate a temporary file name based on TMPL.  TMPL must match the
    rules for mk[s]temp (i.e. end in at least X_SUFFIX_LEN "X"s,
    possibly with a suffix).
@@ -245,7 +257,7 @@ gen_tempname_len (char *tmpl, int suffix
   XXXXXX = &tmpl[len - x_suffix_len - suffixlen];
 
   /* Get some more or less random data.  */
-  rand_src = randint_all_new (NULL, 8);
+  rand_src = randint_all_new (NULL, randomness_bound (x_suffix_len));
   if (! rand_src)
     return -1;