Universally Composable Two-Server PAKE

ISC 2016 • with Mark Manulis - Abstract

X Two-Server Password Authenticated Key Exchange (2PAKE) protocols apply secret shar-ing techniques to achieve protection against server-compromise attacks. 2PAKE protocols eliminate the need for password hashing and remain secure as long as one of the servers remains honest. This concept has also been explored in connection with two-server password authenticated secret sharing (2PASS) protocols for which game-based and universally composable versions have been proposed. In contrast, universally composable PAKE protocols exist currently only in the single-server scenario and all proposed 2PAKE protocols use game-based security definitions. In this paper we propose the first construction of an universally composable 2PAKE protocol, alongside with its ideal functionality. The protocol is proven UC-secure in the standard model, assuming a common reference string which is a common assumption to many UC-secure PAKE and PASS protocols. The proposed protocol remains secure for arbitrary password distributions. As one of the building blocks we define and construct a new cryptographic primitive, called Trapdoor Distributed Smooth Projective Hash Function (TD-SPHF), which could be of independent interest.
Blind Password Registration for Two-Server Password Authenticated Key Exchange and Secret Sharing Protocols

ISC 2016 • with Mark Manulis - Abstract

X Many organisations enforce policies on the length and formation of passwords to encourage selection of strong passwords and protect their multi-user systems. For Two-Server Password Authenticated Key Exchange (2PAKE) and Two-Server Password Authenticated Secret Sharing (2PASS) protocols, where the password chosen by the client is secretly shared between the two servers, the initial remote registration of policy-compliant passwords represents a major problem because none of the servers is supposed to know the password in clear. We solve this problem by introducing Two-Server Blind Password Registration (2BPR) protocols that can be executed between a client and the two servers as part of the remote registration procedure. 2BPR protocols guarantee that secret shares sent to the servers belong to a password that matches their combined password policy and that the plain password remains hidden from any attacker that is in control of at most one server. We propose a security model for 2BPR protocols capturing the requirements of policy compliance for client passwords and their blindness against the servers. Our model extends the adversarial setting of 2PAKE/2PASS protocols to the registration phase and hence closes the gap in the formal treatment of such protocols. We construct an efficient 2BPR protocol for ASCII-based password policies, prove its security in the standard model, give a proof of concept implementation, and discuss its performance.
Blind Password Registration for Verifier-based PAKE

AsiaPKC 2016 • with Mark Manulis - Abstract

X We propose Blind Password Registration (BPR), a new class of cryptographic protocols that is instrumental for secure registration of client passwords at remote servers with additional protection against unwitting password disclosures on the server side that may occur due to the lack of the state-of-the-art password protection mechanisms implemented by the server or due to common server-compromise attacks. The *dictionary attack resistance* property of BPR protocols guarantees that the only information available to the server during and after the execution of the protocol cannot be used to reveal the client password without performing an offline dictionary attack on a password verifier (e.g. salted hash value) that is stored by the server at the end of the protocol. In particular, at no point in time the server is supposed to work with plain passwords. We construct an efficient BPR protocol in the standard model for ASCII-based password policies using some techniques underlying the recently introduced Zero-Knowledge Password Policy Checks (ZKPPC). However, we do not rely on the full power of costly ZKPPC proofs and in fact show that BPR protocols can be modelled and realised simpler and significantly faster (as supported by our implementation) without using them as a building block. Our BPR protocol can directly be used to replace ZKPPC-based registration procedure for existing Verifier-based Password Authenticated Key Exchange protocols.
Secure Set-based Policy Checking and Its Application to Password Registration

CANS 2015 • with Changyu Dong - Abstract

X Policies are the corner stones of today's computer systems. They define secure states and safe operations. A common problem with policies is that their enforcement is often in conflict with user privacy. In order to check the satisfiability of a policy, a server usually needs to collect from a client some information which may be private. In this work we introduce the notion of secure set-based policy checking (SPC) that allows the server to verify policies while preserving the client's privacy. SPC is a generic protocol that can be applied in many policy-based systems. As an example, we show how to use SPC to build a password registration protocol so that a server can check whether a client's password is compliant with its password policy without seeing the password. We also analyse SPC and the password registration protocol and provide security proofs. To demonstrate the practicality of the proposed primitives, we report performance evaluation results based on a prototype implementation of the password registration protocol.
Oblivious PAKE: Efficient Handling of Password Trials

