Top

Published in:

2018 | OriginalPaper | Chapter

Out-of-Band Authentication in Group Messaging: Computational, Statistical, Optimal

Authors : Lior Rotem, Gil Segev

Published in: Advances in Cryptology – CRYPTO 2018

Publisher: Springer International Publishing

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

search-config

AI-assisted search

Off

Abstract

Extensive efforts are currently put into securing messaging platforms, where a key challenge is that of protecting against man-in-the-middle attacks when setting up secure end-to-end channels. The vast majority of these efforts, however, have so far focused on securing user-to-user messaging, and recent attacks indicate that the security of group messaging is still quite fragile.

We initiate the study of out-of-band authentication in the group setting, extending the user-to-user setting where messaging platforms (e.g., Telegram and WhatsApp) protect against man-in-the-middle attacks by assuming that users have access to an external channel for authenticating one short value (e.g., two users who recognize each other’s voice can compare a short value). Inspired by the frameworks of Vaudenay (CRYPTO ’05) and Naor et al. (CRYPTO ’06) in the user-to-user setting, we assume that users communicate over a completely-insecure channel, and that a group administrator can out-of-band authenticate one short message to all users. An adversary may read, remove, or delay this message (for all or for some of the users), but cannot undetectably modify it.

Within our framework we establish tight bounds on the tradeoff between the adversary’s success probability and the length of the out-of-band authenticated message (which is a crucial bottleneck given that the out-of-band channel is of low bandwidth). We consider both computationally-secure and statistically-secure protocols, and for each flavor of security we construct an authentication protocol and prove a lower bound showing that our protocol achieves essentially the best possible tradeoff.

In particular, considering groups that consist of an administrator and k additional users, for statistically-secure protocols we show that at least \((k+1)\cdot (\log (1/\epsilon ) - \varTheta (1))\) bits must be out-of-band authenticated, whereas for computationally-secure ones \(\log (1/\epsilon ) + \log k\) bits suffice, where \(\epsilon \) is the adversary’s success probability. Moreover, instantiating our computationally-secure protocol in the random-oracle model yields an efficient and practically-relevant protocol (which, alternatively, can also be based on any one-way function in the standard model).

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 Optimal Channel Security Against Fine-Grained State Compromise: The Safety of Messaging

next chapter Faster Homomorphic Linear Transformations in HElib

Despite the significant threats posed by man-in-the-middle attacks, research on the security of group messaging has so far assumed an initial authenticated setup phase (e.g., [CGCG+17, RMS18]), and did not address this security-critical assumption.

For example, as specified in WhatsApp’s security whitepaper [Wha, p. 10]: “WhatsApp users additionally have the option to verify the keys of the other users with whom they are communicating so that they are able to confirm that an unauthorized third party (or WhatsApp) has not initiated a man-in-the-middle attack. This can be done by scanning a QR code, or by comparing a 60-digit number. [...] The 60-digit number is computed by concatenating the two 30-digit numeric fingerprints for each user’s Identity Key”.

Unfortunately, potential attacks on the Interlock protocol were identified later on [BM94, Ell96].

Clearly, one may consider a less-minimal extension where several users are allowed to send out-of-band authenticated values (i.e., not only the group administrator that we denote as the sender), but as our results show this is in fact not required.

Concretely, when setting the adversary’s forgery probability \(\epsilon \) to \(2^{-30}\) in a group that consists of \(k = 2^{10}\) users, then in any statistically-secure protocol more than \(k \cdot \log (1/\epsilon ) = 2^{10}\cdot 30\) bits must be out-of-band authenticated, whereas in our computationally-secure protocol only \(\log (1/\epsilon ) + \log k = 40\) bits are out-of-band authenticated.

Note that if the adversary’s forgery probability in the group protocol should be at most \(\epsilon \), then the user-to-user protocol should be parameterized, for example, with \(\epsilon /k\) as the adversary’s forgery probability (enabling a union bound over the k executions).

Of course, a commitment scheme may be interactive, but we use this terminology for ease of presentation in the overview.

We do not go into details regarding the possible models of insecure communication in this high-level overview, and we refer the reader to Sect. 3 for an in-depth discussion.

A successful forgery also requires that the input message for that particular receiver is different in the two executions, but this has little effect on the probability of forgery when the input messages are not too short.

