drostie: this is the most accessible plain-English explanation of rainbow tables I've ever seen, and it's short to boot. From now on, whenever anyone asks me how stolen lists of hashed passwords get hacked, I will point them to your comment. Thank you.
 Of course a lot of hashed passwords have been hacked not because of rainbow tables, but by brute force because the site used a single round of a fast hash function.They think they are good with a 4-byte salt and one round of sha-1, since that is effectively immune to rainbow-table attacks, but its' not immune to "I have a massively powerful processor in my computer called a 'video card'"
 It's good. I wrote my own rainbow table code several years ago, and I had to read and re-read white papers and wikipedia articles for several days until it finally clicked. This would have helped a lot.
 A very enjoyable explanation. That was a little outside the scope of what I was trying to explain, but would make a good follow up. I'll post a link to your comment.
 This is a very good explanation. I have a couple questions though:Is the chain-length of 100 arbitrary, or is there an optimal length of these chains?How many times would you run ORATION through the one-way function and compare it to your rainbow table before you decide it's not in the table?
 >Is the chain-length of 100 arbitrary, or is there an optimal length of these chains?100 is the compression ratio. If you make chains of length 100 then you can compress the dictionary 100:1. If you make the chains of length 1000 then you can compress 1000:1 but you have to do 1000 operations for each lookup instead of 100. It's a trade off.> How many times would you run ORATION through the one-way function and compare it to your rainbow table before you decide it's not in the table?You presumably know the length of the chains your table used, so if you go through the entire length without finding it then you'll know it really isn't in the table (e.g. Alice just provided a random word instead of one which was the output of the hash function and it turns out no dictionary word leads to the one she provided).
 If I wanted to compress 100:1, how would I select which words would be the "heads" of my chains?Choose every 100 words in the dictionary?Is there a risk of not getting complete coverage? Example: I keep applying the one-way function to the ciphertext, but the result is never an endpoint of one of my precomputed chains.
 It may not always be possible to get perfect compression. Suppose for some reason you have the property that the hash for 10% of the words is "be" and the hash for a further 50% of the words is one of the words that hashes to "be." Using rainbow tables for this is not going to go well because all your chains are going to end up at "be" inside of a small number of iterations. But a hash with this property will also fail at its intended purpose because Alice could claim the hash for a word she doesn't know is 'be' and have a 10% chance of being right.Good hash functions are specifically designed to make hash collisions like that as rare as possible, so in practice the compression ratio will be strongly correlated to the chain length, but you can still have instances where one hash value is slightly more common than another. The result is just that if you use a chain length of 100, the compression ratio in practice will be slightly worse than 100:1.As to how to choose the heads of the chains, I suspect the answer for getting the absolute optimal choices will either be NP complete or will involve some application of linear algebra. If all else fails you could just keep adding random chains rooted in a value that isn't in any existing chain until you have full coverage. I don't know what people do in practice.
 Good explanation. I always thought this was a good one too: http://kestas.kuliukas.com/RainbowTables/
 Salting the password should defeat the rainbow table, right?
 Using a salt would require the attacker to include an entry for each possible salt for each password candidate. If the salt is only one bit, this makes the attack take twice as long (or, requires tables twice as large). If the salt sufficiently long it makes the attack infeasible.
 Thanks for this question! The answer is complicated. :DLet me tell you first why it does not help! In order to build a rainbow table, we must be able to build a lookup table (since they're just compressed lookup tables). But a lookup table is basically a brute force attack on a certain category of passwords! So, if your password would fall to a modern rainbow table, it can be brute-forced by modern computational clusters. Salting does not change that. Intrinsically the password is no more secure than it was before. (To make it more secure, use bcrypt, scrypt, or pbkdf2. Seriously, even PHP has pbkdf2 nowadays, you have no excuse[1].)Now let me mitigate that naysaying a bit. If you salt every password with a random 12-character base64 string, you do indeed prevent building a lookup table for the database. And that's actually not bad. Security is best measured not in bits or in operations, but in dollars. If the value of the information is much smaller than the cost to crack it, you'll defeat a rational attacker.Rainbow tables can be built in a highly parallel way, with attackers pooling their resources and attacking multiple systems. So it will generally cost more to brute-force a password than it will to break it with a rainbow table: the rainbow table lookup can be done with one CPU; but brute forcing may require a botnet or lots of GPUs.[1] Okay, there is one excuse: you might want to be able to do password administration from phpMyAdmin using only built-in MySQL functions. If you are stuck in this particular case the REPEAT() and SHA1 commands can have a similar effect:`````` create function pw(salt char(12), password varchar(255)) returns char(40) return sha1(repeat(concat(salt, sha1(password)), 100000)); `````` but if you're not in this case, use something better.
 Is cracking passwords even worth anyone's time anymore?Most password salting is extremely unique from one website to the next. And as long as the salting increases the length of the string that will be encrypted passed 16 characters, it will be uncrackable.It would be much quicker to social engineer your way into a system and just plant a script that honeypots unencrypted passwords.
 Technically, in your example you do still need the full dictionary - a one way function mapping to words requires it for operation.
 »[...] that lookup table is going to be as long as the dictionary! What if he has to take it somewhere [..]« ... now he has to carry around the rainbow table and the dictionary. This didn't work out as expected. ^^
 This is the best explanation of rainbow tables I've read. Thanks!

Search: