双棘轮算法

08 Aug 2017Philip Ye

本文是 Signal 协议中使用的「双棘轮算法」的中文翻译（基于 Revision 1, 2016-11-20),「参考资料」部分保持原文不翻译，英文原文在此。

目录

1. 引言

双棘轮算法用于通信双方基于共享密钥交换加密消息。通常，通信双方将先使用某种密钥协商协议（例如 X3DH1）以协商共享密钥。此后，通信双方即可使用双棘轮算法发送接收加密消息了。

通信双方将为每一个双棘轮消息派生出新的密钥，使得旧的密钥不能从新的密钥计算得到。通信双方还将在消息中附上迪菲-赫尔曼公钥值。迪菲-赫尔曼计算的结果将被混入派生出的密钥中，使得新的密钥不能从旧的密钥计算得到。这些特性将在某一方的密钥泄漏后保护此前或此后的加密消息。

下面描述双棘轮算法及其带头部加密的变种，同时将讨论二者的安全特性。

2. 概述

2.1. KDF 链

KDF 链是双棘轮算法中的核心概念。

我们将 KDF 定义为这样一个密码学函数：输入一个秘密且随机的 KDF 密钥（KDF key） 及其它一些输入数据，并返回输出数据。在密钥未知的前提下，输出的数据与随机数不可区分（也就是说，KDF 满足密码学「PRF」的要求）。若密钥不是秘密且随机的，则 KDF 应仍然能作为密钥和输入数据的安全的密码学哈希。当 HMAC 和 HKDF 使用安全的哈希算法实例化时，二者的构造即满足 KDF 定义23。

我们使用术语 KDF 链表示如下流程：一个 KDF 输出的一部分作为 输出密钥（Output key），而另一部分将取代 KDF 密钥，作为另一个 KDF 的输入密钥。下图展示了一个处理三个输入密钥并生成三个输出密钥的 KDF 链：

一个 KDF 链具有如下特性（使用的术语来自 4）：

  • 弹性（resilience）：对于不知道 KDF 密钥的攻击者来说，输出密钥看起来是随机的。即使攻击者能控制 KDF 的输入，此条特性仍然成立。
  • 前向安全性（forward security）：对于知道某一时刻的 KDF 密钥的攻击者来说，旧的输出密钥看起来是随机的。
  • 被攻破后的可恢复性（break-in recovery）：对于知道某一时刻的 KDF 密钥的攻击者来说，新的输出密钥看起来是随机的，只要新的输入中增加了足够的熵（entropy）。

在 Alice 和 Bob 之间的双棘轮会话中，双方保存的 KDF 密钥将用于三条链：根链（root chain）、发送链（sending chain）及接收链（receiving chain）（Alice 的发送链对应 Bob 的接收链，反之亦然）。

Alice 和 Bob 交换消息的同时，也交换新的迪菲-赫尔曼公钥，而迪菲-赫尔曼输出的密钥将作为根链的输入。根链输出的密钥将作为发送链和接收链的 KDF 密钥。这称为迪菲-赫尔曼棘轮（Diffie-Hellman ratchet）。

每发送和接收一条消息，发送链和接收链都将向前推进。相应的输出密钥将用于加密和解密消息。这称为对称密钥棘轮（symmetric-key ratchet）。

后继几节将更详细地解释对称密钥棘轮和迪菲-赫尔曼棘轮，之后将描述二者如何组合成为双棘轮。

2.2. 对称密钥棘轮

每条发送或接收的消息都使用一个唯一的消息密钥（message key）加密。消息密钥是发送 KDF 链和接收 KDF 链的输出密钥。这些链的 KDF 密钥称为链密钥（chain key）。

由于发送链和接收链的 KDF 输入是常数，所以这两条链不具备被攻破后的可恢复性。发送链和接收链只能确保每条消息使用唯一的密钥加密，而此密钥在加密或解密后可以删除。由一个给定的链密钥计算下一个链密钥和消息密钥的过程，称为对称密钥棘轮（symmetric-key ratchet）的一次棘轮步进（ratchet step）。下图展示了两次步进：

由于消息密钥不用于派生其它密钥，因此可以保存起来而不影响其它消息密钥的安全性。这将有助于处理消息的丢失或乱序（参见第 2.5 节）。

2.3. 迪菲-赫尔曼棘轮

如果中间攻击者窃取了其中一方的发送链密钥和接收链密钥，那么他可以计算此后所有的消息密钥，并解密对应的消息。为了避免这种情况，双棘轮算法将对称密钥棘轮与 DH 棘轮组成在一起，使用后者基于迪菲-赫尔曼的输出更新链密钥。

为了实现 DH 棘轮，通信双方各自生成一个 DH 密钥对（迪菲-赫尔曼公钥和私钥）作为当前的棘轮密钥对（ratchet key pair）。从任意一方发出的每一条消息都将携带一个消息头，其中包含发送者当前的棘轮公钥。当接收到远端发送过来的新的棘轮公钥时，本端将实施一次 DH 棘轮步进（DH ratchet step），生成一个新的棘轮密钥对以取代本端当前的密钥对。

