跳至內容

雙棘輪算法

維基百科,自由的百科全書

密碼學中,雙棘輪算法Double Ratchet Algorithm,以前稱為Axolotl Ratchet[1][2])是由Trevor Perrin和Moxie Marlinspike在2013年開發的密鑰管理算法。它可以用作安全協議的一部分。為即時通訊系統提供端到端加密。在初始密鑰交換之後,它管理持續更新和維護短期會話密鑰。它結合了基於迪菲-赫爾曼密鑰交換(DH)的密碼棘輪和基於密鑰派生函數(KDF)的棘輪,例如散列函數,因此被稱為雙棘輪。

通信雙方為每個雙棘輪消息派生出新密鑰,使得舊的密鑰不能從新的密鑰計算得出。通信雙方還將在消息中附加迪菲-赫爾曼公鑰值。將迪菲-赫爾曼計算的結果將被混合到派生出的密鑰中,使得新的密鑰不能從舊的密鑰計算得出。在一方密鑰泄露的情況下,這些屬性為泄漏前或泄漏後加密的消息提供一些保護。[3]

算法概述

KDF鏈

KDF鏈是雙棘輪算法中的核心概念。KDF是這樣一個密碼學函數:輸入一個秘密且隨機的KDF密鑰(KDF key)及其它一些輸入數據,並返回輸出數據。在密鑰未知的前提下,輸出的數據與隨機數不可區分(也就是說,KDF滿足密碼學「PRF」的要求)。若密鑰不是秘密且隨機的,則KDF應仍然能作為密鑰和輸入數據的安全的密碼學哈希。當HMACHKDF英語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 棘輪步進,以更新鏈密鑰。

應用

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

備註

  1. ^ 1.0 1.1 1.2 1.3 Via the OMEMO protocol
  2. ^ Only in "secret conversations"
  3. ^ 3.0 3.1 3.2 3.3 3.4 3.5 3.6 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

參考文獻

  1. ^ Perrin, Trevor. Compare Revisions. GitHub. 30 March 2016 [9 April 2016]. (原始內容存檔於2017-05-07). 
  2. ^ Marlinspike, Moxie. Signal on the outside, Signal on the inside. Open Whisper Systems. 30 March 2016 [31 March 2016]. (原始內容存檔於2016-12-28). 
  3. ^ Trevor Perrin, Moxie Marlinspike. The Double Ratchet Algorithm. Signal. [2016-11-20]. (原始內容存檔於2017-07-08). 
  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頁面存檔備份,存於互聯網檔案館
  7. ^ Security. Cryptocat. [14 July 2016]. (原始內容存檔於2016-04-07). 
  8. ^ Greenberg, Andy. You Can All Finally Encrypt Facebook Messenger, So Do It. Wired. Condé Nast. 4 October 2016 [5 October 2016]. (原始內容存檔於2017-04-15). 
  9. ^ Seals, Tara. G DATA Adds Encryption for Secure Mobile Chat. Infosecurity Magazine. Reed Exhibitions Ltd. 17 September 2015 [16 January 2016]. (原始內容存檔於2016-07-22). 
  10. ^ SecureChat. GitHub. G Data. [14 July 2016]. (原始內容存檔於2017-05-07). 
  11. ^ Greenberg, Andy. With Allo and Duo, Google Finally Encrypts Conversations End-to-End. Wired. Condé Nast. 18 May 2016 [14 July 2016]. (原始內容存檔於2017-02-02). 
  12. ^ Haven Attributions. GitHub. Guardian Project. [22 December 2017]. (原始內容存檔於2019-06-16). 
  13. ^ Lee, Micah. Snowden's New App Uses Your Smartphone To Physically Guard Your Laptop. The Intercept. First Look Media. 22 December 2017 [22 December 2017]. (原始內容存檔於2019-07-19). 
  14. ^ Langley, Adam. Wire in new ratchet system. GitHub (GitHub contribution). 9 November 2013 [16 January 2016]. (原始內容存檔於2016-12-28). 
  15. ^ Butcher, Mike. Riot wants to be like Slack, but with the flexibility of an underlying open source platform. TechCrunch. AOL Inc. 19 September 2016 [20 September 2016]. (原始內容存檔於2018-10-18). 
  16. ^ Silent Circle/libzina. Github. Silent Circle. [19 December 2017]. (原始內容存檔於2019-04-22). 
  17. ^ Lund, Joshua. Signal partners with Microsoft to bring end-to-end encryption to Skype. Open Whisper Systems. 11 January 2018 [11 January 2018]. (原始內容存檔於2020-02-02). 
  18. ^ Viber Encryption Overview (PDF). Viber. 25 July 2018 [26 October 2018]. (原始內容存檔 (PDF)於2019-07-19). 
  19. ^ Metz, Cade. Forget Apple vs. the FBI: WhatsApp Just Switched on Encryption for a Billion People. Wired. Condé Nast. 5 April 2016 [5 April 2016]. (原始內容存檔於2016-04-05). 
  20. ^ Wire Security Whitepaper. Wire Swiss GmbH. [15 July 2016]. [永久失效連結]

外部連結

 本條目包含了自由內容作品內的文本。 在公共領域下釋出 《The Double Ratchet Algorithm》, Trevor Perrin (editor), Moxie Marlinspike, 欲了解如何向維基百科條目內添加開放許可證文本,請見這裏;欲知如何重用本站文字,請見使用條款

 本條目包含了自由內容作品內的文本。 在公共領域下釋出 《雙棘輪算法》, Philip Ye(譯者), 欲了解如何向維基百科條目內添加開放許可證文本,請見這裏;欲知如何重用本站文字,請見使用條款