session id

Ye' old general discussion board. Basically, for everything that isn't covered elsewhere. Come here to shoot the breeze, shoot your mouth off, or whatever suits your fancy.
This forum is not for asking programming related questions.

Moderator: General Moderators

Post Reply
nincha
Forum Contributor
Posts: 191
Joined: Fri Mar 28, 2003 12:30 pm
Location: CA, USA

session id

Post by nincha »

whats the possibilty of generating the same session id number twice?
User avatar
AnarKy
Forum Contributor
Posts: 119
Joined: Tue Nov 02, 2004 1:49 am
Location: South Africa

Possibilty

Post by AnarKy »

Is this possible?
I don't think that I have encountered this....
User avatar
Todd_Z
Forum Regular
Posts: 708
Joined: Thu Nov 25, 2004 9:53 pm
Location: U Michigan

Post by Todd_Z »

i think they are 32 bit encryptions... so 1 in 2^32? Don't quote me on that
Roja
Tutorials Group
Posts: 2692
Joined: Sun Jan 04, 2004 10:30 pm

Post 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.
User avatar
nielsene
DevNet Resident
Posts: 1834
Joined: Fri Aug 16, 2002 8:57 am
Location: Watertown, MA

Post 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?
User avatar
pickle
Briney Mod
Posts: 6445
Joined: Mon Jan 19, 2004 6:11 pm
Location: 53.01N x 112.48W
Contact:

Post 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)
Real programmers don't comment their code. If it was hard to write, it should be hard to understand.
User avatar
nielsene
DevNet Resident
Posts: 1834
Joined: Fri Aug 16, 2002 8:57 am
Location: Watertown, MA

Post 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....]
timvw
DevNet Master
Posts: 4897
Joined: Mon Jan 19, 2004 11:11 pm
Location: Leuven, Belgium

Post 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.
User avatar
nielsene
DevNet Resident
Posts: 1834
Joined: Fri Aug 16, 2002 8:57 am
Location: Watertown, MA

Post 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.
Post Reply