Speed Hashing

You could also increase the hash rounds which would artificially increase the time needed to calculate the password from the hash. See http://en.wikipedia.org/wiki/Key_stretching for more information.

Salt is not required to be secret at all, the idea of a random salt (and it should be unique for each user) is to make it impossible to use rainbow tables. Of course, attacker knows the salt since it’s in the same DB table as a password, but he will have to brute-force each account separately, which makes it almost impossible to hack thousands of accounts at once. This is pretty much the best you can do, and the same approach is used by linux and many other systems for decades.

Also, when adding the salt one should always use HMAC, instead of simple concatenation of salt to the password. HMAC is developed specially for this, it benefits in better security as e.g. HMAC-MD5 does not suffer from the same weaknesses as MD5. I believe all major languages have support for it.

Thanks for the Article! I’ve added it to the hashcat wiki: http://hashcat.net/wiki/

One note: I did not optimize my MD5 hash cracking code on hashcat CPU for a while. Most of my optimizations go into oclHashcat-lite first. While the 8213 Mhash/s on a stock clocked hd7970 is unbeaten, if I would port this code to CPU a stock clocked 6-core bulldozer it would run at 220 Mhash/s, not 50 Mhash/s.

My bank, BMO, requires exactly 6 alphanumeric characters. No symbols or whitespace. They also use security questions, two of which I always get wrong.

@sofa420: You’ve missed the point quite thoroughly. Nobody is going to try and find collisions for those hashes that would somehow return the original plaintext, they’re just going to run a password dictionary through your algorithm to see if any of them gives them the stored hash.

Given that they will have access to your stored salts (they’ve got your database) all that algorithm does is double the amount of hashing/computing/time needed.

@Lior_Tal: If they got hold of the password database, I would assume they also got hold of the password checking code (be it scripted, compiled or publicly available). Even in the improbable case they didn’t, they could guess the algorithm if they managed to generate and store their own password (known plaintext + digest).

Another example of super high-speed checksum calculation is 40 or 100Gbps Ethernet (High Speed Ethernet) frames CRC check!

@Lior_Tal: The only sane way to approach security is to assume that the bad guys have everything you have, up to and including physical possession of the machine(s) (whether by a successful remote or by actually taking the machine). And understand that there is no such thing as absolute security (even booby-trapping your servers isn’t a guarantee); all you can ever do is make things (to use the technical phrase) really, really frikkin’ inconvenient for the cracker. Making the search space as large as possible (long, complex passwords or passphrases plus a unique per-user token/salt) and the transformation algorithm as slow as possible, while eliminating any inefficiencies that would make it trivially simple to speed things up (as with Bcrypt, Scrypt or PBKDF2) come under the category of “making things really, really frikkin’ inconvenient”.

And let’s keep in mind that no matter how sanitary our own personal habits may be, most users tend to use the same password (or couple of passwords) everywhere, so the comment system on your kitty-cat blog (being a bit facetious) may well be the gatekeeper for your users’ email, bank accounts, work accounts, and so on. I can’t stress this enough: you are never protecting just your own site with your password system.

I’ve recently been working on an app with some crypto stuff in it, and i’m totally pumped that the exact two things you mentioned in your developers advice paragraph (Bcrypt and PBKDF2) are the two algorithms i’m relying on! Sweet :slight_smile:

(if anyone’s interested, it’s called ‘Skeleton Key Password Manager’ on the iOS app store)

Hmmm, Wikipedia says:

One weakness of PBKDF2 is that while its c parameter can be adjusted to make it take an arbitrarily large amount of computing time, it can be implemented with a small circuit and very little RAM, which makes brute-force attacks using ASICs or GPUs relatively cheap[13].

Can we use old hash algorithms but with a better salt? If the reason bcrypt is good is memory requirements perhaps we can use MD5 with a very long salt? Is there a salting method which does not simply concatenate salt with the password but uses a less GPU friendly logic?

@Misha Golub: As Ivanhoe011 pointed out above, there are alternative ways to use a salt, specifically HMAC variants of hashing. But that still leaves you with an algorithm that is relatively small both in time and space requirements, which still leaves you wide-open to fast brute force attacks.

A “system salt” is of very little value, since it represents only a minor modification to the hashing algorithm. A cracker can run a brute-force attack and look for ANY match in the user database. With a per-user salt (a nonce), the algorithm is effectively changed for every user, so brute-forcing can only be done one account at a time.

As for the space weakness of PBKDF2, that’s a fact, but it’s time complexity still makes it valuable for use in environments where space complexity would be a genuine problem. I am thinking specifically about low-cost (or free) shared hosting, where the space requirements for Bcrypt or Scrypt might trigger caps or suspensions. Again, there is no such thing as perfect security, the best we can do is to make things sufficiently inconvenient for the bad guys without overwhelming our own resources. I would have no compunctions about using PBKDF2 in a SME or personal site environment, where the available resources are likely to be significantly smaller than they would be on a dedicated/colo machine or in a multi-instance cloud environment.