通信双方交替地更新棘轮密钥对，使之形成一个「乒乓」行为模式。仅截获了其中一方的窃听者可能得到当前棘轮私钥的值，但此棘轮私钥将最终被未泄露的棘轮私钥取代。那时，棘轮密钥对之间的迪菲-赫尔曼计算将定义一个对攻击者未知的新的 DH 输出。

以下几张图展示了 DH 棘轮如何派生出一系列共享的 DH 输出。

Alice 使用 Bob 的棘轮公钥初始化，而 Bob 尚未得知 Alice 的棘轮公钥。作为初始化的一部分，Alice 使用她自己的棘轮私钥和 Bob 的棘轮公钥作 DH 运算：

Alice 的初始消息宣告了其棘轮公钥。一旦 Bob 收到其中一条初始消息，Bob 就执行一次 DH 棘轮步进：他使用 Alice 的棘轮公钥和自己的棘轮私钥作 DH 运算，得到的结果应与 Alice 的初始 DH 输出相等。之后 Bob 替换掉自己的棘轮密钥对并重新计算一个新的 DH 输出：

Bob 发送的消息宣告了其新的公钥。最终，Alice 将收到其中一条消息并执行一次 DH 棘轮步进，替换自己的棘轮密钥对并派生出两个 DH 输出，一个与 Bob 的最新 DH 输出相等，另一个为新的 DH 输出：

Alice 发送的消息宣告了其新的公钥。最终，Bob 将收到其中一条消息并执行第二次 DH 棘轮步进，如此反复：

每一次 DH 棘轮步进生成的 DH 输出，用于派生新的发送链密钥和接收链密钥。下图重新展示了 Bob 的第一次棘轮步进。Bob 使用其第一个 DH 输出派生出接收链，与 Alice 的发送链对应。Bob 使用第二个 DH 输出派生新的发送链：

当双方交替执行 DH 棘轮步进的同时，也交替地引入新的发送链：

然而，上图是经过简化的版本。实际上并不是直接将 DH 输出作为链密钥，而是将 DH 输出作为根链的 KDF 输入，而根链的 KDF 输出作为发送链密钥和接收链密钥。此处使用 KDF 链改进了算法的弹性和被攻破后的可恢复性。

所以一次完整的 DH 棘轮步进包括两次根 KDF 链的更新，并将其 KDF 输出分别作为新的接收链密钥和发送链密钥：

2.4. 双棘轮

将对称密钥棘轮和 DH 棘轮组合在一起，形成了双棘轮：

  • 当发送或接收消息时，执行一次发送链或接收链的对称密钥棘轮步进，以派生新的消息密钥。
  • 当接收到新的棘轮公钥时，在对称密钥棘轮步进之前，执行一次 DH 棘轮步进，以更新链密钥。

下图中，Alice 已使用 Bob 的棘轮公钥及作为初始根密钥（ RK ）的共享密钥初始化。作为初始化的一部分，Alice 生成一个新的棘轮密钥对，并将 DH 输出作为根 KDF 的输入，计算出新的根密钥（ RK ）和发送链密钥（ CK ）：

当 Alice 发送第一条消息 A1 时，她对发送链密钥执行一次对称密钥棘轮步进，以生成新的消息密钥（消息密钥以其加密或解密的消息编号标注）。新的链密钥将保存起来，但消息密钥和旧的链密钥可以删除：

假如接下来 Alice 收到 Bob 发送的响应消息 B1 ，其中包含 Bob 的新的棘轮公钥（Bob 的公钥以其所在的首条消息编号标注）。Alice 执行一次 DH 棘轮步进，以派生新的接收链密钥和发送链密钥。之后她对接收链执行一次对称密钥棘轮步进，以获取接收到的消息对应的消息密钥：

假设接下来 Alice 发送了消息 A2 ，接收到包含 Bob 旧的棘轮公钥的消息 B2 ，接着又发送了消息 A3 和 A4 。Alice 的发送链将步进三次，而其接收链仅步进一次：

假设接下来 Alice 接收到包含 Bob 新的棘轮公钥的消息 B3 和 B4 ，并发送了消息 A5 。Alice 的最终状态如下：

2.5. 乱序消息

双棘轮算法处理消息丢失或乱序的方法是：在每个消息头部包含此消息在发送链中的编号（N=0,1,2,…）以及之前的发送链的长度（ PN ，即消息密钥的个数）。这使接收方可以保存被跳过的消息密钥而跳转到对应的消息密钥，而当被跳过的消息到达时可使用保存的消息密钥解密。

当接收到一条消息时，如果触发了 DH 棘轮步进，那么接收到的 PN 减掉当前接收链的长度就是此接收链中被跳过的消息数目。接收到的 N 是新的接收链（即 DH 棘轮步进之后的接收链）中被跳过的消息数目。

