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)
本篇论文的两位作者作者来自丹麦的奥胡斯大学

论文PDF

前置知识

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

选择密文攻击下的不可区分性1(Indistinguishability under chosen-ciphertext attack, IND-CCA)

选择密文攻击指攻击者可以掌握解密器(可以将任意的密文转换为明文)

而不可区分性等价于语义安全,攻击者无法获取明文内容。攻击者除去窃听外,其他什么都不能做,也不能进行提问。

假设安全系统(算法)的拥有者是挑战者,与其相对的是攻击者。

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

攻击者正确得到 bb 的值的概率为 1/2+ϵ1/2 + \epsilon,如果 ϵ\epsilon 小到足够忽略,则说明算法安全

上述的称为非自适应选择密文攻击,通常称为 IND-CCA1

非自适应选择密文攻击

非自适应选择密文攻击

如果攻击者在获取明文后还可以选择调用加密器和解密器辅助分析和判断(不能直接调用解密器解密密文),则称为自适应选择密文攻击
在下图中,体现为攻击者可以在

自适应选择密文攻击

自适应选择密文攻击

摘要

原文

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.

在 2015 年,该团队对 Telegram 开源的 Android 源码进行了审计,在本论文中总结了发现。发现的主要问题在于 MTProto 并不具备选择密文攻击不可区分性。尽管目前并没有利用该方式的攻击手段,但存在更优方案的同时,没有使用不安全加密方案的理由。

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. 明文完整性检查

下面则是 MTProto 的更多描述

2.1 MTProto 加密

原文

2.1 MTProto Encryption

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

Payload: The payload x=(aux,rnd,msg,pad)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 xmodB=0|x| \mod B = 0, where BB is the block length; For technical reasons this is never more than 9696 bits (and not 120120 bits as described by the official documentation).

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

Short-Term Key Derivation: MTProto employs a hash function KDF:{0,1}λ+h{0,1}κ+2BKDF: \{0, 1\}^{\lambda+h} \rightarrow \{0, 1\}^{\kappa+2B} for key derivation purposes. This is used to compute (k,x0,y0)=KDF(K,tag)(k, x_0, y_0) = KDF(K, tag) of length (κ,B,B)(\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 KK.

IGE Encryption: MTProto employs an efficiently invertible pseudo-random permutation (PRP) F,F1:{0,1}κ×{0,1}B{0,1}B F,F^{-1}: \{0,1\}^\kappa \times \{0,1\}^B \rightarrow \{0,1\}^B to implement the IGE mode of operation. Let x1,,xlx1, \cdots , x_l be the ll blocks of the payload, each of length BB, then IGE computes yi=Fk(xiyi1)xi1y_i=F_k(x_i \oplus y_{i-1}) \oplus x_{i-1} (where x0x_0, y0y_0 are defined in the previous step). In MTProto F=AESF=AES with κ=256\kappa=256 bit and B=128B=128 bits;

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

长期密钥
发送方和接收方共享的长度为 λ\lambda 的长期密钥 KK(在 MTProto 中,λ=2048\lambda = 2048 位,并且在 Zp\mathbb{Z}_p^*(ppp1/2p-1/2 是素数) 的乘法子祖上 Diffie-Hellman 密钥交换)
负载
负载 x=(aux,rnd,msg,pad)x=(aux,rnd,msg,pad) 包含以下内容
  • 辅助信息 auxaux
  • 随机盐 rndrnd (在 MTProto 中长度为 128128 位)
  • 消息 msgmsg
  • 任意填充值 padpad 比如 xmodB=0|x| \mod B = 0,其中 BB 是分组长度(技术问题,该值不超过 9696 位,而不是官方文档中的 120120 位)
身份验证标签
MTProto 中使用一个用于身份验证的特殊的哈希函数
Tag:{0,1}{0,1}hTag: \{0,1\}^* \rightarrow \{0,1\}^h
该函数采用如下公式计算 tag=Tag(aux,rnd,msg)tag=Tag(aux,rnd,msg)
在 MTProto 中,Tag 使用 SHA-1 哈希,同时 h=128h=128 比特
短期密钥
MTProto 中使用一个用于生成密钥的特殊的哈希函数
KDF:{0,1}λ+h{0,1}κ+2BKDF: \{0,1\}^{\lambda+h} \rightarrow \{0,1\}^{\kappa+2B}
该函数采用如下公式计算 (k,x0,y0)=KDF(K,tag)(k,x_0,y_0)=KDF(K,tag)
: 在 MTProto 中,KDF 是 44 次 SHA-1 调用输出,而 44 次 SHA-1 的输入则是 tagtag 和长期密钥 KK
无限混淆拓展
MTProto 采用了一种有效的可逆伪随机置换(PRP)来实现 IGE 模式。
F,F1:{0,1}κ×{0,1}B{0,1}BF,F^{-1}: \{0,1\}^\kappa \times \{0,1\}^B \rightarrow \{0,1\}^B
假设 x1,,xlx_1,\cdots,x_lll 个分组的负载,每一个负载的长度都是 BB
IGE 使用 yi=Fk(xiyi1)xi1y_i = F_k(x_i \oplus y_{i-1}) \oplus x_{i-1} 计算,其中 x0x_0y0y_0 由上一步计算出
在 MTProto 中,F=AESF=AESκ=256\kappa=256 并且 B=128B=128
密文结果
MTProto 的输出为 c=(tag,y1,,yl)c=(tag,y_1,\cdots,y_l)

2.2 MTProto 解密

原文

2.2 MTProto Decryption

Input Parsing: The ciphertext cc is parsed as c=(tag,y1,,yl)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)(k, x0, y0) = KDF(K, tag)

