This document is intended for advanced readers with knowledge of cryptography. You can find an accessible overview of the article on this page.
A group of researchers from the University of London and ETH Zurich conducted a formal analysis of the Telegram MTProto protocol. The central result of the investigation was that MTProto can provide a confidential and integrity-protected channel if special care is taken when implementing the protocol.
The researchers also highlighted several traits of MTProto that were changed as the result of our discussions before the paper was published. This document provides a technical overview of the changes.
For an accessible overview in layman's terms, see this document.
Requiring all requests to be sent over a single connection and in a strictly maintained sequence within each session, as suggested in the paper, would indeed facilitate formal analysis, while also preventing “crime-pizza”-style reordering. However, such strict ordering only makes sense in contexts when requests are handled in sequence by the server.
MTProto was designed to support the simultaneous use of several TCP or HTTP connections inside a session. While MTProto over UDP is not used in the current implementation of Telegram, the protocol was also designed with the possibility of UDP usage in mind. Just like DTLS, MTProto leaves the ordering of messages up to the higher-level protocol.
Given that A) it is critical for the Telegram server to be able to process several parallel heavy requests on multiple connections simultaneously and B) that an attacker has no way of knowing the content of the messages they might affect, we do not feel that the possibility of reordering in cloud chats presents an issue that would require changes on the protocol level.
On a higher level, Telegram supports special InvokeAfter… methods for cases when the client needs certain requests to be processed in a certain order and intends to send a new request before the previous one is completed.
Previously, these methods were ignored in case of delays of over 0.5 seconds. Since July 2021, such delays trigger the 400 MSG_WAIT_TIMEOUT, effectively preventing reordering of uncompleted requests where relevant.
This part of the document is being updated with additional comments.
MTProto never produces the same ciphertext, even for messages with identical content, because MTProto is stateful and msg_id is changed on every encryption. If one message is re-sent on the order of 2^64 times, MTProto can transmit the same ciphertext for the same message on two of these re-sendings. However, it would not be correct to claim that retransmission over the network of the same ciphertext for a message that was previously sent is a violation of IND-CPA security because otherwise any protocol over TCP wouldn't be IND-CPA secure due to TCP retransmissions.
To facilitate future research, each message that is re-sent by Telegram apps is now either wrapped in a new container or re-sent with a new msg_id.
The attack described in Section VI of the paper would not lead to plaintext recovery. In the researchers' own words, recovering plaintext would only be possible, assuming the attackers “knew the plaintext blocks 𝑚1”. The paper goes on to say:
“On another hand, the requirement of knowing 𝑚1 may not be easy to fulfil in MTProto. The first plaintext block always contains server_salt || session_id, both of which are random values. It is unclear whether they were intended to be secret, but in effect they are, limiting the applicability of this attack.”
session_id are random 64-bit numbers that are changed every 60 minutes and whenever a client is restarted — this makes it impossible to guess them and effectively makes plaintext recovery impossible.
Note also that strategies described in Appendix F of the paper would not help recover server_salt and session_id in practice.
All affected Telegram apps were updated in June 2021 (v.7.8) to make this no longer relevant.
In the past, the processing of the decrypted RSA payload was not performed by constant-time branch-free code. However, the potential tiny difference in processing time — on the order of several CPU cycles — was always overwhelmed by the cross-processor synchronization delays (and their unpredictability) since all such requests were received by one “network” thread, put into a queue, decrypted in a separate “RSA-decryption” process and/or thread, and eventually processed again by the “network” thread to send the computed answer to the client through a chain of proxies. Due to this, the attack described in Appendix F of the paper was impossible in practice.
The attack was further complicated by the fact that it required 2^32 requests to the server before key generation was completed, each of which would include resource-intensive pq factoring. This factoring is required because a new key generation session will be needed for every RSA decryption attempt (since the existing key generation session is immediately destroyed if the RSA-decrypted payload turns out to be invalid). That said, the attack was already impossible – even without this additional consideration – due to the synchronization delays discussed above.
Even though the existing setup didn't present practical security concerns, its theoretical security against potential undiscovered attacks was further improved in the following ways in July 2021:
Any comments on Telegram's security are welcome at firstname.lastname@example.org. All submissions which result in a change of code or configuration are eligible for bounties, ranging from $100 to $100,000 or more, depending on the nature of the changes.