The most commonly adopted password management technique is to store web account passwords on a password manager and lock them using a master password. However, current online password managers do not hide the account passwords or the master password from the password manager itself, which highlights their real-world vulnerability and lack of user confidence in the face of malicious insiders and outsiders that compromise the password management service especially given its online nature. We attempt to address this crucial vulnerability in the design of online password managers by proposing a cloud-based password manager that does not learn or store master passwords and account passwords. We introduce the protocol design and report on a full implementation of the system. Our implementation provides several security features, including enforcement of a unique and secure password per each service, robustness to online password guessing attacks against the password manager and the web service, robustness to password dictionary attacks upon compromise of the password manager and the web service, and security against phishing attacks. Furthermore, to assess users’ perceptions of the security and usability of our password manager, we conducted a lab-based study. The findings from the study suggest that our system is close to being practical for everyday use and is viewed by users as both usable and more secure/trustworthy.

We present a secure two-factor authentication (TFA) scheme based on the user’s possession of a password and a crypto-capable device. Security is “end-to-end” in the sense that the attacker can attack all parts of the system, including all communication links and any subset of parties (servers, devices, client terminals), can learn users’ passwords, and perform active and passive attacks, online and offline. In all cases the scheme provides the highest attainable security bounds given the set of compromised components. Our solution builds a TFA scheme using any Device-enhanced Password-authenticated Key Exchange (PAKE), defined by Jarecki et al., and any Short Authenticated String (SAS) Message Authentication, defined by Vaudenay. We show an efficient instantiation of this modular construction, which utilizes any password-based client-server authentication method, with or without reliance on public-key infrastructure. The security of the proposed scheme is proven in a formal model that we formulate as an extension of the traditional PAKE model. We also report on a prototype implementation of our schemes, including TLS-based and PKI-free variants, as well as several instantiations of the SAS mechanism, all demonstrating the practicality of our approach. Finally, we present a usability study evaluating the viability of our protocol contrasted with the traditional PIN-based TFA approach in terms of efficiency, potential for errors, user experience, and security perception of the underlying manual process.1

We introduce Oblivious Key Management Systems (KMS) as a much more secure alternative to traditional wrapping-based KMS that form the backbone of key management in large-scale data storage deployments. The new system, that builds on Oblivious Pseudorandom Functions (OPRF), hides keys and object identifiers from the KMS, offers unconditional security for key transport, provides key verifiability, reduces storage, and more. Further, we show how to provide all these features in a distributed threshold implementation that enhances protection against server compromise.

We introduce a novel approach to password management, called SPHINX, which remains secure even when the password manager itself has been compromised. In SPHINX, the information stored on the device is theoretically independent of the user's master password. Moreover, an attacker with full control of the device, even at the time the user interacts with it, learns nothing about the master password - the password is not entered into the device in plaintext form or in any other way that may leak information on it. Unlike existing managers, SPHINX produces strictly high-entropy passwords and makes it compulsory for the users to register these passwords with the web services, which defeats online guessing attacks and offline dictionary attack upon service compromise. We present the design, implementation and performance evaluation of SPHINX, offering prototype browser plugins, smartphone apps and transparent device-client communication. We further provide a comparative analytical evaluation of SPHINX with other password managers based on a formal framework consisting of security, usability, and deployability metrics.