如果没有触发 DH 棘轮步进，那么接收到的 N 减掉当前接收链的长度就是此接收链中被跳过的消息数目。

例如，假设上一节的消息序列中，消息 B2 和 B3 被跳过。消息 B4 将触发 Alice 的 DH 棘轮步进（不乱序时本应由 B3 触发）。消息 B4 的 PN=2，N=1。当接收到 B4 时，Alice 的接收链长度为 1（ B1 ），所以 Alice 将 B2 和 B3 的消息密钥保存，以便之后接收到这两个消息时可以对其解密：

3. 双棘轮算法

3.1. 外部函数

为了实例化双棘轮算法，还需要定义以下的函数。推荐的算法请参见第 5.2 节。

  • GENERATE_DH()：返回新的迪菲-赫尔曼密钥对。
  • DH(dh_pair, dh_pub)：返回 DH 密钥对 dh_pair 中的私钥与 DH 公钥 dh_pub 的迪菲-赫尔曼运算结果。如果 DH 函数拒绝无效的公钥，那么此函数可能发生异常并终止处理。
  • KDF_RK(rk, dh_out)：此函数将 32 字节的根密钥 rk 及迪菲-赫尔曼输出 dh_out 作为 KDF 的输入，并返回二元组：新的 32 字节根密钥及 32 字节链密钥。
  • KDF_CK(ck)：此函数将 32 字节链密钥 ck 及某个常量作为 KDF 的输入，并返回二元组：新的 32 字节链密钥及 32 字节消息密钥。
  • ENCRYPT(mk, plaintext, associated_data)：此函数返回使用消息密钥 mk5 对明文 plaintext 做 AEAD 加密的结果。附加数据 associated_data 经过认证但不包含在密文中。由于每个消息密钥只使用一次，因此 AEAD 的 nonce 值可以有多种不同的处理方式：固定为一个常数；使用另外的 AEAD 加密密钥从 mk 派生；从 KDF_CK() 的额外输出中派生；或者随机选择并发送。
  • DECRYPT(mk, ciphertext, associated_data)：此函数返回使用消息密钥 mk 对密文 ciphertext 做 AEAD 解密的结果。如果认证失败，将发生异常并终止处理。
  • HEADER(dh_pair, pn, n)：由密钥对 dh_pair 、之前的链长度 pn 及消息数目 n 生成包含 DH 棘轮公钥的消息头。返回的消息头包含棘轮公钥 dh 及整数 pn 和 n 。
  • CONCAT(ad, header)：将消息头部编码成可解析的字节序列，并在前面附上字节序列 ad 并返回结果。如果不能保证 ad 是可解析的字节序列，将用其长度值取代 ad 本身附加在消息头前面，使得此函数输出的总是可解析且唯一的二元组 (ad, header)。

同时需要定义一个 MAX_SKIP 常量。此常量指定了在同一个链中最多可跳过的消息密钥的个数。此常量的值需要足够大以便允许消息的常规丢失或延迟，但又需要足够小以避免恶意的发送者消耗接收者过多的计算资源。

3.2. 状态变量

通信双方都将跟踪如下的状态变量：

  • DHs：DH 棘轮密钥对（「发送」密钥或「本端」密钥）
  • DHr：DH 棘轮公钥（「接收」密钥或「远端」密钥）
  • RK：32 字节的根密钥
  • CKs, CKr：发送链密钥和接收链密钥，均为 32 字节
  • Ns, Nr：发送链及接收链的消息数目
  • PN：之前的发送链的消息数目
  • MKSKIPPED：已跳过的消息密钥的字典，由棘轮公钥和消息编号索引。若保存了过多的元素则发生异常。

在下文的 Python 代码中，状态变量将作为一个 state 对象的成员被访问。

3.3. 初始化

在初始化之前，双方必须使用某种密钥协商协议以协商出一个 32 字节的共享密钥 SK 及 Bob 的棘轮公钥。这些值将用于生成 Alice 的发送链密钥及 Bob 的根密钥。而 Bob 的（发送及接收）链密钥及 Alice 的接收链密钥暂时留空，将由各自的首次 DH 棘轮步进操作初始化。

（此处假设 Alice 先发送消息，而 Bob 直到接收到 Alice 的某条消息之后才发送消息。为允许 Bob 在初始化后也能立即发送消息，Bob 的发送链密钥及 Alice 的接收链密钥也需要初始化为一个共享密钥。为简单起见，我们不再考虑此场景。）

一旦 Alice 和 Bob 协商好了 SK 及 Bob 的棘轮公钥，Alice 调用 RatchetInitAlice() ，而 Bob 调用 RatchetInitBob() ：

def RatchetInitAlice(state, SK, bob_dh_public_key):
    state.DHs = GENERATE_DH()
    state.DHr = bob_dh_public_key
    state.RK, state.CKs = KDF_RK(SK, DH(state.DHs, state.DHr)) 
    state.CKr = None
    state.Ns = 0
    state.Nr = 0
    state.PN = 0
    state.MKSKIPPED = {}

