php.net |  support |  documentation |  report a bug |  advanced search |  search howto |  statistics |  random bug |  login
Bug #12530 Shuffle shouldn't use the least significant bit of rand()
Submitted: 2001-08-02 07:24 UTC Modified: 2002-07-03 19:07 UTC
From: sulka at sulake dot com Assigned:
Status: Closed Package: Arrays related
PHP Version: 4.0.6 OS: Solaris (most unices)
Private report: No CVE-ID: None
 [2001-08-02 07:24 UTC] sulka at sulake dot com
In ext/standard/array.c, the sorting algorithm of shuffle 
is defined as

(php_rand() % 2) ? 1 : -1

This is fine for rand algorithms in which all bits are 
random but with Solaris and other unices this is not so. 
Quoting man random():

"The difference is that rand(3C) produces  a  much  less  
random sequence-in fact, the low dozen bits generated by 
rand go through a cyclic pattern. All the bits generated by 
random() are usable."

This is not true however - the LSB of random() calls are 
predictable on some systems.

You can verify if your system is affected by running this:

<?PHP
$a = array();
$b = array();

for($i=0; $i<1000; $i++)  // iterate 1000 times
	{
	$foo = "";
	// initialize random seq with new seed
	srand ($i); 
	// create a string with the LSB of first 24 random numbers
	for($j=0; $j<24; $j++) {
		$c = rand();
		// $c = rand(0,32000); works on all systems
		// store the random number so we can check how many 
different
		// numbers were really generated
		$b[$c]= 1;
		// append the least signicant bit to the string
		$foo .= ($c % 2);
		}
	// store the parity string
	$a[$foo]= 1;
	}

echo "Parity string count: " . count($a), "<BR>";
echo "Random number count: " . count($b), "<BR>";
?>

If the counts are 1000/24000 you're fine. Affected systems 
I've tried this on return 4/24000.

Proposed fix: change shuffle to call PHP's own rand 
function with limits, ie, rand(0,32000). This introduces 
randomness into the LSB and fixes shuffle.

Patches

Add a Patch

Pull Requests

Add a Pull Request

History

AllCommentsChangesGit/SVN commitsRelated reports
 [2001-08-04 18:12 UTC] andy@php.net
reclassified
 [2002-04-27 15:53 UTC] jimw@php.net
this is a bug, not a feature request.
 [2002-07-03 19:07 UTC] eru@php.net
This bug has been fixed in CVS. You can grab a snapshot of the
CVS version at http://snaps.php.net/. In case this was a documentation 
problem, the fix will show up soon at http://www.php.net/manual/.
In case this was a PHP.net website problem, the change will show
up on the PHP.net site and on the mirror sites.
Thank you for the report, and for helping us make PHP better.


 
PHP Copyright © 2001-2024 The PHP Group
All rights reserved.
Last updated: Thu Mar 28 12:01:27 2024 UTC