ISC 2015 • with Mark Manulis - Abstract

X In this work we introduce the notion of Oblivious Password based Authenticated Key Exchange (O-PAKE) and a general compiler to transform a large class of PAKE into O-PAKE protocols. O-PAKE allows a client that shares one password with a server to use a set of passwords within one PAKE session. It succeeds if and only if one of those input passwords matches the one stored on the server side. The term oblivious is used to emphasize that no information about any password, input by the client, is made available to the server. Using special processing techniques, our O-PAKE compiler reaches nearly constant runtime on the server side, independent of the size of the client's password set. We prove security of the O-PAKE compiler under standard assumptions using the latest game-based PAKE model by Abdalla, Fouque and Pointcheval (PKC 2005), tailored to our needs. We identify the requirements that PAKE protocols must satisfy in order to suit the compiler and give a concrete O-PAKE instantiation. The compiled protocol is implemented and its performance analysis attests to the practicality of the compiler. Furthermore, we implement a browser plugin demonstrating how to use O-PAKE in practice.
Zero-Knowledge Password Policy Checks and Verifier-Based PAKE

ESORICS 2014 • with Mark Manulis - Abstract

X Zero-Knowledge Password Policy Checks (ZKPPC), introduced in this work, enable blind registration of client passwords at remote servers, i.e., client passwords are never transmitted to the servers. This eliminates the need for trusting servers to securely process and store client passwords. A ZKPPC protocol, executed as part of the registration procedure, allows clients to further prove compliance of chosen passwords with respect to password policies defined by the servers. The main benefit of ZKPPC-based password registration is that it guarantees that registered passwords never appear in clear on the server side. At the end of the registration phase the server only receives and stores some verification information that can later be used for authentication in a suitable Verifier-based Password Authenticated Key Exchange (VPAKE) protocol. We give general and concrete constructions of ZKPPC protocols and suitable VPAKE protocols for ASCII-based passwords and policies that are commonly used on the web. To this end we introduce a reversible mapping of ASCII characters to integers that can be used to preserve the structure of the password string and a new randomized password hashing scheme for ASCII-based passwords.
Distributed Smooth Projective Hashing and its Application to Two-Server Password Authenticated Key Exchange

ACNS 2014 • with Mark Manulis - Abstract

X Smooth projective hash functions have been used as building block for various cryptographic applications, in particular for password-based authentication. In this work we propose the extended concept of distributed smooth projective hash functions where the computation of the hash value is distributed across $n$ parties and show how to instantiate the underlying approach for languages consisting of Cramer-Shoup ciphertexts. As an application of distributed smooth projective hashing we build a new framework for the design of two-server password authenticated key exchange protocols, which we believe can help to "explain" the design of earlier two-server password authenticated key exchange protocols.
Revocation and Non-repudiation: When the First Destroys the Latter

EuroPKI 2013 • with Johannes Braun and Andreas Hülsing - Abstract

X Electronic signatures replace handwritten signatures in electronic processes. In this context, non-repudiation is one of the most desired properties yet in practice it cannot be provided by the signature schemes themselves. Therefore, additional mechanisms in the underlying public key infrastructure are required. In this work, we present a formal treatment of that issue. We extend the formal model for public key infrastructures by Maurer introducing transitions to make it dynamic. We use the extended model to evaluate the relationship between non-repudiation and revocation and prove that backdated revocation always destroys the non-repudiation property. We prove that forward secure signatures can be used to maintain non-repudiation, rendering the costly use of timestamping -- as required by all existing solutions -- superfluous. We also show how to realize this in practice, introducing a new index reporting protocol. Moreover, we show how this protocol can be used to support detection of malicious key usage, thereby improving the overall security of electronic signing. Besides, the index reporting protocol allows for a convenient realization of pay per use models for certificate pricing.
Pseudorandom Signatures

AsiaCCS 2013 • with Nils Fleischhacker, Felix Günther, Mark Manulis, and Bertram Poettering - Abstract

