On the CCA (in)Security of MTProto
本论文针对 MTProto 在 IND-CCA 上理论上存在的两种攻击进行了描述（但是并没有实际该攻击的实现）。更多的细节需要查看作者的硕士毕业论文。
论文发表于 2016 年的智能手机和移动设备安全和隐私研讨会(Annual ACM CCS Workshop on Security and Privacy in Smartphones and Mobile Devices, SPSM)
选择密文攻击下的不可区分性1(Indistinguishability under chosen-ciphertext attack, IND-CCA)
- 挑战者拥有公钥 ，私钥 ，将 发送给攻击者
- 攻击者选择两个长度相等的明文 ， 发送给挑战者
- 挑战者或者明文后，随机决定 的取值，，决定 的加密，，然后发送给攻击者
- 攻击者获得密文后，给出 的值（即确定是加密的 还是 ）
攻击者正确得到 的值的概率为 ，如果 小到足够忽略，则说明算法安全
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.
在 2015 年，该团队对 Telegram 开源的 Android 源码进行了审计，在本论文中总结了发现。发现的主要问题在于 MTProto 并不具备选择密文攻击不可区分性。尽管目前并没有利用该方式的攻击手段，但存在更优方案的同时，没有使用不安全加密方案的理由。
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 不足以满足当前加密方案的安全性标准
代码审查的结果已经反馈给 Telegram 团队，但并未解决
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:
- A lesser known mode of operation, namely Infinite Garble Extension (IGE);
- A short term key derivation mechanism;
- An integrity check on the plaintext;
Here is an abstract description of MTProto:
Telegram 允许两个设备使用 Diffie-Hellman 密钥交换生成长期密钥，接着使用该密钥作为对称加密的密钥。其主要包含三方面：
- 一种很少有人使用的分组密码工作模式——无限混淆拓展( Infinite Garble Extension, IGE)
下面则是 MTProto 的更多描述
2.1 MTProto 加密
2.1 MTProto Encryption
Long-Term key: The sender and the receiver share a long term-key of length . (In MTProto bits and the key is obtained by running the Diffie-Hellman Key-Exchange over a multiplicative subgroup of , where and are primes);
Payload: The payload is obtained by concatenating:
- some auxiliary information aux;
- a random salt rnd (in MTProto this has length 128 bits);
- the message msg;
- some arbitrary padding pad such that , where is the block length; For technical reasons this is never more than bits (and not bits as described by the official documentation).
Authentication Tag: MTProto employs a hash function for authentication purposes. This is used to compute (crucially, pad is not part of the input of the authentication tag). In MTProto and bits;
Short-Term Key Derivation: MTProto employs a hash function for key derivation purposes. This is used to compute of length 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 .
IGE Encryption: MTProto employs an efficiently invertible pseudo-random permutation (PRP) to implement the IGE mode of operation. Let be the blocks of the payload, each of length , then IGE computes (where , are defined in the previous step). In MTProto with bit and bits;
Resulting Ciphertext: The output of MTProto is (as well as other information which is not relevant for our presentation)
- 发送方和接收方共享的长度为 的长期密钥 （在 MTProto 中， 位，并且在 ( 和 是素数) 的乘法子祖上 Diffie-Hellman 密钥交换）
- 负载 包含以下内容
- 随机盐 （在 MTProto 中长度为 位）
- 任意填充值 比如 ，其中 是分组长度（技术问题，该值不超过 位，而不是官方文档中的 位）
- MTProto 中使用一个用于身份验证的特殊的哈希函数
- 在 MTProto 中，Tag 使用 SHA-1 哈希，同时 比特
- MTProto 中使用一个用于生成密钥的特殊的哈希函数
： 在 MTProto 中，KDF 是 次 SHA-1 调用输出，而 次 SHA-1 的输入则是 和长期密钥 。
- MTProto 采用了一种有效的可逆伪随机置换(PRP)来实现 IGE 模式。
- 假设 是 个分组的负载，每一个负载的长度都是
- IGE 使用 计算，其中 和 由上一步计算出
- 在 MTProto 中，， 并且 位
- MTProto 的输出为
2.2 MTProto 解密
2.2 MTProto Decryption
Input Parsing: The ciphertext is parsed as
Short-Term Key Re-computation: The short-term key and the initialization blocks are recomputed as
IGE Decryption: The payload is recovered by computing: and is parsed as . The padding 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 and, if so, outputs msg (or 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.
- 使用如下计算恢复负载 以及 被解析成 。填充值 是从辅助数据中读取，并从中删除部分长度。
如果 Telegram 收到格式不正确的密文，它会简单地丢弃消息，而不会通知发送方。因此攻击者很难确认其尝试的解密是否成功。但实际无法确保同一设备上的攻击者是否能判断是否成功。
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.
这里要介绍的是两种攻击手段，并且假设读者已经熟悉 IND-CCA 的概念。
3.1 Attack #1: Padding-Length Extension
Given a ciphertext which encrypts a payload the attacker picks a random block and outputs
When this is run via the decryption process, the resulting payload is where where: 1) is randomly distributed and 2) the length of is larger than the block length . However, since the length of the is not checked during decryption, and is not an input to the authentication function , decryption outputs msg with probability 1.
Mitigation. This attack can be mitigated simply by checking the length of 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 Attack #2: Last Block Substitution
Given a ciphertext which encrypts a payload the attacker picks a random block and outputs
When this is run via the decryption process, the resulting payload is
Let be the length of the original pad, then it holds that the last bits of are randomly distributed (due to the use of the PRP in the IGE decryption). Hence we have with probability , and in this case the verification of the authentication tag succeeds and the decryption outputs . According to the official description of MTProto the padding length is between and bits, which means that in the best case scenario the above attack succeeds with probability . However experimental validation shows that this is not the case and the length of the padding is in fact between and 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 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.
和上一个攻击类似，假设 是 的长度，则 的最后一个 位是随机分布的，因此有 的概率获得 ，也即验证标签成功，解密出 。根据 MTProto 的官方描述，填充长度在 和 之间。也即在最好的情况下，攻击成功率为 。而实际上填充的长度为 和 位之间（Java 中使用 字节块的方式序列化）
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.
论文中描述了两种简单的攻击方式，说明 Telegram 使用的对称加密方案在选择密文攻击以及认证加密下无法实现理想中的安全性。第一种攻击可以通过兼容性的补丁来减轻危害，但第二种则需要修改协议细节。
同时，MTProto 似乎并没有相对于其他更常用的认证加密方案的额外优点，如 AES-CTR（可以更好地并行化）、HMAC