research-article

Public Access

SEEMless: Secure End-to-End Encrypted Messaging with less</> Trust

Authors:

Apoorvaa Deshpande,

Harjasleen MalvaiAuthors Info & Claims

CCS '19: Proceedings of the 2019 ACM SIGSAC Conference on Computer and Communications Security

Pages 1639 - 1656

https://doi.org/10.1145/3319535.3363202

Published: 06 November 2019 Publication History

Abstract

End-to-end encrypted messaging (E2E) is only secure if participants have a way to retrieve the correct public key for the desired recipient. However, to make these systems usable, users must be able to replace their keys (e.g. when they lose or reset their devices, or reinstall their app), and we cannot assume any cryptographic means of authenticating the new keys. In the current E2E systems, the service provider manages the directory of public keys of its registered users; this allows a compromised or coerced service provider to introduce their own keys and execute a man in the middle attack. Building on the approach of CONIKS (Melara et al, USENIX Security '15), we formalize the notion of a Privacy-Preserving Verifiable Key Directory (VKD): a system which allows users to monitor the keys that the service is distributing on their behalf. We then propose a new VKD scheme which we call SEEMless, which improves on prior work in terms of privacy and scalability. In particular, our new approach allows key changes to take effect almost immediately; we show experimentally that our scheme easily supports delays less than a minute, in contrast to previous work which proposes a delay of one hour.

Supplementary Material

WEBM File (p1639-malvai.webm)

Download
141.80 MB

References

[1]

Muneeb Ali, Jude Nelson, Ryan Shea, and Michael J. Freedman. 2016. Blockstack: A Global Naming and Storage System Secured by Blockchains. In 2016 USENIX Annual Technical Conference (USENIX ATC 16). USENIX Association, Denver, CO, 181--194. https://www.usenix.org/conference/atc16/technical-sessions/presentation/ali

[2]

Joseph Bonneau. 2016. EthIKS: Using Ethereum to audit a CONIKS key transparency log. In International Conference on Financial Cryptography and Data Security. Springer, 95--105.

[3]

Philippe Camacho, Alejandro Hevia, Marcos Kiwi, and Roberto Opazo. 2008. Strong accumulators from collision-resistant hashing. In International Conference on Information Security. Springer, 471--486.

Digital Library

[4]

Melissa Chase, Alexander Healy, Anna Lysyanskaya, Tal Malkin, and Leonid Reyzin. 2005. Mercurial commitments with applications to zero-knowledge sets. In Annual International Conference on the Theory and Applications of Cryptographic Techniques. Springer, 422--439.

Digital Library

[5]

Melissa Chase and Anna Lysyanskaya. 2007. Simulatable VRFs with applications to multi-theorem NIZK. In Annual International Cryptology Conference. Springer, 303--322.

[6]

Ruben Cuevas, Michal Kryczka, Angel Cuevas, Sebastian Kaune, Carmen Guerrero, and Reza Rejaie. 2010. Is content publishing in BitTorrent altruistic or profit-driven?. In Proceedings of the 6th International COnference. ACM, 11.

Digital Library

[7]

developer.twitter.com. 2010. Counting Characters. https://developer.twitter.com/en/docs/basics/counting-characters.html. (2010). Accessed: 2018--12--25.

[8]

Saba Eskandarian, Eran Messeri, Joe Bonneau, and Dan Boneh. 2017. Certificate Transparency with Privacy. arXiv preprint arXiv:1703.02209 (2017).

[9]

Mohammad Etemad and Alptekin Kupcu. 2015. Efficient Key Authentication Service for Secure End-to-end Communications. Cryptology ePrint Archive, Report 2015/833. (2015). https://eprint.iacr.org/2015/833.

[10]

Reza R Farashahi, Pierre-Alain Fouque, Igor Shparlinski, Mehdi Tibouchi, and J Voloch. 2013. Indifferentiable deterministic hashing to elliptic and hyperelliptic curves. Math. Comp., Vol. 82, 281 (2013), 491--512.

[11]

Thomas Icart. 2009. How to hash into elliptic curves. Advances in Cryptology-CRYPTO 2009. Springer, 303--316.

[12]

Keybase.io. 2014. Keybase is now writing to the Bitcoin blockchain. https://keybase.io/docs/server_security/merkle_root_in_bitcoin_blockchain. (2014). Accessed: 2018--10-05.

[13]

Keybase.io. 2019 a. Keybase is not softer than TOFU. https://keybase.io/blog/chat-apps-softer-than-tofu. (2019). Accessed: 2019-05-05.

[14]

Keybase.io. 2019 b. Managing Teams and Keys with Keybase. https://keybase.io/docs-assets/blog/NCC_Group_Keybase_KB2018_Public_Report_2019-02--27_v1.3.pdf. (2019). Accessed: 2019-05-05.

[15]

Keybase.io. 2019 c. Protocol Security Review. https://rwc.iacr.org/2019/slides/keybase-rwc2019.pdf. (2019). Accessed: 2019-05-05.

[16]

Donald Ervin Knuth. 1998. The art of computer programming: sorting and searching. Vol. 3. Pearson Education.

[17]

Ben Laurie, Adam Langley, and Emilia Kasper. 2013. Certificate transparency. Technical Report.

[18]

Moses Liskov. 2005. Updatable zero-knowledge databases. In International Conference on the Theory and Application of Cryptology and Information Security. Springer, 174--198.

Digital Library

[19]

Marcela S Melara, Aaron Blankstein, Joseph Bonneau, Edward W Felten, and Michael J Freedman. 2015. CONIKS: Bringing Key Transparency to End Users. Usenix Security. 383--398.

[20]

Silvio Micali, Michael Rabin, and Joe Kilian. 2003. Zero-knowledge sets. In Foundations of Computer Science, 2003. Proceedings. 44th Annual IEEE Symposium. IEEE, 80--91.

[21]

Namecoin. 2014. https://namecoin.org. (2014). Accessed: 2018--10-05.

[22]

Alina Oprea and Kevin D Bowers. 2009. Authentic time-stamps for archival storage. In European Symposium on Research in Computer Security. Springer, 136--151.

[23]

LEAP Encryption Access Project. 2012. Nicknym. https://leap.se/en/docs/design/nicknym. (2012). Accessed: 2018--10-05.

[24]

signal.org. 2016. Identity binding. https://www.signal.org/docs/specifications/x3dh. (2016). Accessed: 2019-05-05.

[25]

Alin Tomescu and Srinivas Devadas. 2017. Catena: Efficient non-equivocation via Bitcoin. In IEEE Symp. on Security and Privacy.

[26]

Kenton Varda. 2008. Protocol buffers: Google's data interchange format. Google Open Source Blog, Available at least as early as Jul, Vol. 72 (2008).

Cited By

Johnson MSinganamalla SDurand NJang ESevilla SHeimerl KSekar VYu MSeneviratne AVeitch D(2024)dAuth: A Resilient Authentication Architecture for Federated Private Cellular NetworksProceedings of the ACM SIGCOMM 2024 Conference10.1145/3651890.3672263(373-391)Online publication date: 4-Aug-2024
https://dl.acm.org/doi/10.1145/3651890.3672263
Alatawi MSaxena NVilela JSchulmann HLi N(2024)Automating Key Fingerprint Comparisons in Secure Mobile Messaging Apps: A Case Study of SignalProceedings of the Fourteenth ACM Conference on Data and Application Security and Privacy10.1145/3626232.3653251(277-288)Online publication date: 19-Jun-2024
https://dl.acm.org/doi/10.1145/3626232.3653251
Jiang CXu CHan YZhang ZChen K(2024)Two-Factor Authenticated Key Exchange From Biometrics With Low Entropy RatesIEEE Transactions on Information Forensics and Security10.1109/TIFS.2024.337281219(3844-3856)Online publication date: 2024
https://doi.org/10.1109/TIFS.2024.3372812
Show More Cited By

Index Terms

SEEMless: Secure End-to-End Encrypted Messaging with less</> Trust
1. Security and privacy

Recommendations

Public-key encryption with non-interactive opening: new constructions and stronger definitions
AFRICACRYPT'10: Proceedings of the Third international conference on Cryptology in Africa

Public-key encryption schemes with non-interactive opening (PKENO) allow a receiver to non-interactively convince third parties that a ciphertext decrypts to a given plaintext or, alternatively, that such a ciphertext is invalid. Two practical generic ...
Constructions of certificate-based signature secure against key replacement attacks
The 2007 European PKI Workshop: Theory and Practice (EuroPKI'07)

In Eurocrypt 2003, Gentry introduced the notion of certificate-based encryption. The merit of certificate-based encryption lies in the following features: (1) providing more efficient public-key infrastructure (PKI) that requires less infrastructure, (2)...
Certificate-based signature: security model and efficient construction
EuroPKI'07: Proceedings of the 4th European conference on Public Key Infrastructure: theory and practice

In Eurocrypt 2003, Gentry introduced the notion of certificate-based encryption. The merit of certificate-based encryption lies in the following features: (1) providing more efficient public-key infrastructure (PKI) that requires less infrastructure, (2)...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

CCS '19: Proceedings of the 2019 ACM SIGSAC Conference on Computer and Communications Security

November 2019

2755 pages

ISBN:9781450367479

DOI:10.1145/3319535

General Chairs:
Lorenzo Cavallaro
King's College London, UK
,
Johannes Kinder
Bundeswehr University Munich, Germany
,
Program Chairs:
XiaoFeng Wang
Indiana University, USA
,
Jonathan Katz
George Mason University, USA

Copyright © 2019 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than the author(s) must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected].

Sponsors

SIGSAC: ACM Special Interest Group on Security, Audit, and Control

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 06 November 2019

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Funding Sources

National Science Foundation

Conference

CCS '19

Sponsor:

SIGSAC

CCS '19: 2019 ACM SIGSAC Conference on Computer and Communications Security

November 11 - 15, 2019

London, United Kingdom

Acceptance Rates

CCS '19 Paper Acceptance Rate 149 of 934 submissions, 16%;

Overall Acceptance Rate 1,261 of 6,999 submissions, 18%

Upcoming Conference

CCS '25

Sponsor:
sigsac

ACM SIGSAC Conference on Computer and Communications Security

October 13 - 17, 2025

Taipei , Taiwan

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

19
Total Citations
View Citations
1,886
Total Downloads

Downloads (Last 12 months)602
Downloads (Last 6 weeks)77

Reflects downloads up to 18 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Johnson MSinganamalla SDurand NJang ESevilla SHeimerl KSekar VYu MSeneviratne AVeitch D(2024)dAuth: A Resilient Authentication Architecture for Federated Private Cellular NetworksProceedings of the ACM SIGCOMM 2024 Conference10.1145/3651890.3672263(373-391)Online publication date: 4-Aug-2024
https://dl.acm.org/doi/10.1145/3651890.3672263
Alatawi MSaxena NVilela JSchulmann HLi N(2024)Automating Key Fingerprint Comparisons in Secure Mobile Messaging Apps: A Case Study of SignalProceedings of the Fourteenth ACM Conference on Data and Application Security and Privacy10.1145/3626232.3653251(277-288)Online publication date: 19-Jun-2024
https://dl.acm.org/doi/10.1145/3626232.3653251
Jiang CXu CHan YZhang ZChen K(2024)Two-Factor Authenticated Key Exchange From Biometrics With Low Entropy RatesIEEE Transactions on Information Forensics and Security10.1109/TIFS.2024.337281219(3844-3856)Online publication date: 2024
https://doi.org/10.1109/TIFS.2024.3372812
Merrill KNewman ZTorres-Arias SSollins KMeng WJensen CCremers CKirda E(2023)Speranza: Usable, Privacy-friendly Software SigningProceedings of the 2023 ACM SIGSAC Conference on Computer and Communications Security10.1145/3576915.3623200(3388-3402)Online publication date: 15-Nov-2023
https://dl.acm.org/doi/10.1145/3576915.3623200
Wang WLu YPapamanthou CZhang FMeng WJensen CCremers CKirda E(2023)The Locality of Memory CheckingProceedings of the 2023 ACM SIGSAC Conference on Computer and Communications Security10.1145/3576915.3623195(1820-1834)Online publication date: 15-Nov-2023
https://dl.acm.org/doi/10.1145/3576915.3623195
Len JChase MGhosh EJost DKesavan BMarcedone AMeng WJensen CCremers CKirda E(2023)ELEKTRA: Efficient Lightweight multi-dEvice Key TRAnsparencyProceedings of the 2023 ACM SIGSAC Conference on Computer and Communications Security10.1145/3576915.3623161(2915-2929)Online publication date: 15-Nov-2023
https://dl.acm.org/doi/10.1145/3576915.3623161
Ma YWoods JAngel SPolychroniadou ARabin T(2023)Flamingo: Multi-Round Single-Server Secure Aggregation with Applications to Private Federated Learning2023 IEEE Symposium on Security and Privacy (SP)10.1109/SP46215.2023.10179434(477-496)Online publication date: May-2023
https://doi.org/10.1109/SP46215.2023.10179434
Ernstberger JLauinger JElsheimy FZhou LSteinhorst SCanetti RMiller AGervais ASong D(2023)SoK: Data Sovereignty2023 IEEE 8th European Symposium on Security and Privacy (EuroS&P)10.1109/EuroSP57164.2023.00017(122-143)Online publication date: Jul-2023
https://doi.org/10.1109/EuroSP57164.2023.00017
Zhang XDeng Y(2023)Zero-Knowledge Functional Elementary DatabasesAdvances in Cryptology – ASIACRYPT 202310.1007/978-981-99-8733-7_9(269-303)Online publication date: 4-Dec-2023
https://dl.acm.org/doi/10.1007/978-981-99-8733-7_9
Blessing JAnderson R(2023)One Protocol to Rule Them All? On Securing Interoperable MessagingSecurity Protocols XXVIII10.1007/978-3-031-43033-6_17(174-192)Online publication date: 21-Oct-2023
https://doi.org/10.1007/978-3-031-43033-6_17
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

Media

Figures

Other

Tables

View Table of Contents