International Association
for Cryptologic Research

Multi-Factor Authentication (MFA), often coupled with Key Exchange (KE), offers very strong protection for secure communication and has been recommended by many major governmental and industrial bodies for the use in highly sensitive applications. Instantiations of the MFA concept vary in practice and in the research literature and various efforts in designing secure MFA protocols were unsuccessful.

This paper introduces a modular approach to the design and analysis of arbitrary MFAKE protocols, in form of an $(\\alpha,\\beta,\\gamma)$-MFAKE framework, that can accommodate multiple types and quantities of authentication factors, focusing on the three widely adopted categories that provide evidence of knowledge, possession, and physical presence. The framework comes with (i) a model for \\emph{generalized MFAKE} that implies many known flavors of single- and multi-factor Authenticated Key Exchange (AKE), and (ii) offers generic and modular constructions of secure MFAKE protocols that can be tailored to the needs of a particular application.

Our generic $\\mfake$ protocol is based on the new notion of \\emph{tag-based MFA} that in turn implies tag-based versions of many existing single-factor authentication schemes. We show examples and discuss generic ways to obtain tag-based flavors of password-based, public key-based, and biometric-based authentication protocols. By combining various tag-based single-factor authentication-only protocols, whose executions can be parallelized, with a single run of an Unauthenticated Key Exchange (UKE) we construct $\\mfake$ that is superior to a na{\\\"i}ve black-box combination of multiple single-factor AKE schemes.