双棘轮算法

在密码学中，双棘轮算法（Double Ratchet Algorithm，以前称为Axolotl Ratchet^[1]^[2]）是由Trevor Perrin和Moxie Marlinspike在2013年开发的密钥管理算法。它可以用作安全协议的一部分。为即时通讯系统提供端到端加密。在初始密钥交换之后，它管理持续更新和维护短期会话密钥。它结合了基于迪菲-赫尔曼密钥交换（DH）的密码棘轮和基于密钥导出函数（KDF）的棘轮，例如散列函数，因此被称为双棘轮。

通信双方为每个双棘轮消息派生出新密钥，使得旧的密钥不能从新的密钥计算得出。通信双方还将在消息中附加迪菲-赫尔曼公钥值。将迪菲-赫尔曼计算的结果将被混合到派生出的密钥中，使得新的密钥不能从旧的密钥计算得出。在一方密钥泄露的情况下，这些属性为泄漏前或泄漏后加密的消息提供一些保护。^[3]

算法概述

KDF链

KDF链是双棘轮算法中的核心概念。KDF是这样一个密码学函数：输入一个秘密且随机的KDF密钥（KDF key）及其它一些输入数据，并返回输出数据。在密钥未知的前提下，输出的数据与随机数不可区分（也就是说，KDF满足密码学“PRF”的要求）。若密钥不是秘密且随机的，则KDF应仍然能作为密钥和输入数据的安全的密码学哈希。当HMAC和HKDF使用安全的哈希算法实例化时，二者的构造即满足KDF定义。^[4]^[5]

我们使用术语KDF链（KDF chain）表示如下流程：一个KDF输出的一部分作为输出密钥（Output key），而另一部分将取代KDF密钥，作为另一个KDF的输入密钥。

一个KDF链具有如下特性^[6]：

弹性（resilience）：对于不知道KDF密钥的攻击者来说，输出密钥看起来是随机的。即使攻击者能控制KDF的输入，此条特性仍然成立。
前向安全性：对于知道某一时刻的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）。

对称密钥棘轮

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

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

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

迪菲-赫尔曼棘轮

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

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

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

双棘轮

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

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

应用

以下是使用双棘轮算法或其定制化实现的应用程序列表：

备注

↑ ^1.0 ^1.1 ^1.2 ^1.3 Via the OMEMO protocol
↑ Only in "secret conversations"
↑ ^3.0 ^3.1 ^3.2 ^3.3 ^3.4 ^3.5 ^3.6 Via the Signal Protocol
↑ A third-party plug-in must be installed separately
↑ Only in "incognito mode"
↑ Via the Matrix protocol
↑ Via the Zina protocol
↑ Only in "private conversations"
↑ Viber "uses the same concepts of the "double ratchet" protocol used in Open Whisper Systems Signal application"
↑ Via the Proteus protocol

参考文献

↑ Perrin, Trevor. Compare Revisions. GitHub. 2016-03-30 [2016-04-09].
↑ Marlinspike, Moxie. Signal on the outside, Signal on the inside. Open Whisper Systems. 2016-03-30 [2016-03-31].
↑ Trevor Perrin, Moxie Marlinspike. The Double Ratchet Algorithm. Signal. [2016-11-20].
↑ 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
↑ 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
↑ 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
↑ Security. Cryptocat. [2016-07-14].
↑ Greenberg, Andy. You Can All Finally Encrypt Facebook Messenger, So Do It. Wired. Condé Nast. 2016-10-04 [2016-10-05].
↑ Seals, Tara. G DATA Adds Encryption for Secure Mobile Chat. Infosecurity Magazine. Reed Exhibitions Ltd. 2015-09-17 [2016-01-16].
↑ SecureChat. GitHub. G Data. [2016-07-14].
↑ Greenberg, Andy. With Allo and Duo, Google Finally Encrypts Conversations End-to-End. Wired. Condé Nast. 2016-05-18 [2016-07-14].
↑ Haven Attributions. GitHub. Guardian Project. [2017-12-22].
↑ Lee, Micah. Snowden's New App Uses Your Smartphone To Physically Guard Your Laptop. The Intercept. First Look Media. 2017-12-22 [2017-12-22].
↑ Langley, Adam. Wire in new ratchet system. GitHub (GitHub contribution). 2013-11-09 [2016-01-16].
↑ Butcher, Mike. Riot wants to be like Slack, but with the flexibility of an underlying open source platform. TechCrunch. AOL Inc. 2016-09-19 [2016-09-20].
↑ Silent Circle/libzina. Github. Silent Circle. [2017-12-19].
↑ Lund, Joshua. Signal partners with Microsoft to bring end-to-end encryption to Skype. Open Whisper Systems. 2018-01-11 [2018-01-11].
↑ Viber Encryption Overview (PDF). Viber. 2018-07-25 [2018-10-26].
↑ Metz, Cade. Forget Apple vs. the FBI: WhatsApp Just Switched on Encryption for a Billion People. Wired. Condé Nast. 2016-04-05 [2016-04-05].
↑ Wire Security Whitepaper. Wire Swiss GmbH. [2016-07-15]. ^{[永久失效链接]}

