GNU bug report logs - #6683
mktemp foo.XXXXXXXXXXX is not sufficiently random

Previous Next

To add a comment to this bug, you must first unarchive it, by sending
a message to control AT debbugs.gnu.org, with unarchive 6683 in the body.
You can then email your comments to 6683 AT debbugs.gnu.org in the normal way.

Toggle the display of automated, internal messages from the tracker.

Message #5 received at submit <at> debbugs.gnu.org (full text, mbox):

From: Paul Eggert <eggert <at> CS.UCLA.EDU>
To: Bug Coreutils <bug-coreutils <at> gnu.org>
Subject: mktemp foo.XXXXXXXXXXX is not sufficiently random
Date: Tue, 20 Jul 2010 10:21:11 -0700

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;
 

Message #8 received at 6683 <at> debbugs.gnu.org (full text, mbox):

From: Eric Blake <eblake <at> redhat.com>
To: Paul Eggert <eggert <at> CS.UCLA.EDU>
Cc: 6683 <at> debbugs.gnu.org
Subject: Re: bug#6683: mktemp foo.XXXXXXXXXXX is not sufficiently random
Date: Tue, 20 Jul 2010 11:41:29 -0600

[Message part 1 (text/plain, inline)]

On 07/20/2010 11:21 AM, Paul Eggert wrote:
> 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.

Meanwhile, glibc's mkstemp() only replaces the last 6 X, regardless of
how many additional X are present in the template.  Do we even need the
extra randomness if the template contains more X?

-- 
Eric Blake   eblake <at> redhat.com    +1-801-349-2682
Libvirt virtualization library http://libvirt.org

[signature.asc (application/pgp-signature, attachment)]

Message #11 received at 6683 <at> debbugs.gnu.org (full text, mbox):

From: Paul Eggert <eggert <at> CS.UCLA.EDU>
To: Eric Blake <eblake <at> redhat.com>
Cc: 6683 <at> debbugs.gnu.org
Subject: Re: bug#6683: mktemp foo.XXXXXXXXXXX is not sufficiently random
Date: Tue, 20 Jul 2010 11:10:30 -0700

On 07/20/10 10:41, Eric Blake wrote:
> Meanwhile, glibc's mkstemp() only replaces the last 6 X, regardless of
> how many additional X are present in the template.  Do we even need the
> extra randomness if the template contains more X?

Well, I did say that it was a _theoretical_ bug.  You need the extra
randomness if you run mktemp about 18e18 times (or more, of course).

Limiting it to the randomness needed for 6 Xs would give about 57 million
possibilities, which is fine for most applications, but the arbitrary limit
does rankle a bit given that one of GNU's tenets is no arbitrary limits.
The current coreutils code limits it to the randomness needed for about 10.7 Xs,
but that also is arbitrary, and it's easy to remove the arbitrary limit.

Message #14 received at 6683 <at> debbugs.gnu.org (full text, mbox):

From: Jim Meyering <jim <at> meyering.net>
To: Paul Eggert <eggert <at> CS.UCLA.EDU>
Cc: 6683 <at> debbugs.gnu.org
Subject: Re: bug#6683: mktemp foo.XXXXXXXXXXX is not sufficiently random
Date: Sun, 07 Aug 2011 19:04:13 +0200

Paul Eggert wrote:
> 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?

[Yikes, this is over a year old...
 Sorry about the delay in replying. ]

Yes, please do.
Thanks for keeping us honest ;-)

> --- 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:

I agree.
Simpler is better.

> --- 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);
> +}
...

Message #19 received at 6683-done <at> debbugs.gnu.org (full text, mbox):

From: Paul Eggert <eggert <at> cs.ucla.edu>
To: Jim Meyering <jim <at> meyering.net>
Cc: 6683-done <at> debbugs.gnu.org
Subject: Re: bug#6683: mktemp foo.XXXXXXXXXXX is not sufficiently random
Date: Mon, 08 Aug 2011 00:39:30 -0700

On 08/07/2011 10:04 AM, Jim Meyering wrote:

> Yes, please do.

OK, thanks, I installed the one-line change as change to the diff.
This is the first time I've updated a diff file in a while (ever?),
so I hope I did it right.  I'm marking the bug done.

From 8e2767a3f0c279d355f067e53be2c63173959eb1 Mon Sep 17 00:00:00 2001
From: Paul Eggert <eggert <at> cs.ucla.edu>
Date: Mon, 8 Aug 2011 00:29:46 -0700
Subject: [PATCH] mktemp: stir in enough entropy (Bug#6683)

* gl/lib/tempname.c.diff (gen_tempname_len):
Use x_suffix_len bytes' worth of entropy, not 8 bytes.
---
 gl/lib/tempname.c.diff |    2 +-
 1 files changed, 1 insertions(+), 1 deletions(-)

diff --git a/gl/lib/tempname.c.diff b/gl/lib/tempname.c.diff
index fcacf53..3e30c97 100644
--- a/gl/lib/tempname.c.diff
+++ b/gl/lib/tempname.c.diff
@@ -100,7 +100,7 @@ index 2da5afe..562955a 100644
 -  }
 -#endif
 -  value += random_time_bits ^ __getpid ();
-+  rand_src = randint_all_new (NULL, 8);
++  rand_src = randint_all_new (NULL, x_suffix_len);
 +  if (! rand_src)
 +    return -1;
 
-- 
1.7.4.4

Previous Next

GNU bug tracking system
Copyright (C) 1999 Darren O. Benham, 1997,2003 nCipher Corporation Ltd, 1994-97 Ian Jackson.