From unknown Sat Jun 21 10:33:47 2025 X-Loop: help-debbugs@gnu.org Subject: bug#6683: mktemp foo.XXXXXXXXXXX is not sufficiently random Resent-From: Paul Eggert Original-Sender: debbugs-submit-bounces@debbugs.gnu.org Resent-To: owner@debbugs.gnu.org Resent-CC: bug-coreutils@gnu.org Resent-Date: Tue, 20 Jul 2010 17:22:02 +0000 Resent-Message-ID: Resent-Sender: help-debbugs@gnu.org X-GNU-PR-Message: report 6683 X-GNU-PR-Package: coreutils X-GNU-PR-Keywords: To: 6683@debbugs.gnu.org X-Debbugs-Original-To: Bug Coreutils Received: via spool by submit@debbugs.gnu.org id=B.127964650914566 (code B ref -1); Tue, 20 Jul 2010 17:22:02 +0000 Received: (at submit) by debbugs.gnu.org; 20 Jul 2010 17:21:49 +0000 Received: from localhost ([127.0.0.1] helo=debbugs.gnu.org) by debbugs.gnu.org with esmtp (Exim 4.69) (envelope-from ) id 1ObGVp-0003mt-GA for submit@debbugs.gnu.org; Tue, 20 Jul 2010 13:21:49 -0400 Received: from mx10.gnu.org ([199.232.76.166]) by debbugs.gnu.org with esmtp (Exim 4.69) (envelope-from ) id 1ObGVK-0003mW-If for submit@debbugs.gnu.org; Tue, 20 Jul 2010 13:21:48 -0400 Received: from lists.gnu.org ([199.232.76.165]:56338) by monty-python.gnu.org with esmtps (TLS-1.0:DHE_RSA_AES_256_CBC_SHA1:32) (Exim 4.60) (envelope-from ) id 1ObGVW-0004yo-1z for submit@debbugs.gnu.org; Tue, 20 Jul 2010 13:21:30 -0400 Received: from [140.186.70.92] (port=51082 helo=eggs.gnu.org) by lists.gnu.org with esmtp (Exim 4.43) id 1ObGVS-0008Ad-As for bug-coreutils@gnu.org; Tue, 20 Jul 2010 13:21:29 -0400 X-Spam-Checker-Version: SpamAssassin 3.3.1 (2010-03-16) on eggs.gnu.org X-Spam-Level: X-Spam-Status: No, score=-1.9 required=5.0 tests=BAYES_00,T_RP_MATCHES_RCVD autolearn=unavailable version=3.3.1 Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.69) (envelope-from ) id 1ObGVF-0003v5-Ur for bug-coreutils@gnu.org; Tue, 20 Jul 2010 13:21:15 -0400 Received: from kiwi.cs.ucla.edu ([131.179.128.19]:43343) by eggs.gnu.org with esmtp (Exim 4.69) (envelope-from ) id 1ObGVF-0003um-Ly for bug-coreutils@gnu.org; Tue, 20 Jul 2010 13:21:13 -0400 Received: from [131.179.64.200] (Penguin.CS.UCLA.EDU [131.179.64.200]) by kiwi.cs.ucla.edu (8.13.8+Sun/8.13.8/UCLACS-6.0) with ESMTP id o6KHLBFI021849 for ; Tue, 20 Jul 2010 10:21:11 -0700 (PDT) Message-ID: <4C45DB07.6090406@cs.ucla.edu> Date: Tue, 20 Jul 2010 10:21:11 -0700 From: Paul Eggert Organization: UCLA Computer Science Department User-Agent: Mozilla/5.0 (X11; U; Linux i686; en-US; rv:1.9.1.10) Gecko/20100527 Thunderbird/3.0.5 MIME-Version: 1.0 Content-Type: text/plain; charset=ISO-8859-1 Content-Transfer-Encoding: 7bit X-detected-operating-system: by eggs.gnu.org: Solaris 10 (beta) X-detected-operating-system: by monty-python.gnu.org: GNU/Linux 2.6, seldom 2.4 (older, 4) X-Spam-Score: -5.1 (-----) X-BeenThere: debbugs-submit@debbugs.gnu.org X-Mailman-Version: 2.1.11 Precedence: list List-Id: List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Sender: debbugs-submit-bounces@debbugs.gnu.org Errors-To: debbugs-submit-bounces@debbugs.gnu.org X-Spam-Score: -5.1 (-----) 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 +# include # 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; From unknown Sat Jun 21 10:33:47 2025 X-Loop: help-debbugs@gnu.org Subject: bug#6683: mktemp foo.XXXXXXXXXXX is not sufficiently random Resent-From: Eric Blake Original-Sender: debbugs-submit-bounces@debbugs.gnu.org Resent-To: owner@debbugs.gnu.org Resent-CC: bug-coreutils@gnu.org Resent-Date: Tue, 20 Jul 2010 17:43:02 +0000 Resent-Message-ID: Resent-Sender: help-debbugs@gnu.org X-GNU-PR-Message: followup 6683 X-GNU-PR-Package: coreutils X-GNU-PR-Keywords: To: Paul Eggert Cc: 6683@debbugs.gnu.org Received: via spool by 6683-submit@debbugs.gnu.org id=B6683.127964772715179 (code B ref 6683); Tue, 20 Jul 2010 17:43:02 +0000 Received: (at 6683) by debbugs.gnu.org; 20 Jul 2010 17:42:07 +0000 Received: from localhost ([127.0.0.1] helo=debbugs.gnu.org) by debbugs.gnu.org with esmtp (Exim 4.69) (envelope-from ) id 1ObGpT-0003wm-82 for submit@debbugs.gnu.org; Tue, 20 Jul 2010 13:42:07 -0400 Received: from mx1.redhat.com ([209.132.183.28]) by debbugs.gnu.org with esmtp (Exim 4.69) (envelope-from ) id 1ObGpQ-0003wQ-Ab for 6683@debbugs.gnu.org; Tue, 20 Jul 2010 13:42:05 -0400 Received: from int-mx03.intmail.prod.int.phx2.redhat.com (int-mx03.intmail.prod.int.phx2.redhat.com [10.5.11.16]) by mx1.redhat.com (8.13.8/8.13.8) with ESMTP id o6KHgQja032512 (version=TLSv1/SSLv3 cipher=DHE-RSA-AES256-SHA bits=256 verify=OK); Tue, 20 Jul 2010 13:42:27 -0400 Received: from [10.11.10.145] (vpn-10-145.rdu.redhat.com [10.11.10.145]) by int-mx03.intmail.prod.int.phx2.redhat.com (8.13.8/8.13.8) with ESMTP id o6KHgPsh015787; Tue, 20 Jul 2010 13:42:26 -0400 Message-ID: <4C45DFC9.1020803@redhat.com> Date: Tue, 20 Jul 2010 11:41:29 -0600 From: Eric Blake Organization: Red Hat User-Agent: Mozilla/5.0 (X11; U; Linux x86_64; en-US; rv:1.9.1.10) Gecko/20100621 Fedora/3.0.5-1.fc13 Lightning/1.0b2pre Mnenhy/0.8.3 Thunderbird/3.0.5 MIME-Version: 1.0 References: <4C45DB07.6090406@cs.ucla.edu> In-Reply-To: <4C45DB07.6090406@cs.ucla.edu> X-Enigmail-Version: 1.0.1 Content-Type: multipart/signed; micalg=pgp-sha256; protocol="application/pgp-signature"; boundary="------------enig19EEC2C71A7A821F2FEFC7CC" X-Scanned-By: MIMEDefang 2.67 on 10.5.11.16 X-Spam-Score: -10.1 (----------) X-BeenThere: debbugs-submit@debbugs.gnu.org X-Mailman-Version: 2.1.11 Precedence: list List-Id: List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Sender: debbugs-submit-bounces@debbugs.gnu.org Errors-To: debbugs-submit-bounces@debbugs.gnu.org X-Spam-Score: -10.1 (----------) This is an OpenPGP/MIME signed message (RFC 2440 and 3156) --------------enig19EEC2C71A7A821F2FEFC7CC Content-Type: text/plain; charset=ISO-8859-1 Content-Transfer-Encoding: quoted-printable 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: >=20 > $ mktemp foo.XXXXXXXXXXX >=20 > 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? --=20 Eric Blake eblake@redhat.com +1-801-349-2682 Libvirt virtualization library http://libvirt.org --------------enig19EEC2C71A7A821F2FEFC7CC Content-Type: application/pgp-signature; name="signature.asc" Content-Description: OpenPGP digital signature Content-Disposition: attachment; filename="signature.asc" -----BEGIN PGP SIGNATURE----- Version: GnuPG v2.0.14 (GNU/Linux) Comment: Public key at http://people.redhat.com/eblake/eblake.gpg Comment: Using GnuPG with Fedora - http://enigmail.mozdev.org/ iQEcBAEBCAAGBQJMRd/JAAoJEKeha0olJ0Nq/eIH/A16CN7SUFtIO24sRG3+Ss43 fc6dw9sJPRhgWrGJq3K0iZ/J6l45i6AOJ4t28FQI+YONWq9uc3Cgkbw06ZoKQU7K vHHRqyz/ig6mkLLYCJhet95RA3S8qLfC6lIm4yU6ZNhkRS04xyEjIcThTjKm6kR8 /OO1VQ6oTRUAmM5gTJwE0uSAKqm6dq2hV/2jPOMbP9V2z2+lY7v+Ln8XveUbe9zf FAxijx1RcBMcvNEzKK54Qp7dybkBHpZ3hGuwduMOL4Os5CYUpoUrpo8H6BjpS8WZ H7Y6lELAvw4jPmJFMJDknhYkpKlrQ2tdDYIe4Ix7rH9SsWpjEvduMQDY6NPjqPU= =mCr1 -----END PGP SIGNATURE----- --------------enig19EEC2C71A7A821F2FEFC7CC-- From unknown Sat Jun 21 10:33:47 2025 X-Loop: help-debbugs@gnu.org Subject: bug#6683: mktemp foo.XXXXXXXXXXX is not sufficiently random Resent-From: Paul Eggert Original-Sender: debbugs-submit-bounces@debbugs.gnu.org Resent-To: owner@debbugs.gnu.org Resent-CC: bug-coreutils@gnu.org Resent-Date: Tue, 20 Jul 2010 18:11:01 +0000 Resent-Message-ID: Resent-Sender: help-debbugs@gnu.org X-GNU-PR-Message: followup 6683 X-GNU-PR-Package: coreutils X-GNU-PR-Keywords: To: Eric Blake Cc: 6683@debbugs.gnu.org Received: via spool by 6683-submit@debbugs.gnu.org id=B6683.127964941015949 (code B ref 6683); Tue, 20 Jul 2010 18:11:01 +0000 Received: (at 6683) by debbugs.gnu.org; 20 Jul 2010 18:10:10 +0000 Received: from localhost ([127.0.0.1] helo=debbugs.gnu.org) by debbugs.gnu.org with esmtp (Exim 4.69) (envelope-from ) id 1ObHGb-00049C-V4 for submit@debbugs.gnu.org; Tue, 20 Jul 2010 14:10:10 -0400 Received: from kiwi.cs.ucla.edu ([131.179.128.19]) by debbugs.gnu.org with esmtp (Exim 4.69) (envelope-from ) id 1ObHGZ-00048t-M1 for 6683@debbugs.gnu.org; Tue, 20 Jul 2010 14:10:08 -0400 Received: from [131.179.64.200] (Penguin.CS.UCLA.EDU [131.179.64.200]) by kiwi.cs.ucla.edu (8.13.8+Sun/8.13.8/UCLACS-6.0) with ESMTP id o6KIAUAP022486; Tue, 20 Jul 2010 11:10:31 -0700 (PDT) Message-ID: <4C45E696.1020001@cs.ucla.edu> Date: Tue, 20 Jul 2010 11:10:30 -0700 From: Paul Eggert Organization: UCLA Computer Science Department User-Agent: Mozilla/5.0 (X11; U; Linux i686; en-US; rv:1.9.1.10) Gecko/20100527 Thunderbird/3.0.5 MIME-Version: 1.0 References: <4C45DB07.6090406@cs.ucla.edu> <4C45DFC9.1020803@redhat.com> In-Reply-To: <4C45DFC9.1020803@redhat.com> Content-Type: text/plain; charset=ISO-8859-1 Content-Transfer-Encoding: 7bit X-Spam-Score: -3.4 (---) X-BeenThere: debbugs-submit@debbugs.gnu.org X-Mailman-Version: 2.1.11 Precedence: list List-Id: List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Sender: debbugs-submit-bounces@debbugs.gnu.org Errors-To: debbugs-submit-bounces@debbugs.gnu.org X-Spam-Score: -3.4 (---) 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. From unknown Sat Jun 21 10:33:47 2025 X-Loop: help-debbugs@gnu.org Subject: bug#6683: mktemp foo.XXXXXXXXXXX is not sufficiently random Resent-From: Jim Meyering Original-Sender: debbugs-submit-bounces@debbugs.gnu.org Resent-To: owner@debbugs.gnu.org Resent-CC: bug-coreutils@gnu.org Resent-Date: Sun, 07 Aug 2011 17:06:01 +0000 Resent-Message-ID: Resent-Sender: help-debbugs@gnu.org X-GNU-PR-Message: followup 6683 X-GNU-PR-Package: coreutils X-GNU-PR-Keywords: To: Paul Eggert Cc: 6683@debbugs.gnu.org Received: via spool by 6683-submit@debbugs.gnu.org id=B6683.131273671517231 (code B ref 6683); Sun, 07 Aug 2011 17:06:01 +0000 Received: (at 6683) by debbugs.gnu.org; 7 Aug 2011 17:05:15 +0000 Received: from localhost ([127.0.0.1] helo=debbugs.gnu.org) by debbugs.gnu.org with esmtp (Exim 4.69) (envelope-from ) id 1Qq6mo-0004Ts-O0 for submit@debbugs.gnu.org; Sun, 07 Aug 2011 13:05:14 -0400 Received: from mx.meyering.net ([82.230.74.64]) by debbugs.gnu.org with esmtp (Exim 4.69) (envelope-from ) id 1Qq6ml-0004Ti-Ev for 6683@debbugs.gnu.org; Sun, 07 Aug 2011 13:05:12 -0400 Received: from rho.meyering.net (localhost.localdomain [127.0.0.1]) by rho.meyering.net (Acme Bit-Twister) with ESMTP id 5B7FC60150; Sun, 7 Aug 2011 19:04:13 +0200 (CEST) From: Jim Meyering In-Reply-To: <4C45DB07.6090406@cs.ucla.edu> (Paul Eggert's message of "Tue, 20 Jul 2010 10:21:11 -0700") References: <4C45DB07.6090406@cs.ucla.edu> Date: Sun, 07 Aug 2011 19:04:13 +0200 Message-ID: <87ei0xgnle.fsf@rho.meyering.net> Lines: 66 MIME-Version: 1.0 Content-Type: text/plain X-Spam-Score: -6.1 (------) X-BeenThere: debbugs-submit@debbugs.gnu.org X-Mailman-Version: 2.1.11 Precedence: list List-Id: List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Sender: debbugs-submit-bounces@debbugs.gnu.org Errors-To: debbugs-submit-bounces@debbugs.gnu.org X-Spam-Score: -6.1 (------) 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 > +# include > # 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); > +} ... From unknown Sat Jun 21 10:33:47 2025 MIME-Version: 1.0 X-Mailer: MIME-tools 5.427 (Entity 5.427) X-Loop: help-debbugs@gnu.org From: help-debbugs@gnu.org (GNU bug Tracking System) To: Paul Eggert Subject: bug#6683: closed (Re: bug#6683: mktemp foo.XXXXXXXXXXX is not sufficiently random) Message-ID: References: <4E3F92B2.4010906@cs.ucla.edu> <4C45DB07.6090406@cs.ucla.edu> X-Gnu-PR-Message: they-closed 6683 X-Gnu-PR-Package: coreutils Reply-To: 6683@debbugs.gnu.org Date: Mon, 08 Aug 2011 07:41:03 +0000 Content-Type: multipart/mixed; boundary="----------=_1312789263-10586-1" This is a multi-part message in MIME format... ------------=_1312789263-10586-1 Content-Disposition: inline Content-Transfer-Encoding: quoted-printable Content-Type: text/plain; charset="utf-8" Your bug report #6683: mktemp foo.XXXXXXXXXXX is not sufficiently random which was filed against the coreutils package, has been closed. The explanation is attached below, along with your original report. If you require more details, please reply to 6683@debbugs.gnu.org. --=20 6683: http://debbugs.gnu.org/cgi/bugreport.cgi?bug=3D6683 GNU Bug Tracking System Contact help-debbugs@gnu.org with problems ------------=_1312789263-10586-1 Content-Type: message/rfc822 Content-Disposition: inline Content-Transfer-Encoding: 7bit Received: (at 6683-done) by debbugs.gnu.org; 8 Aug 2011 07:40:44 +0000 Received: from localhost ([127.0.0.1] helo=debbugs.gnu.org) by debbugs.gnu.org with esmtp (Exim 4.69) (envelope-from ) id 1QqKS3-0002kE-9J for submit@debbugs.gnu.org; Mon, 08 Aug 2011 03:40:43 -0400 Received: from smtp.cs.ucla.edu ([131.179.128.62]) by debbugs.gnu.org with esmtp (Exim 4.69) (envelope-from ) id 1QqKS0-0002k4-QQ for 6683-done@debbugs.gnu.org; Mon, 08 Aug 2011 03:40:41 -0400 Received: from localhost (localhost.localdomain [127.0.0.1]) by smtp.cs.ucla.edu (Postfix) with ESMTP id 06EA839E80F7; Mon, 8 Aug 2011 00:39:39 -0700 (PDT) X-Virus-Scanned: amavisd-new at smtp.cs.ucla.edu Received: from smtp.cs.ucla.edu ([127.0.0.1]) by localhost (smtp.cs.ucla.edu [127.0.0.1]) (amavisd-new, port 10024) with ESMTP id AuLcbGDbhI1c; Mon, 8 Aug 2011 00:39:38 -0700 (PDT) Received: from [10.1.205.231] (206-169-234-26.static.twtelecom.net [206.169.234.26]) by smtp.cs.ucla.edu (Postfix) with ESMTPSA id 759F739E80DC; Mon, 8 Aug 2011 00:39:38 -0700 (PDT) Message-ID: <4E3F92B2.4010906@cs.ucla.edu> Date: Mon, 08 Aug 2011 00:39:30 -0700 From: Paul Eggert User-Agent: Mozilla/5.0 (X11; U; Linux i686; en-US; rv:1.9.2.18) Gecko/20110617 Thunderbird/3.1.11 MIME-Version: 1.0 To: Jim Meyering Subject: Re: bug#6683: mktemp foo.XXXXXXXXXXX is not sufficiently random References: <4C45DB07.6090406@cs.ucla.edu> <87ei0xgnle.fsf@rho.meyering.net> In-Reply-To: <87ei0xgnle.fsf@rho.meyering.net> Content-Type: text/plain; charset=ISO-8859-1 Content-Transfer-Encoding: 7bit X-Spam-Score: -2.2 (--) X-Debbugs-Envelope-To: 6683-done Cc: 6683-done@debbugs.gnu.org X-BeenThere: debbugs-submit@debbugs.gnu.org X-Mailman-Version: 2.1.11 Precedence: list List-Id: List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Sender: debbugs-submit-bounces@debbugs.gnu.org Errors-To: debbugs-submit-bounces@debbugs.gnu.org X-Spam-Score: -2.3 (--) 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 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 ------------=_1312789263-10586-1 Content-Type: message/rfc822 Content-Disposition: inline Content-Transfer-Encoding: 7bit Received: (at submit) by debbugs.gnu.org; 20 Jul 2010 17:21:49 +0000 Received: from localhost ([127.0.0.1] helo=debbugs.gnu.org) by debbugs.gnu.org with esmtp (Exim 4.69) (envelope-from ) id 1ObGVp-0003mt-GA for submit@debbugs.gnu.org; Tue, 20 Jul 2010 13:21:49 -0400 Received: from mx10.gnu.org ([199.232.76.166]) by debbugs.gnu.org with esmtp (Exim 4.69) (envelope-from ) id 1ObGVK-0003mW-If for submit@debbugs.gnu.org; Tue, 20 Jul 2010 13:21:48 -0400 Received: from lists.gnu.org ([199.232.76.165]:56338) by monty-python.gnu.org with esmtps (TLS-1.0:DHE_RSA_AES_256_CBC_SHA1:32) (Exim 4.60) (envelope-from ) id 1ObGVW-0004yo-1z for submit@debbugs.gnu.org; Tue, 20 Jul 2010 13:21:30 -0400 Received: from [140.186.70.92] (port=51082 helo=eggs.gnu.org) by lists.gnu.org with esmtp (Exim 4.43) id 1ObGVS-0008Ad-As for bug-coreutils@gnu.org; Tue, 20 Jul 2010 13:21:29 -0400 X-Spam-Checker-Version: SpamAssassin 3.3.1 (2010-03-16) on eggs.gnu.org X-Spam-Level: X-Spam-Status: No, score=-1.9 required=5.0 tests=BAYES_00,T_RP_MATCHES_RCVD autolearn=unavailable version=3.3.1 Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.69) (envelope-from ) id 1ObGVF-0003v5-Ur for bug-coreutils@gnu.org; Tue, 20 Jul 2010 13:21:15 -0400 Received: from kiwi.cs.ucla.edu ([131.179.128.19]:43343) by eggs.gnu.org with esmtp (Exim 4.69) (envelope-from ) id 1ObGVF-0003um-Ly for bug-coreutils@gnu.org; Tue, 20 Jul 2010 13:21:13 -0400 Received: from [131.179.64.200] (Penguin.CS.UCLA.EDU [131.179.64.200]) by kiwi.cs.ucla.edu (8.13.8+Sun/8.13.8/UCLACS-6.0) with ESMTP id o6KHLBFI021849 for ; Tue, 20 Jul 2010 10:21:11 -0700 (PDT) Message-ID: <4C45DB07.6090406@cs.ucla.edu> Date: Tue, 20 Jul 2010 10:21:11 -0700 From: Paul Eggert Organization: UCLA Computer Science Department User-Agent: Mozilla/5.0 (X11; U; Linux i686; en-US; rv:1.9.1.10) Gecko/20100527 Thunderbird/3.0.5 MIME-Version: 1.0 To: Bug Coreutils Subject: mktemp foo.XXXXXXXXXXX is not sufficiently random Content-Type: text/plain; charset=ISO-8859-1 Content-Transfer-Encoding: 7bit X-detected-operating-system: by eggs.gnu.org: Solaris 10 (beta) X-detected-operating-system: by monty-python.gnu.org: GNU/Linux 2.6, seldom 2.4 (older, 4) X-Spam-Score: -5.1 (-----) X-Debbugs-Envelope-To: submit X-BeenThere: debbugs-submit@debbugs.gnu.org X-Mailman-Version: 2.1.11 Precedence: list List-Id: List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Sender: debbugs-submit-bounces@debbugs.gnu.org Errors-To: debbugs-submit-bounces@debbugs.gnu.org X-Spam-Score: -5.1 (-----) 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 +# include # 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; ------------=_1312789263-10586-1--