Django session key generation flawed

secret_key isn't useless - it's needed. Because randoms aren't real random and so might be predictable. But I agree that adding more variable data to the stuff to build digests on would be in order to prevent duplicates. But I would opt for adding time.ctime() to the mix instead of yet another non-random random number, as that would be much better in preventing duplicates.

Whatever the solution hugo, it'd be better than what is there currently. For some reason the generator was generating duplicate keys every couple seconds (I have 30000 people online on my site so they generate a lot of 'logins') for the SECRET_KEY + one random number in the original version of the cookie generator.

And yeah secret_key can perhaps help but I don't really think anyone would predict two pseudo-random numbers and the current time including milliseconds.

Hmm. Actually the get_new_session_key function checks the generated session key for uniqueness, before returning. Ok, it doesn't register a new session key right away with the database, so another thread/process _can_ produce the same key, if the keys aren't actually used for storing stuff in the database (and since the system won't know what keys it handed out, it will happily mix sessions from different users). This get's worse after some time, of course.

After checking with the session middleware source (that's the only place where get_new_session_key is used), I still wonder how that actually can lead to problems - because the session_key is only generated when the session is sent out - and in those cases it will be stored in the database, and so shouldn't ever be regenerated (as get_new_session_key explicitely checks for that).

Anyway, I wrote a short test script:

from django.models.core.sessions import get_new_session_key

h = {}

for i in range(0,999999):
    k = get_new_session_key()
    if h.has_key(k):
        print 'dupliate', k
    h[k] = True
    if i % 1000 == 0:
        print 'generated', i

After around 200000 generated keys, the sytem starts to produce more and more duplicates. This is to be expected, since the random number generator isn't really a good idea to solely base those session keys on. And since the test script doesn't register new session keys, it will happily produce duplicates.

After changing the algorithm to the following:

sessin_key = md5.new(str(random.randint(0, sys.maxint - 1)) + str(random.randint(0, sys.maxint - 1)) + SECRET_KEY).hexdigest()

The system ran fine without dupliates to far higher numbers - I stopped at one million (and the hash took 0.5 GB up to then ;-) ). So it looks much better and I think it's ok to just use the double random number (I actually would have expected a much worse behaviour of the random number generator - seems they did some good work on that one).

Of course, if there are ever session_keys reused in some application without actually storing them in the database, you still will get duplicates after some time - but it's at least much better than with the original algorithm.

I am still curious why your site produces session keys that aren't registered with the database, though. Do you do anything special with session keys that's outside the standard stuff? It might be that different processes/threads produce the same random number, of course. But that doesn't really sound likely (but of course, as allways, how stuff sound isn't necessarily how stuff is ...)

(In [1851]) fixes #1180 - added another random number to the get_new_session_key function to prevent early duplicates

Please reopen if you still have the duplication problem - eventually we would have to throw in some more data to prevent duplicates (time, pid are two that come to mind). It's hard to reproduce a highly parallel production environment in test settings, so it's better to get direct feedback from the production system.

One thing that I did find on the random number generator in Python: it isn't thread safe, threads might expose duplicate random numbers. Could that be the case in your system? Are you running a multi-threaded environment or a multi-processed one?

Usually a timestamp is always part of the input data (at least all session key generators i have seen so far). Random generators can't be random, only pseudo random, if they do not messure some hardware parameters like fan speed or better use a noise generator. I suggest adding a time.ctime() to the input as well.

As written, I have run tests to see what the duplicate-rate of that is. Actually the random generator of Python has a period of over 6 billion (according to the doc) and we only take a rather small part of that (up to sys.maxint, which usually is half of 32bit). That was the problem with the former approach: the random numbers in the range of 0..maxint just repeated too often, now there needs to be a pair of random numbers in the range 0..maxint (out of a random stream with period of over 6 billion) to produce a dupliacte. time.ctime (or time.time) can be added if we really still have duplication happening. And that's best discovered with wojtek's site, since I don't know of any other site with such a heavy traffic :-)

