双棘轮算法

在密碼學中，雙棘輪演算法（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