2 ms·

> Twenty years ago Rainbow Tables didn't exist. Maybe they weren’t called rainbow tables back then, but lookup tables of pre-computed hashes for password crack

> Twenty years ago Rainbow Tables didn't exist. Maybe they weren’t called rainbow tables back then, but lookup tables of pre-computed hashes for password cracking existed. I was there. However, I may be off by a year... I cannot recall the exact date I first became aware of them. I am fairly certain it was in the 90s.

tialaramex 6y ago
Rainbow Tables are not just lookup tables of pre-computed hashes. Pre-computation is obvious. Hellman comes up with chained pre-computation in the 1980s. Rainbow Tables are further improvement on Hellman's idea. Let's use LM hash as the example, the core idea in LM hash is you can turn up to 7 characters of password into a 64-bit value. LM hash does this twice (so up to 14 character passwords) but we can divide it into two 64-bit hashes. In 1975 LM hash hasn't actually been invented, but if you somehow went back and showed people from 1975 how it works they can pre-compute hashes. There are 2^56 possible hashes. So if you've got somewhere to store 2^56 hashes and passwords you can do the work and then reverse any LM hash. Hmm, 2^56 is a lot though. In 1975 nobody can store this data. By 1995 LM hash does exist, and Hellman has proposed his chaining optimisations. So, you do 2^56 calculations still (this is a bunch of work but it's certainly possible) but they form long chains so now you don't need to store 2^56 answers somewhere. Maybe you store 2^40 answers, you need to do 2^16 calculations for every reverse and you need 2^40 storage and sadly your recall is now poor. Maybe it only works 80% of the time. Storing 2^40 answers in 1995 is expensive, you can't afford to do it, but the government or a rich company can. By 2005 there are Rainbow Tables. Phillipe's idea massively improved recall. You can have say 99.9% recall, store 2^40 answers and do 2^16 calculations to reverse a hash. Also in 2005, storing 2^40 answers seems reasonable, you can just walk to a store and buy many gigabytes of storage space no problem.

tialaramex 6y ago

Rainbow Tables are not just lookup tables of pre-computed hashes. Pre-computation is obvious. Hellman comes up with chained pre-computation in the 1980s. Rainbow Tables are further improvement on Hellman's idea. Let's use LM hash as the example, the core idea in LM hash is you can turn up to 7 characters of password into a 64-bit value. LM hash does this twice (so up to 14 character passwords) but we can divide it into two 64-bit hashes. In 1975 LM hash hasn't actually been invented, but if you somehow went back and showed people from 1975 how it works they can pre-compute hashes. There are 2^56 possible hashes. So if you've got somewhere to store 2^56 hashes and passwords you can do the work and then reverse any LM hash. Hmm, 2^56 is a lot though. In 1975 nobody can store this data. By 1995 LM hash does exist, and Hellman has proposed his chaining optimisations. So, you do 2^56 calculations still (this is a bunch of work but it's certainly possible) but they form long chains so now you don't need to store 2^56 answers somewhere. Maybe you store 2^40 answers, you need to do 2^16 calculations for every reverse and you need 2^40 storage and sadly your recall is now poor. Maybe it only works 80% of the time. Storing 2^40 answers in 1995 is expensive, you can't afford to do it, but the government or a rich company can. By 2005 there are Rainbow Tables. Phillipe's idea massively improved recall. You can have say 99.9% recall, store 2^40 answers and do 2^16 calculations to reverse a hash. Also in 2005, storing 2^40 answers seems reasonable, you can just walk to a store and buy many gigabytes of storage space no problem.