Paper 2022/1682

Interactive Authentication

Deepak Maram, Cornell University, Mysten Labs
Mahimna Kelkar, Cornell University
Ittay Eyal, Technion – Israel Institute of Technology
Abstract

Authentication is the first, crucial step in securing digital assets like cryptocurrencies and online services like banking and social networks. It relies on principals maintaining exclusive access to credentials like cryptographic signing keys, passwords, and physical devices. But both individuals and organizations struggle to manage their credentials, resulting in loss of assets and identity theft. Multi-factor authentication improves security, but its analysis and design are mostly limited to one-shot mechanisms, which decide immediately. In this work, we study mechanisms with back-and-forth interaction with the principals. For example, a user receives an email notification about sending money from her bank account and is given a period of time to abort the operation. We formally define the authentication problem, where an authentication mechanism interacts with a user and an attacker and tries to identify the user. A mechanism's success depends on the scenario~-- whether the user / attacker know the different credentials; each credential can be safe, lost, leaked, or stolen. The profile of a mechanism is the set of all scenarios in which it succeeds. Thus, we have a partial order on mechanisms, defined by the subset relation on their profiles. We find an upper bound on the profile size and discover three types of $n$-credential mechanisms (for any $n$) that are maximally secure, meeting this bound. We show these are all the unique maximal mechanisms for $n \le 3$. We show the efficacy of our model by analyzing existing mechanisms, both theoretical and deployed in widely-used systems, and make concrete improvement proposals. We demonstrate the practicality of our mechanisms by implementing a maximally-secure cryptocurrency wallet.

Note: Latest version: includes partial knowledge and many small improvements.

Metadata
Available format(s)
PDF
Category
Applications
Publication info
Preprint.
Keywords
key managementauthentication
Contact author(s)
sm2686 @ cornell edu
History
2023-04-14: last of 2 revisions
2022-12-03: received
See all versions
Short URL
https://ia.cr/2022/1682
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2022/1682,
      author = {Deepak Maram and Mahimna Kelkar and Ittay Eyal},
      title = {Interactive Authentication},
      howpublished = {Cryptology ePrint Archive, Paper 2022/1682},
      year = {2022},
      note = {\url{https://eprint.iacr.org/2022/1682}},
      url = {https://eprint.iacr.org/2022/1682}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.