Paper 2018/885

PASTA: PASsword-based Threshold Authentication

Shashank Agrawal, Peihan Miao, Payman Mohassel, and Pratyay Mukherjee

Abstract

Token-based authentication is commonly used to enable a single-sign-on experience on the web, in mobile applications and on enterprise networks using a wide range of open standards and network authentication protocols: clients sign on to an identity provider using their username/password to obtain a cryptographic token generated with a master secret key, and store the token for future accesses to various services and applications. The authentication server(s) are single point of failures that if breached, enable attackers to forge arbitrary tokens or mount offline dictionary attacks to recover client credentials. Our work is the first to introduce and formalize the notion of password-based threshold token-based authentication which distributes the role of an identity provider among $n$ servers. Any t servers can collectively verify passwords and generate tokens, while no t-1 servers can forge a valid token or mount offline dictionary attacks. We then introduce PASTA, a general framework that can be instantiated using any threshold token generation scheme, wherein clients can "sign-on" using a two-round (optimal) protocol that meets our strong notions of unforgeability and password-safety. We instantiate and implement our framework in C++ using two threshold message authentication codes (MAC) and two threshold digital signatures with different trade-offs. Our experiments show that the overhead of protecting secrets and credentials against breaches in PASTA, i.e. compared to a naive single server solution, is extremely low (1-5%) in the most likely setting where client and servers communicate over the internet. The overhead is higher in case of MAC-based tokens over a LAN (though still only a few milliseconds) due to public-key operations in PASTA. We show, however, that this cost is inherent by proving a symmetric-key only solution impossible.

Metadata
Available format(s)
PDF
Category
Cryptographic protocols
Publication info
Published elsewhere. ACM CCS 2018
DOI
10.1145/3243734.3243839
Keywords
passwordstoken-based authenticationthreshold cryptographydigital signaturemessage authentication codeoblivious pseudorandom function
Contact author(s)
shashank agraval @ gmail com
History
2018-09-23: received
Short URL
https://ia.cr/2018/885
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2018/885,
      author = {Shashank Agrawal and Peihan Miao and Payman Mohassel and Pratyay Mukherjee},
      title = {PASTA: PASsword-based Threshold Authentication},
      howpublished = {Cryptology ePrint Archive, Paper 2018/885},
      year = {2018},
      doi = {10.1145/3243734.3243839},
      note = {\url{https://eprint.iacr.org/2018/885}},
      url = {https://eprint.iacr.org/2018/885}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.