def RatchetInitBob(state, SK, bob_dh_key_pair):
    state.DHs = bob_dh_key_pair
    state.DHr = None
    state.RK = SK
    state.CKs = None
    state.CKr = None
    state.Ns = 0
    state.Nr = 0
    state.PN = 0
    state.MKSKIPPED = {}

3.4. 加密消息

调用 RatchetEncrypt() 以加密消息。此函数执行一次对称密钥棘轮步进，并使用生成的消息密钥加密消息。除了消息明文 plaintext 之外，此函数还需要一个字节序列 AD 附加在消息头前面，以形成底层 AEAD 加密所需的附加数据：

def RatchetEncrypt(state, plaintext, AD):
    state.CKs, mk = KDF_CK(state.CKs)
    header = HEADER(state.DHs, state.PN, state.Ns)
    state.Ns += 1
    return header, ENCRYPT(mk, plaintext, CONCAT(AD, header))

3.5. 解密消息

调用 RatchetDecrypt() 以解密消息。此函数完成如下操作：

  • 如果消息对应一个被跳过的消息密钥，此函数使用对应的消息密钥解密消息，删除消息密钥后返回。
  • 否则，如果接收到新的棘轮密钥，此函数保存当前接收链上所有被跳过的消息密钥，并执行一次 DH 棘轮步进以取代发送链和接收链。
  • 之后，此函数执行一次对称密钥棘轮步进，以派生对应的消息密钥及下一个链密钥，并解密消息。

如果发生异常（例如消息认证失败），则消息被丢弃，对状态对象的修改也同时被丢弃。否则，接受解密后的明文并保存对状态对象的修改：

def RatchetDecrypt(state, header, ciphertext, AD):
    plaintext = TrySkippedMessageKeys(state, header, ciphertext, AD)
    if plaintext != None:
        return plaintext
    if header.dh != state.DHr:                 
        SkipMessageKeys(state, header.pn)
        DHRatchet(state, header)
    SkipMessageKeys(state, header.n)             
    state.CKr, mk = KDF_CK(state.CKr)
    state.Nr += 1
    return DECRYPT(mk, ciphertext, CONCAT(AD, header))

def TrySkippedMessageKeys(state, header, ciphertext, AD):
    if (header.dh, header.n) in state.MKSKIPPED:
        mk = state.MKSKIPPED[header.dh, header.n]
        del state.MKSKIPPED[header.dh, header.n]
        return DECRYPT(mk, ciphertext, CONCAT(AD, header))
    else:
        return None

def SkipMessageKeys(state, until):
    if state.Nr + MAX_SKIP < until:
        raise Error()
    if state.CKr != None:
        while state.Nr < until:
            state.CKr, mk = KDF_CK(state.CKr)
            state.MKSKIPPED[state.DHr, state.Nr] = mk
            state.Nr += 1

def DHRatchet(state, header):
    state.PN = state.Ns                          
    state.Ns = 0
    state.Nr = 0
    state.DHr = header.dh
    state.RK, state.CKr = KDF_RK(state.RK, DH(state.DHs, state.DHr))
    state.DHs = GENERATE_DH()
    state.RK, state.CKs = KDF_RK(state.RK, DH(state.DHs, state.DHr))

4. 带头部加密的双棘轮算法

4.1. 概述

本节介绍双棘轮算法的头部加密（header encryption） 变种。

消息头部包含棘轮公钥及 (PN, N) 值。在某些场景下，可能需要对头部也加密，以使监听者无法区分哪个消息属于哪个会话，或某个会话中消息的顺序。

使用头部加密，通信双方需要为发送和接收两个方向都保存一个对称的头部密钥（header key）及下一个头部密钥（next header key）。发送头部密钥用于当前发送链的头部加密。

当接收者收到一条消息时，她必须首先将消息关联到对应的双棘轮会话（假设她与多方同时保持多个会话）。如何关联不在本文讨论范围内，读者可参考 Pond 协议6。

将消息与会话关联之后，接收者依次尝试使用此会话中接收链的头部密钥、下一个头部密钥及与被跳过的消息对应的所有头部密钥对消息头解密。若使用下一个头部密钥解密成功，则表示接收者必须执行一次 DH 棘轮步进。在 DH 棘轮步进过程中，下一个头部密钥取代当前头部密钥，而根 KDF 的额外输出作为新的下一个头部密钥。

下图中，Alice 已使用 Bob 的棘轮公钥及初始根密钥（ RK ）、发送头部密钥（ HK ）、下一个接收头部密钥（ NHK ）作为共享密钥初始化。作为初始化的一部分，Alice 生成其棘轮密钥对并更新根链以派生新的根密钥（ RK ）、发送链密钥（ CK ）及下一个发送头部密钥（ NHK ）：

当 Alice 发送第一个消息 A1 时，她使用已初始化的发送头部密钥对消息头加密：

假如接下来 Alice 收到来自 Bob 的响应消息 B1 ，此消息的头部将使用已初始化的下一个接收头部密钥加密。Alice 执行一次 DH 棘轮步进，使得下一个头部密钥成为当前头部密钥，并生成新的下一个头部密钥：

