[Cryptography] Why don't we protect passwords properly?

[Arnold Reinhold]

On Sun, 22 Dec 2013 11:26 Jerry Leichter wrote
...
> The ability to do mass off-line attacks wasn't anticipated.  Its success was based on the combination of several things that would have been hard to predict:  Clever fast implementations of some of the primitives optimized for the purpose of password cracking rather than ordinary cryptography - e.g., doing encryption in bit-wise parallel; the ability to utilize large numbers of machines for password cracking purpose, whether on a service like AWS or through botnets of ever growing size; the wide deployment of graphics cards, which it turned out could be used to implement cracking algorithms very quickly - and of course the availability of all those databases of encrypted passwords, some of which didn't even bother to use salts, which was best practice by the late 1970's.
> 
> All this didn't come together until the last 2-3 years or so.  There simply were no plausible, much less *demonstrated*, large scale attacks against encrypted passwords until not long before that.  bcrypt was first published in 1999 specifically to protect against rainbow tables - a neat theoretical attack that may never have actually been used in practice anywhere.  (The newer brute force techniques are much more practical than rainbow tables in today's environment; if you hear someone talking about using rainbow tables today, it probably means they don't know what they are talking about.)  scrypt is 10 years more recent - the paper defining it was only published in 2009, and a (since-expired) draft RFC dates to 2012.  Most cryptographers would probably be leery of scrypt: It simply hasn't been around long enough, and survived enough concerted attacks by those who are really good at such attacks, to form a good judgement as to its strength.  Just because all publicly known 
> implementations are slow doesn't mean there aren't fast ones waiting to be found. ...

I must respectfully take exception to the above. The possibility of mass off-line attacks was anticipated from the very beginning. The original Cyrpt (3) circa 1978 was designed to prevent such attacks. I proposed a KDF called HEKS that was designed to use large amounts of memory and computing resources in order to defeat hardware attacks on hashed passwords way back in 1999. It's referenced in the scrypt paper. And rainbow tables are indeed available and in use against password hash systems that do not employ salt, including Microsoft's notorious LM hash, straight MD5 and SHA1, etc. A quick Google search got me to freerainbowtables.com which offers some 9 terabytes of rainbow tables via torrents for your favorite low sodium hashes.

While the best hash attack methods in use today do involve novel ideas, the possibility of using mass parallel attacks in hardware and software has been on the minds of cryptographers since the early controversies about DES in the mid-1970s. That underling threat is what drives most innovations in cryptography. We are always looking ahead to be ready for processing breakthroughs. 

So why the lack of attention to KDFs? If one tenth the effort to replace SHA-2 had been devoted to improving password storage, the benefits to industry and the public would be far greater than anything we can expect from SHA-3.  While I'm glad the hear that there is at last a password-hashing competition (password-hashing.net), scrypt is available now. As long as an algorithm identifier is included in a password database, it's easy to substitute a better algorithm when it comes along. And is there any cryptographer out there who knows the algorithm and believes that scrypt could be weaker than PBKDF2? Seriously?

Arnold Reinhold