Password managers (aka stores or vaults) allow a user to store and retrieve (usually high-entropy) passwords for her multiple password-protected services by interacting with a "device" serving the role of the manager (e.g., a smartphone or an online third-party service) on the basis of a single memorable (low-entropy) master password. Existing password managers work well to defeat offline dictionary attacks upon web service compromise, assuming the use of high-entropy passwords is enforced. However, they are vulnerable to leakage of all passwords in the event the device is compromised, due to the need to store the passwords encrypted under the master password and/or the need to input the master password to the device (as in smartphone managers). Evidence exists that password managers can be attractive attack targets. In this paper, we introduce a novel approach to password management, called SPHINX, which remains secure even when the password manager itself has been compromised. In SPHINX, the information stored on the device is information theoretically independent of the user's master password - an attacker breaking into the device learns no information about the master password or the user's site-specific passwords. Moreover, an attacker with full control of the device, even at the time the user interacts with it, learns nothing about the master password - the password is not entered into the device in plaintext form or in any other way that may leak information on it. Unlike existing managers, SPHINX produces strictly high-entropy passwords and makes it compulsory for the users to register these randomized passwords with the web services, hence fully defeating offline dictionary attack upon service compromise. The design and security of SPHINX is based on the device-enhanced PAKE model of Jarecki et al. that provides the theoretical basis for this construction and is backed by rigorous cryptographic proofs of security. While SPHINX is suitable for different device and online platforms, in this paper, we report on its concrete instantiation on smartphones given their popularity and trustworthiness as password managers (or even two-factor authentication). We present the design, implementation and performance evaluation of SPHINX, offering prototype browser plugins, smartphone apps and transparent device-client communication. Based on our inspection analysis, the overall user experience of SPHINX improves upon current managers. We also report on a lab-based usability study of SPHINX, which indicates that users' perception of SPHINX security and usability is high and satisfactory when compared to regular password-based authentication. Finally, we discuss how SPHINX may be extended to an online service for the purpose of back-up or as an independent password manager.

We introduce a setting that we call Device-Enhanced PAKE (DE-PAKE), where PAKE (password-authenticated key exchange) protocols are strengthened against online and offline attacks through the use of an auxiliary device that aids the user in the authentication process. We build such schemes and show that their security, properly formalized, achieves maximal-attainable resistance to online and offline attacks in both PKI and PKI-free settings. In particular, an online attacker must guess the user's password and also corrupt the user's auxiliary device to authenticate, while an attacker who corrupts the server cannot learn the users' passwords via an offline dictionary attack. Notably, our solutions do not require secure channels, and nothing (in an information-theoretic sense) is learned about the password by the device (or a malicious software running on the device) or over the device-client channel, even without any external protection of this channel. An attacker taking over the device still requires a full online attack to impersonate the user. Importantly, our DE-PAKE scheme can be deployed at the user end without the need to modify the server and without the server having to be aware that the user is using a DE-PAKE scheme. In particular, the schemes can work with standard servers running the usual password-over-TLS authentication. We use these protocols to implement a practical DE-PAKE system and we evaluate its performance. To improve usability the implemented system utilizes automated and user-transparent data channel between the mobile device and the client, falling back to localized communication if the device looses primary connectivity.