X We develop a three-level hierarchy of privacy notions for (unforgeable) digital signature schemes. We first prove mutual independence of existing notions of anonymity and confidentiality, and then show that these are implied by higher privacy goals. The top notion in our hierarchy is pseudorandomness signatures with this property hide the entire information about the signing process and cannot be recognized as signatures when transmitted over a public network. This implies very strong unlinkability guarantees across different signers and even different signing algorithms, and gives rise to new forms of private public-key authentication. We show that one way towards pseudorandom signatures leads over our mid-level notion, called indistinguishability: such signatures can be simulated using only the public parameters of the scheme. As we reveal, indistinguishable signatures exist in different cryptographic settings (e.g. based on RSA, discrete logarithms, pairings) and can be efficiently lifted to pseudorandomness deploying general transformations using appropriate encoding techniques. We also examine a more direct way for obtaining pseudorandomness for any unforgeable signature scheme. All our transformations work in the standard model. We keep public verifiability of signatures in the setting of system-wide known public keys. Some results even hold if signing keys are disclosed to the adversary --- given that signed messages have high entropy.
Practical Security in E-Mail Applications

SAM 2012 • with Alexander Wiesmaier and Christian Fritz - Abstract

X This paper deals with practicability issues of encrypted e-mails. A quick survey on the status quo indicates that popular e-mail clients lack substantial practicability qualities, for example searching in encrypted e-mails. Other approaches such as De-Mail provide solutions, but offer transport encryption only. We present and discuss a number of improvements to the practicability of e-mail encryption. These enable efficient searching in encrypted e-mails as well as subject encryption and the use of cryptographic functions in calendar applications. We present a prototype, called CryptoBird, providing a proof of concept for the proposed core features.
An efficient mobile PACE implementation

AsiaCCS 2011 • with Alex Wiesmaier, Moritz Horsch, Johannes Braun, Detlef Hühnlein, Falko Strenzke, and Johannes Buchmann - Abstract

X Many future electronic identity cards will be equipped with a contact-less interface. Analysts expect that a significant proportion of future mobile phones support Near Field Communication (NFC) technology. Thus, it is a reasonable approach to use the cell phone as mobile smart card terminal, which in particular supports the Password Authenticated Connection Establishment (PACE) protocol to ensure user consent and to protect the wireless interface between the mobile phone and the smart card. While there are efficient PACE implementations for smart cards, there does not seem to be an efficient and platform independent solution for mobile terminals. Therefore we provide a new implementation using the Java Micro Edition (Java ME), which is supported by almost all modern mobile phones. However, the benchmarks of our first, straightforward PACE implementation on an NFC-enabled mobile phone have shown that improvement is needed. In order to reach a user friendly performance we implemented an optimized version, which, as of now, is restricted to optimizations which can be realized using features of existing Java ME libraries. In the work at hand we present a review of the relevant algorithms and provide benchmarks of the corresponding arithmetic functions in different Java ME libraries. We discuss the different optimization approaches, introduce our optimized PACE implementation, and provide timings for a desktop PC and a mobile phone in comparison to the straightforward version. Finally, we investigate potential side channel attacks on the optimized implementation.


PhD Thesis

Advancements in Password-based Cryptography 2016 • Supervised by Mark Manulis and Shujun Li; Examination panel: Steve Schneider and Feng Hao

Group Signatures: Privacy-Preserving Authentication Methods

BSI 2011 • with Nils Fleischhacker, Felix Günther, Mark Manulis, and Bertram Poettering - Abstract

X Group signatures are cryptographic privacy-preserving authentication mechanisms. Potential signers are formed into a group, which is managed by a usually centralized authority (group manager). Each group member being in possession of a (valid) membership certificate can sign documents on behalf of the whole group. In addition to various forms of unforgeability the distinguished privacy property of group signatures is that they do not leak any information about the actual signer, except for the validity of the signer's membership in the group. In case of dispute the group manager can, however, identify the signer and possibly prove this fact to a third-party. The concept of group signatures was introduced in 1991 by Chaum and Van Heyst and many more schemes appeared since then. The goal of the project is to reflect the state-of-the-art in this field by providing a comparative study of existing group signatures, thereby focusing on their security and privacy properties, cryptographic strength, performance, and practical relevance.
Towards a mobile eCard Client

Kryptotag 2010 • with Alex Wiesmaier, Moritz Horsch, Johannes Braun, Detlef Hühnlein, and Falko Strenzke