Practical Threshold Multi-Factor Authentication

Multi-factor authentication (MFA) has been widely used to safeguard high-value assets. Unlike single-factor authentication (e.g., password-only login), $t$ -factor authentication ( $t$ FA) requires a user always to carry and present $t$ specified factors so as to strengthen the security of login. Nevertheless, this may restrict user experience in limiting the flexibility of factor usage, e.g., the user may prefer to choose any factors at hand for login authentication. To bring back usability and flexibility without loss of security, we introduce a new notion of authentication, called $(t,n)$ threshold MFA, that allows a user to actively choose $t$ factors out of $n$ based on preference. We further define the “most-rigorous” multi-factor security model for the new notion, allowing attackers to control public channels, launch active/passive attacks, and compromise/corrupt any subset of parties as well as factors. We state that the model can capture the most practical security needs in the literature. We design a threshold MFA key exchange (T-MFAKE) protocol built on the top of a threshold oblivious pseudorandom function and an authenticated key exchange protocol. Our protocol achieves the “highest-attainable” security against all attacking attempts in the context of parties/factors being compromised/corrupted. As for efficiency, our design only requires $4+t$ exponentiations, 2 multi-exponentiations and $\mathbf {2}$ communication rounds. Compared with existing $t$ FA schemes, even the degenerated $(t,t)$ version of our protocol achieves the strongest security (stronger than most schemes) and higher efficiency on computational and communication. We instantiate our design on real-world platform to highlight its practicability and efficiency.

I. Introduction

Multi-factor authentication (MFA) has been deployed in real-world applications to safeguard high-value assets, e.g., online banking. A user is required to make use of factors, at the same time, to execute secure authentication. This -factor authentication (FA) naturally brings more challenges, than single-factor authentication, to attackers since there are factors that need to be compromised for an impersonation. For instance, EMV [1], [2], a widely adopted payment method, allows one to present his smart card and the password/PIN to pay a bill on a POS terminal. Attackers cannot steal the money by only being given the smart card or the password.