PlayNoEvil pointed to an interesting old story about analysing a seeming innocent-looking shuffle algorithm for Texas Holdem’. Makes for a very good read. And proves that the behavior of most code is not fundamentally understood even by the person who wrote the code.
This reminded me of an old bug I reported on PHP, which was causing similar huge security issues on a number of website, the owners of whom ended up never knowing they had had a problem. The issues was that a number of open source PHP-based applications used the following algorithm (which was also suggested in PHP website) to generate random passwords who registered or wanted their passwords reset:
password = “”;
$array = array(‘a’,’b’,’c’,’d’,’e’,’f’,’g’,’h’,’i’,’j’,’k’,’l’,’m’,’ n’,’o’,’p’,’q’,’r’,’s’,’t’,’u’,’v’,’w’,’x’,’y’,’z’,0,1,2,4, 5,6,7,8,9);
shuffle(&$array);
for ($i=0; $i<6; $i++) { $password .= $array[$i]; }
Looks innocent, right? An array of wanted characters is shuffled to random order and the first six are concatenated to form the new password. The issue here is, the programmer assumes the shuffle is actually random. And on some systems, it was, some it wasn’t.
The c-language implementation of PHP’s shuffle sorting at the time was the following:
(php_rand() % 2) ? 1 : -1
where php_rand was actually using the platform’s native rand() call. The cunning reader notices the algorithm really only uses the least significant bit of the generated random number, and hence relies on the stream of least significant bits being random. This is the point where the chain of assumptions failed.
On Solaris and Linux of the time (and maybe still!), the least significant bit of the generated random numbers wasn’t random at all. If you generate a sequence of random numbers on these systems with rand(), the LSB always follows one of the following four patterns, depending on which point in the sequence in the grand scheme of things you start iterating: 1001, 0011, 0110 or 1100.
Now where does this leave our password algorithm? The answer is, on the affected systems the above algorithm only ever generated four different passwords, because there only were four different shuffles. These four looked random, but weren’t. And any user could generate the four combinations by just requesting a password reset a few times, after which you could request the password of someone else be reset.
To resolve the issue, PHP was changed to use an algorithm that generates a more random sequence of LSB’s. One could also point that sending passwords to users when they register or want one reset is exceedingly stupid, but I’ll leave that as an exercise to the reader. I’d be interested to know how many pieces of software still use the LSB from rand(), though.
Update: reading what I wrote made me think the story is a bit strange, coming from someone working as a concept designer. But hey, knowing a broad range of stuff can’t hurt.