My concern is more about session hijacking than the randomness of the session key. Pseudo ramdon generators need some sort of seed which they increase or change after every returned value. When the seed is not stored when the machine reboots, or the generator is recreated, the returned random numbers are the same every run. I havn't looked at the radom module which seed they use, but adding a timestamp make such attacks much much harder combined with a private site key, nearly impossible.

You can't guess a session key where part of the key generation process is a secret that you don't know. We don't use only random numbers, we use random numbers plus the secret key. And the latter isn't known to the end user, so he can't guess the next key, even if he succeeds to find the exact point in time of a random number generator with more than 6 billion steps in one round ...

Actually adding the time isn't really that more secure than without - although the python library returns milliseconds, depending on the system it might actually just fake those and in reality return times of a much lower stepping. And in those cases, if the server is synchronized to some outside time server, it might even be feasible to guess the time :-) (although admittedly it's near impossible to guess the time on systems with high resolution timers).

That's not to say that it isn't a good idea to add the time - wether or not they add it is up to the core devs. I only (hopefully) fixed the "duplication happens too soon" problem. How they see the likelihood of guessing the next session key with the current algorithm is up to adrian and jacob - I only applied as less change as possible to fix the given problem. I am usually a bit reluctant to add more if the problem is already fixed. It's not _my_ source ;-)

I know that there is a secret key. That's very usefull. The idea which poped in my mind was, that you use a script to collect some session keys for example. When the server restarts, the chances that these keys you saved before maight be generated again could be higher than random guesses, which is nearly impossible due the lenght of the md5. Adding a timestamp fixes this, because the timestamp is always different. It's not that you could recalculate the key, md5 is a crypto hash which makes it impossible to guess what was going in.

This discussion really should take place on the list, not on the ticket. (yes, I am guilty of that, too).

You may have a look at the GUID recipe in Python Cookbook for solving this issue:

http://aspn.activestate.com/ASPN/Cookbook/Python/Recipe/163604

I tested the GUID recipe with md5 and secret key on 2 computers generating 10 mio keys each at the same time. The have not been any duplicates.

So I think this piece of code in django/models/core.py:

while 1:
  session_key = md5.new(str(random.randint(0, sys.maxint - 1)) + SECRET_KEY).hexdigest()
  try:
    get_object(session_key__exact=session_key)
  except SessionDoesNotExist:
    break
  return session_key

may be replaced with:

session_key = md5.new(GUID.generate() + SECRET_KEY).hexdigest()

Benefit: unique without the need to access the database, really fast (more than 20.000 session key per second)

Drawback: Additional third party dependency.

Please take the discussion to the django-developer list.

Guys

I've got multiple reports from users that they were able by some chance to get to another user's session so I think the problem still exists and I can explain why: it exists 'by design' I've released a 'newsession' module with is compatible to current sessions and has no such problem.

Gonna put a patch here

Patch is introduced here: #3716

#3716 spawned some fairly intensive discussion

Here's a recap -

ubernostrum says the problem appears to be this:

1. User A visits the site and server process A generates a session
key, checks the database to see whether that key is in use, finds that
it is not, and assigns that key to User A.
2. At or around the same time, User B visits the site and server
process B generates the same session key (probably because both
processes started out with the same seed for Python's RNG). Because
User A's session has not yet been serialized and stored, server
process B also finds that the key is not in use, and assigns that key
to User B.
3. At some later point, both sessions are serialized and stored; the
first one executes an INSERT --- because Django does not distinguish
INSERT from UPDATE for purposes of a model's 'save' method -- and the
second executes an UPDATE on that row. Assume for the moment that User
B's session gets the INSERT and User A's session gets the UPDATE.
4. When User B comes back to the site, he finds that the Django
session framework thinks he is User A. 

There are several possible approaches here:

1. Manually seeding the RNG with a value unique to the server process,
or to the request, would move the probability of key collision closer
to what it "should" be, thus dramatically reducing the problem.
2. Changing the session framework's behavior so that it stores the
session in the database as soon as it finds an unused key (e.g., by
looping with 'get_or_create' until it gets a new object) would
drastically reduce the odds of two independent processes with the same
key each thinking that their key is unused.
3. Changing Django's ORM to separate INSERT from UPDATE would make it
impossible for two processes to each execute a 'save' on sessions with
the same key and think that they each created a new row.

Options 1 and 2 are relatively easy and could be implemented quickly.
Option 3 is attractive, but would be harder to do. 

Benjamin Slavin suggests:

Do we really need to re-seed the RNG?  What if we did something like:
session_key = md5.new("%x%s%s" % (random.getrandbits(64),
datetime.datetime.utcnow(), settings.SECRET_KEY)).hexdigest()

datetime.datetime.utcnow could be replaced with whatever would be used
for the seed.  You could include os.getpid if you desire. 

The general consensus is that this should be addressed after 0.96 is released, and the patch in #3716 from Anton Khalikov is a good starting point.

(In [4771]) Reduced the chances of session object collision. The window of opportunity is now about five Python instructions in get_or_create(). This doesn't guarantee no collisions, but should fix many occurrences. Refs #1180.

Replying to mtredinnick:

(In [4771]) Reduced the chances of session object collision. The window of opportunity is now about five Python instructions in get_or_create(). This doesn't guarantee no collisions, but should fix many occurrences. Refs #1180.

I suggest few more changes

models.py (code for the save function in Session Manager)

    def save(self, session_key, session_dict, expire_date):
        "Prior to a call to this function, the session key will be created/stored"
        try:
            s = self.get(session_key=session_key)
        except ObjectDoesNotExist:
            raise   #Caller should handle the exception

        if session_dict:
            s.session_data=self.encode(session_dict)
            s.expire_date=expire_date
            s.save()
        else:
            s.delete() # Clear sessions with no data.
            s=None

        return s

models.py (session_key is nolong a primary key)

session_key = models.CharField(_('session key'), maxlength=40, unique=True)

and finally in middleware.py (added an error check in process_response)

    if new_session is not None:
        response.set_cookie(settings.SESSION_COOKIE_NAME, session_key,
                            max_age=max_age, expires=expires, domain=settings.SESSION_COOKIE_DOMAIN)

This would permanently avoid collisions. It however introduces the problem of a ProgrammingError? exception incase of collision. For that there does not seem to be a better solution around there seems to be no better solution than to lock the session table prior to updation.

I have also refined the save method in Session Manager and added an error check in the middleware.

We recently got into problem when using Django over FastCGI. It appears that the Python's own random number generator is initialized with random seed just before starting to fork processes. This way all fcgi processes got the "same" random number generator. The possibility to get duplicates rose so high, that we had to add additionally PID value to session key generation salt.

Does session_key field necessarily needs to be a PK? If we change Session model to have a plain auto-incremented integer primary key and use unique=True for session_key field, collisions can be avoided completely since there will be no chance to INSERT two different sessions with equal session keys.

Replying to Densetsu no Ero-sennin <densetsu.no.ero.sennin@gmail.com>:

Does session_key field necessarily needs to be a PK? If we change Session model to have a plain auto-incremented integer primary key and use unique=True for session_key field, collisions can be avoided completely since there will be no chance to INSERT two different sessions with equal session keys.

Actually there is, because some databases (SQLite) can re-use primary key values if rows have been deleted from the table, which means it's possible for two users get the same "incremented" primary key value on their sessions.

it's possible for two users get the same "incremented" primary key value on their sessions

Can't agree with that. Primary keys are unique by definition, even if they are reused somehow.

But anyway, that does not really matter for us. We just need to impose a UNIQUE constraint on session_key, which would guarantee that all sessions in the DB have different keys. Unfortunately, Django tries to be smart and treats primary key fields specially. So when we save() a new session with a newly created key and another session with this key already exists, Django happily runs UPDATE instead of simply trying to INSERT and failing. What we need is a way to tell Django not to UPDATE here (save(update=False) or something like that). If that's not possible or difficult to implement, we can just create a separate PK field and add unique=True constraint to session_key field. Any solution will do.

Not sure if this is still and issue, but since it is still open I figured I would throw my hat in the mix on this.

I am using uuid, which follows http://www.faqs.org/rfcs/rfc4122.html, to generate the session_key.

the uuid file fall back for python 2.3 & 2.4. I put it in django/utils