Paper 2019/1470

PESTO: Proactively Secure Distributed Single Sign-On, or How to Trust a Hacked Server

Carsten Baum, Tore K. Frederiksen, Julia Hesse, Anja Lehmann, and Avishay Yanai


Single Sign-On (SSO) is becoming an increasingly popular authentication method for users that leverages a trusted Identity Provider (IdP) to bootstrap secure authentication tokens from a single user password. It alleviates some of the worst security issues of passwords, as users no longer need to memorize individual passwords for all service providers, and it removes the burden of these service to properly protect huge password databases. However, SSO also introduces a single point of failure. If compromised, the IdP can impersonate all users and learn their master passwords. To remedy this risk while preserving the advantages of SSO, Agrawal et al. (CCS'18) recently proposed a distributed realization termed PASTA (password-authenticated threshold authentication) which splits the role of the IdP across $n$ servers. While PASTA is a great step forward and guarantees security as long as not all servers are corrupted, it uses a rather inflexible corruption model: servers cannot be corrupted adaptively and --- even worse --- cannot recover from corruption. The latter is known as proactive security and allows servers to re-share their keys, thereby rendering all previously compromised information useless. In this work, we improve upon the work of PASTA and propose a distributed SSO protocol with proactive and adaptive security (PESTO), guaranteeing security as long as not all servers are compromised at the same time. We prove our scheme secure in the UC framework which is known to provide the best security guarantees for password-based primitives. The core of our protocol are two new primitives we introduce: partially-oblivious distributed PRFs and a class of distributed signature schemes. Both allow for non-interactive refreshs of the secret key material and tolerate adaptive corruptions. We give secure instantiations based on the gap one-more BDH and RSA assumption respectively, leading to a highly efficient 2-round PESTO protocol. We also present an implementation and benchmark of our scheme in Java, realizing OAuth-compatible bearer tokens for SSO, demonstrating the viability of our approach.

Available format(s)
Cryptographic protocols
Publication info
Published elsewhere. Minor revision. EuroS&P 2020
Single Sign-OnAuthenticationIdentity ProviderDistributed Protocols
Contact author(s)
cbaum @ cs au dk
tore frederiksen @ alexandra dk
juliahesse2 @ gmail com
anja lehmann @ hpi de
yanaia @ vmware com
2020-11-16: last of 5 revisions
2019-12-23: received
See all versions
Short URL
Creative Commons Attribution


      author = {Carsten Baum and Tore K.  Frederiksen and Julia Hesse and Anja Lehmann and Avishay Yanai},
      title = {{PESTO}: Proactively Secure Distributed Single Sign-On, or How to Trust a Hacked Server},
      howpublished = {Cryptology ePrint Archive, Paper 2019/1470},
      year = {2019},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.