Henry Ford takes 3 of his division presidents out for diner to decide which of them will be the new CEO. As soon as they start eating Mr. Ford chooses Bob, the man to his left, to be the new CEO. The other division presidents are shocked, and ask why Bob was picked over them. Henry replies: Bob was the only man who tasted his food before salting it.
Unlike at dinner time, hashes should always be salted. A hash is a one way function that maps something, for this discussion a password, to a short string. The point of a hash is if you're given the hash, you can't figure out the password. A common scenario for hashes is checking users passwords. Instead of storing a users passowrd and checking the passwords match, you store the hash of the users password, and make sure a hash of the users password matches the hash you stored. The advantage of storing the hash is if someone steals your disk they don't get your user's passwords.
There's a rub though. What happens if two users have the same password? Then both passwords will have the same hash. Uhoh, now we know if multiple users have the same password. This is bad! Now lets say I'm a bad guy, and compute the hashes for all the common passwords ahead of time? This is called a dictionary attack. You might be asking yourself if a dictionary attack is feasible - how much space is needed to store said dictionary? A hash is usually 20 bytes, to make the math easier lets assume it's only 16 (2^4) bytes. Lets make a dictionary for an 8 digit password; each character can be uppercase, lowercase or a numbers (26+26+10) = 62 (~ 2^6) choices per character x 8 (2^3) characters.
= (2^6)^8 * 2^4 bytes
= 2^48 passwords * 2^4 bytes storage for hash.
= 2^52 bytes for storage
~ 4,000 TB for storage.
This is really big, and clearly not feasible. Fortunately for attackers there is a trick you can play called a rainbow table. A rainbow table is a time space trade off algorithm were you can do a lot of upfront computation to cut down on the amount of required storage in the dictionary. This technique is very effective. The rainbow table for Vista for the 8 character password I describe in this blog post is only 153 GB and you can buy it here.
To defend against rainbow table attacks, we add salt. Before hashing the password, you prepend some random bytes, which we call salt. Then we store the salt alongside the hash. To verify the users password you prepend the users password with the stored salt, do the hash, and check for a match.
This rainbow table attack can be used against my windows box – watch this:
1) create a user account with password dogfood.
c:\temp>net user sillyuser dogfood /add The command completed successfully.2) Dump password hash using tool called fgdump.
c:\temp>c:\bin_drop\fgdump.exe >junk c:\temp>findstr sillyuser * 127.0.0.1.pwdump:sillyuser:1006:NO PASSWORD*********************:72B76234CCC8E047C6D12F2E391F5DF7:::
3) Lookup hashes for your password on a helpful website: http://lmcrack.com/index.php
ASCII : dogfood Hex. : 646f67666f6f64 LM : 655C44FFBF761281AAD3B435B51404EE NTLM :72B76234CCC8E047C6D12F2E391F5DF7 MD5 : 5D6423C4CCDDCBBDF0FCFAF9234A72D0 MD4 : E840B5EB9173B2E137AB14A98742A285 SHA1 : 67A2C23E0AEF5D92CBE084E22AA8E9A9311322C8 SHA256 : E674F78D2BF55FD93C878F7FE14448ABE677E7C3160F820AC6A012E457520B81
4) Clean up
c:\temp>net user /delete sillyuser c:\temp>del *.* The command completed successfully.