A cunning, attractive individual of the opposite sex can still get all of your information, the key to your house, the money in your wallet, and the clothes on your back, in just a week or two of telling you what you want to hear.

Hackers don’t use software to nearly as much these days, not because security measures have improved, but because they can dig through your dumpster or lie to you on a social networking site and achieve the same objectives, for a tiny fraction of the time & effort.

You can build another Great Wall of China but it’s pointless when your attackers are coming from anywhere but the North.

It’s too bad that I cannot find a bank that allows me to use pass-phrases of a usable length, much less any consistency between password requirements.

Password requirements

  • Wells Fargo
    • 6-14
    • at least one letter and one number.
    • It cannot contain nine or more numbers.
    • Allows @, %, &, #
  • Chase
    • 7-32
    • at least one letter and one number
    • Cannot include special characters (&, %, *, etc.)
    • Cannot be the same as any of the last five Passwords you've used
    • Cannot be the same as your User ID
  • American Express
    • 8 - 20
    • at least one letter and one number
    • Allows %,&,_,?,#,=,-
    • Is not case sensitive!!
  • Pay Pal
    • 8 - 40
    • includes both capital and lower case letters
    • Not a word you can find in the dictionary
    • Requires at least one 1-9,!,*,_,etc

Great tips for users and developers alike. I’m very interested to see how this field changes when quantum computers start to play a role. With the D-Wave One now sporting a 128-qubit processor chipset, it’s going to get interesting soon. This isn’t my field (by a very long shot), but it seems like hardware like that could supplant GPUs in calculating hashes and potentially force some big changes in how we secure… jeez, maybe everything.

Is the claim no one bothers with rainbow tables any more really accurate though? I note someone in reply to Anthony Ferrara’s blog claimed that rainbow tables still have their uses.

I’m not involved in the field, but it strikes me too as probably wrong. Storage space isn’t exactly expensive. Even with the recent spikes due to the Thailand floods, you can still have 8TB for less then US$500 or about the price of a high end GPU. This is more then enough to store all current MD5 tables from the distributed rainbow tables effort http://www.freerainbowtables.com/en/tables2/ with room for expansion either of your own work or future stuff from the distributed work. How much time will this save you? I don’t actually know although my impression is it will often be faster then computing the stuff again. (Many of the tables apparently require GPU for use http://www.freerainbowtables.com/phpBB3/viewtopic.php?f=2&t=3255 .)

I’m not sure it’s really a matter of just hoping your victim didn’t use a salt. If you’ve targeting a specific victim or perhaps a few where security is paramount perhaps it’s forlorn. But if you’re say. a spammer breaking in to sites to try and steal their passwords hoping they were used for Facebook, twitter or email accounts you can then use for spamming, the recent high profile anonymous and LulzSec breaches have shown theres a fair chance you will have success many times since so many sites still don’t bother to salt. Given the price of storage space, you probably only have to use your rainbow table a few times to make up for the cost. In other words, it’s a numbers game and the evidence suggests to me rainbow tables will often still be a winner in some fashion.

See also http://news.ycombinator.com/item?id=2891654

Note that I’m not disagreeing with the basic premise, that with GPUs certain hashes can be calculated very fast so a salt is far from sufficient with out a fairly long password and a better hash function, simply pointing out from what I can tell, rainbow tables are still useful and still being used.

sanderd: The idea of the questions is to apply more than one human authentication approach (Something you know, have or are) without introducing any extra complexity such as credit cards or electronic signature.

More on the subject: http://www.cs.cornell.edu/courses/cs513/2005fa/nnlauthpeople.html

Bcrypt and PBKDF2 are not hashes! Sure, PBKDF2 may use cryptographically secure hashes internally, but it’s a key derivation function, not a hash. You should never use plain secure hash, salted or not, to store passwords. Secure hashes, contrary to what this terrible in its sloppy wording article states, are always designed to be as fast as possible. Even the newest of NIST-approved hash functions, SHA-3 (Keccak), which is somewhat slow in software, is fast in hardware. See also BLAKE2 which is a state-of-the-art of hashes for software (it’s based on another finalist of SHA-3).

As for the comments recommending scrypt over bcrypt and PBKDF, indeed, scrypt was designed to be sequential memory-hard and therefore more expensive to crack on ASICs than other password storage schemes, but experimental results showed that you need really a lot of memory, more than you can afford using on each login in most setups, for it to provide the same level of security as you can easily achieve with bcrypt today. Scrypt is the future, but for today you’re probably better off with bcrypt (or you can combine them if you’re super paranoid, but you’ll probably do it wrong so stick to bcrypt for the time being).

There are a couple of issues with bcrypt in PHP applications: It truncates after 72 characters OR after any null bytes. Anthony Ferrara (author of PHP’s password_*) API wrote up these issues recently.

One solution is to use password_hash(base64_encode(hash('sha256', $password, true))); and password_verify(base64_encode(hash('sha256', $password, true)), $storedHash).

Another solution is to use scrypt instead.