Top

Published in:

2019 | OriginalPaper | Chapter

Efficient Ratcheting: Almost-Optimal Guarantees for Secure Messaging

Authors : Daniel Jost, Ueli Maurer, Marta Mularczyk

Published in: Advances in Cryptology – EUROCRYPT 2019

Publisher: Springer International Publishing

Activate our intelligent search to find suitable subject content or patents.

search-config

AI-assisted search

Off

Abstract

In the era of mass surveillance and information breaches, privacy of Internet communication, and messaging in particular, is a growing concern. As secure messaging protocols are executed on the not-so-secure end-user devices, and because their sessions are long-lived, they aim to guarantee strong security even if secret states and local randomness can be exposed.

The most basic security properties, including forward secrecy, can be achieved using standard techniques such as authenticated encryption. Modern protocols, such as Signal, go one step further and additionally provide the so-called backward secrecy, or healing from state exposures. These additional guarantees come at the price of a moderate efficiency loss (they require public-key primitives).

On the opposite side of the security spectrum are the works by Jaeger and Stepanovs and by Poettering and Rösler, which characterize the optimal security a secure-messaging scheme can achieve. However, their proof-of-concept constructions suffer from an extreme efficiency loss compared to Signal. Moreover, this caveat seems inherent.

This paper explores the area in between: our starting point are the basic, efficient constructions, and then we ask how far we can go towards the optimal security without losing too much efficiency. We present a construction with guarantees much stronger than those achieved by Signal, and slightly weaker than optimal, yet its efficiency is closer to that of Signal (only standard public-key cryptography is used).

On a technical level, achieving optimal guarantees inherently requires key-updating public-key primitives, where the update information is allowed to be public. We consider secret update information instead. Since a state exposure temporally breaks confidentiality, we carefully design such secretly-updatable primitives whose security degrades gracefully if the supposedly secret update information leaks.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

previous chapter The Double Ratchet: Security Notions, Proofs, and Modularization for the Signal Protocol

next chapter Indistinguishability Obfuscation Without Multilinear Maps: New Methods for Bootstrapping and Instantiation

Of course, for the healing to take effect, the adversary must remain passive and not immediately use the compromised state to impersonate a party.

Namely, the messages sent right before or right after an active impersonation attack.

Looking ahead, it turns out that in order to prove the security of this construction, we need circular-secure encryption. We achieve this in the random oracle model.

Note that this also makes the choice of abstraction levels particularly difficult, as we need confidentiality, in order to obtain authentication.

We can assume that Alice sends this value confidentially. It makes no sense to consider Bob’s state being exposed, as this would mean that both parties are exposed at the same time, in which case, clearly, we cannot guarantee any security.

The adversary knows which states are exposed, and hence can check himself before submitting a forgery attempt, whether this will make him lose the game.

In fact, the counter is not necessary to prove security of the construction, since every message is signed with a different key. However, we find it cleaner to include it.

For example, in our construction the public part of the update is a fresh verification key, and the secret part is the corresponding signing key. This would not satisfy the requirements of [11], since there is no way to update the signing key using only the fresh verification key.

For technical reasons, we only allow one query to the Expose oracle.

Roughly, the additional data is needed to provide post-hijack security of the final construction: changing the additional data means that the adversary decided to hijack the channel, hence, the decryption key should be updated.

Alwen, J., Coretti, S., Dodis, Y.: The double ratchet: security notions, proofs, and modularization for the signal protocol. In: Ishai, Y., Rijmen, V. (eds.) EUROCRYPT 2019, LNCS, vol. 11476, pp. 129–158. Springer, Heidelberg (2019)

Bellare, M., Kohno, T., Namprempre, C.: Breaking and provably repairing the SSH authenticated encryption scheme: a case study of the Encode-then-Encrypt-and-MAC paradigm. ACM Trans. Inf. Syst. Secur. 7(2), 206–241 (2004)CrossRef

Bellare, M., Miner, S.K.: A forward-secure digital signature scheme. In: Wiener, M. (ed.) CRYPTO 1999. LNCS, vol. 1666, pp. 431–448. Springer, Heidelberg (1999). https://doi.org/10.1007/3-540-48405-1_28CrossRef

