PASTA: PASsword-based Threshold Authentication

We introduce and formalize a new notion of password-based threshold token authentication, which protects password-based authentication against single point of failures. Specifically, we distribute the role of a single server among n servers and allow any t servers to collectively verify clients’ 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 wherein clients can sign on using a two-round (optimal) protocol that meets our strong security guarantees.

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.

Based on joint work with Shashank Agrawal, Payman Mohassel, and Pratyay Mukherjee: https://eprint.iacr.org/2018/885.pdf.

[SLIDES]

Speaker Bios

Peihan Miao just received her PhD in Cryptography from UC Berkeley (advised by Prof. Sanjam Garg) and will join VISA Research as a research scientist in July. She is primarily interested in the area of secure computation. Her research focuses on building cryptographic tools for achieving the optimal computation, communication, and round complexity in secure computation, aiming for bridging the gap between theory and practice.