As any C/C++ programmer knows, just using rand() won’t return random numbers, and not even pseudo-random numbers, as each time the program runs the same random number 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 number sequence if needed for some reason, if the seed used to create it is known.
To randomize the random number generator, most programmers pass to srand() the time in seconds since the 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 just isn’t random enough. Let’s consider a program with a very fast runtime that 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 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 generated for himself a strong 8-character-long alphanumeric password. Joe thought that his password was secure and that even if somebody knew its length, they would need to try 62^8=218,340,105,584,896 combinations in order to crack it. Now Sally wants to crack Joe’s “secure” password. Instead of attacking the password directly, 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 now get 86,400 different combinations of the 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 the password generator in a better way. We also use the microseconds since the epoch. The function gettimeofday() (defined in sys/time.h) returns both the seconds since the epoch and the microseconds. So we 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 access to the source code I wrote about, she will still have to check 600,000,000 combinations. Under these conditions, 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 the 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.
Thanks for the info dude! That’s exactly what I was looking for.
Thank you so much mate! That’s my assignment today!
Based on reading the man pages for rand() (man 3 rand) and random (man 4 random), I came up with this. Thoughts?
// Generate random seedFILE * rand_fd;
rand_fd = fopen("/dev/random", "r");
if (rand_fd != 0) {
printf("Random device opened for reading.\n");
} else {
exit(EXIT_FAILURE);
}
uint *seed = (uint *) malloc(50 * sizeof(uint));
fread(seed, sizeof(uint), 50, rand_fd);
srand(*seed);
fclose(rand_fd);
JustMe, this seems to be a good idea, however it is not recommended to use /dev/random for such activity, because reading from it is normally blocking, and returns -1 if there aren’t enough bytes in the entropy pool, unlike /dev/urandom, that when the entropy is not sufficient, uses a pseudorandom number generator to create the requested bytes. It’s also recommended to read as less bytes from entropy pool as you can.
My solution(based on yours):
#include <sys/types.h>
#include <sys/stat.h>
#include <fcntl.h>
#include <unistd.h>
#include <stdio.h>
#include <stdlib.h>
#define SSIZE 8
typedef unsigned int uint;
uint* genrs()
{
int fd = open(“/dev/urandom”, O_RDWR);
uint* seed = (uint)malloc(sizeof(seed[0])SSIZE);
read(fd, seed, SSIZE);return seed;
}
// Test
int main(int argc, char** argv)
{
int LIM = 5;
for(int i=0; i<LIM; ++i)
{
srand(*genrs());
printf(“Random number: %d\n”, rand());
}
return 0;
}
(*-s went missing on posting)
uint* seed = (uint * )malloc(sizeof(seed[0]) * SSIZE);