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

Previous Next

Full log

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

Previous Next

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