author: 路边的阿不 title: 「译」iMessage采用PQ3量子密码技术实现消息传递 slug: imessage-pq3 description: "Translation of 'iMessage with PQ3: The new state of the art in quantum-secure messaging at scale'" date: 2024-03-11 09:42:43 draft: false ShowToc: true TocOpen: true tags:
今天，我们宣布推出 PQ3，这是 iMessage 历史上最重要的加密安全升级。PQ3 是一种突破性的后量子密码协议，它将使 iMessage 的端到端安全消息传递更上一层楼。得益于抗泄密加密和针对即使是极其复杂的量子攻击的强大防御能力，PQ3 是首个达到我们称为 “3级安全” 的消息传递协议 - 提供的协议保护措施超越了所有其他广泛部署的消息应用。据我们所知，PQ3 拥有当今规模最大的消息传递协议中最强的安全性属性。
当 iMessage 在 2011 年推出时，它是首个默认提供端到端加密的广泛可用消息应用，并且多年来我们对其加密技术进行了重大升级。最近一次是在 2019 年，我们将 iMessage 的加密协议从 RSA 升级到椭圆曲线密码 (ECC)，并通过 Secure Enclave 保护设备上的加密密钥，使即使是最复杂的攻击者也更难从设备中提取密钥。该协议更新通过额外的防御措施更进一步：周期性的重新生成密钥机制，即使在密钥被泄露的极端情况下，也能提供加密自我修复功能。这些改进中的每一个都通过符号评估进行了正式验证，这是提供密码协议安全性的最佳实践方法。
历史上，消息平台一直使用经典公钥密码术，例如 RSA、椭圆曲线签名和 Diffie-Hellman 密钥交换，来建立设备之间的安全端到端加密连接。所有这些算法都基于困难的数学问题，这些问题长期以来被认为计算量太大，即使考虑到摩尔定律，计算机也无法解决。然而，量子计算的兴起可能会改变这一局面。足够强大的量子计算机可以以根本不同的方式解决这些经典数学问题，因此“理论上”可以足够快地威胁到端到端加密通信的安全性。
尽管具有这种能力的量子计算机尚未问世，但拥有巨额资源的攻击者已经可以利用现代数据存储成本的大幅下降来为其可能到来的出现做准备。前提很简单：此类攻击者可以收集大量当今的加密数据并将它们全部归档以供将来参考。即使他们今天无法解密任何这些数据，他们也可以保留它们，直到他们获得能够在未来解密它们的量子计算机为止，这种攻击场景称为“现在收集，以后解密”。
为了减轻来自未来量子计算机的风险，密码学界一直在研究后量子密码 (PQC)：提供构建量子安全协议的基础块的新型公钥算法，但不需要量子计算机运行，也就是说，这些协议可以在我们今天所有人都在使用的经典非量子计算机上运行，但仍能安全地抵御未来量子计算机带来的已知威胁。
理解各种消息应用如何应对攻击的原理，我们可以将他们按照安全性质放置在一个谱系中。对此没有标准的对比方法，所以我们在这篇文章的顶部图片中描述了自己简单的、粗粒度的消息安全度的阶段性进程：我们从左边的经典密码学开始，然后逐渐发展到解决量子计算机现有和未来威胁的量子安全。大多数现有的消息应用或者位于0级——即默认情况下没有端到端加密和量子安全，或者位于1级——默认情况下有端到端加密，但没有量子安全。几个月前，Signal加入了对PQXDH协议的支持，它成为首个在初始密钥建立中引进后量子安全的大规模消息应用。这是一个我们所欢迎的、关键的步骤，按照我们的标准，将Signal的安全等级从1级提升到了2级。
在 2 级，后量子密码术的应用仅限于初始密钥的建立，仅在会话密钥材料从未泄露的情况下才能提供量子安全性。但是，当今复杂的对手已经有了破坏加密密钥的动机，因为这样做使他们能够解密那些在密钥未更改期间由这些密钥保护的信息。为了最大限度地保护端到端加密消息传递，后量子密钥需要不断改变，以便为任何一个单一时间点上的密钥泄露所带来的信息泄露设定一个上限--无论是现在还是未来的量子计算机。因此，我们认为消息传递协议安全级别应该更进一步达到 3 级，除了保护初始密钥建立和正在进行的消息交换，还能够在密钥泄露后快速自动地恢复对话的加密安全性。
iMessage 现在通过我们称之为 PQ3 的新加密协议实现了这一目标，提供针对量子攻击的最强保护，并成为唯一达到 3 级安全的广泛可用消息服务。对 PQ3 的支持将从 iOS 17.4、iPadOS 17.4、macOS 14.4 和 watchOS 10.4 的公共版本开始推出，并且已经包含在相应的开发者预览版和测试版中。支持 PQ3 的设备之间的 iMessage对话会自动升级到后量子加密协议。随着我们在全球范围内大规模使用 iMessage 积累的运营经验，它将在今年内完全取代所有支持的对话中的现有协议。
不仅仅是简单地用一种新算法替换现有算法，我们从头开始重建了 iMessage 加密协议，以推进端到端加密的最新技术，并满足以下要求：
PQ3 在每个设备本地生成并传输到 Apple 服务器作为 iMessage 注册的一部分的公共密钥集中引入了一个新的后量子加密密钥。对于此应用程序，我们选择使用 Kyber 后量子公共密钥，该算法受到了全球密码学界的密切关注，并被 NIST 选为“模块化晶格基密钥封装机制标准”或 ML-KEM。这使发送设备即使接收方不在线也能获取接收方的公共密钥并生成用于第一条消息的后量子加密密钥。我们将其称为初始密钥建立。
然后，我们在对话中包含一个周期性的后量子重新密钥机制，该机制能够自我修复密钥泄露并保护未来消息。在 PQ3 中，与对话一起发送的新密钥用于创建新的消息加密密钥，这些密钥无法从过去的密钥计算出来，从而使对话即使以前的密钥被提取或泄露也能恢复到安全状态。PQ3 是首个引入这种新型后量子重新密钥属性的大规模加密消息传递协议。
PQ3 采用混合设计，将椭圆曲线密码术和后量子加密结合用于初始密钥建立和重新密钥过程中。因此，新的密码术纯粹是附加的，要攻破 PQ3 的安全性需要同时攻破现有的经典 ECC 密码术和新的后量子原语。这也意味着该协议可以从我们部署 ECC 协议及其实现中积累的所有经验中受益。
PQ3 中的重新密钥涉及在设备交换的加密消息中与之一起传输新鲜的公共密钥材料。基于椭圆曲线 Diffie-Hellman (ECDH) 的新公共密钥会与每个回复一起内联传输。PQ3 使用的后量子密钥比现有协议的线路尺寸大得多，因此为了满足我们的消息大小要求，我们设计了定期而不是每条消息都进行量子安全重新密钥。为了确定是否传输新的后量子密钥，PQ3 使用了一个重新密钥条件，该条件旨在平衡线路上传输的消息的平均大小，保持用户在连接有限情况下的体验，并将全局消息量保持在我们的服务器基础设施容量之内。如果需要，未来的软件更新可以提高重新密钥频率，同时向所有支持 PQ3 的设备保持向后兼容性。
使用 PQ3，iMessage 继续依赖经典加密算法来验证发送者身份和验证联系人密钥验证帐户密钥，因为这些机制无法在未来使用量子计算机进行追溯攻击。为了尝试将自己插入 iMessage 对话的中间，攻击者需要一台能够在通信发生之前或同时破坏身份验证密钥之一的量子计算机。换句话说，这些攻击无法在 “现在收集，以后解密” 的场景中执行 - 它们需要能够与被攻击的通信同时进行攻击的量子计算机。我们相信任何这样的能力都还需要很多年，但随着量子计算机威胁的演变，我们将继续评估对后量子身份验证的需求，以挫败此类攻击。
我们对 iMessage PQ3 的最后一个要求是正式验证 - 数学上证明协议预期安全属性的证明。PQ3 受到 Apple 内部安全工程和架构 (SEAR) 团队以及一些世界上最杰出的密码学专家的广泛审查。这包括由苏黎世联邦理工学院信息安全小组组长 David Basin 教授领导的团队，以及用于评估 PQ3 的领先安全协议验证工具之一 Tamarin的发明者之一，以及来自滑铁卢大学的 Douglas Stebila 教授，他一直在研究互联网协议的后量子安全性。每个团队都采用了一种不同但互补的方法，使用不同的数学模型来证明只要底层加密算法保持安全，PQ3 也一样安全。最后，一家领先的第三方安全咨询公司又对我们内部的实施评审进行了补充，对PQ3源代码进行了独立评估，并且没有发现安全问题。
在第一次数学分析中，关于iMessage PQ3协议的安全分析，Douglas Stebila教授专注于所谓的基于游戏的证明。这种方法，也被称为简化，定义了一系列的“游戏”或逻辑声明，以显示协议至少与其基础算法同样强大。Stebila的分析显示，即使在经历对经典和量子对手的一些关键性妥协的情况下，PQ3在协议的初始密钥建立和进行的密钥再生阶段也提供保密性。该分析将众多的密钥派生层次降解至消息密钥，并证明这些对攻击者来说，就如同随机噪音一样不可辨识。Stebila在证明中考虑了经典和量子攻击者的不同攻击路径，并广泛地展示了只要椭圆曲线Diffie-Hellman问题仍然困难，或者Kyber后量子KEM仍然安全，那么PQ3使用的密钥就安全。
iMessage PQ3协议是一个设计良好的加密协议，用于安全消息传递，使用最新的技术进行端到端加密通信。在我使用简化安全方法的分析中，我确认了PQ3协议提供后量子保密性，这可以让用户即使在可能的量子计算技术改进面前，也对他们通信的隐私有信心。 ——Douglas Stebila教授
在第二次评估中，关于iMessage PQ3消息协议的正式分析，苏黎世联邦理工学院的David Basin教授、Felix Linker 和Ralf Sasse博士采用了一种叫作符号评估的方法。就像文章的摘要突出显示的那样，这次分析包括了iMessage PQ3协议的详细形式模型，其精密的安全性质的精确定义，以及使用最新的符号Tamarin证明器的机器检查的证据。评估得出了PQ3秘密性质的精细分析，证明了“在发送者或接收者没有被妥协的情况下，传输的所有密钥和信息都是秘密的”并且证明了“妥协可以在一个明确定义的意义上被容忍，其中妥协对数据秘密性的影响在时间和效果上有限”。这就证实了PQ3满足了我们的目标。
我们提供了PQ3的数学模型，并使用机器检查安全证明的验证工具证明了其秘密性和真实性。即使是在能够使参与方堕落或拥有量子计算机并因此击败经典密码学的非常强大的对手存在的情况下，协议也能保持其特性。PQ3在对后量子防御上超越了Signal。在PQ3中，一个后量子安全算法是搬运的一部分，并反复使用，而不仅仅是在Signal 的初始化中使用一次。我们的验证提供了非常高的保证，即设计的协议即使在后量子世界中也能安全运行。 ——David Basin教授
因为我们知道PQ3将在安全研究员和工程师以及密码学社区中引起极大的关注，所以这篇博客文章实际上是两篇文章合成的。到现在为止，我们已经阐述了我们的设计目标，描绘了PQ3如何达到这些目标，并且解释了我们如何通过独立评估来验证我们对协议的信心。如果你希望了解更多关于密码学基础的细节，那么接下来的文章将会是我们如何构建PQ3协议的更深层次的探讨。
iMessage允许用户在同一个账户上注册多个设备。每个设备会生成自己的一套加密密钥，而私钥从不会导出到任何外部系统。与此关联的公钥被注册在Apple的身份目录服务(Identity Directory Service, IDS)中，以便用户能够通过简单的标识符（电子邮件地址或电话号码）向彼此发送消息。当用户从其中一个设备发送消息时，他们的所有其他设备和接收者的所有设备都会收到该消息。消息是通过在发送设备和每个接收设备之间建立的一对一的会话进行交换的。同一条消息会依次被加密给每个接收设备，每个会话都会独立生成密钥。在此描述的剩余部分，我们将专注于单个设备对设备的会话。
因为在对话建立时，接收设备可能不在线，所以一个会话中的第一个消息是使用在IDS服务器上注册的公开加密密钥进行加密的。
每个设备在PQ3中都会注册两个公开加密密钥，并定期用全新的密钥替换它们：
这些加密密钥使用由设备的Secure Enclave生成的P-256认证密钥进行ECDSA签名，以及一个用于限制其有效期的时间戳。设备认证公开密钥本身则由联系人密钥验证帐户密钥签名，以及一些属性，如支持的密码协议版本。这个流程允许发送者验证接收者设备的公开加密密钥是由预期的接收者上传的，并且抵御降级攻击。
当爱丽丝的设备与鲍勃的设备初始化一个新的会话时，她的设备就会向IDS服务器查询与鲍勃设备相关联的密钥包。密钥包中包含设备认证密钥和版本信息的子集通过联系人密钥验证进行验证。然后，设备验证覆盖加密密钥和时间戳的签名，证明密钥是有效的且没有过期。
然后，爱丽丝的设备就可以使用两个公开加密密钥向鲍勃分享两个对称密钥。第一个对称密钥是通过一个ECDH密钥交换计算出来的，它结合了爱丽丝的一个临时加密密钥和鲍勃注册的P-256公开密钥。第二个对称密钥是通过与鲍勃的后量子公开密钥进行Kyber密钥封装得到的。
为了合并这两个对称密钥，我们首先通过调用HKDF-SHA384-Extract两次（每个密钥一次）来提取其熵。得到的48字节秘密进一步与领域分离字符串和会话信息（包括用户的标识符、用于密钥交换的公开密钥和封装的秘密）结合，再次调用HKDF-SHA384-Extract派生会话的初始密钥状态。这个组合确保了如果不知道两个共享秘密，就无法推导出初始会话状态。这意味着攻击者需要破解两种算法才能恢复结果秘密，从而满足我们的混合安全需求。
持续的加密会话的密钥更新设计旨在即使强大的假想攻击者能够在某个特定时间点提取设备的加密状态，也无法重新计算用于加密过去和未来消息的密钥。该协议为每一条消息生成一个新的唯一密钥，这个密钥周期性地包含来自当前对话状态的新的熵，从而有效地为协议提供自愈能力。我们的密钥更新方法是基于采用了从其他密钥中衍生出新的会话密钥并确保加密状态只能向一个方向前进的技术即滑动窗口技术。PQ3合并了三个滑动窗口以实现后量子加密。
第一个滑动窗口，称为对称滑动窗口，通过保护对话中的旧消息来实现前向安全性。对于每一条消息，我们都会从当前会话密钥派生一个用于每条消息的加密密钥。之后，当前的会话密钥进一步衍生出一个新的会话密钥，推动状态向前滑动。每个消息密钥在相应消息解密后立即被删除，这可以防止对手在以后某个时间攻破设备时解密先前收集到的密文，并防止重放消息攻击。这个过程使用256位的密钥和中间值，以及HKDF-SHA384作为一个衍生函数，这为对抗经典和量子计算机提供了保护。
第二个滑动窗口，称为ECDH滑动窗口，通过使用来自椭圆曲线密钥协议的新熵更新会话，保护未来的消息，即使对手攻破了过去的会话密钥，他们也无法解密新消息（称为后妥协安全性）。基于ECDH的滑动窗口有一个对称的流程：使用发送者的外发滑动窗口公钥的私钥和从接收者那里收到的最后一个公钥来在发送者和接收者之间建立一个新的共享秘密，然后将这个秘密混入会话的密钥材料中。iMessage的新PQ3协议使用NIST P-256椭圆曲线密钥执行这个滑动窗口，这只会对每个消息增加32字节的开销。
因为第二个滑动窗口使用经典密码学，所以PQ3也加入了一个有条件执行的基于Kyber KEM的滑动窗口。这第三个滑动窗口补充了基于ECDH的滑动窗口，也提供了抵抗“现在收集，以后解密”量子攻击的后妥协安全。
使用后量子滑动窗口与同一安全级别的基于ECDH的滑动窗口相比，会造成显著的网络开销。后量子KEM需要发送公钥和封装的密钥，而不仅仅是发送一个外出公钥。此外，对于公钥和封装密钥的参数，量子安全的基础数学结构需要相比椭圆曲线显著更大的参数大小。
为了在保持高安全性的同时限制频繁再密钥化带来的大小开销，后量子KEM采用了Kyber-768协议。与用于初始密钥建立的IDS注册公钥不同，滑动窗口公钥一次只用于封装一个共享密钥给接收者，显著地限制了单一密钥的泄露的影响。然而，虽然在每个消息上增加32字节的基于ECDH的滑动窗口的开销是可以接受的，但是后量子KEM滑动窗口将消息大小增加了2千字节以上。为了避免当设备连接有限时消息传送出现可见的延迟，这个滑动窗口需要在多个消息上分摊。
因此，我们实施了一个适应性的后量子密钥更新标准，该标准考虑到了正在发送的消息数量、上次再密钥化以来的时间，以及当前的连接情况。在启动时，这意味着大约每50条消息将执行一次后量子滑动窗口。但是，该条件有一定的限制，即至少每7天确保执行一次密钥更新。就像我们之前提到的，随着量子计算机的威胁和基础设施容量随着时间的推移发展，在保持完全向后兼容的同时，未来的软件更新可以增加密钥更新的频率。
完成基于ECDH或Kyber的公钥滑动窗口需要发送和接收一条消息。虽然用户可能不会立即回复一条消息，但iMessage包含了加密的交付回执，方便设备即使没有接收者的回复也能快速完成滑动窗口，只要设备在线。这种技术避免了在密钥更新过程中的延迟，并有助于支持泄漏后的有力恢复。
与初始会话密钥建立相似，通过三个滑动窗口建立的密钥都与通过HKDF-SHA384和连续调用抽取函数的一个演变中的会话密钥组合。在这个过程的末尾，我们得到一个最后的消息密钥，现在它可以用来加密载荷。
为了避免泄露消息大小的信息，PQ3 在加密之前向消息添加填充。此填充使用 Padmé 启发式方法实现，该方法专门将具有最大长度 M 的密文的泄露信息限制为 O(log log M) 位的实用最佳值。这与填充到 2 的幂次方相当，但产生的开销更低，最大为 12%，对于更大的有效载荷则更低。这种方法在隐私和效率之间取得了绝佳的平衡，并且在设备连接受限的情况下保持了用户体验。
使用256位的加密密钥和初始化向量的AES-CTR将填充后的有效负载进行加密，这两者都来自消息密钥。虽然公钥算法需要根本性的变化才能实现量子安全，但是像AES块密码这样的对称密码学算法只需要加倍密钥大小就能保持他们对量子计算机的安全级别。
每个消息都使用保护在Secure Enclave中的椭圆曲线P-256设备认证密钥进行ECDSA签名。接收设备验证发送者的标识符（电子邮件地址或电话号码）和用于签名验证的公钥之间的映射。如果双方用户都启用了联系人密钥验证并验证了彼此的帐户密钥，设备会验证设备认证密钥是否存在于密钥透明度日志中，以及相应的帐户密钥是否与存储在用户的iCloud钥匙链中的帐户密钥匹配。
设备的认证密钥是由Secure Enclave生成的，永远不会暴露给设备的其他部分，这有助于防止即使应用处理器完全被妥协，也能防止私钥的提取。如果攻击者成功攻破应用处理器，他们可能能够使用Secure Enclave来签名任意消息。但在设备通过重启或软件更新从被攻破的状态中恢复后，他们将无法再冒充用户。这种方法提供的保证比其他消息协议更强，而其他消息协议中的认证密钥有时在设备之间共享，或者认证只在会话开始时进行。
消息签名涵盖了广泛的字段，包括用户的唯一标识符和他们的推送通知令牌、加密的有效负载、经过认证的数据、将签名绑定到滑动窗口中的唯一位置的滑动窗口衍生的消息密钥指示器，以及在协议中使用的任何公钥信息。将这些字段包含在签名中保证了消息只能在发送者预期的环境中使用，所有的字段都在Stebila、Basin和他们的合作者的研究论文中详尽地进行了文档记录。
近年来，端到端加密消息在创新方面取得了巨大的进步，包括Signal的PQXDH协议在后量子密码学方面的重大进步，以及WhatsApp的可审计密钥目录在密钥透明度方面的进步。
作为首个默认提供端到端加密的广泛可用消息应用的先驱，iMessage 始终致力于提供超越现有系统的先进保护措施。iMessage 联系人密钥验证是目前大规模部署的消息应用中最复杂的密钥透明度系统，也是目前自动密钥验证的全球顶尖技术。新的 iMessage PQ3 加密协议将后量子初始密钥建立与三个用于抵御密钥泄露的自修复棘轮结合起来，定义了保护消息免受 “现在收集，以后解密” 攻击和未来量子计算机攻击的全球顶尖技术。