PPSS is a central primitive introduced by Bagherzandi et al. [2] which allows a user to store a secret among n servers such that the user can later reconstruct the secret with the sole possession of a single password by contacting t + 1 (t <; n) servers. At the same time, an attacker breaking into t of these servers - and controlling all communication channels - learns nothing about the secret (or the password). Thus, PPSS schemes are ideal for on-line storing of valuable secrets when retrieval solely relies on a memorizable password. We show the most efficient Password-Protected Secret Sharing (PPSS) to date (and its implied Threshold-PAKE scheme), which is optimal in round communication as in Jarecki et al. [10] but which improves computation and communication complexity over that scheme requiring a single per-server exponentiation for the client and a single exponentiation for the server. As with the schemes from [10] and Camenisch et al. [4] we do not require secure channels or PKI other than in the initialization stage. We prove the security of our PPSS scheme in the Universally Composable (UC) model. For this we present a UC definition of PPSS that relaxes the UC formalism of [4] in a way that enables more efficient PPSS schemes (by dispensing with the need to extract the user's password in the simulation) and present a UC-based definition of Oblivious PRF (OPRF) that is more general than the (Verifiable) OPRF definition from [10] and is also crucial for enabling our performance optimization.

In the setting of searchable symmetric encryption (SSE), a data owner D outsources a database (or document/file collection) to a remote server E in encrypted form such that D can later search the collection at E while hiding information about the database and queries from E. Leakage to E is to be confined to well-defined forms of data-access and query patterns while preventing disclosure of explicit data and query plaintext values. Recently, Cash et al. presented a protocol, OXT, which can run arbitrary boolean queries in the SSE setting and which is remarkably efficient even for very large databases.

We revisit the problem of protecting user's private data against adversarial compromise of user's device(s) which store this data. We formalize the solution we propose as Password-Protected Secret-Sharing (PPSS), which allows a user to secret-share her data among n trustees in such a way that (1) the user can retrieve the shared secret upon entering a correct password into a reconstruction protocol, which succeeds as long as at least t+1 uncorrupted trustees are accessible, and (2) the shared data remains secret even if the adversary which corrupts t trustees, with the level of protection expected of password-authentication, i.e. the probability that the adversary learns anything useful about the secret is at most q/|D| where q is the number of reconstruction protocol the adversary manages to trigger and |D| is the size of the password dictionary. We propose an efficient PPSS protocol in the PKI model, secure under the DDH assumption, using non-interactive zero-knowledge proofs with efficient instantiations in the Random Oracle Model. Our protocol is practical, with fewer than 16 exponentiations per trustee and 8t+17 exponentiations per user, with O(1) bandwidth between the user and each trustee, and only three message flows, implying a single round of interaction in the on-line phase. As a side benefit our PPSS protocol yields a new Threshold Password Authenticated Key Exchange (T-PAKE) protocol in the PKI model with significantly lower message, communication, and server computation complexities then existing T-PAKE's.

We propose a new method to speed up discrete logarithm (DL)-based cryptosystems by considering a new variant of the DL problem, where the exponents are formed as e1+ e2for some fixed a and two integers e1, ae2with a low weight representation. We call this class of exponents split exponents, and we show that with certain choice of parameters the DL problem on split exponents is essentially as secure as the standard DL problem, while the exponentiation operation using exponents of this class is significantly faster than best exponentiation algorithms given for standard exponents. For example, the speed of scalar multiplication on the standard Koblitz curve K163 is estimated to be accelerated by up to 51.5 % and 23.5 % at the cost of memory for one precomputed point, compared to the TNAF and window TNAF methods, respectively. As for security, we show that the provable security of the DL problem using split exponents is only by a small constant, e.g., 1/4, worse than the security of the standard DL problem. Split exponents can be adopted to speed up various DL-based cryptosystems. We exemplify this on the recent CCA-secure public key encryption of Bellare, Kohno, and Shoup.

A robust group key agreement protocol (GKA) allows a set of players to establish a shared secret key, regardless of network/node failures. Current constant-round GKA protocols are either efficient and nonrobust or robust but not efficient; assuming a reliable broadcast communication medium, the standard encryption-based group key agreement protocol can be robust against arbitrary number of node faults, but the size of the messages broadcast by every player is proportional to the number of players. In contrast, nonrobust group key agreement can be achieved with each player broadcasting just constant-sized messages. We propose a novel 2-round group key agreement protocol, which tolerates up to T node failures, using O(T)-sized messages for any T. We show that the new protocol implies a fully-robust group key agreement with logarithmic-sized messages and expected round complexity close to 2, assuming random node faults. The protocol can be extended to withstand malicious insiders at small constant factor increases in bandwidth and computation. The proposed protocol is secure under the (standard) Decisional Square Diffie-Hellman assumption.

Access control is the fundamental security service in ad hoc groups. It is needed not only to prevent unauthorized entities from joining the group, but also to bootstrap other security services. Luo,proposed a set of protocols for providing ubiquitous and robust access control (called URSA) in mobile ad hoc networks without relying on a centralized authority. The URSA protocol relies on the new proactive RSA signature scheme, which allows members in an ad hoc group to make access control decisions in a distributed manner. The proposed proactive RSA signature scheme is assumed secure as long as no more than an allowed threshold of participating members is simultaneously corrupted at any point in the lifetime of the scheme. In this paper, we show an attack on this proposed proactive RSA scheme, in which an admissible threshold of malicious group members can completely recover the group RSA secret key in the course of the lifetime of this scheme. Our attack stems from the fact that the threshold signature protocol which is a part of this proactive RSA scheme leaks some seemingly innocuous information about the secret signature key. We show how the corrupted members can influence the execution of the scheme in such a way so that the slowly leaked information is used to reconstruct the entire shared secret.

Multisignatures allow n signers to produce a short joint signature on a single message. Multisignatures were achieved in the plain model with a non-interactive protocol in groups with bilinear maps, by Boneh et al, and by a three-round protocol under the Discrete Logarithm (DL) assumption, by Bellare and Neven, with multisignature verification cost of, respectively, O(n) pairings or exponentiations. In addition, multisignatures with O(1) verification were shown in so-called Key Verification (KV) model, where each public key is accompanied by a short proof of well-formedness, again either with a non-interactive protocol using bilinear maps, by Ristenpart and Yilek, or with a three-round protocol under the Diffie-Hellman assumption, by Bagherzandi and Jarecki.

A group key agreement protocol (GKA) allows a set of players to establish a shared secret key which can be used to secure a subsequent communication. Several efficient constant-round GKA's have been proposed. However, their performance degrades if some players fail during protocol execution. This is a problem in practice, e.g. for mobile nodes communicating over wireless media, which can loose connectivity during the protocol execution. Current constant-round GKA protocols are either efficient and non-robust or robust but not efficient: Assuming a reliable broadcast communication medium, the standard encryption-based group key agreement protocol can be robust against arbitrary number of node faults, but the size of the messages broadcast by every player is proportional to the number of players. In contrast, non-robust group key agreement can be achieved with each player broadcasting just constant-sized messages.

We propose several highly-practical and optimized constructions for joint signature and encryption primitives often referred to as signcryption. All our signcryption schemes, built directly from trapdoor permutations such as RSA, share features such as simplicity, efficiency, generality, near-optimal exact security, flexible and ad-hoc key management, key reuse for sending/receiving data, optimally-low message expansion, "backward" use for plain signature/encryption, long message and associated data support, the strongest-known qualitative security and, finally, complete compatibility with the PKCS#1 infrastructure.

Secret handshake protocols were recently introduced by Balfanz, et al. [1] to allow members of the same group to authenticate each other secretly, in the sense that someone who is not a group member cannot tell, by engaging in the handshake protocol, whether his counterparty is a member of the group. On the other hand, any two parties who are members of the same group will recognize each other as members. Thus, secret handshakes can be used in any scenario where group members need to identify each other without revealing their group affiliations to outsiders. The secret handshake protocol of [1] relies on a Bilinear Diffie-Hellman assumption on certain elliptic curves. We show how to build secret handshake protocols secure under more standard cryptographic assumptions, like the RSA or the Diffie Hellman (DH) assumption, using a novel tool of CA-oblivious public key encryption, i.e. an encryption scheme where neither the public key nor the ciphertext reveal any information about the Certification Authority which certified the public key.

Emerging applications like electronic commerce and secure communications over open networks have made clear the fundamental role of public key cryptography as a unique enabler for world-wide scale security solutions. On the other hand, these solutions clearly expose the fact that the protection of private keys is a security bottleneck in these sensitive applications. This problem is further worsened in the cases where a single and unchanged private key must be kept secret for very long time (such is the case of certification authority keys, bank and e-cash keys, etc.). One crucial defense against exposure of private keys is offered by threshold cryptography where the private key functions (like signatures or decryption) are distributed among several parties such that a predetermined number of parties must cooperate in order to correctly perform these operations. This protects keys from any single point of failure. An attacker needs to break into a multiplicity of locations before it c...