Two-factor authentication (TFA), enabled by hardware tokens and personal devices, is gaining momentum. The security of TFA schemes relies upon a human-memorable password p drawn from some implicit dictionary D and a t-bit device-generated one-time PIN z. Compared to password-only authentication, TFA reduces the probability of adversary’s online guessing attack to 1/(|D|*2^t) (and to 1/2^t if the password p is leaked). However, known TFA schemes do not improve security in the face of offline dictionary attacks, because an adversary who compromises the service and learns a (salted) password hash can still recover the password with O(|D|) amount of effort. This password might be reused by the user at another site employing password-only authentication.
We present a suite of efficient novel TFA protocols which improve upon password-only authentication by a factor of 2^t with regards to both the online guessing attack and the offline dictionary attack. To argue the security of the presented protocols, we first provide a formal treatment of TFA schemes in general. The TFA protocols we present enable utilization of devices that are connected to the client over several channel types, formed using manual PIN entry, visual QR code capture, wireless communication (Bluetooth or WiFi), and combinations thereof. Utilizing these various communication settings we design, implement, and evaluate the performance of 13 different TFA mechanisms, and we analyze them with respect to security, usability (manual effort needed beyond typing a password), and deployability (need for additional hardware or software), showing consistent advantages over known TFA schemes.
The idea underlying all our TFA protocols is for the server to store a randomized hash of the password, h = H(p|s), and for the device to store the corresponding random secret s as shown in the following figure. The authentication protocol then checks whether the user types the correct password p and owns the device, which stores s. If F_k is computed on a nonce x – e.g. equal to the current time, or chosen as a challenge by the server – the device could output z = s xor F_k(x) as its PIN without exposing s , and the server can verify the (password, PIN) pair (p, z) against the hash H(p; s) by recomputing s as z xor F_k(x). Such protocol is 1/(|D| * 2^t)-secure against online guessing even in the presence of lunch-time attacks on the device and man-in-the-middle attacks on the communication channel between the client and the device. As for an offline dictionary attack after a server corruption, the attacker needs s to verify password guesses, making the off-line dictionary attack time grow to O(|D| * 2^t).

Our LBD-PIN variant, Low-bandwidth TFA mechanism with PIN entry
Our LBD-PIN variant, Low-bandwidth TFA mechanism with PIN entry

This work relies on PKI-authenticated client-server channel which is the prominent setting deployed by web-services. However, PKI requires trust on third parties and has been extensively under attack in the past. In our ASIACCS’16 paper, we introduced Device-Enhanced Password-Authenticated Key Exchange (DE-PAKE), a cryptographic primitive. Based on DE-PAKE protocol we designed another class of secure TFA that does not rely on PKI and has improved the user experience by replacing the PIN copy action with a simpler/easier PIN verification.

We presented a secure two-factor authentication (TFA) scheme based on the possession by the user of a password and a crypto-capable device. Security is “end-to-end” in the sense that the attacker can attack all parts of the system, including all communication links and any subset of parties (servers, devices, client terminals), can learn users’ passwords, and perform active and passive attacks, online and offline. In all cases the scheme provides the highest attainable security bounds given the set of compromised components. Our solution builds a TFA scheme using any Device-Enhanced PAKE, and any Short Authenticated String (SAS) Message Authentication, defined by Vaudenay.

We showed an efficient instantiation of this modular construction which utilizes any password-based client-server authentication method, with or without reliance on public-key infrastructure. The security of the proposed scheme is proven in a formal model that we formulated as an extension of the traditional PAKE model. We also reported on a prototype implementation of our schemes, including TLS-based and PKI-free variants, as well as several instantiations of the SAS mechanism, all demonstrating the practicality of our approach.




External Collaborators:

  • Stanislaw Jarecki (Associate Professor; School of Information and Computer Sciences, University of California at Irvine)
  • Hugo Krawczyk (IBM Watson Research)
  • Naveen Nathan (Graduate student; School of Information and Computer Sciences, University of California at Irvine)


  • Two-Factor Password-Authenticated Key Exchange with End-to-End Password Security.
    Maliheh Shirvanian, Nitesh Saxena, Stanislaw Jarecki, and Hugo Krawczyk
    Stanislaw Jarecki, Mohammed Jubur, Hugo Krawczyk, Maliheh Shirvanian, and Nitesh Saxena. In ACM Transactions on Privacy and Security, 2020. [pdf]
  • Two-Factor Authentication with End-to-End Password Security.
    Stanislaw Jarecki, Hugo Krawczyk, Maliheh Shirvanian and Nitesh Saxena
    In International Conference on Practice and Theory of Public Key Cryptography (PKC), March 2018.
  • Two-Factor Authentication Resilient to Server Compromise Using Mix-Bandwidth Devices.
    Maliheh Shirvanian, Stanislaw Jarecki, Nitesh Saxena, Naveen Nathan.
    In the Network and Distributed System Security Symposium (NDSS), February 2014.