Is Keccak (aka SHA-3) too fast for passwords?

Yesterday, October 2, 2012, was a big day for computer security. The U.S. National Institute of Standards and Technology (NIST) announced the winner of a 5 year competition to select a new cryptographic hash algorithm, to be known as SHA-3.   The winner, developed by Guido Bertoni, Joan Daemen, Gilles Van Assche  and Michaël Peeters, is called Keccak, pronounced "ketchak" or “catch-ack." It is very fast when running on a computer, as were many of the 63 other hash candidates. But a major reason for its selection was that "Keccak has higher performance in hardware implementations than SHA-2 or any of the other finalists."

That's good news and bad news. Speed is important in many applications that employ a cryptographic hash, and their users should be pleased, but there is one hash use where speed is not desirable, secure storage of the passwords that protect electronic resources, such as user accounts on computers and web sites.  It is standard practice never to store passwords in plaintext format, lest a hacker break-in, which happens all too frequently, compromise all user accounts. Instead a hash of the password is stored. The validity of a submitted password can be checked by hashing the submitted password and comparing the resulting hash value against the stored file of hashed passwords.  This provides some protection in case the stored password file is compromised. It is computationally difficult to reverse a well constructed hash function, which Keccak presumably is after the exhaustive analysis and testing it received prior to selection.

However there is another way to attack stored hashed passwords, exhaustive search using a file of likely passwords, perhaps with common modifications. Each candidate password is hashed and compared with the stored hash value until a match is found. For short enough passwords, all possible combinations can be searched. In this situation having a fast hash algorithm aids the attacker as she can test more possible passwords in a given amount of time and computing resources. 

One solution to this conundrum has been to hash the password multiple times, typically thousands of times or more. This practice, known as key stretching, makes the attacker's job more difficult by slowing down any search. Key stretching is typically done in software, the PBKDF2 algorithm being a common example. 

Having an especially fast hardware implementation makes Keccak less suitable for use in key stretching. A determined attacker who gets hold of the hashed passwords can build special purpose hardware to test each trial password much faster than the legitimate, software-based authentication system can.

One relatively quick solution to this disappointing outcome would be to review the NIST SHA-3 candidate pool for an algorithm that passed all security tests, but which was the slowest and most difficult to implement in hardware, perhaps as measured by gate count. This secondary selection could be done quickly using all the evaluation data already submitted.  Hopefully the algorithm's hardware vs software difficulty ratio would favor software to a greater degree than either SHA 1 or SHA-2 now do. If so, the selected algorithm would be a good a candidate to use for password security, a particularly vital application of cryptographic hashes.