接下来 Alice 发送消息 A2 ，并接收消息 B2 ，此消息可使用当前接收头部密钥解密，并包含与消息 B1 相同的棘轮公钥。之后 Alice 发送消息 A3 和 A4 。当前头部密钥用于此阶段所有发送和接收的消息：

此后 Alice 收到消息 B3 ，其中包含 Bob 新的棘轮密钥，且消息头部使用下一个接收头部密钥加密。使用下一个头部密钥对消息头成功解密后，将触发一次 DH 棘轮步进。接着 Alice 收到使用（与 B3 ）相同的棘轮密钥和头部密钥的消息 B4 ，再发送消息 A5 。Alice 的最终状态如下所示：

4.2. 外部函数

头部加密需要额外的函数：

  • HENCRYPT(hk, plaintext)：此函数返回使用头部密钥 hk 对明文 plaintext 做 AEAD 加密的结果。由于相同的 hk 将重复使用，因此 AEAD 的 nonce 值要么必须是有状态且不重复的值，要么必须是由至少 128 比特的熵生成的不重复的随机值。
  • HDECRYPT(hk, ciphertext)：此函数返回使用头部密钥 hk 对密文 ciphertext 做 AEAD 解密的结果。如果认证失败，或头部密钥 hk 为空（ None ），则此函数返回 None 。
  • KDF_RK_HE(rk, dh_out)：此函数将根密钥 rk 及迪菲-赫尔曼输出 dh_out 作为 KDF 的输入，并输出三元组：新的根密钥，链密钥，以及下一个头部密钥。

4.3. 状态变量

所需额外的状态变量：

  • HKs, HKr：发送和接收的头部密钥，均为 32 字节
  • NHKs, NHKr：发送和接收的下一个头部密钥，均为 32 字节

以下变量的定义有所变化：

  • MKSKIPPED：已跳过的消息密钥的字典，由头部密钥和消息编号索引。若保存了过多的元素则发生异常。

4.4. 初始化

必须使用一些额外的共享密钥以初始化头部密钥：

  • Alice 的发送头部密钥和 Bob 的下一个接收头部密钥必须设置为相同的值，以便 Alice 的第一条消息能触发 Bob 执行一次 DH 棘轮步进。
  • Alice 的下一个接收头部密钥和 Bob 的下一个发送头部密钥必须设置为相同的值，以便在 Bob 的首次 DH 棘轮步进之后，Bob 的下一条消息能触发 Alice 执行一次 DH 棘轮步进。

一旦 Alice 和 Bob 协商好了 SK 、Bob 的棘轮公钥及上述额外的值，Alice 调用 RatchetInitAliceHE() ，而 Bob 调用 RatchetInitBobHE() ：

def RatchetInitAliceHE(state, SK, bob_dh_public_key, shared_hka, shared_nhkb):
    state.DHRs = GENERATE_DH()
    state.DHRr = bob_dh_public_key
    state.RK, state.CKs, state.NHKs = KDF_RK_HE(SK, DH(state.DHRs, state.DHRr)) 
    state.CKr = None
    state.Ns = 0
    state.Nr = 0
    state.PN = 0
    state.MKSKIPPED = {}
    state.HKs = shared_hka
    state.HKr = None
    state.NHKr = shared_nhkb

def RatchetInitBobHE(state, SK, bob_dh_key_pair, shared_hka, shared_nhkb):
    state.DHRs = bob_dh_key_pair
    state.DHRr = None
    state.RK = SK 
    state.CKs = None
    state.CKr = None
    state.Ns = 0
    state.Nr = 0
    state.PN = 0
    state.MKSKIPPED = {}
    state.HKs = None
    state.NHKs = shared_nhkb
    state.HKr = None
    state.NHKr = shared_hka

4.5. 加密消息

调用 RatchetEncryptHE() 以加密带头部加密的消息：

def RatchetEncryptHE(state, plaintext, AD):
    state.CKs, mk = KDF_CK(state.CKs)
    header = HEADER(state.DHRs, state.PN, state.Ns)
    enc_header = HENCRYPT(state.HKs, header)
    state.Ns += 1
    return enc_header, ENCRYPT(mk, plaintext, CONCAT(AD, enc_header))

4.6. 解密消息

调用 RatchetDecryptHE() 以解密带头部加密的消息：

def RatchetDecryptHE(state, enc_header, ciphertext, AD):
    plaintext = TrySkippedMessageKeysHE(state, enc_header, ciphertext, AD)
    if plaintext != None:
        return plaintext
    header, dh_ratchet = DecryptHeader(state, enc_header)
    if dh_ratchet:
        SkipMessageKeysHE(state, header.pn)
        DHRatchetHE(state, header)
    SkipMessageKeysHE(state, header.n)
    state.CKr, mk = KDF_CK(state.CKr)
    state.Nr += 1
    return DECRYPT(mk, ciphertext, CONCAT(AD, enc_header))

