Keeping passwords safe by staying up to date | Hacker News Reader

Keeping passwords safe by staying up to date

blog.cloudflare.com

53 pointsjgrahamc22 comments

As a HN non-hacker old-timer, I've read plenty of conversations about security and had a vague idea of what the heck y'all were talking about with hashes, salts etc.

But this post explained it all so clearly, I found it immensely useful to put some of the pieces together. Have already shared it with some of my even-less-technical colleagues so they too can appreciate 1) the complexity, 2) the problem, and 3) the importance of their role in setting passwords. Well written JGC!

Thanks for the kind words.

For those who are interested in how to do the hash upgrade, I wrote a blog post on my personal site here: http://blog.jgc.org/2012/06/one-way-to-fix-your-rubbish-pass...

Depending on the framework you're using, if any, there might already be a built-in way to upgrade your users' passwords.

For Django: https://docs.djangoproject.com/en/dev/topics/auth/#password-...

Really nice writeup, but why not also append a discussion of scrypt and its use of both CPU work factor and memory-hard functions to confound Moore's Law? It's the next step after bcrypt, after all.

It may not be be implemented across as many platforms as bcrypt yet, but there's plenty for people to experiment with [1], if only for learning and educational purposes.

1. http://www.freebsd.org/cgi/cvsweb.cgi/ports/security/scrypt/

http://manpages.ubuntu.com/manpages/oneiric/man1/scrypt.1.ht...

http://rubygems.org/gems/scrypt

http://pypi.python.org/pypi/scrypt/

https://github.com/search?q=scrypt

The article describes what we did at CloudFlare, not a general survey of cryptographic hash functions. We chose not to use scrypt because it is relatively new.

I fully expect that scrypt will stand the test of time and I'll probably be happy using it.

Please not again. Discussions of passwords always brings up these stupid scrypt bcrypt fanboy comments.

Repeating it one more time won't change anything.

Easy there. You're projecting and reading a little too much into it. I'm not a fanboy, it simply struck me as a conspicuous oversight to write what appeared to be a survey of password hashing history and technology, and not mention scrypt at all.

It's very instructive, especially for people new to this stuff, to see the contrast between bcrypt's CPU-hard algorithm and scrypt's CPU-hard + memory-hard algorithm.

But jgrahamc's clarification above makes sense - it wasn't meant to be a general survey, but only what CloudFlare has done.

Here is a name-and-shame site for services that store and send passwords in plain text (or any reversible encryption): http://plaintextoffenders.com/

There are a number there that are new registration e-mail, which doesn't necessarily mean it's stored insecurely.

E-mailing it around isn't a great idea, certainly, but it's not as bad as storing it reversibly.

Where do you store the individual salts, or the rules for creating the salts? Do you hash those too? It seems like they'd have to be sitting somewhere so that you could salt the input password before hashing to compare with the salted/hashed password in your database. If the salts are sitting in a database, and that database is compromised, aren't we sitting right back where we started with hashed passwords that may be subject to attack by rainbow tables?

// question asked by an attorney who knows nothing about this subject but what he's read on HN.

That's why they recommend bcrypt. Generating a rainbow table for a sha1 salted string is very quick with the right hardware. Generating one for a bcrypt string is going to take ages, and improvements in computing power can be dealt with by increasing the work factor for the bcrypt hashed strings in one's database.

Why in the world would anybody create a rainbow table for a salted string?

The username it's attached to is "admin"?

Plenty of situations where cracking the administrator's password via a custom rainbow table is potentially worth it.

Rainbow tables are a very specific form of attack that allows you to do a single brute force attack against multiple accounts simultaneously. Against a single salted hash, you would not bother to generate a rainbow table; instead you would just stop once you found a match.

Sure, if you somehow get the salt but not the hash, and expect to get the hash in the future. Then, precomputing things makes sense while you wait.

Otherwise, it's silly - building a rainbow table means 1) using a large amount of storage to store the results, and 2) waisting cycles organizing your data in that space to ensure efficient lookup. Doing this makes no sense if you already have the one hash you're going to check against - just do a regular brute-force attack.

