Page 1 of 1

session id

Posted: Thu Jul 28, 2005 6:43 pm
by nincha
whats the possibilty of generating the same session id number twice?

Possibilty

Posted: Fri Jul 29, 2005 9:50 am
by AnarKy
Is this possible?
I don't think that I have encountered this....

Posted: Fri Jul 29, 2005 10:33 am
by Todd_Z
i think they are 32 bit encryptions... so 1 in 2^32? Don't quote me on that

Posted: Fri Jul 29, 2005 10:35 am
by Roja
Yes, it is (in theory) possible.

Getting a specific answer is very messy, because it depends on the platform you are on (entropy on windows, linux, and other unixes are handled differently).

It also depends on the time functions for the platform, and their accuracy.

Beyond those, it *also* depends on numerous other issues (Process ID randomness, etc).

I'll take the easy, general route and say that a session id is 32 bits, so the potential recurrance is something like one in 2,147,483,647.

Again, that is ignoring predicatability in md5, entropy, time, and other issues. It's not a very accurate estimate, but its a starting point.

Posted: Fri Jul 29, 2005 10:37 am
by nielsene
Roja wrote: I'll take the easy, general route and say that a session id is 32 bits, so the potential recurrance is something like one in 2,147,483,647.

Again, that is ignoring predicatability in md5, entropy, time, and other issues. It's not a very accurate estimate, but its a starting point.
Well approaching it as a birthday collision problem would great increase the probability of collision. I wonder.... what load is required for P(c)=.5?

Anyone have access to a machine with really good fractional accuracy?

P(n)= 1 - [(2^(32)-1)!/(2^(32)-1-n)!*(2^(32)-1)^n]

Loop from one to 2^20th ish?

Posted: Fri Jul 29, 2005 10:43 am
by pickle
As you've read, the likelihood is extremely rare. So, you can handle it in two ways - just don't worry about a collision and call everyone that has a problem crazy :twisted: , or you can put your id generation in a do...while loop:

Code: Select all

do
{
  generate_session_id();
  determine_if_it_exists_already();
}
while($generated_id_already_exists)

Posted: Fri Jul 29, 2005 2:10 pm
by nielsene
Well I managed to run the modified birthday collision calculation through to 31 simultaneous sessions before the numbers overfulled.

With 31 simultaneous sessions, the chance of a collision (assuming more or less random population of the session id space) is only 1.15e-07 or about 1 in ten million. or a reduction of all 3 magnitudes. I'm trying to find a way to run the match for upto say 100 sessions for moderate load sites....


[Edit: Just got a revised version to run up to 100,000 entries.
50% chance of a collision happens around 65,000 simultaneous sessions. (around 70% chance at 100K). So not too much of a worry for most of us, but I wonder how if the Amazon's of the world have switched to using a doubled token to reach 2^64 space....]

Posted: Fri Jul 29, 2005 6:47 pm
by timvw
Somewhat amazon.com seems to use a numeric sessionid like xxx-xxxxxxx-xxxxxxx. (17^10)


But there are other sites that seem to use a loadbalancer like: visit http://www.example.com and then you are redirected to www1.example.com, or www9.example.com. In this case each server has it's own set of session_ids so it reduces the propability.

Posted: Fri Jul 29, 2005 8:09 pm
by nielsene
Well two comments:
as shiflett pointed out in the companion thread I strarted in the Security forum, the earlier comment about the session id being 32 bit is completely false. Its 128 bit (32 characters long using the stadard 4 bit per character encoding that PHP uses. At 128 bit the probability, even properly acccounting for the birthday collision situation is extremely small.

Second, most load-balanced servers are using a database session management tool so that it doesnt matter which server handles a given uses on each subseaquent request. Thus they must still share the same session space. The server's do not have their own session_ids. However, as the first paragraph correction indicates, its not a problem.