http://qs1969.pair.com?node_id=844411


in reply to Re^3: Randomness encountered with CGI Session
in thread Randomness encountered with CGI Session

CGI::Session with default options uses pseudorandom numbers to generate a unique ID. The actual code from v4.42 in CGI::Session::ID::md5 is ...

my $md5 = new Digest::MD5(); $md5->add($$ , time() , rand(time) ); return $md5->hexdigest();

... and that looks just wrong. The process ID in $$ is not very random, neither is the current time from time(). And limiting the output of rand() to the value of time does not make any sense. Perhaps this was meant to initialise the pseudo-random number generator with the current time, but it doesn't, and that would be a bad idea. Using MD5 reduces the entropy even further.

There is no piece of code in that ID generator that guarantees that the returned ID is really a unique identifier, actually the three lines shown above are the only relevant code in the CGI::Session::ID::md5 module.

The code can generate colliding IDs, but I have no idea how likely that is. One should be able to calculate how many of the 2128 possible MD5 values can be generated with this code. $$ is probably defined as 32 bit integer, with the topmost 16 or 17 Bit being constantly 0 on most systems, effectively using 15 bits, time() uses 31 bits (32 bit signed integer defined to be >=0) with most of the the most significant bits being constant for years, and rand() returns a double - 64 Bit. So the input to MD5 is just 15+31+64=110 bits for the entire ctime definition from 1970 to 2038. For one day, time() changes only 86400 times, so time() gives only 17 varying bits, not 31. MD5 input is thus only 15+17+64=96 bits. Unlike the pseudo-random number generator, which also depends on its previous state, MD5 depends only on its input. Given 296 different input values, MD5 can generate at most 296 different output values. Due to the hashing, there will actually be fewer distinct output values. For one minute, time() changes 60 times, giving just 6 varying bits, MD5 input will be reduced to 15+6+64=85 bits, still assuming that the PID changes wildly with each request , and rand() returns real white noise. For one second, during which modern hardware can still process more than 109 instructions, time changes just one bit, so MD5 input is 80 bits. The process ID is usually incremented until it hits an arbitary upper limit defined in the OS kernel, then it starts again at the lowest free ID. For a sequence of requests to a webserver running a CGI for each request, it is quite safe to assume that the PID will increment by one or a very low number most of the times. So PID doesn't give 15 bits, but just one, two or perhaps four bits. MD5 input for one second is thus not more than 4+1+64=69 bits.

Now for rand(). I assumed 64 bits, i.e. sizeof(double). But that may be wrong. I don't know how rand() is implemented, and I'm too lazy to search. Assuming 32 bit integer arithmetics, rand() will perhaps generate only 232 different values, further reducing MD5 input to 4+1+32=37 bits. With Strawberry Perl 5.10.0, the actual number of bits (perl -V:randbits) is just 15, while perl 5.10.0 on a 32 bit Slackware 13.0 gives 48 bits. So, with that Strawberry Perl, MD5 input would be just 20 bits.

Note that the ID does not depend at all on the incoming request. It only depends on the process ID (which is typically a regularily overflowing unsigned integer), the current time, and the state of the pseudo-random number generator.


CGI::Session::ID::incr uses a flock()ed file to return a constantly increased ID, using this code:

my $IDFile = $args->{IDFile} or croak "Don't know where to store t +he id"; my $IDIncr = $args->{IDIncr} || 1; my $IDInit = $args->{IDInit} || 0; sysopen(FH, $IDFile, O_RDWR|O_CREAT, 0666) or return $self->set_er +ror("Couldn't open IDFile=>$IDFile: $!"); flock(FH, LOCK_EX) or return $self->set_error("Couldn't lock IDFil +e=>$IDFile: $!"); my $ID = <FH> || $IDInit; seek(FH, 0, 0) or return $self->set_error("Couldn't seek IDFile=>$ +IDFile: $!"); truncate(FH, 0) or return $self->set_error("Couldn't truncate IDFi +le=>$IDFile: $!"); $ID += $IDIncr; print FH $ID; close(FH) or return $self->set_error("Couldn't close IDFile=>$IDFi +le: $!"); return $ID;

Note that the caller is responsible for error checking here, but that's not the problem. The IDs are easily guessable, making the script vulnerable. As a side note, the code should not use FH, but my $fh instead, so that the file is properly unlocked and closed when an error occurs.


CGI::Session::ID::static returns a constant ID supplied by the caller. The documentation shows only one example, $session = new CGI::Session("id:static", $ENV{REMOTE_ADDR});. This is even worse outside a controlled network. Many users work behind proxies, so you may have several thousand users with the same REMOTE_ADDR (of the proxy). AOL once hat a set of proxies configured in a way that each new request goes through a random proxy, so the REMOTE_ADDR was not constant for a user, and it was shared by all AOL users. I don't know if this setup is still in use, and I don't care.


From what I saw studying the CGI::Session code, there is no secure and reliable ID generator available. The documentation has absolutely no information about how secure and how reliable each of the generators is, and which generator to use in which situation. That's very sad.

A quick look at the storage drivers CGI::Session::Driver::DBI (base class), CGI::Session::Driver::mysql, CGI::Session::PostgreSQL, and CGI::Session::Driver::sqlite shows another nasty surprise: While all of those databases provide at least one way to generate a reliable, unique ID, CGI::Session does not use this advantage. Instead, it relies on the problematic ID generators shown above.

Alexander

--
Today I will gladly share my knowledge and experience, for there are no sweeter words than "I told you so". ;-)