I often program in the Django web framework. Recently, I became interested in how it tracks the information of users that have already logged in.
By default, Django uses a cookie named
sessionid and contains a 32 character string built from lowercase letters and digits, or 36 possible characters. Therefore, there are a total of 3632 or 63,340,286,662,973,277,706,162,286,946,811,886,609,896,461,828,096 possibilities for your session key. This number is between 2165 and 2166 and is slightly larger than the possibilities produced by a good cryptographic hash.
But what are the chances that two randomly generated session keys in a large collection of session keys will be equal? The solution to this problem is actually counter-intuitive and is summarized in a similar problem:
The Birthday Problem is to find the probability that, in a group of N people, there is at least one pair of people who have the same birthday. Birthday Problem
While some people estimate this number to be over 100,000, it is much less than that, since to determine a “collision” of birthdays we have to compare not just your birthday to everyone, but everybody’s birthday to each other.
Turns out, there only needs to be 23 people before the chance of two of them sharing a birthday is greater than 50%.
So how many sessions have to exist before a key collision becomes likely? We can estimate this value using the equation:
Q(H) = √(π / 2 * H)
H is the number of possibilities. In our case,
H is 3632, the number of unique sessions, giving a result of 9.97 * 1024 or about 283.
That’s still 10 septillion sessions before our first collision is likely.