TU Darmstadt / ULB / TUprints

Personal and Password-Based Cryptography

Samelin, Kai (2018)
Personal and Password-Based Cryptography.
Technische Universität Darmstadt
Ph.D. Thesis, Primary publication

1.pdf - Published Version
Copyright Information: CC BY-NC-ND 4.0 International - Creative Commons, Attribution NonCommercial, NoDerivs.

Download (2MB) | Preview
Item Type: Ph.D. Thesis
Type of entry: Primary publication
Title: Personal and Password-Based Cryptography
Language: English
Referees: Waidner, Prof. Dr. Michael ; Boyd, Prof. Dr. Colin ; Camenisch, Dr. Jan
Date: 2018
Place of Publication: Darmstadt
Date of oral examination: 23 February 2018

This thesis addresses the question what cryptography can do for one personally, i.e., it looks at security and privacy challenges of individuals in today's world. In particular, this thesis solves a number of real-world problems, including secure handling of passwords used for authentication and how to extend digital signature schemes to allow for additional features. The presented protocols are provably secure under realistic assumptions, while providing state-of-the-art security and privacy guarantees. All proposed protocols are highly efficient, useful, yet deployable on a large scale, i.e., they are truly practical, thus bridging the gap between theory and practice. This is demonstrated by providing performance evaluations and estimates of selected protocols.

In more detail, this thesis is split up into two main parts. The first part of this thesis deals with protocols which allow a user to authenticate securely with a, potentially low-entropy, password which must be considered a valuable asset not to be made public. The second part applies several of the ideas given in the first part of this thesis to digital signatures. In particular, the ideas introduced add new possibilities and privacy features to this already very versatile primitive.

The first part of this thesis on protocols is split up into three sub-parts. The first sub-part addresses single sign-on (SSO) protocols. In existing work, ticket-granting server(s) can, e.g., impersonate users towards service providers or offline attack their passwords. To tackle this situation, two distributed password-based single sign-on (SSO) functionalities and their realizing protocols are presented, where the password check and token generation is distributed among multiple entities. Both functionalities are formulated in the universal-composition (UC) framework. This guarantees security in arbitrary contexts, while also absorbing unavoidable practical limitations such as typos, correlated password attempts by users and the case of guessed passwords into the definition. The first protocol offers the basic functionality one expects from such a distributed password-based SSO protocol, while the second protocol provides even more privacy guarantees. For example, the service providers no longer learn which other access rights an entity has, how long a token is valid and allows to establish different identities, i.e., pseudonyms, with each service provider.

The second sub-part introduces password-authenticated signatures, realizing virtual smart-cards, as real smart-cards have a number of serious drawbacks. For example, special smart-card readers are needed for usage and are not always available, while assuming that users always carry such readers with them is unrealistic. Virtual smart-cards circumvent these limitations by letting a user enter a password on a personal device, such as a smart-phone, to generate signatures on arbitrary messages with the help of an additional server. This approach prevents an adversary from using the signing key, if a user loses a device without also entering the correct password. The server only contributes to signature generation, if the password entered was correct. Neither the server nor the device alone can mount attacks on the password or on the password attempts, while the server does not learn the messages signed. As for SSO, security is defined by providing an ideal functionality in the UC-framework, implying the same advantages. The realizing protocol is secure against adaptive adversaries, i.e., an adversary can adaptively corrupt any protocol participants. To account for the main use-case of lost devices, a new corruption model is introduced. Namely, the simulator does not receive all prior input and output upon corruption, which is necessary to model the case of lost devices such that the adversary does not receive the prior password attempts. This is accompanied by a new non-committing encryption scheme for the receiver which requires secure erasures. The implementation of the given protocol shows that it even outperforms state-of-the-art smart-cards.

In the third sub-part, a fully simulatable non-committing encryption scheme is introduced. In particular, the encryption scheme introduced for the virtual smart-cards requires secure erasures. However, this is not always a reasonable assumption. To tackle this situation, this part presents an extended definition and protocol which allows simulating non-interactive ciphertexts even without secure erasures in a fully adaptive way. Hence, the simulator can give away the randomness for secret key generation and the randomness used for ciphertext generation to an adaptive adversary simultaneously. Such a non-interactive definition is in particular useful, if ciphertexts are further processed. This is demonstrated by providing the first definition of UC-secure signcryption in a setting with adaptive corruptions without secure erasures, which was not possible before. However, this part also comes with an impossibility result: it is proven that neither such an encryption scheme nor signcryption can be realized in non-idealized models.

