Subverting Telegram's End-to-End Encryption

Telegram is a popular secure messaging service with third biggest user base as of 2021. In this paper, we analyze the security of Telegram’s end-to-end encryption (E2EE) protocol in presence of mass-surveillance. Specifically, we show that Telegram’s E2EE protocol is susceptible to fairly efficient algorithm substitution attacks. While official Telegram clients should be protected against this type of attack due their open-source nature and reproducible builds, this could potentially lead to a very efficient state sponsored surveillance of private communications over Telegram, either on individuals through a targeted attack or massively through some compromised third-party clients. We provide an efficient algorithm substitution attack against MTProto2.0 --- the underlying authenticated encryption scheme --- that recovers significant amount of encryption key material with a very high probability with few queries and fairly low latency. This could potentially lead to a very efficient state sponsored surveillance of private communications over Telegram, either through a targeted attack or a compromised third-party app. Our attack exploits MTProto2.0's degree of freedom in choosing the random padding length and padding value. Accordingly, we strongly recommend that Telegram should revise MTProto2.0's padding methodology. In particular, we show that a minor change in the padding description of MTProto2.0 makes it subversion-resistant in most of the practical scenarios. As a side-effect, we generalize the underlying mode of operation in MTProto2.0, as MTProto-G, and show that this generalization is a multi-user secure deterministic authenticated encryption scheme.