def TrySkippedMessageKeysHE(state, enc_header, ciphertext, AD):
    for ((hk, n), mk) in state.MKSKIPPED.items():
        header = HDECRYPT(hk, enc_header)
        if header != None and header.n == n:
            del state.MKSKIPPED[hk, n]
            return DECRYPT(mk, ciphertext, CONCAT(AD, enc_header))
    return None

def DecryptHeader(state, enc_header):
    header = HDECRYPT(state.HKr, enc_header)
    if header != None:
        return header, False
    header = HDECRYPT(state.NHKr, enc_header)
    if header != None:
        return header, True
    raise Error()

def SkipMessageKeysHE(state, until):
    if state.Nr + MAX_SKIP < until:
        raise Error()
    if state.CKr != None:
        while state.Nr < until:
            state.CKr, mk = KDF_CK(state.CKr)
            state.MKSKIPPED[state.HKr, state.Nr] = mk
            state.Nr += 1

def DHRatchetHE(state, header):
    state.PN = state.Ns
    state.Ns = 0
    state.Nr = 0
    state.HKs = state.NHKs
    state.HKr = state.NHKr
    state.DHRr = header.dh
    state.RK, state.CKr, state.NHKr = KDF_RK_HE(state.RK, DH(state.DHRs, state.DHRr))
    state.DHRs = GENERATE_DH()
    state.RK, state.CKs, state.NHKs = KDF_RK_HE(state.RK, DH(state.DHRs, state.DHRr))

5. 实现方面的考虑

5.1. 与 X3DH 集成

双棘轮算法可与 X3DH 密钥协商协议1集成。双棘轮算法将 X3DH 协商好的会话密钥 SK 作为初始根密钥，扮演「后 X3DH」协议的角色。

以下 X3DH 的输出将用于双棘轮算法：

  • X3DH 输出的 SK 作为双棘轮算法初始化所需的 SK 输入（参见第 3.3 节）。
  • X3DH 输出的 AD 作为双棘轮算法加解密所需的 AD 输入（参见第 3.4 节及第 3.5 节）。
  • Bob 从 X3DH 输出的已签名的预共享密钥（ SPKB ）作为双棘轮算法初始化所需的 Bob 的初始棘轮公钥（及对应的密钥对）。

使用 Alice 的初始发送链加密的所有双棘轮消息都可认为是 X3DH 的「初始密文」。为了处理可能发生的消息丢失或乱序，推荐的模型是 Alice 不停地发送前附相同 X3DH 初始消息的双棘轮消息，直到她接收到 Bob 的首条双棘轮响应消息为止。

5.2. 推荐的密码学算法

推荐使用以下算法实例化第 3.1 节中的密码学函数：

  • GENERATE_DH()：此函数推荐使用 Curve25519 或 Curve448 椭圆曲线7生成密钥对。

  • DH(dh_pair, dh_pub)：此函数推荐返回 7 中定义的 X25519 或 X448 函数的输出。没必要检查无效的公钥。

  • KDF_RK(rk, dh_out)：此函数推荐使用 SHA-256 或 SHA-5128 的 HKDF3 实现，并使用 rk 作为 HKDF 的 盐（salt） 、dh_out 作为 HKDF 的 输入密钥材料（input key material） 及特定于应用的字节序列作为 HKDF 的 信息（info） 。信息（info） 的值应该与应用中其它 HKDF 使用的值不同。

  • KDF_CK(ck)：此函数推荐使用 SHA-256 或 SHA-5128 的 HMAC2 实现，并使用 ck 作为 HMAC 的密钥，使用不同的常数作为输入生成不同的输出（例如，使用单一字节 0x01 作为输入生成消息密钥，单一字节 0x02 作为输入生成下一个链密钥）。

  • ENCRYPT(mk, plaintext, associated_data)：此函数推荐使用基于 SIV 或基于 CBC 与 HAMC 的组合59的 AEAD 加密方案实现。这些方案可避免密钥被多次重复使用。基于 CBC 与 HAMC 的具体推荐方案如下：

    • HKDF 与 SHA-256 或 SHA-512 一起使用以生成 80 字节的输出。HKDF 的 盐（salt） 设置为与哈希输出等长的零填充字节序列。HKDF 的 输入密钥材料（input key material） 设置为 mk 。HKDF 的 信息（info） 设置为特定于应用的字节序列且与应用中其它 HKDF 使用的值不同。
    • HKDF 的输出拆分成三个部分：32 字节的加密密钥，32 字节的认证密钥，以及 16 字节的初始向量（IV）。
    • 明文使用 CBC 模式、带 PKCS#7 填充的 AES-256 算法，使用上一步生成的加密密钥和初始向量（IV）加密1011。
    • HMAC 使用认证密钥及上述相同的哈希函数2计算得到。HMAC 的输入由关联数据 associated_data 附加在密文前面组成。HAMC 的输出附加在密文后面。

6. 安全方面的考虑

