# On the CCA (in)Security of MTProto

## 选择密文攻击下的不可区分性

1. 挑战者拥有公钥 $PK$，私钥 $SK$，将 $PK$ 发送给攻击者
2. 攻击者选择两个长度相等的明文 $M_1$$M_2$ 发送给挑战者
3. 挑战者或者明文后，随机决定 $b$ 的取值，$b=\{0,1\}$，决定 $M_b$ 的加密，$C=Enc(PK,M_b)$，然后发送给攻击者
4. 攻击者获得密文后，给出 $b$ 的值（即确定是加密的 $M_1$ 还是 $M_2$

## 摘要

ABSTRACT

Telegram is a popular messaging app which supports end-toend encrypted communication. In Spring 2015 we performed an audit of Telegram’s Android source code. This short paper summarizes our findings.

Our main discovery is that the symmetric encryption scheme used in Telegram – known as MTProto – is not IND-CCA secure, since it is possible to turn any ciphertext into a different ciphertext that decrypts to the same message.

We stress that this is a theoretical attack on the definition of security and we do not see any way of turning the attack into a full plaintext-recovery attack. At the same time, we see no reason why one should use a less secure encryption scheme when more secure (and at least as efficient) solutions exist.

The take-home message (once again) is that well-studied, provably secure encryption schemes that achieve strong definitions of security (e.g., authenticated-encryption) are to be preferred to home-brewed encryption schemes.

## 1. 介绍

### Telegeam

Telegram. Telegram is an instant messaging service designed for mobile devices, that has had (as of May 2015) 62 million monthly active users and is used to deliver 1010 messages daily. It offers two modes, the first being the regular chat mode in which all messages can be read by the server and are stored, allowing for synchronization between devices and group chats. The second mode, called secret chat, is an end-to-end encrypted chat which supports at most two parties. Messages are sent through the server in encrypted form only, and are claimed not to be stored.

The official Telegram client application is open source, allowing for full auditing, but the server software is not. According to the Electronic Frontier Foundation, Telegram was audited in February 2015 and the secret chat mode achieved full marks for its security.

Telegram 是一种为移动设备设计的即时消息服务，到 2015 年 5 月，已经有 6200 万月活。其提供两种聊天模式，分别是和大多数即时通信一致的普通模式，所有消息都由服务器存取；另一种则是秘密聊天，最多支持双方的端到端加密聊天，服务器无法获知内容。
Telegram 客户端时开源的，允许任何用户审查，但服务器并未开源。在 2015 年 2 月的审计中，证明秘密聊天模式达到满分。

### 分析

Our Analysis. In Spring 2015 we performed an independent audit of the Telegram source code. The analysis is based on the official Telegram source code for version 2.7.0, downloaded in mid April 2015 from github.

Instead of using proven cryptographic constructs, Telegram opted to create its own original protocol for symmetric encryption, known as MTProto. Our main finding is that MTProto does not satisfy the definitions of authenticated encryption (AE) or indistinguishability under chosenciphertext attack (IND-CCA) [KL14]. Those definitions are designed to guarantee security of symmetric encryption schemes in the presence of active attacks (i.e., attacks where the adversary freely manipulates ciphertexts and has access to a decryption oracle). We note that MTProto includes some kind of integrity mechanism, which means that active attacks are included in Telegram’s threat-model. Alas, the non-standard countermeasures that MTProto implements are not enough to satisfy current standards for security of encryption schemes.

In a nutshell, MTProto uses a block-cipher structure and therefore includes padding. Unfortunately, neither the length nor the content of the padding are checked for integrity during decryption. This means that given any ciphertext it is possible to create different ciphertexts that decrypt to the same message, thus breaking the definition of security. In fact, we found two ways of doing this: either by adding one more random block at the end of the ciphertext or by replacing the last block with a random block. The first method produces a ciphertext which decrypts correctly with probability 1, while the second method produces a ciphertext which decrypts correctly with probability exponentially small in the amount of payload contained in the last block (i.e., the block length minus the padding length).

Our findings were communicated to the Telegram team on the 3rd of September 2015. The Telegram team has not fixed the problem, but has changed the description of the protocol instead.

Telegram 没有使用经过验证的加密结构，而是使用自研的 MTProto。在审查过程中，发现的问题在于 MTProto 不满足认证加密(Authenticated Encryption, AE)和选择密文攻击下的不可区分性(Indistinguishability under chosen-ciphertext attack, IND-CCA)。攻击者可以自由操作密文并解密。现有的 MTProto 不足以满足当前加密方案的安全性标准
MTProto 使用分组密码，因此需要对明文进行填充。但在解密期间未检查填充的长度和内容的完整性。对于任意给定的密文，可以生成不同的密文，但可以解密出相同的明文，而这破坏了安全性的定义。要解决该问题，有两个思路：

• 在密文末尾添加随机的分组（可以完全正确解密）
• 使用随机的块替换最后一个分组（正确解密的概率取决于最后一个块中明文的长度）
代码审查的结果已经反馈给 Telegram 团队，但并未解决