As a commitment scheme may be interactive, when referring to a commitment, we mean the transcript of the interaction between the committer and the receiver during an execution of the commit phase of the commitment scheme. When the scheme is non-interactive, a commitment is simply a single string sent from the committer to the receiver.

[BM94]

Bellovin, S.M., Merritt, M.: An attack on the Interlock protocol when used for authentication. IEEE Trans. Inf. Theory 40(1), 273–275 (1994)CrossRef

[BR93]

Bellare, M., Rogaway, P.: Random oracles are practical: a paradigm for designing efficient protocols. In: Proceedings of the 1st ACM Conference on Computer and Communications Security, pp. 62–73 (1993)

[BSJ+17]

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

[CCD+17]

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

[CF01]

Canetti, R., Fischlin, M.: Universally composable commitments. In: Kilian, J. (ed.) CRYPTO 2001. LNCS, vol. 2139, pp. 19–40. Springer, Heidelberg (2001). https://doi.org/10.1007/3-540-44647-8_2CrossRef

[CGCG+17]

Cohn-Gordon, K., Cremers, C., Garratt, L., Millican, J., Milner, K.: On ends-to-ends encryption: Asynchronous group messaging with strong security guarantees. Cryptology ePrint Archive, Report 2017/666 (2017)

[CIO98]

Crescenzo, G.D., Ishai, Y., Ostrovsky, R.: Non-interactive and non-malleable commitment. In: Proceedings of the 30th Annual ACM Symposium on Theory of Computing, pp. 141–150 (1998)

[CKO+01]

Di Crescenzo, G., Katz, J., Ostrovsky, R., Smith, A.: Efficient and non-interactive non-malleable commitment. In: Pfitzmann, B. (ed.) EUROCRYPT 2001. LNCS, vol. 2045, pp. 40–59. Springer, Heidelberg (2001). https://doi.org/10.1007/3-540-44987-6_4CrossRef

[COS+17]

Ciampi, M., Ostrovsky, R., Siniscalchi, L., Visconti, I.: Four-round concurrent non-malleable commitments from one-way functions. In: Katz, J., Shacham, H. (eds.) CRYPTO 2017. LNCS, vol. 10402, pp. 127–157. Springer, Cham (2017). https://doi.org/10.1007/978-3-319-63715-0_5CrossRef

[DDN00]

Dolev, D., Dwork, C., Naor, M.: Non-malleable cryptography. SIAM J. Comput. 30(2), 391–437 (2000)MathSciNetCrossRef

[DG03]

Damgard, I., Groth, J.: Non-interactive and reusable non-malleable commitment schemes. In: Proceedings of the 35th Annual ACM Symposium on Theory of Computing, pp. 426–437 (2003)

[Ell96]

Ellison, C.M.: Establishing identity without certification authorities. In: Proceedings of the 6th USENIX Security Symposium, p. 7 (1996)

[FF00]

Fischlin, M., Fischlin, R.: Efficient non-malleable commitment schemes. In: Bellare, M. (ed.) CRYPTO 2000. LNCS, vol. 1880, pp. 413–431. Springer, Heidelberg (2000). https://doi.org/10.1007/3-540-44598-6_26CrossRefMATH

[FMB+16]

Frosch, T., Mainka, C., Bader, C., Bergsma, F., Schwenk, J., Holz, T.: How secure is TextSecure? In: Proceedings of the 1st IEEE European Symposium on Security and Privacy (EuroS&P), pp. 457–472 (2016)

[Gol01]

Goldreich, O.: Foundations of Cryptography – Volume 1: Basic Techniques. Cambridge University Press, Cambridge (2001)CrossRef

[Goy11]

Goyal, V.: Constant round non-malleable protocols using one way functions. In: Proceedings of the 43rd Annual ACM Symposium on Theory of Computing, pp. 695–704 (2011)

[Gre18a]

Green, M.: Attack of the week: Group messaging in WhatsApp and Signal. A Few Thoughts on Cryptographic Engineering (2018). https://blog.cryptographyengineering.com/2018/01/10/attack-of-the-week-group-messaging

[Gre18b]

Greenberg, A.: WhatsApp security flaws could allow snoops to slide into group chats. Wired Mag. (2018). https://www.wired.com/story/whatsapp-security-flaws-encryption-group-chats

[KBB17]

