New Protection Scheme Makes Weak Passwords Virtually Uncrackable

A team of researchers at the New York University Polytechnic School of Engineering say they have found a way to help organizations better protect passwords.

Using an open-source password protection scheme they dubbed PolyPasswordHasher, the researchers believe they can make it much more difficult for hackers to decode even the shortest individual passwords. The PolyPasswordHasher is currently being tested as part of the Password Hashing Competition, a global effort organized by security professionals to identify new password protection schemes.  

According to the researchers, most passwords are stored in databases using a salted hash, a one-way encryption technique that offers protection in the event a database is hacked. However in cases where attackers gain privileged access to a running system, they can intercept an administrator’s password information before that protection is in place.

With PolyPasswordHasher, password information is never stored directly in a database; the information is used to encode a cryptographic “store” that cannot be validated unless a certain number of passwords are entered. In other words, an attacker would need to crack multiple passwords simultaneously in order to verify any single hash.

“PolyPasswordHasher divides secret information—in this case, password hashes—into shares, and just like a puzzle that is meaningless unless the pieces are assembled, no individual password can be validated unless a certain number of them are known and entered,” said Assistant Professor of Computer Science and Engineering Justin Cappos, in a statement. “Even if the password file and all other information on disk were stolen, an attacker could not verify a single correct password without guessing a large number of them correctly.”

Cappos estimated an attacker using a modern laptop could crack at least three six-character passwords in an hour if the computer was checking roughly a billion password hashes per second. With PolyPasswordHasher, the attacker would be required to compute these three passwords at the same time, increasing the search space by approximately 23 orders of magnitude. The researchers estimate that in practice, all 900 million computers on Earth would need to work nonstop for longer than 13 billion years to compute the three passwords at the same time. 

“This is conceptually similar to encrypting the passwords with a key that is only recoverable when a threshold of passwords are known,” the researchers note in their paper. “Even if the password file and all other data on disk is obtained by a malicious party, the attacker cannot crack any individual password without simultaneously guessing a large number of them correctly. PolyPasswordHasher is the first single server, software-only technique that increases the attacker’s search space exponentially.”

The researchers’ paper can be read here.