## 2. MTProto

2. MTPROTO

From a high-level point of view, Telegram allows two devices to exchange a long term key using Diffie-Hellman key exchange. Afterwards, the two devices can use this key to exchange encrypted messages using a symmetric encryption scheme known as MTProto. In a nutshell MTProto is a combination of:

1. A lesser known mode of operation, namely Infinite Garble Extension (IGE);
2. A short term key derivation mechanism;
3. An integrity check on the plaintext;

Here is an abstract description of MTProto:

Telegram 允许两个设备使用 Diffie-Hellman 密钥交换生成长期密钥，接着使用该密钥作为对称加密的密钥。其主要包含三方面：

1. 一种很少有人使用的分组密码工作模式——无限混淆拓展( Infinite Garble Extension, IGE)
2. 短期密钥派生机制
3. 明文完整性检查

### 2.1 MTProto 加密

2.1 MTProto Encryption

Long-Term key: The sender and the receiver share a long term-key $K$ of length $\lambda$. (In MTProto $\lambda = 2048$ bits and the key is obtained by running the Diffie-Hellman Key-Exchange over a multiplicative subgroup of $Z_p^*$, where $p$ and $p-1/2$ are primes);

Payload: The payload $x = (aux, rnd, msg, pad)$ is obtained by concatenating:

1. some auxiliary information aux;
2. a random salt rnd (in MTProto this has length 128 bits);
3. the message msg;
4. some arbitrary padding pad such that $|x| \mod B = 0$, where $B$ is the block length; For technical reasons this is never more than $96$ bits (and not $120$ bits as described by the official documentation).

Authentication Tag: MTProto employs a hash function $Tag: \{0, 1\}^∗ \rightarrow \{0, 1\}^h$ for authentication purposes. This is used to compute $tag = Tag(aux, rnd, msg)$ (crucially, pad is not part of the input of the authentication tag). In MTProto $Tag = \text{SHA-1}$ and $h = 128$ bits;

Short-Term Key Derivation: MTProto employs a hash function $KDF: \{0, 1\}^{\lambda+h} \rightarrow \{0, 1\}^{\kappa+2B}$ for key derivation purposes. This is used to compute $(k, x_0, y_0) = KDF(K, tag)$ of length $(\kappa,B, B)$ respectively. In MTProto the output of KDF is obtained by (a permutation of) the output of four SHA-1 invocations, which in turn take as input (a permutation of) the tag and (different) portions of the long term key $K$.

IGE Encryption: MTProto employs an efficiently invertible pseudo-random permutation (PRP) $F,F^{-1}: \{0,1\}^\kappa \times \{0,1\}^B \rightarrow \{0,1\}^B$ to implement the IGE mode of operation. Let $x1, \cdots , x_l$ be the $l$ blocks of the payload, each of length $B$, then IGE computes $y_i=F_k(x_i \oplus y_{i-1}) \oplus x_{i-1}$ (where $x_0$, $y_0$ are defined in the previous step). In MTProto $F=AES$ with $\kappa=256$ bit and $B=128$ bits;

Resulting Ciphertext: The output of MTProto is $c=(tag, y_1,\cdots, y_l)$ (as well as other information which is not relevant for our presentation)

• 辅助信息 $aux$
• 随机盐 $rnd$ （在 MTProto 中长度为 $128$ 位）
• 消息 $msg$
• 任意填充值 $pad$ 比如 $|x| \mod B = 0$，其中 $B$ 是分组长度（技术问题，该值不超过 $96$ 位，而不是官方文档中的 $120$ 位）

MTProto 中使用一个用于身份验证的特殊的哈希函数
$Tag: \{0,1\}^* \rightarrow \{0,1\}^h$

MTProto 中使用一个用于生成密钥的特殊的哈希函数
$KDF: \{0,1\}^{\lambda+h} \rightarrow \{0,1\}^{\kappa+2B}$

： 在 MTProto 中，KDF 是 $4$ 次 SHA-1 调用输出，而 $4$ 次 SHA-1 的输入则是 $tag$ 和长期密钥 $K$

MTProto 采用了一种有效的可逆伪随机置换(PRP)来实现 IGE 模式。
$F,F^{-1}: \{0,1\}^\kappa \times \{0,1\}^B \rightarrow \{0,1\}^B$

IGE 使用 $y_i = F_k(x_i \oplus y_{i-1}) \oplus x_{i-1}$ 计算，其中 $x_0$$y_0$ 由上一步计算出

MTProto 的输出为 $c=(tag,y_1,\cdots,y_l)$

### 2.2 MTProto 解密

2.2 MTProto Decryption

Input Parsing: The ciphertext $c$ is parsed as $c = (tag, y_1, \cdots , y_l)$

Short-Term Key Re-computation: The short-term key and the initialization blocks are recomputed as $(k, x0, y0) = KDF(K, tag)$

