雙棘輪算法

在密碼學中，雙棘輪算法（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（英語：HKDF）使用安全的哈希算法實例化時，二者的構造即滿足KDF定義。^[4][5]

我們使用術語KDF鏈（KDF chain）表示如下流程：一個KDF輸出的一部分作為輸出密鑰（Output key），而另一部分將取代KDF密鑰，作為另一個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棘輪步進，以更新鏈密鑰。

應用

以下是使用雙棘輪算法或其定製化實現的應用程序列表：

• ChatSecure^[a]
• Conversations^[a]
• Cryptocat^[a][7]
• Facebook Messenger^[b][c][8]
• G Data Secure Chat^[c][9][10]
• Gajim^[a][d]
• Google Allo^[e][c][11]
• Haven^[c][12][13]
• Pond^[14]
• Riot^[f][15]
• Signal^[c]
• Silent Phone^[g][16]
• Skype^[h][c][17]
• Viber^[i][18]
• WhatsApp^[c][19]
• Wire^[j][20]

備註

1. Via the OMEMO protocol
2. Only in "secret conversations"
3. Via the Signal Protocol
4. A third-party plug-in must be installed separately
5. Only in "incognito mode"
6. Via the Matrix protocol
7. Via the Zina protocol
8. Only in "private conversations"
9. Viber "uses the same concepts of the "double ratchet" protocol used in Open Whisper Systems Signal application"
10. Via the Proteus protocol