SPIES Lab, Computer Science and Engineering

DE-PAKE

Device-enhanced password protocols with optimal online-offline protection

Today, passwords constitute the prevalent authentication mechanism for bootstrapping security in most online applications (and many offline systems). A plethora of sensitive information stored in many different contexts therefore depends on the security of password-based authentication. However, passwords are vulnerable to both online and offline dictionary attacks that build on password dictionaries from which a significant portion of passwords are chosen. Candidate passwords for authenticating a user to a server can be tested by an attacker through online interactions with the server. Furthermore, an attacker breaking into a server can mount an offline attack that uses information stored on the server (typically, a salted one-way mapping of the password) to test the different passwords in the dictionary.
Furthermore, since many users re-use their passwords across multiple services, compromising one service may compromise user accounts at other services. In this paper, we present solutions directed to enhance password protocols against both online and offline attacks by an active man-in-themiddle attacker acting on both user-server and user-device links, and capable of compromising devices and servers by learning their full internal state (e.g., a server’s password file or the device’s secrets).
In this work we introduce a setting that we call Device-Enhanced PAKE (DE-PAKE), where PAKE (password-authenticated key exchange) protocols are strengthened against online and offline attacks through the use of an auxiliary device that aids the user in the authentication process as shown in the following figure.

Figure 1: The FK-PTR-PAKE Scheme

Figure 1: The FK-PTR-PAKE Scheme


We build such schemes and show that their security, properly formalized, achieves maximal-attainable resistance to online and offline attacks in both PKI and PKI-free settings. In particular, an online attacker must guess the user’s password and also control the user’s auxiliary device to authenticate. Moreover, an attacker who corrupts the server cannot learn the users’ passwords via an offline dictionary attack. Notably, our solutions do not require secure channels, and nothing (in an information-theoretic sense) is learned about the password by the device (or a malicious software running on the device) or over the device-client channel, even without any external protection of this channel. An attacker taking over the device still requires a full online attack to impersonate the user.

Figure2: Instantiation of FK-PTR-PAKE with PKI-free PAKE protocol

Figure2: Instantiation of FK-PTR-PAKE with PKI-free PAKE protocol


 
Importantly, our DE-PAKE scheme can be deployed at the user end without the need to modify the server and without the server having to be aware that the user is using a DE-PAKE scheme. In particular, the schemes can work with standard servers running the usual password-over-TLS authentication. Based on these protocols we implement a practical DE-PAKE system and evaluate its performance based on the instantiation shown in following figure. To improve usability the implemented system utilizes automated and user-transparent data channel between the mobile device and the client, falling back to localized communication only when the device looses data connectivity.

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