Analysis of the Telegram Key Exchange

Martin R. Albrecht; Lenka Mareková; Kenneth G. Paterson; Eyal Ronen; Igors Stepanovs

Paper 2025/451

Analysis of the Telegram Key Exchange

Martin R. Albrecht, King's College London

Lenka Mareková

, ETH Zurich

Kenneth G. Paterson

, ETH Zurich

Eyal Ronen

, Tel-Aviv University

Igors Stepanovs

, Amazon

Abstract

We describe, formally model, and prove the security of Telegram's key exchange protocols for client-server communications. To achieve this, we develop a suitable multi-stage key exchange security model along with pseudocode descriptions of the Telegram protocols that are based on analysis of Telegram's specifications and client source code. We carefully document how our descriptions differ from reality and justify our modelling choices. Our security proofs reduce the security of the protocols to that of their cryptographic building blocks, but the subsequent analysis of those building blocks requires the introduction of a number of novel security assumptions, reflecting many design decisions made by Telegram that are suboptimal from the perspective of formal analysis. Along the way, we provide a proof of IND-CCA security for the variant of RSA-OEAP+ used in Telegram and identify a hypothetical attack exploiting current Telegram server behaviour (which is not captured in our protocol descriptions). Finally, we reflect on the broader lessons about protocol design that can be taken from our work.

Metadata

Available format(s): PDF
Category: Cryptographic protocols
Publication info: A major revision of an IACR publication in EUROCRYPT 2025
Keywords: Telegram provable security secure messaging key exchange security analysis
Contact author(s): martin albrecht @ kcl ac uk
lenka marekova @ inf ethz ch
kenny paterson @ inf ethz ch
eyalronen @ tauex tau ac il
igors stepanovs @ gmail com
History: 2025-03-11: approved; 2025-03-10: received; See all versions
Short URL: https://ia.cr/2025/451
License: CC BY

BibTeX

@misc{cryptoeprint:2025/451,
      author = {Martin R. Albrecht and Lenka Mareková and Kenneth G. Paterson and Eyal Ronen and Igors Stepanovs},
      title = {Analysis of the Telegram Key Exchange},
      howpublished = {Cryptology {ePrint} Archive, Paper 2025/451},
      year = {2025},
      url = {https://eprint.iacr.org/2025/451}
}