6.1. 安全删除

双棘轮算法的设计可避免攻击者记录加密消息并在后继的时间攻破发送者或接收者。但若攻击者获得了设备的底层读取权限并将已删除的明文或密钥从其中恢复，则此安全性不再有效。从存储介质中恢复已删除的数据是个非常复杂的话题，已超出本文的讨论范围。

6.2. 从泄露中恢复

假如被动监听者攻破了会话的一方或双方并观察其加密消息，DH 棘轮的设计保证了从泄露中恢复的安全性。尽管如此，若密钥或设备完整性被攻破将对后继通信的安全产生毁灭性的后果。例如：

  • 攻击者可使用被攻破的密钥以伪装成被攻破方（比如，将被攻破方的私钥用于 X3DH 以创建新的会话）。
  • 攻击者可通过持续主动的中间人攻击使用自己的棘轮密钥替换会话中的棘轮密钥，以持续监听被攻破的会话。
  • 攻击者可修改被攻破方的随机数生成器（RNG）使得后继生成的棘轮私钥可预测。

如果某一方怀疑自己的密钥或设备被攻破，必须立即将其更换。

6.3. 密码学分析与棘轮公钥

由于所有的 DH 棘轮计算都混入到根密钥之中，所以一个能使用被动密钥学分析解密会话的攻击者，如果没有观察到某些棘轮公钥，则有可能无法继续解密。

这当然不是针对密码学分析的可靠对策。如果在会话依赖的任何密码学算法中发现了弱点，对应的会话应该被丢弃，并使用更强的密码学算法创建新的会话。

6.4. 已跳过的消息密钥的删除

保存已跳过的消息密钥引入了如下风险：

  • 恶意发送者可使接收者存储大量的已跳过的消息密钥，可能因过于消耗存储空间而导致拒绝服务。
  • 丢失的消息即使未到达接收者也可以被攻击者捕获（并记录）。攻击者可在后继时刻通过获取跳过的消息密钥来攻破对应的接收者。

为降低第一种风险，通信双方应为每个会话设置合理的已跳过消息密钥的数目上限（例如 1000）。为降低第二种风险，通信双方应在某个合适的时间间隔后删除已跳过的消息密钥。删除操作可由定时器触发，或由事件计数触发（事件可以是接收到消息、DH 棘轮步进，等等）。

6.5. 推迟新棘轮密钥的生成

每次 DH 棘轮步进过程中，会生成新的棘轮密钥对和发送链。由于发送链暂时不需使用，这些步骤可推迟到即将发送新消息时完成。这样可通过缩短棘轮密钥的生命周期而轻微地提高安全性，而代价是增加一些复杂性。

6.6. 认证标签的截断

如果 ENCRYPT() 函数使用第 5.2 节中描述的 CBC 和 HMAC 实现，那么将 HMAC 的最终输出截断到 128 比特以减小消息长度是可接受的。尽管将其进一步截断也是可接受的，但需要仔细地分析。但任何情况下都不应将 HAMC 的最终输出截断到小于 64 比特。

如果 ENCRYPT() 函数使用不同的方式实现，那么截断操作可能需要更复杂的分析且不推荐截断。

6.7. 指纹信息的实现

如果本协议用于匿名双方的设定，需要特别注意所有场景下的实现必须一致。

在匿名场景下，建议实现时精确遵循第 3 节及第 4 节中的算法。同时建议实现时对于各方使用相同的保存已跳过消息密钥的数目上限，以及相同的已跳过消息密钥删除策略。删除策略应该基于确定的事件（例如接收到消息），而不应基于时间。

7. 知识产权

本文自发布之日起进入公共领域。

8. 致谢

本算法由 Trevor Perrin 及 Moxie Marlinspike 设计。

迪菲-赫尔曼棘轮的概念来自 Nikita Borisov、Ian Goldberg 和 Eric Brewer 的 OTR 协议12。

对称密钥棘轮是一个旧有的概念1314，在最近的 SCIMP、MinimaLT 等协议151617中均有使用。

术语「棘轮」用于表示前向安全的密钥更新由 Adam Langley 在 Pond 协议18中引入。

感谢 Michael Rogers 和 Adam Back 在邮件列表中的讨论19。

感谢 Adam Langley 关于改进接收算法的讨论。

本协议及相似协议的安全性已由 Katriel Cohn-Gordon、Cas Cremers、Benjamin Dowling、Luke Garratt 及 Douglas Stebila 完成分析2021。

感谢 Tom Ritter、Joseph Bonneau、Ximin Luo、Yan Zhu、Samuel Neves、Raphael Arias 及 David J. Wu 关于编辑方向的反馈。

