Salts won't give you that much greater security these days. Password-cracking GPGPU hardware is already well into the consumer domain. Using a pair of AMD's HD 5970, you can get cranking to just over 1bn SHA256 hashes/s.
There's some remarkably complete rainbow tables out there for MD5... Last time I heard any details, every 11char string and every combination of dictionary words including letter/number substitutions out to 16chars is now just a lookup away...
Any password small enough to remember is probably vulnerable if stored as an unsalted MD5 hash.
From the available info there were indeed simple passwords and password reuse between systems of different security levels.
openssl speed md5
The 'numbers' are in 1000s of bytes per second processed.
type 16 bytes 64 bytes 256 bytes 1024 bytes 8192 bytes
md5 23895.04k 85345.30k 231322.03k 412608.40k 546306.56k
If you look at the openssl numbers from my workstation, you'll find I can generate hashes for 1.5 million 16 byte passwords per second. The nice part about rainbow tables is that they are easy to compute in a distributed nature. Take a couple hundred EC2 boxes and you can generate HUGE tables, if you're smart with how you use S3 you can write the tables directly to S3. Cracking unsalted passwords is a very simple time/memory trade off. Given the issues with MD5 with a good math background you might even be able to reverse the password. (eg. create a known password that computes to the same hash)
If you got creative with some FPGAs or GPUs you could do far better.
I think you may be thinking bits not bytes. The typical ASCII/UTF-8 char is 8 bits. UTF-16 doesn't really get used outside of Windows, I'm unsure if Windows hashes on char or wchar. I don't think anything uses UTF-32 other than to make string searching simple in regard to texts containing characters outside the BMP.
Please don't downvote the OP, it's a simple mistake.
Regarding what I mean by 16 byte passwords, MD5 requires computation on a fixed block size. If your password is not a multiple of block size it needs to be padded before it can be hashed. IIRC, the usual thing to do for MD5 is a simple zero pad, because you never have to produce the plaintext so you'd never bother writing the algorithm to put number of padded bytes in the pad. IIRC the MD5 block size is 64 bits (8 bytes), so you usually have to do two invocations to compute the hash for a 16 byte password. From a hashing speed perspective an 0-16 byte passwords take roughly the same time to hash. It really depends on your cache line size as MD5 doesn't have any branches, and your hashing speed is dominated by memory access. If you look at the perfomance numbers you can see that as you increase block size your hashing speed increases drastically, but unfortunately passwords are short so you need a mechanism for generating passwords with out having to hit the L2 cache. Luckily, this is fairly easy to do so if you used something like jack the ripper to generate/hash passwords you'll see much better performance than openssl.
@com, on a purely technical level UTF-8 gets all of ASCII in one byte, only extended ASCII requires multiple bytes. In practice ASCII is extended ASCII / ISO-8859-1, almost all of extended ascii fits into two bytes, but some require 3.
