I published the first modern password cracker in 1991; the first with dictionary generation, the first with networking, the first with a fast crypt() implementation and (eventually) the first with a vector-friendly (and network-authentication capable) pluggable API, although this was originally meant for bitslicing rather than GPU which eventually superseded real vector processors.
But when I started back in 1990 all I could manage was a few calls to Bob Morris’s libc crypt() per second, per CPU; on a Sun 3/60 (of which I had three) I could do 3 or 4 guesses per second; also I had a couple of DEC 5830s which could do perhaps a dozen guesses per second apiece, but they were “user service” machines which meant they were meant to be doing “real work”. I later discovered a DECstation 5000/200 which I could use, and which gave me another 20 guesses per second.
All told by scrounging spare university hardware I could make fewer than perhaps 100 guesses per second at peoples’ passwords, and there were a few thousand students to monitor.
So instead of speed I attacked peoples’ habits – at 100 guesses per second a good weekend will give you 20 million guesses, and with a userbase of 7500 students you could thereby make 2500+ guesses at each student’s password; you’d certainly catch some of them so long as you structured your guesses wisely. So I did that, and the results were astonishingly successful. The release of Crack kicked up a storm with rates of sub-1000 guesses per second, way before the thousands, millions or billions of guesses per second that systems have been able to achieve since.
But then there’s this article, regarding which I will not criticise anything that Tom Ptacek says, because his head is largely screwed on properly regards what we need to do:
Ptacek: It’s similar to if you said, let’s take SHA-1 password, but instead of just using SHA-1, let’s run SHA-1 on itself thousands of times. So, we’ll take the output of SHA-1 and feed it back to SHA-1, and we’ll do that thousands and thousands of times, and you’ll only know if your password hash is right, when you look at the result of that 1,000th SHA-1 run. So, in order to make that password hash work, you have to run the algorithm 1,000 times for each guess. That’s roughly the tactic that the modern, secure password hashes take. These are algorithms that are designed so that you can’t arrive at the result without lots and lots of work. I mean, we’re talking about 100 milliseconds [one-tenth of a second] worth of work on modern hardware to get the results of a single password attempt.
I’m with you totally, Tom … right up until:
Let’s say we have a Web application that lost 10 million password hashes, but they’re bcrypted passwords. So, I think in that last dump we saw from the LinkedIn dump, about like three million of those passwords had been cracked. It was really quick and easy to see if your password had been in there. In this case, if we lost 10 million bcrypted passwords, instead of 3 million of them being published and compromised, you might be looking at tens or hundreds of user passwords being compromised. Because you could maybe effectively look for every password that was “password,” but you certainly couldn’t run a dictionary against every password there anymore.
To make this short: history disagrees; of your few million hashes pick off a bitesize piece and have fun. Whoever said you had to break all of them?
There’s a pendulum that swings from structured-guessing to brute-force, and I think we’re on the return path at the moment; the complementary solution to widespread adoption of bcrypt() and PBKDF2 is to fix the user password management problem.
For me that means:
adoption of long pseudorandom passwords; plucking a number out of the air I go around telling people to use 16-character random mixed-case alphanumerics with punctuation, which are clearly untenable for human use especially when you…
change your passwords on a schedule – once a quarter, once a year, whatever the schedule it’s in case someone has picked specifically your ciphertext to break and is throwing a few thousand bucks’ worth of AWS and Hashcat at it specifically – so you need to change before their likely time-to-break is exceeded; because this is all such a pain you will need to…
use a decent password management tool like 1Password, PasswordSafe, whatever, so you can stop whining about how long the passwords are and how hard it is to choose and change them because most of the work is done for you; and finally you need…
user education and motivation. But you knew that already didn’t you?
Two factor? Yah, no argument Tom, I totally love it so long as implementors don’t have to call out to a trusted third party or other identity hierarchy to achieve it. You know – like SecurID, or voice synthesis.
UPDATE: Commentary continues at http://dropsafe.crypticide.com/article/7310
 …while we’re at it I believe I wrote the first network vulnerability scanner too, but that’s when I was working for Sun and they wouldn’t publish it due to legal fears. Take heed everyone, open-source full-disclosure would have given the community a Nessus-like tool 3 or 4 years earlier and we’d all have been better off…