Abstract We study the use of symmetric cryptography in the MTProto 2.0 protocol, Telegram’s equivalent of the TLS protocol. We give positive and negative results. On the one hand, we formally and in detail specify a slight variant of Telegram’s “record protocol” and prove that it achieves security in a suitable bidirectional secure channel model, albeit under unstudied assumptions; this model itself advances the state of the art for secure channels. On the other hand, we first motivate our slight deviation from MTProto as deployed by giving two attacks on the original protocol specification: one of practical, one of theoretical interest. Then, we give two attacks on the implementation, which are outside of our formal model: one targeting the client, one targeting the server. The client-side attack enables plaintext recovery by exploiting timing side channels, of varying strength, in three official Telegram clients. On its own this attack is thwarted by the secrecy of header fields that are established by Telegram’s key exchange protocol. We thus chain this attack with an attack against the implementation of the key exchange protocol on Telegram’s servers. This final attack breaks the authentication properties of Telegram’s key exchange, allowing a MitM attack. More mundanely, it also reduces the cost of the client-side plaintext-recovery attack. In totality, our results provide the first comprehensive study of MTProto’s use of symmetric cryptography, as well as highlight weaknesses in its key exchange.

We study the use of symmetric cryptography in the MTProto 2.0 protocol, Telegram’s equivalent of the TLS record protocol. We give positive and negative results. On the one hand, we formally and in detail model a slight variant of Telegram’s “record protocol” and prove that it achieves security in a suitable bidirectional secure channel model, albeit under unstudied assumptions; this model itself advances the state-of-the-art for secure channels. On the other hand, we first motivate our modelling deviation from MTProto as deployed by giving two attacks – one of practical, one of theoretical interest – against MTProto without our modifications. We then also give a third attack exploiting timing side channels, of varying strength, in three official Telegram clients. On its own this attack is thwarted by the secrecy of salt and id fields that are established by Telegram’s key exchange protocol. To recover these, we chain the third attack with a fourth one against the implementation of the key exchange protocol on Telegram’s servers. In totality, our results provide the first comprehensive study of MTProto’s use of symmetric cryptography.

A multi-signature scheme allows a group of signers to collaboratively sign a message, creating a single signature that convinces a verifier that every individual signer approved the message. The increased interest in technologies to decentralize trust has triggered the proposal of highly efficient two-round Schnorr-based multi-signature schemes designed to scale up to thousands of signers, namely BCJ by Bagherzandi et al. (CCS 2008), MWLD by Ma et al. (DCC 2010), CoSi by Syta et al. (S&P 2016), and MuSig by Maxwell et al. (ePrint 2018). In this work, we point out serious security issues in all currently known two-round multi-signature schemes (without pairings). First, we prove that none of the schemes can be proved secure without radically departing from currently known techniques. Namely, we show that if the one-more discrete-logarithm problem is hard, then no algebraic reduction exists that proves any of these schemes secure under the discrete-logarithm or one-more discrete-logarithm problem. We point out subtle flaws in the published security proofs of the above schemes (except CoSi, which was not proved secure) to clarify the contradiction between our result and the existing proofs. Next, we describe practical sub-exponential attacks on all schemes, providing further evidence to their insecurity. Being left without two-round multi-signature schemes, we present mBCJ, a variant of the BCJ scheme that we prove secure under the discrete-logarithm assumption in the random-oracle model. Our experiments show that mBCJ barely affects scalability compared to CoSi, allowing 16384 signers to collaboratively sign a message in about 2 seconds, making it a highly practical and provably secure alternative for large-scale deployments.