5 ms·

The rainbow tables are an implementation of a form of time-memory tradeoff attack using a refined hash reduction algorithm based on the work of Martin Hellman (

by iuguy 16y ago

The rainbow tables are an implementation of a form of time-memory tradeoff attack using a refined hash reduction algorithm based on the work of Martin Hellman (of Diffie-Hellman fame) - http://en.wikipedia.org/wiki/Rainbow_table http://en.wikipedia.org/wiki/Rainbow_table Basically Ophcrack uses optimised hash chains to speed things up. The precomputed hashes are generated with a specific character set. This works particularly well for unsalted algorithms that support limited character sets such as LM. LM splits the password into two on the 7 character boundary, capitalises it and only supports a subset of printable characters. Also it's unsalted, so while more computationally expensive than NTLM it's actually easier to crack. Rainbow tables for LM can be downloaded from freerainbowtables.net and are about 30-40Gb. NTLM on the other hand supports unicode and very long password lengths. Most rainbow tables are mixalpha, or alphanumeric but short length. Our mixalphanum with symbols rainbow table set goes up to 14 characters and is about just under a terabyte. This is more difficult to put on SSDs cheaply. Your best bet to protecting from rainbow tables is to use a character not referenced in commonly available sets in your password as you inevitably otherwise reach the limits of security vs usability with exceptionally long characters. As I use british keyboards, I generally recommend the £ symbol (British pound) or accent over a vowel. The Euro symbol is also good if you're staying in Europe.

Confusion 16y ago
Your best bet to protecting from rainbow tables [..] is using a salt. No need to use uncommon characters.
- iuguy 16y ago
  You are correct. However, pursuant to the use of NTLM or LM, neither of which are salted non-US ASCII characters are about as good as you can get without ridiculously long passwords. For anything else, ready salted is definitely the best crypto flavour. Having said that, a few years ago I co-ordinated a distributed effort to create rainbow tables for standard Oracle database accounts. Oracle's crypto mechanism uses the username as a salt. It meant that we had to generate different (but small as the algorithm was crap) tables for DBSNMP,SYSTEM etc. The same applies to WPA-PSK - don't use a common SSID in the Church of Wifi tables. I guess the moral of the story is that salting alone won't get you out of the woods. You need to think very carefully when it comes to crypto, and get as many second opinions as you can.
  - tptacek 16y ago
    You say "definitely the best crypto flavor" as if you knew. But you don't, because no serious system designer cares about rainbow tables. Unix solved this problem in the nineteen seventies. Real system designers care about incremental crackers, of the sort used since the 1980's to harvest thousands of passwords from compromised Unix boxes, of the sort that forced Unix systems in the 1990's to adopt "shadowed" password files. The solution to that threat, the real threat, is scrypt, bcrypt, or PBKDF2 --- the "adaptive" hashes that can be tuned to trade a marginal increase in defender cost for an untenable increase in attacker cost.
    - iuguy 16y ago
      Are you saying that we should ignore rainbow tables? I appreciate that you know way more about crypto than I do, but I think you're working from the standpoint that people know how to do things the right way, as opposed to the real world situation where people very clearly don't (e.g. NTLM, Oracle being 'Unbreakable', iPhone screen lock security mechanisms). For as long as there's people using unsalted MD5 hashes in their PHP applications, Rainbow Tables are a real threat.
      - tptacek 16y ago
        Yes. I think you should ignore rainbow tables. People using salted MD5 hashes in their PHP applications are also creating a real threat.
    - dstorrs 16y ago
      > Unix solved [the problem of rainbow tables] in the nineteen seventies. > incremental crackers [were used to] harvest thousands of passwords [and] forced Unix systems in the 1990's to adopt "shadowed" password files. As someone who is interested in security but has not spent significant time studying it, I'd be interested to hear more about this. How did Unix solve the rainbow table issue? What is an incremental cracker and how does it relate to shadowed password files? (I'm familiar with the latter but not the former, and a Google search generates more noise than signal without more keywords to go on.)
- silentbicycle 16y ago
  Also, using a hash (such as bcrypt) that can be made arbitrarily expensive. With a cost of 14, it takes this computer four seconds of CPU time per attempt to hash each password. While merely annoying for one user, that would really slow down rainbow table creation.
dfox 16y ago
By the way are there any other security implications of cracking LM hash than recovery of passwords from already compromised machine?
- iuguy 16y ago
  LM is a particularly poor algorithm for passwords. There's a fair bit of info here: http://en.wikibooks.org/wiki/Reverse_Engineering/Cracking_Windows_XP_Passwords http://en.wikibooks.org/wiki/Reverse_Engineering/Cracking_Wi... It's disabled by default on Vista and 7 (AFAIK, it was on my Windows 7 build, and I don't think that was me) but is enabled by default on Windows XP. You can find out how to disable it here: http://support.microsoft.com/kb/299656 http://support.microsoft.com/kb/299656

by iuguy 16y ago

Confusion 16y ago

Your best bet to protecting from rainbow tables [..] is using a salt. No need to use uncommon characters.

iuguy 16y ago
You are correct. However, pursuant to the use of NTLM or LM, neither of which are salted non-US ASCII characters are about as good as you can get without ridiculously long passwords. For anything else, ready salted is definitely the best crypto flavour. Having said that, a few years ago I co-ordinated a distributed effort to create rainbow tables for standard Oracle database accounts. Oracle's crypto mechanism uses the username as a salt. It meant that we had to generate different (but small as the algorithm was crap) tables for DBSNMP,SYSTEM etc. The same applies to WPA-PSK - don't use a common SSID in the Church of Wifi tables. I guess the moral of the story is that salting alone won't get you out of the woods. You need to think very carefully when it comes to crypto, and get as many second opinions as you can.
- tptacek 16y ago
  You say "definitely the best crypto flavor" as if you knew. But you don't, because no serious system designer cares about rainbow tables. Unix solved this problem in the nineteen seventies. Real system designers care about incremental crackers, of the sort used since the 1980's to harvest thousands of passwords from compromised Unix boxes, of the sort that forced Unix systems in the 1990's to adopt "shadowed" password files. The solution to that threat, the real threat, is scrypt, bcrypt, or PBKDF2 --- the "adaptive" hashes that can be tuned to trade a marginal increase in defender cost for an untenable increase in attacker cost.
  - iuguy 16y ago
    Are you saying that we should ignore rainbow tables? I appreciate that you know way more about crypto than I do, but I think you're working from the standpoint that people know how to do things the right way, as opposed to the real world situation where people very clearly don't (e.g. NTLM, Oracle being 'Unbreakable', iPhone screen lock security mechanisms). For as long as there's people using unsalted MD5 hashes in their PHP applications, Rainbow Tables are a real threat.
    - tptacek 16y ago
      Yes. I think you should ignore rainbow tables. People using salted MD5 hashes in their PHP applications are also creating a real threat.
  - dstorrs 16y ago
    > Unix solved [the problem of rainbow tables] in the nineteen seventies. > incremental crackers [were used to] harvest thousands of passwords [and] forced Unix systems in the 1990's to adopt "shadowed" password files. As someone who is interested in security but has not spent significant time studying it, I'd be interested to hear more about this. How did Unix solve the rainbow table issue? What is an incremental cracker and how does it relate to shadowed password files? (I'm familiar with the latter but not the former, and a Google search generates more noise than signal without more keywords to go on.)
silentbicycle 16y ago
Also, using a hash (such as bcrypt) that can be made arbitrarily expensive. With a cost of 14, it takes this computer four seconds of CPU time per attempt to hash each password. While merely annoying for one user, that would really slow down rainbow table creation.

dfox 16y ago

By the way are there any other security implications of cracking LM hash than recovery of passwords from already compromised machine?

iuguy 16y ago
LM is a particularly poor algorithm for passwords. There's a fair bit of info here: http://en.wikibooks.org/wiki/Reverse_Engineering/Cracking_Windows_XP_Passwords http://en.wikibooks.org/wiki/Reverse_Engineering/Cracking_Wi... It's disabled by default on Vista and 7 (AFAIK, it was on my Windows 7 build, and I don't think that was me) but is enabled by default on Windows XP. You can find out how to disable it here: http://support.microsoft.com/kb/299656 http://support.microsoft.com/kb/299656