On passwords and encryption

[mooseberry]

Which hashing algorithm was used on the passwords?

Out of pure curiousity amirite? 

[David]

md5.  Not that it really makes much difference.

[silverbak]

md5.  Not that it really makes much difference.

It does to me because it lets me know the overall likelihood of a hashed password being recovered due to significant differences between the hashing algorithms.

MD5 is unfortunately a very weak choice of hash compared to other contemporary options.  There really is no reason to not be using SHA-512 at this point in time and the administrators would be wise to reconsider their choice of MD5.  Anyway, we can take away the emotional fear of a hashed password being recovered by looking at the statistics:

I believe the passwords here can consist of mixed upper and lower case alphabetic characters plus numbers, so this gives 62 different possible characters.

If you had an 8 letter password that was random, the total hash space is 62^8.  To put that in to context, 62^8 = 2.18340106 × 1014 total amount of possible different passwords, which is, a relatively huge number.  (This presumes the hashes were unsalted, which would increase the hash space significantly).

If someone were to generate a hash for each password that 62^8 allows, you would need approximately 6.2 pebibytes of hard drive space to store every hash.  You would then need a supercomputer or cluster of supercomputers to find your hash in that table.  Alternatively you could generate the hashes as you go.

It is therefore unviable that any random 8 letter password could be recovered from the MD5 hash alone by civilian or corporate resources.  It could be viable for an intelligence agency to recover your password from a hash, however it would be a very expensive use of cracking resources and could take days, weeks, or even years depending on how much processing power was allocated to the recovery.  There does however always remain the possibility that the cracker gets lucky and recovers the password on the first random guess, however the odds of this happening are so low one should not concern themselves with this consideration.

If your password was weak though, either in respect of being a word in the dictionary, less than 8 letters long, or even a variant of a word in a dictionary, you have shot yourself in the foot and have dramatically reduced the time to recoverability of the password, even by motivated civilians.  I would suggest to anyone who engages in this malpractice to seek a random password generator a generate a 10 letter password and remember it.  Sure it will be hard at first, but you'll get there.

[David]

Why is using MD5 bad for this?
The only difference SHA256 would make is extra server load.

[silverbak]

Why is using MD5 bad for this?
The only difference SHA256 would make is extra server load.

Given the low loads on the server, this would most likely not be an issue.  If this were a forum that millions of people use (for example, like the World of Warcraft forum), then indeed there would be a performance difference and one would be wise to consider all options depending on your goals.  For a database with a few thousand password hashes the server would need to be absolute obsolescent junk for there to be a performance issue.  In all other cases where server performance is not a consideration, the most rational choice is to choose the solution deemed most secure.

The reason that MD5 is bad for this is because of the recoverability issue when bruteforce measures are applied.  At the moment it is presumed by some academics that very large and well financed organisations may be able in an emergency to retrieve MD5 hashes for a password of say 8 characters in a matter of days.  In 10 years time the recoverability will be an order of magnitude easier and could be in the realms of minutes to seconds if MD5 hashes are used.  Furthermore, that MD5 database that was stolen from the server will at some point later in our lifetimes, be effortlessly bruteforceable by the computers we own in our own homes.

While MD5 is ok for many purposes, SHA-256 and SHA-512 produce longer hashes that vastly increase the hash space that needs to be searched by a brute-force attack, rendering that attack vector neutralised.

An example hash for the password "tremulous":
MD5:       ec4287009e6d3ab10c9604baa5c0afa4
SHA-512: 361c5def14777236655f906624d7560ffe575591ffc5b2fcd 49e6299338fb87d5948a46a79cc777271f707fcab084cf1b5 c32cb048f1afc4ec7a943b661ee429

Each additional byte in a hash output hardens up the resistance by orders of magnitude.  Crucially, the reason for this is that although every (unsalted) password leads to a unique hash, very few hashes would lead to a password that would meet the constraints of being 8 letters long and randomised from 62 characters.  If you use MD5, the amount of 'useless' hashes is much less so you can afford computationally to just try them all anyway.  With  SHA-256 or SHA-512 the 'useless' hash space relative to any particular password is so huge it would be like trying to find a pebble in an area of water the size of the solar system.

In my view it is the difference between following up a security breach by saying "the password hash database has been stolen, change your passwords", or "the password hash database has been stolen, if your password was even remotely secure it will probably take beyond the age of the the universe to recover your password".

[gimhael]

The length of the output has no effect on a brute force attack (i.e. you try all reasonable keys). This obviously depends only on the number of possible keys.

If you talk about hash collisions, then a longer hash output reduces the probability, but given the assumed 62^8 keys and the 2^512 possible MD5 outputs, the number of key collisions within this key space is negligible (even if you consider the birthday paradox).

[silverbak]

The length of the output has no effect on a brute force attack (i.e. you try all reasonable keys). This obviously depends only on the number of possible keys.

If you talk about hash collisions, then a longer hash output reduces the probability, but given the assumed 62^8 keys and the 2^512 possible MD5 outputs, the number of key collisions within this key space is negligible (even if you consider the birthday paradox).

In my examples, I have used output length as an observable guide to key space.  The reason I propose that this is a sane utility is that a.) observable phenomena aid understanding and b.) contemporary cryptographic hash functions have a positive correlation between output length and key space.

Given the real but unlikely threat of hash collisions in algorithms like MD5 and SHA-1, I have opted not to discuss them as items worthy of concern.

To address the central aspect of your post more directly, it's a matter of what one considers 'reasonable keys'.  If you mean a dictionary attack of millions of commonly used passwords and variations of them, those hashes already exist and all one needs to do is search through the database without having to bother doing any hashing computation at all.  If 'reasonable keys' means to you random 8 letter passwords with each character derived from a pool of 62 possible combinations then that database doesn't exist because as I discussed in my original post there ~218 trillion possible passwords and the storage space would be immense.  For SHA-512 you still have the same ~218 trillion possible passwords, however a.) given the cumulative increased computational effort required to generate an SHA-512 hash vs and MD5 hash, and b.) as it's a much longer hash, you need a much larger storage space.

This should make people understand why a weak password is useless, regardless of which algorithm you choose to use.