9. 参考资料

  1. T. Perrin and M. Marlinspike, “The X3DH Key Agreement Protocol,” 2016. https://whispersystems.org/docs/specifications/x3dh/ ↩︎ ↩︎

  2. H. Krawczyk, M. Bellare, and R. Canetti, “HMAC: Keyed-Hashing for Message Authentication.” Internet Engineering Task Force; RFC 2104 (Informational); IETF, Feb-1997. http://www.ietf.org/rfc/rfc2104.txt ↩︎ ↩︎ ↩︎

  3. H. Krawczyk and P. Eronen, “HMAC-based Extract-and-Expand Key Derivation Function (HKDF).” Internet Engineering Task Force; RFC 5869 (Informational); IETF, May-2010. http://www.ietf.org/rfc/rfc5869.txt ↩︎ ↩︎

  4. B. Barak and S. Halevi, “A model and architecture for pseudo-random generation with applications to /dev/random.” Cryptology ePrint Archive, Report 2005/029, 2005. http://eprint.iacr.org/2005/029 ↩︎

  5. P. Rogaway, “Authenticated-encryption with Associated-data,” in Proceedings of the 9th ACM Conference on Computer and Communications Security, 2002. http://web.cs.ucdavis.edu/~rogaway/papers/ad.pdf ↩︎ ↩︎

  6. A. Langley, “Pond,” 2012. https://github.com/agl/pond ↩︎

  7. A. Langley, M. Hamburg, and S. Turner, “Elliptic Curves for Security.” Internet Engineering Task Force; RFC 7748 (Informational); IETF, Jan-2016. http://www.ietf.org/rfc/rfc7748.txt ↩︎ ↩︎

  8. NIST, “FIPS 180-4. Secure Hash Standard (SHS),” National Institute of Standards & Technology, Gaithersburg, MD, United States, 2012. http://csrc.nist.gov/publications/fips/fips180-4/fips-180-4.pdf ↩︎ ↩︎

  9. P. Rogaway and T. Shrimpton, “A Provable-security Treatment of the Key-wrap Problem,” in Proceedings of the 24th Annual International Conference on The Theory and Applications of Cryptographic Techniques, 2006. http://web.cs.ucdavis.edu/~rogaway/papers/keywrap.html ↩︎

  10. NIST, “FIPS 197. Advanced Encryption Standard,” National Institute of Standards & Technology, Gaithersburg, MD, United States, 2001. http://csrc.nist.gov/publications/fips/fips197/fips-197.pdf ↩︎

  11. B. Kaliski, “PKCS #7: Cryptographic Message Syntax Version 1.5.” Internet Engineering Task Force; RFC 2315 (Informational); IETF, Mar-1998. http://www.ietf.org/rfc/rfc2315.txt ↩︎

  12. N. Borisov, I. Goldberg, and E. Brewer, “Off-the-record Communication, or, Why Not to Use PGP,” in Proceedings of the 2004 aCM workshop on privacy in the electronic society, 2004. http://doi.acm.org/10.1145/1029179.1029200 ↩︎

  13. M. Abdalla and M. Bellare, “Increasing the Lifetime of a Key: A Comparative Analysis of the Security of Re-keying Techniques,” in Advances in Cryptology - ASIACRYPT 2000, 6th International Conference on the Theory and Application of Cryptology and Information Security, 2000. https://cseweb.ucsd.edu/~mihir/papers/rekey.html ↩︎

  14. B. Olson, “Key Coercion after encrypted message transmission.” sci.crypt, 1994. https://groups.google.com/d/topic/sci.crypt/3MJzGwiTZ10/discussion ↩︎

  15. Wikipedia, “Silent Circle Instant Messaging Protocol — Wikipedia, The Free Encyclopedia.” 2016. https://en.wikipedia.org/w/index.php?title=Silent_Circle_Instant_Messaging_Protocol ↩︎

  16. G. Belvin, “A Secure Text Messaging Protocol.” Cryptology ePrint Archive, Report 2014/036, 2014. http://eprint.iacr.org/2014/036 ↩︎

  17. W. M. Petullo, X. Zhang, J. A. Solworth, D. J. Bernstein, and T. Lange, “MinimaLT: Minimal-latency Networking Through Better Security,” in Proceedings of the 2013 ACM SIGSAC Conference on Computer & Communications Security, 2013. http://doi.acm.org/10.1145/2508859.2516737 ↩︎

  18. A. Langley, “Pond/README.md,” 2012. https://github.com/agl/pond/commit/7bb06244b9aa121d367a6d556867992d1481f0c8 ↩︎

  19. M. Rogers and A. Back, “Asynchronous forward secrecy encryption.” Cryptography mailing list, 2013. http://lists.randombit.net/pipermail/cryptography/2013-September/005327.html ↩︎

  20. K. Cohn-Gordon, C. Cremers, B. Dowling, L. Garratt, and D. Stebila, “A Formal Security Analysis of the Signal Messaging Protocol.” Cryptology ePrint Archive, Report 2016/1013, 2016. http://eprint.iacr.org/2016/1013 ↩︎

  21. K. Cohn-Gordon, C. Cremers, and L. Garratt, “On Post-Compromise Security.” Cryptology ePrint Archive, Report 2016/221, 2016. http://eprint.iacr.org/2016/221 ↩︎

comments powered by Disqus