UAB - The University of Alabama at Birmingham

SPHINX: A Password Store that Perfectly Hides Passwords from Itself

Passwords are the prime example of text-based authentication, and the most dominant means of user authentication deployed on the Internet today. However, they suffer from numerous security and usability issues. For example, passwords are often weak secrets, i.e. low-entropy – short and non-random, due to the human memorability requirement. Current mechanisms password managers have been proposed to improve the security of systems relying on passwords. However, these schemes do not address the issue of compromised or malicious servers that store the passwords. Given that the users reuse their password over multiple accounts, exposure of the passwords stored on one service leads to compromise of other services that use the same password. Similarly, if the password manager that stores the password gets compromised, all the stored passwords would be reveals.
One broad class of approaches that improves the security of password-based authentication protocol from the client-side or user-side alone (i.e., without making any changes to a persistent server that uses traditional password-based authentication) is referred to as password managers. Password managers allow users to pick randomized high-entropy passwords without the need to memorize them.

In this work, we introduced a new password management mechanism, SPHINX, that can address many security and usability problems with passwords from the client/user side (i.e., transparent to most existing web authentication services, including the typical password-over-TLS mechanism). SPHINX is a device-based password manager that transforms a human-memorable password into a random password with the aid of a device, without the need to store the passwords on the device and without the device learning anything about the password even when computing on it.

In SPHINX, user registers a hardened randomized password rwd with the server, but only remembers a memorable password pwd that could be the same for multiple accounts (we use the terms master password and memorable password interchangeably). For each server S with which the user U has an account, the device D (a smart phone) stores a unique key k. The key is used to map pwd into rwd using the oblivious pseudo random function (OPRF) F such that rwd = Fk(pwd|domain). The OPRF function receives input k from the device and pwd from the user and computes rws as H(pwd|domain, H’(pwd|domain)k), where H is a SHA256 hash and H’ is a special-purpose hash that maps a string to a point on an elliptic curve. pwd and rwd are never stored in C and (in contrast to the current password managers neither rwd nor pwd is ever stored in or exposed to D. Instead, D and C run the PTR protocol to obliviously compute rwd at the login time.

A high-level overview of SPHINX. U enters memorable password pwd and approves the communication on D (explicit consent), D and C run an OPRF protocol (instantiated as FK-PTR) to construct a randomized password rwd, C sends rwd to S over SSL/TLS to authenticate to the service. A smartphone instantiation is developed and tested in the paper. However, the phone can be replaced with an online service.

A high-level overview of SPHINX. U enters memorable password, pwd, and approves the communication on D (explicit consent). D and C run an OPRF protocol (instantiated as FK-PTR) to construct a randomized password, rwd, C sends rwd to S over SSL/TLS to authenticate to the service. A smartphone instantiation is developed and tested in the paper. However, the phone can be replaced with an online service.

Our password manager has several interesting security and usability features including: 1) Resistance to offline dictionary attacks under server compromise (or server being malicious). 2) Resistance to phishing attacks. 3) Resistance to offline dictionary attacks under device compromise (or device being malicious), in particular hiding the user’s master password with information theoretic security. 4) Resistance to eavesdropping and MitM on the device-client channel without the need to establish a confidential channel (the properties of the OPRF protocol executed over this channel ensure that no externally protected or secured channel is needed).

People

Faculty

Student

External Collaborators:

  • Stanislaw Jarecki (Associate Professor; School of Information and Computer Sciences, University of California at Irvine)
  • Hugo Krawczyk (Research Scientist; IBM T.J. Watson Research Center)

Publication