The Anonymous End to End Encryption Group Messaging Protocol Based on Asynchronous Ratchet Tree

摘要

即时通讯在人们生活中起着重要的作用，2018年中国即时通讯用户已达7.9172亿[8]，比2017年的7.2023亿增长9.9％。与2016年的6.6623亿人相比，2017年的IM用户人口增长了8.1％[7]。研究表明，我国即时通讯用户数量的增长趋势将保持稳定。CNNIC的报告[7，8]指出，2018年人们每周上网时间为27.6小时，其中15.6％用于即时通讯。中国最流行的即时通讯应用是微信，其次是QQ。全球最流行的即时通讯应用WhatsApp自2017年以来每月拥有超过12亿活跃用户[1]。这些应用程序每天会产生数万亿的数据，而且大部分数据都涉及用户的私人信息。　　为了保护用户隐私，端到端加密(E2EE)在IM应用中得到了广泛的应用。E2EE的特点是:消息主机或任何第三方由于使用了加密技术而无法泄露消息内容。为了在密钥泄漏时保护安全，需要保证前向安全性[18]和后向安全性[10]。前向安全是为了确保当前密钥泄漏时，敌方不能获取过去秘密消息的密钥。后向安全要确保在多次交互之后，在前密钥泄漏后，通信通道将重新达到安全状态。当密钥未被泄露时，需要认证加密[3]来保护当前的内容安全。认证加密的攻击者可以对目标密码体系采取选择明文攻击和密文完整性攻击。在安全认证加密的体系下，攻击者即使拥有选择明文攻击的能力，也不能破译语义安全，并且无法创造在不知道密钥的情况下创造合法的密文。群消息是即时通讯的一个重要组成部分。许多应用程序都设计了它们的协议。由于通信信道应该保持密钥的异步性，因此很难设计同步的群密钥交换。为了解决这种情况，许多实现者采用了这种策略:用户应该逐个向所有群成员发送密码文本或者密钥，这就是所谓的“发送密钥”策略。此策略无法保证后向安全，因为会话密钥不是由所有群成员决定的。后向安全只能通过点到点的[9]和有状态的[10]协议来实现。Cohn-Gordon等人设计了一个异步棘轮树协议。异步棘轮树是一个多级协议，可以异步进行群密钥交换。这些特性可以在即时通讯中提供近乎完美的安全性，但仍有机会在通讯中泄露用户身份。由于工程漏洞，手机即使应用E2EE也很容易被黑客攻击。2019年，黑客通过WhatsApp的语音通话入侵用户手机。WhatsApp的母公司Facebook起诉称，这次攻击是以色列NSO所为[23]。在E2EE的保护下，由于黑客攻击和密钥泄露，用户身份仍会受到威胁。但目前群消息协议并没有在保证前后向安全的前提下实现匿名性保护。因此，本文设计了一个能够提供匿名特性的协议，保证群内部匿名性和群外部匿名性，同时还具有前后向安全。群外部匿名:攻击者无法区分不同群的两个通信通道。因此，在群外部匿名中，非群成员不能判断用户来自哪个群。当密钥泄露时，群外部匿名可能不安全，因此需要实现群内部匿名。群内部匿名指:一个群成员不能区分消息是来自除他自己以外的哪个群成员。当密钥泄露时，外部攻击者可以被视为群成员。也就是说:当密钥泄露时，群内部匿名是必需的。　　本文给出了认证加密安全，前向安全，后向安全，群内部匿名，群外部匿名的安全性定义。　　认证加密安全游戏的定义是:攻击者可以随机选取任意明文，并询问其密文。之后，攻击者构造随机选取两个等长的新明文，和一个构造的新密文，并把三者发给挑战者，挑战者随机选取其中一个明文加密并发给攻击者。挑战者需要确认攻击者的新密文是否是合法的，攻击者需要猜测挑战者加密的是哪个明文。如果新密文被认为是合法的，或者攻击者猜中被加密的明文，攻击者赢得这个游戏。如果一个加密模式是认证加密安全的，那么攻击者赢得游戏的概率应该是可以忽略的。　　前向安全性游戏的定义:挑战者生成公私钥对，并把公钥发给攻击者。攻击者可以进行Q轮明文询问。在一轮询问中，攻击者随机选两个等长且不相同的明文发给挑战者，挑战者随机选一个明文加密并返还密文。进行Q次后，挑战者把密钥发给攻击者。攻击者需要猜测前Q次的密文分别是哪些明文的加密结果。如果攻击者猜对Q次中的一次，则其赢得游戏。如果一个加密模式是前向安全的，那么攻击者赢得游戏的概率应该是可以忽略的。该安全性定义描述了攻击者在获取当前加密密钥后，能否以前的密文中获得至少一比特的明文信息。　　后向安全游戏的定义:挑战者生成公私钥对，并把公私钥发给攻击者。攻击者进行最多Q次明文询问。然后在下一个询问中随机选择两个等长且不相同的明文发给挑战者。挑战者选择随机选择一个明文并加密，密文返还给攻击者。攻击者猜测对应的明文，猜对则赢得游戏。如果一个加密模式是后向安全的，那么攻击者赢得游戏的概率应该是可以忽略的。该安全性定义描述了攻击者在获取当前加密密钥后，能否从未来的密文中获得至少一比特的明文信息。　　群内部匿名游戏的定义:挑战者生成群公私钥，并把公私钥发给攻击者。攻击者随机选一个明文发给挑战者。挑战者从两个不同的成员中选一个，让他加密这个明文，然后把密文发给攻击者。攻击者需要猜测是哪个群成员加密的密文，猜对则其赢得游戏。如果一个加密模式是群内部匿名的，那么攻击者赢得游戏的概率应该是可以忽略的。该安全性定义描述了攻击者在获取当前加密密钥后，能否从密文中获得至少一比特用户身份信息。　　群外部匿名游戏的定义:挑战者生成两个群公私钥对，并把两个公钥发给攻击者。攻击者随机选一个明文发给挑战者。挑战者随机选一个群密钥去加密明文，并返还密文。攻击者猜测被选中的群是哪个，猜对则赢得游戏。如果一个加密模式是群外部匿名的，那么攻击者赢得游戏的概率应该是可以忽略的。该安全性定义描述了攻击者能否从密文中获得至少一比特群身份信息。　　本文的方案是在椭圆曲线上(ECC)，基于PRF-ODH的决定性迪夫霍尔曼困难问题(DDHP)和计算性迪夫霍尔曼困难问题(CDHP)。假定一个安全的伪随机函数t能将椭圆曲线上的点映射到大素数循环群上，则:　　DDHP的定义为:给定ECC上的两个DH元组(aP，bP，t(abP))和(aP，bP，zP)，z是随机值，P是ECC生成元，攻击者在不知道a和b的情况下将这两个组区分开的概率是可以忽略的。　　CDHP的定义为:给定ECC上的一个元组(aP，bP)，P是ECC生成元，攻击者在不知道a和b的情况下计算出abP的概率是可以忽略的。　　结合上述五个定义，本文将异步棘轮树方案改进为匿名棘轮树。每个棘轮树的叶节点代表一个用户（包括空用户）。每个用户节点的兄弟节点均为空用户，则一个用户节点与空节点构成一个父节点的左右孩子。故而匿名棘轮树叶节点数量是同用户数的异步棘轮树的两倍。每个节点都包含公钥，每个用户都有自己的私钥，但是不知道别人的私钥。在初始阶段，群建立者会通过认证密钥交换与其他群员共同确定该群员的初始私钥。所以一开始，群建立者知道所有的私钥。然后通过DH方法计算出父节点的公私钥对。依此类推至根节点。将根节点的私钥和上一轮会话的链密钥作为密钥生成函数的输入，产生当前会话的会话密钥和链密钥。第一轮的链密钥是空。　　发送方在加密时，会根据会话密钥生成一次性地址addr，用会话密钥加密明文c。然后他可以选择直接或者以匿名的方式更新匿名棘轮树。当直接更新时，发送方记录自己的叶节点的位置为pos，记录叶节点私钥。否则随机选择一个空用户节点标记为pos。然后随机从密钥空间选一个数作为pos叶节点私钥。然后用DH方法更新其父节点直至根节点的公私钥对。最后，以列表的形式从pos叶节点开始依次记录祖先节点的公钥，记为path。用链密钥对pos，path，一次性地址和密文做消息认证码σ。将c，pos，path，σ，addr发送到服务器上。由于链密钥和根私钥为群成员所共享，故而其他群成员也能计算出相同的当前会话的addr。然后从服务器上获得对应一次性地址对应的数据。　　在AART方案中，攻击者仅能获取五元组(c，pos，path，σ，addr)。若攻击者想获取任何关于明文和身份信息，仅能从链密钥和根密钥人手。则可将其规约到解决PRF-ODH上的CDHP和安全消息认证码系统(MAC)。由于攻击者不能攻破CDHP和MAC，他就不能攻破认证加密，其安全性得证。由前向安全的定义可知，攻击者在获得当前会话密钥的情况下，无法获得上上一轮的链密钥，故而解决前向安全性就相当于从Q次明文询问中解决一次认证加密安全。所以，前向安全得证。在AART中，攻击者获取当前会话密钥后，若所有用户（包括空用户）都更新过一个匿名棘轮树，则，在下一轮会话中，攻击者不能获取根密钥，无法解开密文，后向安全性得证。在群内部匿名，由于发送方会随机选择空用户节点来进行更新，其他群成员无法将发送方的身份与更新操作结合起来。由于其他操作所有群成员都能进行，而且当明文一样的时候，密文结果一致。故而内部攻击者无法将用户身份与密文信息相关联，群内部匿名得证。在群外部匿名中，攻击者只攻击一次性地址。由于DDHP，攻击者无法分别将两个不同群的一次性地址和一个随机值区分开来。结合两次DDHP游戏，可证群外部匿名的安全性。AART的五种安全性得证。　　综上，本文通过对流行的端到端即时通讯应用的协议分析，和匿名端到端协议的分析，发现现有端到端群消息协议存在身份泄露的风险，通过对异步棘轮树协议的分析和改进，结合一次性地址，在保证前向安全性，后向安全性的前提下，实现了群内部匿名和群外部匿名的功能，并给出了安全性证明。

目录