As any C/C++ programmer know, just using rand() won’t return random-numbers, and not even pseudo random numbers, as each time the program will run the same random numbers sequence will be generated. To overcome this you seed the random number generator of rand() with a number that creates a different random number sequence. For every seed there is a corresponding random number sequence, and for the same seed the same sequence will be generated every time. This can be used to recreate a random numbers sequence if needed for some reason if the seed used to create it is known.
To randomize the random numbers generator, most programmers pass to strand() the time in seconds since epoch, e.g. they do something like this:
srand( (unsigned)time(NULL) );
It’s a very common way to seed the random number generator, and it’s also shown in many books that teach programming. This may look sufficient for most uses (and it does) but nonetheless it’s also used many times where it’s just isn’t random enough. Let’s consider a program with a very fast runtime which depends on the above mentioned method for seeding the random number generator. If someone wrote a script that runs this program in a loop, causing the program to run several times in a second, the same random number sequence will be generated multiple times as the same seed was used. One can see that this behavior may not be what was intended.
Another problem might come up if we will use this method for let’s say password generation. Let’s say Joe wrote a small program that seeds the password generator in the above mentioned way and now generated for himself a strong 8 character long alphanumeric password. Joe thought that his password was secured and that even is somebody knew its length they will need to try 62^8=218,340,105,584,896 combinations in order to crack it. Now Sally want to crack Joe’s “secure” password. Instead of attacking directly on the password Sally will attack the password generator. Sally can easily know the day Joe created the password, and we shall assume Sally got access to the password generator’s source code Joe used. During the day Joe generated his password, the time(NULL) function returned 86400 different values. Let’s also assume that Sally knows the length of Joe’s password. Sally just modifies the password generator and seeds the random number generator with each one of the possible values of time(). Sally will get now 86,400 different combinations of password, and one of them is guaranteed to be Joe’s. If you think 86400 is many, remember that Sally went down from 218,340,105,584,896 possible combinations and under very weak assumptions, if sally knew the exact 10 minutes in which Joe generated the password (this isn’t a very hard thing to find out) the number will drop to only 600 combinations.
So here is a way to seed in a better way the password generator. We also use the microseconds since epoch. The function
gettimeofday() (defined in
sys/time.h) returns both the seconds since epoch and the microseconds. So will shall use both values to seed the random number generator.
timeval t1; gettimeofday(&t1, NULL); srand(t1.tv_usec * t1.tv_sec);
Let’s see how this change influences our test cases. Now when running the program in a loop the program will have to run several times in the same microsecond in order to use the same random number sequence. This is very unlikely (if even possible on current hardware) so it can be safely assumed that the first problem is solved.
Now for the password generation problem. If Joe uses this method to seed the random number generator, he multiplies by 1,000,000 the number of possible seed values given in the same time frame. That means that even if Sally knows the exact 10 minutes in which Joe generated his password, and has the access to the source code I wrote about, she will still have to check 600,000,000. Under this conditions the password the password still can be cracked, but nonetheless it will be much harder to do.
So as you saw seeding the random number generator with only the seconds since epoch, gives very poor results. This can be relatively easily solved, to some extent, by also using the microseconds returned by
gettimeofday(). Although I’ve used a Linux specific function to do so, there are alternative ways to achieve the exact same method under Windows.