Crack that Password? Not in a Billion Years

In less than an hour, a single computer hacker armed with a laptop can crack a handful of six-character passwords, no matter how cleverly crafted. If those passwords are stored with a new scheme devised by researchers at the New York University School of Engineering, however, that same attack could take every computer in existence longer than the estimated age of the universe.

Assistant Professor of Computer Science and Engineering Justin Cappos has introduced PolyPasswordHasher, an open-source password protection scheme for institutions and corporations that offers an unprecedented level of security for password servers, making it immensely difficult for hackers to decode even small numbers of individual passwords.

Compromising password files is both a lucrative and common attack method for cyber criminals, and dozens of high-profile companies each year fall prey to costly attacks that expose customers’ personal information.

The majority of passwords are stored in databases using a method called a salted hash, a one-way encryption technique that considerably reduces the vulnerability of password text in the event that a database is hacked. However, in cases in which attackers gain privileged access to a running system, they can intercept an administrator’s password information before such protections are in place.  In other instances, password databases are encrypted using a key, but if the key itself is stored on a disk, it too can be quickly compromised and used to decode administrator passwords and thereby obtain information about others on the network.

PolyPasswordHasher takes a completely different approach, never directly storing password information in a database. Instead, the information is used to encode a cryptographic “store” that cannot be validated unless a threshold number of passwords are entered. A would-be attacker would need to crack groups of passwords simultaneously—a task so labor-intensive as to be nearly insurmountable—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,” explained Cappos. “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.”

For example, in the above-referenced plausible scenario of an attacker attempting to crack six-character passwords using a modern laptop, Cappos estimated that at least three passwords could be decoded, one at a time, in less than one hour if the computer was checking roughly a billion password hashes per second. PolyPasswordHasher would require that these three passwords be computed at the same time, increasing the search space by approximately 23 orders of magnitude. In practice, this means that all 900 million computers on Earth would need to work nonstop for longer than 13 billion years—the estimated age of the universe—to accomplish the same task.

In the event that an attacker had prior knowledge of a threshold number of administrator passwords and was able to enter the system, all remaining password data would remain under the same protections offered by today’s salted hashing schemes. System administrators can designate which user accounts “count” toward the system threshold of passwords and which do not, allowing them to control for users who may be less diligent about security measures such as password strength.

“In the best case, this is perhaps the safest password data would ever need to be, and at minimum, the protections are the same as the current industry standard,” Cappos said.

PolyPasswordHasher is the first security scheme to employ this approach, and the only single-server, software-only system to exponentially increase the search space for attackers. The system creates no noticeable changes in interface or user experience, and it can be integrated quickly and seamlessly into existing systems with a negligible increase in database storage requirements.

Cappos and his collaborators believe PolyPasswordHasher could dramatically reduce or eliminate the impact from password file breaches that routinely plague corporations. They also explained in their paper that while PolyPasswordHasher is not designed for use on an individual smartphone or computer with a single user, “every device that is networked or communicates with a cloud or web-based server—and that’s nearly every device in use today— would be safer if servers used this storage method.”

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 and improve security practices in this area. Collaborators on the project are Santiago Torres, an NYU School of Engineering graduate student, and Justin Quick, a senior application developer at the National Geographic Society.

To read more and access free reference implementations for Python, Ruby, C, and Django, visit https://polypasswordhasher.github.io/PolyPasswordHasher/.