[tptacek]

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.

[_b8r0]

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]

Yes. I think you should ignore rainbow tables. People using salted MD5 hashes in their PHP applications are also creating a real threat.

[dstorrs]

> 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.)

[tptacek]

The original Unix crypt(3) password scheme invented (and coined the term for) salts.

Incremental password crackers, like John the Ripper and Crack, take a single password hash, and an actual dictionary, and hash each entry in the dictionary looking for a match. They take days to run instead of seconds, and until people started wanting to break into Windows boxes, they were the only way people cracked passwords.

[_b8r0]

They don't take days to run. The other week I cracked around 16,000 LM hashes with EDPR in about 6 hours.

Incremental crackers have improved substantially over the past few years primarily due to the introduction of GPU programming (in some cases algorithms port easily, in other cases they need some work first to be optimal on a GPU), easier distributed programming and rainbow tables. There's some interesting projects that use GPU technology to optimise the rainbow table reduction function (see http://www.cryptohaze.com/ for an example). As GPU technology improves and as hardware becomes cheaper and more powerful these technologies bring capabilities previously limited to three-lettered agencies into the commercial and home space.