在密碼學中，雙棘輪算法（Double Ratchet Algorithm，以前稱為Axolotl Ratchet[1][2]）是由Trevor Perrin和Moxie Marlinspike在2013年開發的密鑰管理算法。它可以用作安全協議的一部分。為即時通訊系統提供端到端加密。在初始密鑰交換之後，它管理持續更新和維護短期會話密鑰。它結合了基於迪菲-赫爾曼密鑰交換（DH）的密碼棘輪和基於密鑰派生函數（KDF）的棘輪，例如散列函數，因此被稱為雙棘輪。
通信雙方為每個雙棘輪消息派生出新密鑰，使得舊的密鑰不能從新的密鑰計算得出。通信雙方還將在消息中附加迪菲-赫爾曼公鑰值。將迪菲-赫爾曼計算的結果將被混合到派生出的密鑰中，使得新的密鑰不能從舊的密鑰計算得出。在一方密鑰泄露的情況下，這些屬性為泄漏前或泄漏後加密的消息提供一些保護。[3]
算法概述
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 棘輪步進，以更新鏈密鑰。
應用
以下是使用雙棘輪算法或其定製化實現的應用程序列表：
備註
參考文獻
外部連結
Wikiwand in your browser!
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.