The second part of this thesis deals with digital signature schemes with additional features. Here, two main contributions are presented. The first contribution of this part is about sanitizable signature schemes. In already existing definitions of sanitizable signature schemes, a semi-trusted third party, named the sanitizer, can alter signer-chosen blocks of signed messages, but a third party can derive which parts are actually admissible. The newly introduced notion of invisible sanitizable signature schemes improves on this situation by also hiding which parts of a given message are sanitizable, adding an additional layer of privacy. To build this new primitive, the new notion of chameleon-hashes with ephemeral trapdoors is introduced. These chameleon-hashes allow one to find arbitrary collisions of a hash, if two trapdoors at the same time are known. One trapdoor is a long-term secret, while the second one is generated at hash generation.

Finally, this thesis address the case of signing-right revocation. Nowadays, a certificate needs to be checked whether it is revoked at every signature verification. As verification naturally occurs more often, this negatively impacts on practicality, as thus network connectivity at verification is required. The protocols presented solve this by letting the signature itself vouch for the fact that the certificate was not revoked at signature generation time. This is achieved by letting a revocation authority contribute to signature generation. To account for privacy concerns, the authority does not learn the messages signed, while an extension also prohibits that the authority can link a signing protocol to the final signature.

Summarized, this thesis presents provably secure protocols which are geared to be highly efficient and are of direct practical relevance for personal usage, meaning that the primitives can directly be deployed and used, even in today's infrastructure.

Alternative Abstract:
Alternative AbstractLanguage

Diese Dissertation geht der Frage nach, wie Kryptographie alltägliche Probleme lösen kann. Genauer werden eine Reihe von Herausforderungen gelöst, die in der heutigen vernetzten Welt für dessen Benutzer von Bedeutung sind. Insbesondere wird in dieser Arbeit die sichere Handhabung von Benutzerpasswörtern und das Erweitern von digitalen Signaturen um zusätzliche Funktionen und Möglichkeiten diskutiert. Alle vorgestellten Protokolle sind unter Standardannahmen beweisbar sicher, geben Benutzern weitgehende Privatheit- und Sicherheitsgarantien, während sie gleichzeitig sehr effizient und direkt benutzbar sind. Dies wird dadurch demonstriert, dass einige ausgewählte Protokolle implementiert bzw. Laufzeitabschätzungen präsentiert werden.

Genauer ist diese Dissertation in zwei Hauptteile gegliedert. Der erste Teil dieser Arbeit zeigt wie sich ein Benutzer sicher mit einem Passwort authentifizieren kann, ohne dass dieses Benutzergeheimnis unnötigen Risiken ausgesetzt wird. Der zweite Teil erweitert digitale Signaturen um einige der Ideen, die im ersten Teil vorgestellt wurden.

Der erste Teil ist in drei Unterteile aufgespalten. Der erste Unterteil adressiert ``Single Sign-On''-Protokolle (SSO), da existierende Protokolle einige gravierende Nachteile besitzen. Beispielsweise kann ein korrupter Server in Kerberos sich gegenüber Services als ein beliebiger Benutzer ausgeben und Benutzerpasswörter mit Wörterbuchattacken angreifen. Um diese Situation zu verbessern, werden zwei verteile SSO-Protokolle vorgestellt, in denen die Tokenerzeugung und die Passwortüberprüfung auf mehrere Server verteilt werden. Die dazugehörigen Funktionalitäten werden im UC-Framework definiert, welche zahlreiche handfeste Vorteile bietet. Beispielsweise wird die Sicherheit der realisierenden Protokolle in arbiträren Kontexten garantiert, während gleichzeitig einige praktische Limitierungen wie, zum Beispiel, Typos, korrelierende Passwortversuche und zufällig von einem Angreifer geratene Passwörtern direkt in der Definition verankert sind. Das erste realisierende Protokoll implementiert die Basisfunktionalität, während das zweite Protokoll erweitere Privatheitseigenschaften offeriert. Insbesondere lernen die Services im zweiten Protokoll nicht, welche anderen Zugriffberechtigungen ein Token hat, wie lange ein Token valide ist und Benutzer können ihre Identität hinter Pseudonymen verstecken.

