TU Darmstadt

ULB

TUprints

Practical Private Set Intersection Protocols for Privacy-Preserving Applications

Weinert, Christian (2021)
Practical Private Set Intersection Protocols for Privacy-Preserving Applications.
Technische Universität Darmstadt
doi: 10.26083/tuprints-00019295
Ph.D. Thesis, Primary publication, Publisher's Version

Preview

Text
Dissertation_ChristianWeinert_010921.pdf
Copyright Information: In Copyright.
Download (5MB) | Preview

Item Type:

Ph.D. Thesis

Type of entry:

Primary publication

Title:

Practical Private Set Intersection Protocols for Privacy-Preserving Applications

Language:

English

Referees:

Schneider, Prof. Dr. Thomas ; Pinkas, Prof. Dr. Benny

Date:

2021

Place of Publication:

Darmstadt

Collation:

XIII, 157 Seiten

Date of oral examination:

31 August 2021

DOI:

10.26083/tuprints-00019295

Abstract:

Private set intersection (PSI) protocols are cryptographic protocols that allow two parties to securely compute the intersection of their private input sets without disclosing elements outside of the intersection. While this simple functionality turns out to be instrumental for many real-world applications, existing protocol designs and implementations unfortunately incur an impractical computation and/or communication overhead. As a consequence, service providers currently deploy insecure alternatives that threaten users' privacy at a large scale.

Therefore, in this thesis, we design, implement, and evaluate practical PSI protocols to provide viable privacy-preserving alternatives for three specific application scenarios: mobile contact discovery, mutual authentication for Apple AirDrop, and database intersection analytics.

Mobile Contact Discovery. Mobile messengers commonly offer a feature that allows users to discover their existing contacts on the platform based on the phone numbers stored in their address book. Unfortunately, we find that popular messengers implement contact discovery either by uploading the users' entire address books in the clear or by using simple hashing-based protocols. As we show that such hashing-based protocols are vulnerable to brute-force attacks, the users' entire social graphs are exposed to anyone with access to the service providers' infrastructure. To instead perform the matching procedure between address books and user databases in a privacy-preserving manner, we develop and optimize two PSI protocols that are significantly more efficient than the state-of-the-art protocols of Kiss et al. (PoPETs'17) while also providing security against malicious clients.

By closely investigating the contact discovery implementation of three popular messengers (WhatsApp, Telegram, and Signal), we also find that due to insufficient rate limits, attackers can crawl the global user databases simply by enumerating phone numbers. For this problem, we propose multiple mitigation techniques, including a novel PSI-compatible rate-limiting scheme that strictly improves over the approach currently deployed by Signal.

This part of the thesis is based on the following two publications:

