I have been heavily researching password storage lately, because I believe there are still lapses in internet security that keep it far behind what hackers are able to achieve, and, as a programmer, I want to keep such things as lock-tight as possible.
It, shamefully, just clicked with me the power of rainbow tables (for which I only learned the term in the last few days). For some background, any legitimate website or authentication system does not store your password in plain text. It uses a one-way encryption and stores that encryption. Then to check if you used the right password, it encrypts the one you send it and compares it against the stored encryption. This minimizes opportunities for a copy of your password to be easily accessible, decryptable, or readable, in any sense to someone who want to use it for malfeasance.
The trick with all one-way encryptions used for such “hashing” purposes is their resulting strings are fixed length. For example, sha1, which is probably the most widely used method on the web, creates alphanumeric (0-9, a-z not case sensitive) hexadecimal strings of length 40 (at least using the php sha1() method with which I am familiar — I’m not a sha1 expert). Because of this, there are possible collisions. In other words, although your password might encrypt to one string, there are effectively infinite other strings that would encrypt to that same string.
Before getting too uptight about this, just do the basic numbers. The sha1 encryption creates 40 character strings with 36 16 possible characters in each place, meaning there are 36^40 16^40 possible resulting encryptions. That number?
178,689,910,246,017,054,531,432,477,289,437,798,228,285,773,001,601,743,140,683,776
1,461,501,637,330,902,918,203,684,832,716,283,019,655,932,542,976
Is there even a word for that? Yes … 178.69 novemdecillion 1.46 quindecillion. (that is a big number)
So a hacker would build the corresponding rainbow table by finding exactly 1 string that converts to each of those 178,689 1,461,501 … hashes. Then, somehow, they get your encrypted password, and all they have to do is look it up in this table, and they have your password (or at least one that collides with yours’ hash).
It is very simple, but, fortunately, at this point, that rainbow table would not fit on all the hard drives in the world. In fact, it would take about 50 billion earths to find an equivalent number of atoms the earth is only composed of about 133 quindecillion atoms. (That’s one hash per 89 atoms — a human hair is about 10000 atoms thick).
But let’s abandon the seeming impossibility of the existence of this table temporarily. A common practice in secure storage of passwords these days is to “salt” the password before hashing and storing it. That is, you take the password, prepend (or append) a random string, then encrypt the resulting string. (More complex salts can exist, but the idea is that you modify the password in a predictable, repeatable way). What this does is force a hacker to build a corresponding rainbow table for EVERY password he/she wants to hack, because the unsalted rainbow table won’t work (I’ll leave this to you to figure out why if you don’t know at this point.)
The problem is, if you’re still using sha1 to encrypt the salted password, it’s no different than if you didn’t salt the password. If this complete sha1 rainbow table DID exist, the salt would serve absolutely no purpose, it would just shift the collision. Some infinite subset of strings would still map to this encrypted string.
As a side note, the rainbow tables that exist are simply compilations of common types of passwords, and, in many instances, they work, because people just don’t use strong enough passwords. This reduces the size of the tables to a usable form, so, in this case, the salting is imperative. I am discussing today the case where a complete sha1 rainbow table exists. I have said that it is pretty much impossible, but, from a purely theoretical standpoint, eventually, even the number 178.69 novemdecillion 1.46 quindecillion will become small as technology improves with time.
By the way, “strong,” for all intents and purposes of one-way hashing, just means long. Knowing a password is short drastically decreases the number of hashes that need to be generated for the table. Good advice? Use passwords 20 characters or longer — i.e. a sentence “This is my password, baby. Nothing personal, but don’t steal it.”
My question is, is it really effective to use the same encryption mechanism after you salt the password? Salting is little more than an obfuscation in the presence of a complete rainbow table. In the face of the assumed existence of this rainbow table, and ignoring that most passwords aren’t truly “random,” there is exactly no difference between “salt and hash” and simply “hash.” This just leads me to the conclusion that the inherent flaw in one way hashes is that they create strings of finite length, but that is exactly why they are useful.
Perhaps the only purpose of this post was to legitimately use the word novemdecillion quindecillion more than once. I dunno, but I would certainly appreciate expert commentary on the topic.
Edit: After initially writing this, I realized that sha1 created hex strings, not alphanumeric. This changed the numbers, but fortunately not the article. I decided to leave the old numbers in strikethrough because, well, novemdecillion is a cool freaking word.
