[patch] Password salt and other algorithms support

I'd never heard of "Rainbow Tables" before, but a Google search turns up Project RainbowCrack which claims to be able to break "passwords up to 14 characters" in a few minutes. However, if you look more closely, you can see that this "few minutes" claim is based on pre-computed hash tables that are 64 GB in size and "will take several years [to] compute these tables on single computer." There's a big difference between what cryptographers refer to as "broken" and the real world!

Jacob: have a look at passcracking.com. They have a distributed rainbow table calculator for MD5 hashes that cracks passwords with up to 8 parts in less than two hours. And it's not a scientists paper, it's a real implementation. Yep, security of simple hash-stored passwords are gone. At least use a salted hash as storage, as that will make the password internally longer and so make the hashcracking with rainbow tables more complicated due to larger setup time.

if your password is 'dummy' you just add a 8 characters random string to the front. Then build the MD5 hash (or SHA-256 or SHA-512 hash - as both MD5 and SHA-1 have known algorithmic problems) on that one and store $1$<randompart>$<hash as base64> in the database. That way the hash is depended on len(password)+len(randompart) chars and additionally the same password won't be stored as the same hash, as the random part should be what it is named: random.

That's actually what linux does with MD5 passwords - the $1$ magic is to tell the system that it's MD5. You can later upgrade to better algorithms by using $2$ etc.

If you can stand a bit of Perl, here is the source of the algorithm used for linux passwords. Look for the unix_md5_crypt sub, it gives the algorithm.

This file claims to be a rewrite of the perl algorithm (or the original C algorihtm below that?) in Python and it looks identical to the perl one (and is more readable). Just remember that the salt should be some random string when you first store the password, later on you just pass in the full crypted password as salt, the function takes care of the rest.

import md5crypt

salt = 'random string of 8 chars'

crypted_password = md5crypt.md5crypt('Password', salt)

# store crypted_password in the db and later on do

if crypted_password == md5crypt.md5crypt('Password entered', crypted_password):
   # let her in

Does Django use salt for it's passwords? I think this must be a default for 1.0, it's really easy to implement and improves security considerably.

If you're going to change things like that, provide a name, don't do it anonymously

...and I need to follow my own advice

Well, here's what I pulled up. I made two new drop-in replacements for the current check_password() and set_password() in django/models/core.py A "new-style" hash looks like "<algo>$<salt>$<hash>". The implementation is pretty straightforward. I also added an updating block, which will update the old-style hash to the new one when check_password_new() returns true (thus, when we have the password available).

This code allows for newer algorithms to be added as needed with no difficulties, by simply modifying the set_password function and adding a new check to check_password.

>       def set_password(self, raw_password):
>               import sha, random
>               algo = 'sha1'
>               salt = sha.new(random.random()).hexdigest()[:5]
>               hash = sha.new(salt+raw_password).hexdigest()
>               self.password_md5 = '%s$%s$%s' % (algo, salt, hash)
>
>       def check_password(self, raw_password):
>               "Returns a boolean of whether the raw_password was correct,
>                while considering other encryption formats, and salt. A typical
>                password hash looks like <algo>$<salt>$<hash>"
>                if self.password_md5.find('$') != -1: # backward compatibility check
>                       # assume md5, hexdigests are only [0-9a-z]
>                       # We will convert the password to the new format if raw_password matches
>                       import md5
>
>                       result = (self.password_md5 == md5.new(raw_password).hexdigest())
>                       if result:
>                               self.set_password(raw_password)
>
>                       return result
>
>               else: # regular password check
>                       (algo, salt, hash) = p.split('$')
>                       if algo == 'md5':
>                               import md5
>                               return self.password_md5 == md5.new(salt+raw_password).hexdigest()
>                       elif algo == 'sha1':
>                               import sha
>                               return self.password_md5 == sha.new(salt+raw_password).hexdigest()

Let me know what you think about this.

Oops, replace the "p.split()" line above by "self.password_md5.split(". And (in yet another backwards compatibility breakage), password_md5 should be changed to password_hash or maybe just "password".

And finally, it should read "if self.password_md5.find('$') == -1". I hope that's the last horrific bug in it. How do i get an account so I can edit my older posts?

Patch for trunk/django/models/auth.py

Ok, here's the working and tested patch. I wanted to keep backwards compatibility, but since passwords were stored in a varchar(32), the new-style hashes wouldn't fit. I also changed "password_md5" to "password". I left the hash upgrader out, because of the need to replace the columns anyway would make it useless. The code I pasted before was horrid, don't look at it too much, I had a severe lack of sleep. Sorry about the whitespace changes, I am used to tabs instead of spaces in my python files.

Patch for trunk/django/models.auth.py (fixes createsuperuser)

Patch for trunk/django/models.auth.py (fixes createsuperuser, and removes whitespace error in 2nd patch)

Alternatives hash functions:

Tiger: hash value is 192 bits. http://en.wikipedia.org/wiki/Tiger_%28hash%29

Whirlpool: hash value is 512 bits. Whirlpool hash algorithm hash has been recommended by the NESSIE project. It has also been adopted by the International Organization for Standardization (ISO) and the International Electrotechnical Commission (IEC) as part of the joint ISO/IEC 10118-3 international standard. http://en.wikipedia.org/wiki/WHIRLPOOL

There is a free (under GNU Lesser GPL) library which provides a uniform interface to a large number of hash algorithms. And there is a python interface to mhash. http://mhash.sourceforge.net/

I don't think django should require any c-based libary for additional hash algorithms - it should stick to what is delivered with the python standard library. That leaves us with md5 and sha1 with sha1 being still much better than md5. And if you use salted hashes, many of the problems of pure hashes go away anyway. I would opt for using salted sha1 hashes, or at least salted md5 hashes (as are used currently with most unix systems).

Please strongly consider SHA1 + salt.

I support Hugo's and John's opinion: SHA1 + salt.

The patch I submitted makes $ANY_ALGO_YOU_WANT + salt possible. Today this is SHA1 (mostly because of builtin-ness), but by making the algorithm name a part of the hash, you can provide multi-algorithm support and backwards compatibility can be mantained, with algorithm migration made transparent to the users, whose hashes get updated when they successfully log in. I think this (or something else that achieves the same effect) should go in before 1.0 because the User model column has to be changed in order to allow for longer hashes.

Bruce Schneier: "Don't use SHA-1 for anything new, and start moving away from it as soon as possible."

http://www.schneier.com/blog/archives/2005/10/nist_hash_works_2.html

For info -- this MD5 collision generator apparantly averages 45 minutes to find a collision on a 1.6MHz P4 machine.

http://www.stachliu.com.nyud.net:8090/collisions.html

(In [1327]) Fixed #273 -- BACKWARDS-INCOMPATIBLE CHANGE -- Changed auth.User.password field to add support for other password encryption algorithms. Renamed password_md5 to password and changed field length from 32 to 128. See http://code.djangoproject.com/wiki/BackwardsIncompatibleChanges for upgrade information

Milestone Version 1.0 deleted