3 ms·

> “At the time, it would not have been possible to crack an encrypted password hash, such as the one Manning obtained.” Wrong. Rainbow tables have always worke

> “At the time, it would not have been possible to crack an encrypted password hash, such as the one Manning obtained.” Wrong. Rainbow tables have always worked, even 20 years ago.

tialaramex 6y ago
Twenty years ago Rainbow Tables didn't exist. Philippe Oechslin published his paper explaining them in 2003. Hellman's improved time-space trade-off is older, but the actual Rainbow Table, popularly used to attack Windows hashes, dates only to Oechslin's paper. The claim is that the hash is from an offline SAM. Windows by that era has an encrypted SAM file, so when it isn't running the raw hashes are actually encrypted with RC4. In principle 128-bits of RC4-enciphered data is useless. RC4 is not good encryption by 2020 standards (nor indeed in 2010) but it's enough that if the 128-bits is from an encrypted SAM they're useless. But the trouble is that tools to decrypt the SAM certainly did exist in 2010.
- TedDoesntTalk 6y ago
  > 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.

> “At the time, it would not have been possible to crack an encrypted password hash, such as the one Manning obtained.” Wrong. Rainbow tables have always worked, even 20 years ago.

tialaramex 6y ago

Twenty years ago Rainbow Tables didn't exist. Philippe Oechslin published his paper explaining them in 2003. Hellman's improved time-space trade-off is older, but the actual Rainbow Table, popularly used to attack Windows hashes, dates only to Oechslin's paper. The claim is that the hash is from an offline SAM. Windows by that era has an encrypted SAM file, so when it isn't running the raw hashes are actually encrypted with RC4. In principle 128-bits of RC4-enciphered data is useless. RC4 is not good encryption by 2020 standards (nor indeed in 2010) but it's enough that if the 128-bits is from an encrypted SAM they're useless. But the trouble is that tools to decrypt the SAM certainly did exist in 2010.

TedDoesntTalk 6y ago
> 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.