News for hackers. Stuff that matters.
Re:Cheap GPUs rendering strong passwords useless? by Joakal on Sunday June 05, 2011 @09:26PM (#2623351)
Codahale's article is misleading with salts. Bcrypt can't also protect against brute-forcing or dictionary attacks. Please don't spread that link as an example of good password storage security.

Edit: Since I can't reply to poster. I don't see bcrypt using a unique salt for each password. It's the equivalent of exchanging a SHA256 + Same Salt for Bcyrpt + Built-in-Salt.

Does bcrypt use a unique salt per account?

Re:Cheap GPUs rendering strong passwords useless? by tptacek on Sunday June 05, 2011 @09:28PM (#2623358)
No; you're incorrect.

You can find the answers to your bcrypt questions at the Usenix paper which is the first link in the article you're advising people not to read.

Re:Cheap GPUs rendering strong passwords useless? by Joakal on Sunday June 05, 2011 @09:42PM (#2623381)
I did, it uses a preset list of salts at the time. That doesn't seem unique per account salting raising the possibility of collisions to me.
Re:Cheap GPUs rendering strong passwords useless? by tptacek on Sunday June 05, 2011 @09:49PM (#2623399)
bcrypt uses 128 bit salts. Every bcrypt library I've seen will generate the salt for you.

    [8:48pm:~] RIDGELAND:tqbf [1:45]% irb -rrubygems -rbcrypt
    >> BCrypt::Password.create("test password")
    => "$2a$10$KyxzQ6ZlAAYdLWwpgCbyjuqo53.LzPbsaSK2BiTnzpYEpRVZOHAAy"
    >> BCrypt::Password.create("test password")
    => "$2a$10$d0uUieyk0NWsU7E9CmQNwOsveyznwKwplphsF73yILdEyStmoUGgG"
Notice how they aren't the same hash? And, how I didn't have to go mine pink salts from the Himalayas?

By spreading the notion that there is something wrong with Coda's article when you really aren't familiar with bcrypt, you're doing people a disservice. They are going to go use SHA1 with a big random salt instead, because they've heard of SHA1 before and it therefore sounds more secure. And they will thus be terribly vulnerable to brute-force attacks.

Re:Cheap GPUs rendering strong passwords useless? by palish on Sunday June 05, 2011 @11:31PM (#2623578)
A preset list of salts would still show a different hash for 2 consecutive bcrypt executions. Your example proves nothing.

I'm not saying you're wrong. I'm saying you didn't demonstrate proof, so you shouldn't act like you did.

I'm extremely interested why bcrypt is much more secure than SHA1 + extremely long hash, so perhaps you could shed some photons on that?

Also, in order for bcrypt to generate a unique salt on two different computers, it needs a unique source of randomness. Obviously seeding by "current time" is insufficient, as this would generate the same salt for two different computers at the same time. So what does it use? Mac address of network card + current time?

Re:Cheap GPUs rendering strong passwords useless? by tptacek on Sunday June 05, 2011 @11:54PM (#2623638)
I don't need to prove that bcrypt has a "preset list of salts". Read the paper. Or even just Coda's summary of the paper. What an extremely silly objection to raise. Why would any cryptosystem embed a preset list of nonces?

How frustrating to have to argue about a system with someone who clearly hasn't done any reading on it at all. It's a Usenix paper. It's not a EUROCRYPT paper full of math. It was written by systems programmers, then from the OpenBSD project. You think the OpenBSD programmers devised a password scheme with a "preset list of nonces"?

"MAC address of the network card plus the current time"? To get a random number?

[deleted]
Re:Cheap GPUs rendering strong passwords useless? by Xk on Monday June 06, 2011 @01:56AM (#2623841)
[edit: palish deleted his comment; excerpts below for what I was responding to:

> Except random numbers aren't random. They only appear to be. If an online casino seeds its random number generator with current time, then you can do the same, and predict which cards it will deal.

> So here you are saying that bcrypt generates a random seed, and I'm thinking "how does bcrypt get around the aforementioned problem?"

> If you don't want to answer my specific question ("why is bcrypt stronger..."), then don't.

]

I'm neither tptacek nor a security expert, but I think I know bcrypt well enough to answer your questions. Apologies if anything I say isn't correct; someone correct me if that's the case.

Starting with the problem: SHA1+salts are well and good. The password isn't in plaintext, so I can't just read it. SHA1 has no real cryptographic attacks on it. The salts prevent rainbow table attacks.

Except there's a major flaw. SHA1 is fast. SHA1 is very fast.

When you hash your password with SHA1+salt (even if you use a 1024 bit salt) an attacker will get a GPU cluster and run billions of hashes per second until they bruteforce your password. Anything under eight characters will fall in under a day, easily.

Now, let's talk bcrypt. Based off of blowfish (which has a reasonably long key-schedule algorithm), bcrypt is designed to be very slow. Very very slow.

If you want to think of a very naive way of doing this, imagine my hashing function is simply salt||SHA1(SHA1(SHA1(SHA1(...(SHA1(password||salt)))))) It is easy to see how this would take significantly longer than simply salt||SHA1(password||salt). Now there's some other details that you don't seem to be interested in, but that's the main idea. If you care to read more, see the paper.

This means that if an attacker would try to bruteforce even the simplest passwords, it would take significantly longer. Look at the chart on page 11, for example. The nice thing about this is that you can, over time, adjust it to take longer and longer as computers get faster and faster.

So, bcrypt isn't some fancy thing which picks salts in some random way (although it does get salts; as for how, I don't know, but /dev/random would work just fine).

If you care about it and want to look in to it more, scrypt is also interesting -- it also uses as much memory as it can to stop simply throwing just CPU time at a problem.

Re:Cheap GPUs rendering strong passwords useless? by palish on Monday June 06, 2011 @07:09PM (#2627146)
Thanks for the analysis! Much appreciated.
Re:Cheap GPUs rendering strong passwords useless? by djmdjm on Monday June 06, 2011 @12:54AM (#2623732)
> Mac address of network card + current time?

you're trolling, right?

If not, begin your journey to enlightenment at http://www.cs.berkeley.edu/~daw/papers/ddj-netscape.html (15 years old now!), http://www.schneier.com/paper-prngs.pdf and the kernel source for your favourite OS' /dev/random (the OpenBSD one is pretty well commented)

Re:Cheap GPUs rendering strong passwords useless? by caf on Sunday June 05, 2011 @09:43PM (#2623386)
Read the bcrypt paper: http://www.usenix.org/events/usenix99/provos/provos_html/ind...

The algorithm requires (cost, salt, password) as input, and the output hash includes the cost and salt. When generating a hash for a new password you should of course be choosing this salt randomly, and when checking a password be using the stored cost and salt.

In particular see the Implementation section:

An important requirement of any bcrypt implementation is that it exploit the full 128-bit salt space. OpenBSD generates the 128-bit bcrypt salt from an arcfour key stream, seeded with random data the kernel collects from device timings.

Re:Cheap GPUs rendering strong passwords useless? by Joakal on Sunday June 05, 2011 @09:48PM (#2623397)
Ah. The original article was saying that it was all built-in (salt), only the password is the input. I misread that.