Bcrypt was not designed to counter rainbow tables. Although the internal salt does provide that defense. Bcrypt was designed to protect against raw brute force:

See: http://static.usenix.org/events/usenix99/provos/provos_html/...

> "At the time of deployment in 1976, crypt could hash fewer than 4 passwords per second. Since the only known way of inverting crypt is to guess preimages, the algorithm made passwords very difficult to recover from their hashes--so much so, in fact, that the designers of UNIX felt comfortable leaving the password file readable by all users. Today, over 20 years later, a fast workstation with heavily optimized software can perform over 200,000 crypt operations per second. Attackers can now expediently discover plaintext passwords by hashing entire dictionaries of common passwords and comparing the results to entries in a password file."

> "While salted passwords defeat lookup tables, given a particular salt and hash, an adversary can still mount a brute force attack by evaluating F(s,t) on every possible password. It follows that the best security one can achieve is $\epsilon\approx 1/\vert F\vert$, where |F| is the cost in gates of implementing F. Usability requirements therefore effect a lower limit on $\epsilon$--if people can only tolerate a one second delay for checking passwords, F can take at most one second to evaluate. F should not take significantly less, however, as this would unnecessarily weaken security."

> "The number of gates |A| that an adversary can reasonably muster for an attack increases constantly as hardware improves. Fortunately, so does the speed of machines that must legitimately evaluate F. That means passwords should not be hashed by a single function F with fixed computational cost, but rather by one of a family of functions with arbitrarily high cost. Instead of repeatedly throwing out functions like crypt and MD5 crypt to start over with more expensive but incompatible ones, systems should allow the cost of any password manipulation software to scale gracefully with a tunable parameter. Thus, $\epsilon$ can decrease as fast as hardware improves and users will tolerate. Compromised password databases will then enjoy maximum security against off-line attacks."

The purpose of bcrypt was to allow for a single algorithm that can be tuned for existing speed of existing computers to produce a "slow" algorithm. Then, as Moore's law makes computers faster, bcrypt can be progressively slowed to keep pace, so that performing a brute force still takes an unreasonable amount of time.

> Bcrypt was designed to protect against raw brute force

Which is precisely what calculating a rainbow table involves.

Aren't rainbow tables in general defeated by proper use of a salt, regardless of the hash or key generation?

Wouldn't bcrypt without a salt would be vulnerable to a lookup table of the top 100K passwords, say?

The salts are just random strings. They can be stored with the hashed passwords. The security of the scheme does not depend on keeping salts secret. It depends on the strength of the hashing algorithm.

Two things:

1. Rainbow tables are today an irrelevance because of the speed of computers. What you need to worry about is not precomputed tables, but the ability to compute hashes when needed. The point of the salt is to prevent you precomputing anything.

2. So, suppose you have a database where (hash, salt) has been compromised for each user. Assuming salt was chosen randomly for each user then attacking the database boils down to calculating the hashes for common passwords incorporating the salt. The security of that will depend on the security of the hash algorithm and its slowness.

I think I get it. Using a unique salt, they'd have to completely rebuild their entire rainbow table for each password (given a unique salt for each). Is that right? Even then, it seems like they might want to use a smaller dictionary, but rebuilding for each username would still be doable. Just slower.

I totally get the slow algorithm part. Seems to me that's the trick.

Our IT department is dead set against using password managers. I've been trying to learn why, given companies like lastpass use excessive salting/hashing and slow algorithms. Unfortunately, at this point, I fear my limited knowledge may actually surpass theirs. All I hear is grumbling about all my eggs being in one basket.

#1 is not true. Algorithms like bcrypt rely on being so expensive to compute that brute-forcing is prohibitively expensive. bcrypt does use salt. If it did not then it would indeed be vulnerable to rainbow table attacks.

o/t,

jgrahamc, when does the spdy beta start? :)

Reply on news.ycombinator.com