IGE Decryption: The payload is recovered by computing: $x_i = y_{i−1} \oplus F^{−1}_k (y_i \oplus x_{i−1})$ and $(x1, \cdots , x_l)$ is parsed as $(aux, rnd, msg, pad)$. The padding $pad$ is stripped from the payload by reading the byte length from the auxiliary data, and removing any bytes beyond this length.

Tag Verification: The decryption checks if $tag \overset{?}{=} Tag(aux, rnd, msg)$ and, if so, outputs msg (or $\bot$ otherwise).

Interestingly, if a Telegram client receives an ill-formed ciphertext, it simply drops the message and does not notify the sender about the error. This implies that it seems very hard for a network attacker to detect whether a decryption was performed successfully or not (and therefore it does not seem possible to run a Bleichenbacher-style attack [Ble98]). However, we cannot exclude that an attacker which sits on the same client and shares resources (such as memory, CPU, etc.) might be able to detect if (and how) decryption fails using other channels.

## 3. MTProto 不具备 IND-CCA

3. MTPROTO IS NOT IND-CCA SECURE

Here we briefly present the two attacks that show that MTProto is not IND-CCA secure. We assume the reader to be familiar with the notion of IND-CCA security. More details on the attacks (and experimental validations) can be found in [Jak15].

Once again, we stress that the attacks are only of theoretical nature and we do not see a way of turning them into full-plaintext recovery. Yet, we believe that these attacks are yet another proof (see e.g., [JN15]) that designing your own crypto rarely is a good idea.

### 3.1 攻击方式1：填充长度拓展

Given a ciphertext $c = (tag, y1, \cdots, y_l)$ which encrypts a payload $x = (aux, rnd, msg, pad)$ the attacker picks a random block $r \leftarrow \{0, 1\}^B$ and outputs $c' = (tag, y1, \cdots, y_l, r)$
When this is run via the decryption process, the resulting payload is $x' = (aux, rnd, msg, pad')$ where $pad' = (pad, pad^∗)$ where: 1) $pad^∗$ is randomly distributed and 2) the length of $|pad'|$ is larger than the block length $B$. However, since the length of the $pad'$ is not checked during decryption, and $pad'$ is not an input to the authentication function $Tag$, decryption outputs msg with probability 1.

Mitigation. This attack can be mitigated simply by checking the length of $pad'$ during decryption, and letting decryption abort if this is larger than the block size. Note that since honest clients never produce ill-formed ciphertexts, patching the decryption process in this way will not prevent clients running older versions of the software to

### 3.2 攻击方式2：末分组替换

3.2 Attack #2: Last Block Substitution

Given a ciphertext $c = (tag, y_1, \cdots , y_l)$ which encrypts a payload $x = (aux, rnd, msg, pad)$ the attacker picks a random block $r \leftarrow \{0, 1\}^B$ and outputs $c' = (tag, y_1, \cdots, y_{l−1}, r)$
When this is run via the decryption process, the resulting payload is $x' = (aux, rnd, msg', pad')$

Let $P = |pad|$ be the length of the original pad, then it holds that the last $B − P$ bits of $msg'$ are randomly distributed (due to the use of the PRP in the IGE decryption). Hence we have $msg' = msg$ with probability $2^{P−B}$, and in this case the verification of the authentication tag succeeds and the decryption outputs $msg$. According to the official description of MTProto the padding length is between $0$ and $120$ bits, which means that in the best case scenario the above attack succeeds with probability $2^{−8}$. However experimental validation shows that this is not the case and the length of the padding is in fact between $0$ and $96$ bits (this is due to the way the objects are serialized in chunks of four bytes in Java).

So we conclude that in the best case this attack succeeds with probability $2^{−32}$ which, while still being too high to satisfy the definition of security, makes this attack more cumbersome than expected.

Mitigation. This attack can be mitigated by adding pad to the computation of the authentication tag. However, since this requires to change the encryption process as well, patched clients will not be able to communicate with unpatched clients.

## 4. 结论

4. CONCLUSION

We described two simple attacks which show that MTProto, the symmetric encryption scheme used by Telegram, fails to achieve desirable notions of security such as indistinguishability under chosen-ciphertext attack or authenticated encryption. While the first attack can be mitigated by applying a patch which does not affect backward compatibility with unpatched (but honest) senders, the second one can only be patched in a way that only allows communication between patched clients. Therefore it is fair to ask whether the next version of Telegram should use a patched version of MTProto or a better studied mode of operation which provably implements authenticated encryption.

We believe that the second option is the only sensible choice since while a patched version of MTProto would not be susceptible to the attacks described in this note, this gives no guarantees that no other attacks exist. On the other hand well studied authenticated encryption schemes offer much stronger security guarantees. In addition, MTProto does not seem to be more efficient than the many available options for authenticated encryption such as e.g., encrypt-then-MAC using AES in counter mode (which can be parallelized better than IGE) together with e.g., HMAC.