IGE Decryption: The payload is recovered by computing: xi=yi1Fk1(yixi1)x_i = y_{i−1} \oplus F^{−1}_k (y_i \oplus x_{i−1}) and (x1,,xl)(x1, \cdots , x_l) is parsed as (aux,rnd,msg,pad)(aux, rnd, msg, pad). The padding padpad 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=?Tag(aux,rnd,msg)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.

输入解析
密文需要被解析成 c=(tag,y1,,yl)c=(tag, y_1, \cdots, y_l)
短期密钥重计算
短期密钥以及初始化分组需要重新计算 (k,x0,y0)=KDF(K,tag)(k, x_0, y_0) = KDF(K,tag)
无限混淆拓展解密
使用如下计算恢复负载 xi=yi1Fk1(yixi1)x_i = y_{i-1} \oplus F^{-1}_k (y_i \oplus x_{i-1}) 以及 (x1,,xl)(x_1, \cdots, x_l) 被解析成 (aux,rnd,msg,pad)(aux, rnd, msg, pad)。填充值 padpad 是从辅助数据中读取,并从中删除部分长度。
标签验证
检查标签是否满足 tag=?Tag(aux,rnd,msg)tag \overset{?}{=} Tag(aux, rnd, msg)

如果 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 攻击方式1:填充长度拓展

原文

3.1 Attack #1: Padding-Length Extension

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

Mitigation. This attack can be mitigated simply by checking the length of padpad' 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

给定一个加密后的负载 x=(aux,rnd,msg,pad)x = (aux, rnd, msg, pad) 的密文 c=(tag,y1,,yl)c = (tag, y1, \cdots, y_l)。攻击者从其中任意选择一个分组 r{0,1}Br \leftarrow \{0, 1\}^B 以及输出 c=(tag,y1,,yl,r)c' = (tag, y1, \cdots, y_l, r)
解密过程中,得到的有效负载是 x=(aux,rnd,msg,pad)x' = (aux, rnd, msg, pad'),其中 pad=(pad,pad)pad' = (pad, pad^∗)padpad^∗ 随机获得, pad|pad'| 的长度大于分组长度 BB
但由于解密过程中不会检查 padpad' 的长度,并且 padpad' 不是身份验证函数 TagTag, 这样可以确保解密的正确

应对方案
在解密期间检查 padpad' 的长度,可以有效缓解该问题。如果该长度大于分组长度大小,则解密中止。由于正常客户端产生的密文都是合法的,因此不会影响旧版本的协议。

3.2 攻击方式2:末分组替换

原文

3.2 Attack #2: Last Block Substitution

Given a ciphertext c=(tag,y1,,yl)c = (tag, y_1, \cdots , y_l) which encrypts a payload x=(aux,rnd,msg,pad)x = (aux, rnd, msg, pad) the attacker picks a random block r{0,1}Br \leftarrow \{0, 1\}^B and outputs c=(tag,y1,,yl1,r)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)x' = (aux, rnd, msg', pad')

Let P=padP = |pad| be the length of the original pad, then it holds that the last BPB − P bits of msgmsg' are randomly distributed (due to the use of the PRP in the IGE decryption). Hence we have msg=msgmsg' = msg with probability 2PB2^{P−B}, and in this case the verification of the authentication tag succeeds and the decryption outputs msgmsg. According to the official description of MTProto the padding length is between 00 and 120120 bits, which means that in the best case scenario the above attack succeeds with probability 282^{−8}. However experimental validation shows that this is not the case and the length of the padding is in fact between 00 and 9696 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 2322^{−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.

和上一个攻击类似,假设 P=padP = |pad|padpad 的长度,则 msgmsg' 的最后一个 BPB-P 位是随机分布的,因此有 2PB2^{P-B} 的概率获得 msg=msgmsg' = msg,也即验证标签成功,解密出 msgmsg。根据 MTProto 的官方描述,填充长度在 00120120 之间。也即在最好的情况下,攻击成功率为 282^{-8}。而实际上填充的长度为 009696 位之间(Java 中使用 44 字节块的方式序列化)
因此可以得出结论,该攻击方式概率为 2322^{-32},虽然其概率相对很高,已经无法满足安全性的定义,但其很难实现。

应对方案
可以通过在身份验证标签中增加填充值,来减轻该攻击。但这将会修改加密过程,无法向上兼容。

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.

论文中描述了两种简单的攻击方式,说明 Telegram 使用的对称加密方案在选择密文攻击以及认证加密下无法实现理想中的安全性。第一种攻击可以通过兼容性的补丁来减轻危害,但第二种则需要修改协议细节。
同时,MTProto 似乎并没有相对于其他更常用的认证加密方案的额外优点,如 AES-CTR(可以更好地并行化)、HMAC

参考资料


  1. 什么是公钥密码学的IND-CCA安全定义? ↩︎