外部链接

Specification by Open Whisper Systems
"Advanced cryptographic ratcheting", abstract description by Moxie Marlinspike
Olm: implementation in C++ under the Apache license

[OMEMO-7] 1.0 ^1.1 ^1.2 ^1.3 Via the OMEMO protocol

[9] Only in "secret conversations"

[SIGNAL-10] 3.0 ^3.1 ^3.2 ^3.3 ^3.4 ^3.5 ^3.6 Via the Signal Protocol

[Plugin-14] A third-party plug-in must be installed separately

[15] Only in "incognito mode"

[Matrix-20] Via the Matrix protocol

[zina-22] Via the Zina protocol

[24] Only in "private conversations"

[26] Viber "uses the same concepts of the "double ratchet" protocol used in Open Whisper Systems Signal application"

[Proteus-29] Via the Proteus protocol

[Perrin-2016-03-30-1] Perrin, Trevor. Compare Revisions. GitHub. 2016-03-30 [2016-04-09].

[signal-inside-and-out-2] Marlinspike, Moxie. Signal on the outside, Signal on the inside. Open Whisper Systems. 2016-03-30 [2016-03-31].

[3] Trevor Perrin, Moxie Marlinspike. The Double Ratchet Algorithm. Signal. [2016-11-20].

[4] 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

[5] 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

[6] 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

[8] Security. Cryptocat. [2016-07-14].

[11] Greenberg, Andy. You Can All Finally Encrypt Facebook Messenger, So Do It. Wired. Condé Nast. 2016-10-04 [2016-10-05].

[G_Data-12] Seals, Tara. G DATA Adds Encryption for Secure Mobile Chat. Infosecurity Magazine. Reed Exhibitions Ltd. 2015-09-17 [2016-01-16].

[13] SecureChat. GitHub. G Data. [2016-07-14].

[Greenberg-2016-05-18-16] Greenberg, Andy. With Allo and Duo, Google Finally Encrypts Conversations End-to-End. Wired. Condé Nast. 2016-05-18 [2016-07-14].

[17] Haven Attributions. GitHub. Guardian Project. [2017-12-22].

[18] Lee, Micah. Snowden's New App Uses Your Smartphone To Physically Guard Your Laptop. The Intercept. First Look Media. 2017-12-22 [2017-12-22].

[Pond-19] Langley, Adam. Wire in new ratchet system. GitHub (GitHub contribution). 2013-11-09 [2016-01-16].

[21] Butcher, Mike. Riot wants to be like Slack, but with the flexibility of an underlying open source platform. TechCrunch. AOL Inc. 2016-09-19 [2016-09-20].

[libzina-23] Silent Circle/libzina. Github. Silent Circle. [2017-12-19].

[25] Lund, Joshua. Signal partners with Microsoft to bring end-to-end encryption to Skype. Open Whisper Systems. 2018-01-11 [2018-01-11].

[27] Viber Encryption Overview (PDF). Viber. 2018-07-25 [2018-10-26].

[Metz-2016-04-05-28] Metz, Cade. Forget Apple vs. the FBI: WhatsApp Just Switched on Encryption for a Billion People. Wired. Condé Nast. 2016-04-05 [2016-04-05].

[Wire_Security_Whitepaper-30] Wire Security Whitepaper. Wire Swiss GmbH. [2016-07-15]. ^{[永久失效链接]}

[1]

[2]

[3]

[4]

[5]

[6]

[a]

[7]

[b]

[c]

[8]

[9]

[10]

[d]

[e]

[11]

[12]

[13]

[14]

[f]

[15]

[g]

[16]

[h]

[17]

[i]

[18]

[19]

[j]

[20]