Der zweite Unterteil stellt passwort-authentifizierte Signaturen vor, die virtuelle Smart-Cards realisieren, da reale Smart-Cards einige gravierende Nachteile besitzen. Beispielsweise sind immer spezielle Lesegeräte vonnöten, welche nicht immer zur Verfügung stehen, während es unrealistisch erscheint einem Benutzer zuzumuten diese immer bei sich führen. Virtuelle Smart-Cards umgehen diese Probleme indem ein persönliches Gerät, wie zum Beispiel ein Smart-Phone oder Tablet, benutzt werden kann um, nach einer zusätzlichen Passworteingabe, Signaturen auf beliebigen Nachrichten zu erzeugen. Diese Signaturen werden mit Hilfe einer zusätzlichen Servers generiert, um zu verhindern, dass im Falle einer Korruption des persönlichen Gerätes der private Signaturschlüssel dem Angreifer in die Hände fällt. Dieser Server hilft allerdings nur bei der Signaturerstellung, wenn das eingegebene Passwort korrekt war. Das vewendete Passwort (und die Passwortversuche) sind nur angreifbar, wenn beide Entitäten korrumpiert wurden, während der Server die zu signierenden Nachrichten nicht lernt. Die dazugehörige Funktionalität ist, wie schon bereits für SSO, im UC-Framework definiert, also die gleichen Vorteile offeriert. Darüber hinaus ist das realisierende Protokoll sicher gegen adaptive Angreifer in einem neuen Korruptionsmodell. In diesem lernt der Simulator nicht alle vorherigen Ein- und Ausgaben der korrumpierten Partei. Dies modelliert, dass ein verlorenes Gerät dem Angreifer nicht alle verwendeten Passwörter aushändigt. Um das Protokoll beweisbar sicher zu machen, wird in diesem Unterteil ein neues Verschlüsselungsschema vorgestellt, welche es erlaubt Chiffrate für den Empfänger zu simulieren, allerdings sicheres Löschen voraussetzt. Die Implementierung zeigt, dass das Protokoll sogar schneller als moderne reale Smart-Cards ist.

Der dritte Unterteil stellt ein vollständig simulierbares Veschlüsselungsschema vor. Das im vorherigen Unterteil eingeführte Verschlüsselungsschema benötigt sicheres Löschen, was allerdings nicht immer zuverl\"ssig realisiert werden kann. Um dieses Problem zu lösen, stellt dieser Unterteil eine erweiterte, und nicht-interaktive, Verschlüsselungsdefinition vor, welche es einem Angreifer erlaubt adaptiv Chiffrate erstellen zu lassen und, gleichzeitig, den verwendeten Zufall für die Schlüsselerzeugung und Chiffraterzeugung zu bekommen. Eine nicht-interaktive Definition ist insbesondere dann vonnöten, wenn Chriffrate weiterverwendet werden. Das wird dadurch demonstriert, indem die erste UC-Definition von adaptiv-sicherer Signcryption vorgestellt wird. Darüber hinaus wird auch gezeigt, dass weder solch ein Veschlüsselungsschema noch Signcryption in nicht-idealisierten Modellen realisierbar ist.

Der zweite Hauptteil dieser Arbeit behandelt digitale Signaturen und wie diese um zusätzliche Möglichkeiten erweitert werden können. Der erste Teil diskutiert schwärzbare Signaturen. In existierenden Definitionen von schwärzbaren Signaturen kann eine, teilweise vertrauenswürdige, dritte Partei (der ``Sanitizer'') Teile von signierten Nachrichten abändern. Allerdings ist für jeden ersichtlich welche Teile einer signierten Nachricht änderbar sind. Die neue Definition von unsichtbar schwärzbaren Signaturen fügt die Privatheitseigenschaft hinzu, dass nicht ersichtlich ist, welche Teile schwärzbar sind. Um diese Signaturen zu realisieren, werden Chameleon-Hashfunktionen mit flüchtigen Falltüren eingeführt. Diese Art von Hashfunktion erlaubt es beliebe Kollisionen zu finden, wenn zwei Geheimnisse zur gleichen Zeit bekannt sind. Eines dieser Geheimnisse ist ein geheimer Langzeitschlüssel, während der Zweite erst bei der Hashgenerierung erzeugt wird.

Der letzte Teil dieser Arbeit diskutiert das Problem wie Signaturerzeugungsrechte effizient entzogen werden können. Heutzutage muss bei jeder Signaturverifikation der Status des dazugehörigen öffentlichen Schlüssels überprüft werden. Dies benötigt im Regelfall Netzwerkzugriff und wirkt sich negativ auf die Effizienz aus. Die in diesem Unterteil vorgestellten Protokolle umgehen dies, indem sie die Zertifizierungsstelle schon bei Signaturerstellung beweisen lässt, dass der Schlüssel gültig ist. Um den gestiegenen Privatheitsanforderungen gerecht zu werden, lernt diese Entität nicht, welche Nachrichten signiert werden, während eine Erweiterung es sogar verhindert, dass Signaturen mit einem vorherigen Signaturerstellungsprotokoll verknüpft werden können.

Zusammengefasst stellt diese Dissertation beweisbar sichere, und effiziente, Protokolle vor, welche Alltagsprobleme lösen.

URN: urn:nbn:de:tuda-tuprints-73612
Classification DDC: 000 Generalities, computers, information > 004 Computer science
Divisions: 20 Department of Computer Science
Date Deposited: 08 Jun 2018 13:38
Last Modified: 09 Jul 2020 02:04
URI: https://tuprints.ulb.tu-darmstadt.de/id/eprint/7361
PPN: 432475303
Actions (login required)
View Item View Item