Kobeissi, N., Bhargavan, K., Blanchet, B.: Automated verification for secure messaging protocols and their implementations: a symbolic and computational approach. In: Proceedings of the 2nd IEEE European Symposium on Security and Privacy (EuroS&P), pp. 435–450 (2017)

[LP11]

Lin, H., Pass, R.: Constant-round non-malleable commitments from any one-way function. In: Proceedings of the 43rd Annual ACM Symposium on Theory of Computing, pp. 705–714 (2011)

[LPV08]

Lin, H., Pass, R., Venkitasubramaniam, M.: Concurrent non-malleable commitments from any one-way function. In: Canetti, R. (ed.) TCC 2008. LNCS, vol. 4948, pp. 571–588. Springer, Heidelberg (2008). https://doi.org/10.1007/978-3-540-78524-8_31CrossRef

[NSS06]

Naor, M., Segev, G., Smith, A.: Tight bounds for unconditional authentication protocols in the manual channel and shared key models. In: Dwork, C. (ed.) CRYPTO 2006. LNCS, vol. 4117, pp. 214–231. Springer, Heidelberg (2006). https://doi.org/10.1007/11818175_13CrossRefMATH

[NSS08]

Naor, M., Segev, G., Smith, A.D.: Tight bounds for unconditional authentication protocols in the manual channel and shared key models. IEEE Trans. Inf. Theory 54(6), 2408–2425 (2008)MathSciNetCrossRef

[PM16]

Perrin, T., Marlinspike, M.: The double ratchet algorithm (2016). https://signal.org/docs/specifications/doubleratchet/doubleratchet.pdf. Accessed 16 May 2018

[PR05]

Pass, R., Rosen, A.: Concurrent non-malleable commitments. In: Proceedings of the 46th Annual IEEE Symposium on Foundations of Computer Science, pp. 563–572 (2005)

[PR08]

Pass, R., Rosen, A.: New and improved constructions of nonmalleable cryptographic protocols. SIAM J. Comput. 38(2), 702–752 (2008)MathSciNetCrossRef

[PV06]

Pasini, S., Vaudenay, S.: An optimal non-interactive message authentication protocol. In: Pointcheval, D. (ed.) CT-RSA 2006. LNCS, vol. 3860, pp. 280–294. Springer, Heidelberg (2006). https://doi.org/10.1007/11605805_18CrossRef

[RMS18]

Rösler, P., Mainka, C., Schwenk, J.: More is less: on the end-to-end security of group chats in Signal, WhatsApp, and Threema. In: Proceedings of the 3rd IEEE European Symposium on Security and Privacy (EuroS&P) (2018)

[RS84]

Rivest, R.L., Shamir, A.: How to expose an eavesdropper. Commun. ACM 27(4), 393–395 (1984)CrossRef

[RS18]

Rotem, L., Segev, G.: Out-of-band authentication in group messaging: computational, statistical, optimal. Cryptology ePrint Archive, Report 2018/493 (2018)

[Tela]

Telegram. End-to-end encrypted voice calls - key verification. https://core.telegram.org/api/end-to-end/voice-calls#key-verification. Accessed 16 May 2018

[Telb]

Telegram. End-to-end encryption. https://core.telegram.org/api/end-to-end. Accessed 16 May 2018

[Vau05]

Vaudenay, S.: Secure communications over insecure channels based on short authenticated strings. In: Shoup, V. (ed.) CRYPTO 2005. LNCS, vol. 3621, pp. 309–326. Springer, Heidelberg (2005). https://doi.org/10.1007/11535218_19CrossRef

[Vib]

Viber encryption overview. https://www.viber.com/app/uploads/Viber-Encryption-Overview.pdf. Accessed 16 May 2018

[Wha]

WhatsApp encryption overview. https://www.whatsapp.com/security/WhatsApp-Security-Whitepaper.pdf. Accessed 16 May 2018

[Wik]

Wikipedia. Instant messaging. https://en.wikipedia.org/wiki/Instant_messaging. Accessed 16 May 2018

Title: Out-of-Band Authentication in Group Messaging: Computational, Statistical, Optimal
Authors: Lior Rotem
Gil Segev
Publisher: Springer International Publishing
Book: Advances in Cryptology – CRYPTO 2018
Print ISBN: 978-3-319-96883-4

Electronic ISBN: 978-3-319-96884-1

Copyright Year: 2018
DOI: https://doi.org/10.1007/978-3-319-96884-1_3

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