Bellare, M., Singh, A.C., Jaeger, J., Nyayapati, M., Stepanovs, I.: Ratcheted encryption and key exchange: the security of messaging. In: Katz, J., Shacham, H. (eds.) CRYPTO 2017. LNCS, vol. 10403, pp. 619–650. Springer, Cham (2017). https://doi.org/10.1007/978-3-319-63697-9_21CrossRef

Borisov, N., Goldberg, I., Brewer, E.: Off-the-record communication, or, why not to use PGP. In: Proceedings of the 2004 ACM Workshop on Privacy in the Electronic Society, WPES 2004, pp. 77–84. ACM, New York (2004)

Canetti, R., Halevi, S., Katz, J.: A forward-secure public-key encryption scheme. In: Biham, E. (ed.) EUROCRYPT 2003. LNCS, vol. 2656, pp. 255–271. Springer, Heidelberg (2003). https://doi.org/10.1007/3-540-39200-9_16CrossRef

Cohn-Gordon, K., Cremers, C., Dowling, B., Garratt, L., Stebila, D.: A formal security analysis of the signal messaging protocol. In: 2nd IEEE European Symposium on Security and Privacy, EuroS and P 2017, pp. 451–466 (2017)

Durak, F.B., Vaudenay, S.: Bidirectional asynchronous ratcheted key agreement without key-update primitives. Cryptology ePrint Archive, Report 2018/889 (2018). https://eprint.iacr.org/2018/889

Gentry, C., Silverberg, A.: Hierarchical ID-based cryptography. In: Zheng, Y. (ed.) ASIACRYPT 2002. LNCS, vol. 2501, pp. 548–566. Springer, Heidelberg (2002). https://doi.org/10.1007/3-540-36178-2_34CrossRef

10.

Horwitz, J., Lynn, B.: Toward hierarchical identity-based encryption. In: Knudsen, L.R. (ed.) EUROCRYPT 2002. LNCS, vol. 2332, pp. 466–481. Springer, Heidelberg (2002). https://doi.org/10.1007/3-540-46035-7_31CrossRef

11.

Jaeger, J., Stepanovs, I.: Optimal channel security against fine-grained state compromise: the safety of messaging. In: Shacham, H., Boldyreva, A. (eds.) CRYPTO 2018. LNCS, vol. 10991, pp. 33–62. Springer, Cham (2018). https://doi.org/10.1007/978-3-319-96884-1_2CrossRef

12.

Jost, D., Maurer, U., Mularczyk, M.: Efficient ratcheting: almost-optimal guarantees for secure messaging. Cryptology ePrint Archive, Report 2018/954 (2018). https://eprint.iacr.org/2018/954. (full version of this paper)

13.

Kaplan, D., Kedmi, S., Hay, R., Dayan, A.: Attacking the Linux PRNG on android: weaknesses in seeding of entropic pools and low boot-time entropy. In: Proceedings of the 8th USENIX Conference on Offensive Technologies, WOOT 2014, p. 14. USENIX Association, Berkeley (2014)

14.

Li, Y., Shen, T., Sun, X., Pan, X., Mao, B.: Detection, classification and characterization of Android malware using API data dependency. In: Thuraisingham, B., Wang, X.F., Yegneswaran, V. (eds.) SecureComm 2015. LNICST, vol. 164, pp. 23–40. Springer, Cham (2015). https://doi.org/10.1007/978-3-319-28865-9_2CrossRef

15.

Open Whisper Systems. Signal protocol library for java/android. GitHub repository (2017). https://github.com/WhisperSystems/libsignal-protocol-java. Accessed 01 Oct 2018

16.

Poettering, B., Rösler, P.: Towards bidirectional ratcheted key exchange. In: Shacham, H., Boldyreva, A. (eds.) CRYPTO 2018. LNCS, vol. 10991, pp. 3–32. Springer, Cham (2018). https://doi.org/10.1007/978-3-319-96884-1_1CrossRef

Title: Efficient Ratcheting: Almost-Optimal Guarantees for Secure Messaging
Authors: Daniel Jost
Ueli Maurer
Marta Mularczyk
Publisher: Springer International Publishing
Book: Advances in Cryptology – EUROCRYPT 2019
Print ISBN: 978-3-030-17652-5

Electronic ISBN: 978-3-030-17653-2

Copyright Year: 2019
DOI: https://doi.org/10.1007/978-3-030-17653-2_6

Springer Professional

Abstract

Please log in to get access to your license.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"

Premium Partner