[KRS+19] D. KALES, C. RECHBERGER, T. SCHNEIDER, M. SENKER, C. WEINERT. "Mobile Private Contact Discovery at Scale". In: 28. USENIX Security Symposium (USENIX Security'19). Website: https://contact-discovery.github.io. Full version: https://ia.cr/2019/517. USENIX Association, 2019, pp. 1447–1464. CORE Rank A*. Appendix B.

[HWS+21] C. HAGEN, C. WEINERT, C. SENDNER, A. DMITRIENKO, T. SCHNEIDER. "All the Numbers are US: Large-scale Abuse of Contact Discovery in Mobile Messengers". In: 28. Network and Distributed System Security Symposium (NDSS'21). Website: https://contact-discovery.github.io. Full version: https://ia.cr/2020/1119. Internet Society, 2021. CORE Rank A*. Appendix A.

Mutual Authentication for Apple AirDrop. Based on the reverse-engineering efforts of Stute et al. (USENIX Security'19), we identify two privacy vulnerabilities in Apple's proprietary offline file sharing service AirDrop. They are rooted in the exchange of vulnerable hash values of contact identifiers during the authentication handshake that determines whether two device owners are mutual contacts. We demonstrate both attacks with a proof-of-concept implementation called "AirCollect" that can almost instantly recover the mobile phone numbers of nearby Apple users who open the sharing pane on their devices.

As a privacy-preserving alternative, we develop "PrivateDrop". Our solution is based on two consecutive executions of optimized PSI protocols that provide security against malicious parties and additionally enforce authentic inputs. We implement PrivateDrop in Apple's native programming language Swift and show in an empirical performance evaluation on real Apple devices that the overall authentication delay of below one second preserves the user experience of the original insecure AirDrop protocol.

This part of the thesis is based on the following two publications:

[HHS+21a] A. HEINRICH, M. HOLLICK, T. SCHNEIDER, M. STUTE, C. WEINERT. "DEMO: AirCollect: Efficiently Recovering Hashed Phone Numbers Leaked via Apple AirDrop". In: 14. ACM Conference on Security and Privacy in Wireless and Mobile Networks (WiSec'21). Website: https://privatedrop.github.io. Full version: https://ia.cr/2021/893. ACM, 2021, pp. 371–373. Appendix C.

[HHS+21b] A. HEINRICH, M. HOLLICK, T. SCHNEIDER, M. STUTE, C. WEINERT. "PrivateDrop: Practical Privacy-Preserving Authentication for Apple AirDrop". In: 30. USENIX Security Symposium (USENIX Security'21). Website: https://privatedrop.github.io. Full version: https://ia.cr/2021/481. USENIX Association, 2021, pp. 3577–3594. CORE Rank A*. Appendix D.

Database Intersection Analytics. Scenarios where two companies or governmental agencies want to conduct analyses on data subjects they have in common without revealing their entire database are usually addressed with generic circuit-based PSI protocols that can compute arbitrary functions of the database intersection. The best prior circuit-based PSI protocols of Pinkas et al. (USENIX Security'15 and ACM TOPS'18) have a complexity of O(n log n/ log log n), where n is the number of database entries. In our work, we create the first circuit-based PSI protocol with almost linear ω(n) complexity that also significantly outperforms prior works in terms of concrete performance. Our construction is based on a novel hashing scheme called "2D Cuckoo hashing", which we analyze experimentally by spending millions of core hours on a high-performance computer.

This part of the thesis is based on the following publication:

[PSWW18] B. PINKAS, T. SCHNEIDER, C. WEINERT, U. WIEDER. "Efficient Circuit-Based PSI via Cuckoo Hashing". In: 37. Advances in Cryptology – EUROCRYPT'18. Vol. 10822. LNCS. Code: https://encrypto.de/code/2DCH. Full version: https://ia.cr/2018/120. Springer, 2018, pp. 125–157. CORE Rank A*. Appendix E.

Overall, this thesis contributes to make private set intersection protocols sufficiently practical to provide privacy-preserving solutions for three widely-used real-world applications.

Alternative Abstract:

Alternative Abstract

Language

Protokolle zur privaten Schnittmengenberechnung (im Englischen private set intersection, PSI) sind kryptographische Protokolle, die es zwei Parteien erlauben, die Schnittmenge ihrer geheimen Eingabemengen zu berechnen, ohne dass Elemente außerhalb der Schnittmenge bekannt werden. Obwohl diese einfache Funktionalität instrumental für eine Vielzahl von praktischen Anwendungen ist, erzeugen existierende Protokolle leider einen unpraktikablen Berechnungs- und Kommunikationsmehraufwand. Aus diesem Grund nutzen Dienstanbieter derzeit unsichere Alternativen, welche die Privatsphäre von Nutzern massiv gefährden.

Daher entwerfen, implementieren und evaluieren wir in dieser Thesis effiziente PSI Protokolle, um praktikable Privatsphäre-schützende Alternativen für drei spezifische Anwendungsszenarien anbieten zu können: mobile Kontaktermittlung, Authentifizierung für Apple AirDrop und Analyse von Datenbankschnittmengen.

Mobile Kontaktermittlung. Mobile Messenger bieten Nutzern in der Regel die Möglichkeit, existierende Kontakte auf der Plattform basierend auf den Telefonnummern in ihren Adressbüchern zu finden. Leider implementieren populäre Dienste diese Kontaktermittlung entweder durch das Hochladen der gesamten Adressbücher oder durch simple Hashing-basierte Protokolle. Da wir zeigen, dass solche Hashing-basierten Protokolle anfällig für Brute-Force-Angriffe sind, sind die gesamten sozialen Graphen der Nutzer für jeden einsehbar, der Zugriff auf die Infrastruktur der Dienstanbieter erlangt. Um den Abgleich zwischen Adressbüchern und Nutzerdatenbanken auf Privatsphäre-schützende Art und Weise durchzuführen, entwickeln und optimieren wir zwei PSI Protokolle, die signifikant effizienter sind als die derzeit besten Protokolle von Kiss et al. (PoPETS'17) und außerdem noch Sicherheit gegenüber böswilligen Nutzern bieten.

Durch eine nähere Untersuchung der Implementierung von Kontaktermittlungsverfahren von drei populären mobilen Messengern (WhatsApp, Telegram und Signal) finden wir außerdem heraus, dass durch unzureichende Beschränkung der Anfragen Angreifer die globalen Nutzerdatenbanken durchsuchen können, einfach indem aufeinanderfolgende Telefonnummern abgefragt werden. Für dieses Problem schlagen wir mehrere Schutzmaßnahmen vor, einschließlich eines neuen PSI-kompatiblen Verfahrens zur Beschränkung der Anfragen, das eine strikte Verbesserung gegenüber der von Signal derzeit eingesetzten Methode darstellt.

Dieser Abschnitt der Dissertation basiert auf folgenden zwei Publikationen:

Authentifizierung für Apple AirDrop. Basierend auf den Reverse-Engineering-Bemühungen von Stute et al. (USENIX Security'19) identifizieren wir zwei Privatsphäre-gefährdende Schwachstellen in Apple's proprietärem Dienst AirDrop, der das lokale Teilen von Dateien ermöglicht. Diese Schwachstellen beruhen auf dem Austausch von unsicheren Hashwerten von Kontaktdaten während des Authentifizierungsschritts, der ermittelt, ob zwei Gerätebesitzer gegenseitige Kontakte sind. Wir demonstrieren beide Angriffe mit einer Machbarkeitsstudie namens "AirCollect", die fast unmittelbar die Mobilfunknummern von in der Nähe befindlichen Apple-Nutzern offenbart, die das "Teilen"-Menü auf ihren Geräten öffnen.

Als Privatsphäre-schützende Alternative entwickeln wir "PrivateDrop". Unsere Lösung basiert auf zwei aufeinanderfolgenden Ausführungen von optimierten PSI Protokollen, die Sicherheit gegenüber böswilligen Parteien gewährleisten und zusätzlich die Authentizität von Eingabewerten garantieren. Wir implementieren PrivateDrop in Apple's nativer Programmiersprache Swift und zeigen in einer empirischen Evaluation auf echten Apple Geräten, dass die Gesamtdauer des Authentifizierungsschritts von unter einer Sekunde die Benutzererfahrung des originalen, unsicheren AirDrop Protokolls aufrecht erhalten kann.

Dieser Abschnitt der Dissertation basiert auf folgenden zwei Publikationen:

Analyse von Datenbankschnittmengen. Szenarien in denen zwei Firmen oder Regierungsbehörden Analysen auf gemeinsamen Datensubjekten durchführen wollen, ohne ihre gesamten Datenbanken preiszugeben, werden üblicherweise mit generischen, Schaltkreisbasierten PSI Protokollen adressiert, die beliebige Funktionen der Datenbankschnittmenge berechnen können. Die besten vorherigen Schaltkreis-basierten PSI Protokolle von Pinkas et al. (USENIX Security'15 und ACM TOPS'18) haben eine Komplexität von O(n log n/ log log n), wobei n die Anzahl der Datenbankeinträge ist. In unserer Arbeit entwickeln wir das erste Schaltkreis-basierte PSI Protokoll mit fast linearer ω(n) Komplexität, welches vorherige Arbeiten auch bezüglich konkreten Leistungswerten übertrifft. Unsere Konstruktion basiert auf einem neuen Hashverfahren namens "2D Cuckoo Hashing", das wir experimentell analysieren, indem wir mehrere Millionen Stunden Rechenzeit auf einem Hochleistungsrechner in Anspruch nehmen.

Dieser Abschnitt der Dissertation basiert auf folgender Publikation:

[PSWW18] B. PINKAS, T. SCHNEIDER, C. WEINERT, U. WIEDER. "Efficient Circuit-Based PSI via Cuckoo Hashing". In: 37. Advances in Cryptology – EUROCRYPT'18. Bd. 10822. LNCS. Code: https://encrypto.de/code/2DCH. Full version: https://ia.cr/2018/120. Springer, 2018, S. 125–157. CORE Rank A*. Appendix E.

Insgesamt tragen wir mit dieser Thesis dazu bei, Protokolle zur privaten Schnittmengenberechnung effizient genug zu gestalten, sodass wir Privatsphäre-schützende Lösungen für drei weitverbreitete praktische Anwendungen realisieren können.

German

Status:

Publisher's Version

URN:

urn:nbn:de:tuda-tuprints-192952

Classification DDC:

000 Generalities, computers, information > 004 Computer science

Divisions:

20 Department of Computer Science > Cryptography and Privacy Engineering (ENCRYPTO)

Date Deposited:

02 Sep 2021 12:18

Last Modified: