作者：Ethan Heilman, Neha Narula, Garrett Tanzer, James Lovejoy, Michael Colavita, Madars Virza, and Tadge Dryja
原文：Cryptanalysis of Curl-P and Other Attacks on the IOTA Cryptocurrency
譯者：知道創宇404實驗室

摘要

本文介紹了使用偽造簽名攻擊IOTA區塊鏈的方法。加密哈希函數Curl-P-27中存在一些弱點，允許攻擊者快速生成可碰撞的短消息，并且這個方法也適用于相同長度的消息，利用這些弱點我們實現了對加密哈希函數Curl-P-27的攻擊，破解了前IOTA簽名方案（ISS）的EU-CMA。本文最后我們將介紹如何在消息已經被簽署的情況下偽造有效支出的簽名和多重簽名（在IOTA中稱為bundle）。

關鍵詞：加密貨幣，簽名偽造，加密哈希函數，密碼分析

1 介紹

加密貨幣通過數字簽名來鑒別用戶的轉賬行為。為了提高性能，在許多簽名方案中，用戶簽署的是消息的哈希值而不是消息本身。在此情況下，如果底層哈希函數受到了攻擊，攻擊者便可以在付款時偽造數字簽名。

IOTA 的付款操作需要獲得簽名方案的授權。本文介紹了對該簽名方案的攻擊，這些攻擊利用了哈希函數Curl-P-27的弱點。重要的是，我們在2017年8月披露并修補了此漏洞，由此保證了IOTA簽名方案的安全性[20]。

IOTA是一種加密貨幣，被應用于物聯網（IoT）和汽車生態系統。截至2018年7月24日，它以26億美元的市值成為全球第九大最有價值的加密貨幣[9]。許多公司與 IOTA 有過合作，包括汽車制造商大眾汽車公司和歐洲大型工業公司博世公司。 IOTA 曾發布公告稱大眾汽車計劃在2019年初發布一款使用 IOTA 的產品[7]。 2017年底，博世購買了“大量 IOTA代幣”[6]。此外，IOTA 基金會與臺北市簽署了一項協議，將 IOTA 用于其智能城市計劃，其中包括數字市民卡項目[8]。

IOTA使用加密簽名來授權用戶付款。基于 Winternitz 一次性簽名[25]，IOTA建立了自己的簽名方案（ISS）。但與傳統的 Winternitz 簽名不同，IOTA 用戶簽署的是消息的哈希值。由此可見，ISS的安全性依賴于其加密哈希函數，即 Curl-P-27。通過常見的差分密碼分析方法，我們可以使用Curl-P-27快速創建哈希值相同且長度相同的消息，從而打破了功能的碰撞阻力。我們做到了每次都能在一個上限值之內實現碰撞。

使用此碰撞攻擊，我們可以在 IOTA 中偽造簽名。我們從被簽署的消息著手，為攻擊者分別創建良性支付和惡意支付，并且使這兩種支付具有相同的有效簽名。我們的攻擊適用于正常付款和多簽名付款，并且只針對IOTA 簽名方案，而沒有包括整個 IOTA 網絡。從多簽名地址支出需要一個用戶為另一個用戶簽名支付，這完全取決于如何設置被簽署消息。我們詳細介紹了如何攻擊多簽名地址支出，并提供了在單簽名和多簽名付款中生成碰撞的工具，并且評估了攻擊的效率。在使用80個核的條件下，我們可以在不到20秒的時間內制造 IOTA 付款碰撞。

1.1 漏洞狀況和影響

2017年7月14日，我們與 IOTA 開發人員準備披露這個攻擊，并且就修補漏洞的時間安排以及發布日期進行了協商。 2017年8月7日，IOTA 開發人員部署了一個向后兼容的升級，通過將 Curl-P-27 替換為另一個哈希函數來消除漏洞[32]。為了進行升級，Bitfinex 暫停了其存取款業務，時間接近三天 [4]。所有直接持有 IOTA（不通過交易所）的用戶都被鼓勵升級他們的錢包和地址。 2017年9月7日，我們發布了漏洞報告[20]，描述了此攻擊的原理。

在報告中，我們給出了有效碰撞和簽名偽造的示例以及驗證他們的軟件。在此基礎上，本文詳細分析了破解 Curl-P-27 抗碰撞性的方法，并介紹了開發偽造簽名的軟件的流程。我們還研發了應對多簽名方案的技術——選擇消息攻擊特別適用于多簽名方案。我們沒有向 IOTA 發送任何偽造簽名或以任何方式攻擊 IOTA。由于 Curl-P-27 不再用于 ISS，本文提出的簽名偽造不適用于當前的 IOTA，同樣不適用的還包括 5.2 節提到的的多重簽名攻擊。 Curl-P-27 仍然用于 IOTA 的其他部分[14]，但我們不會對他們進行攻擊。

2 相關工作

在我們發布了初始報告之后，Colavita和Tanzer [10]分別復現了我們的分析，并驗證了Curl-P 的round函數，即這個函數通過排列的方法，根據特定的表達式進行舍入。他們二人也參與了本論文的撰寫。

1991年，Biham 和 Shamir [3]首次發布了差分密碼分析技術（IBM的研究人員在1974年發現了類似技術但沒有對外公布[11]）。在本篇論文中，我們通過平衡三元加密哈希函數實現了差分密碼分析的一個簡單應用。除了我們的漏洞報告[10]以外，還有其他研究對基于三元的加密偽隨機序列發生器進行了設計分析[16]，但是沒有研究過此函數的差分密碼。

通過對 Curl-P-27 的加密分析，我們對 ISS 的不可偽造性進行了選擇消息攻擊。或許我們還看不出降低碰撞抵抗性和建立攻擊模型有多大的作用，但 MD5 哈希函數的研究過程可以給我們答案。王小云在 2004 年首次實現了 MD5 哈希算法的碰撞[35]，并在隨后發布了生成隨機碰撞的通用程序[34]。 2005年，Lenstra 與王小云合作將這個加密漏洞應用于X.509 認證中。X.509 支持 HTTPS 等協議，并且能夠構建成對的碰撞證書[24]，是公鑰基礎設施的基石。有人認為證書頒發機構不會簽署此類可疑證書，而且由于 X.509 認證缺乏“有意義的”結構，它很有可能被濫用。2007 年, Stevens 加入 Lenstra 等人，將 MD5 的原始隨機碰撞攻擊擴展到選擇前綴碰撞攻擊[30]。2009年，Stevens 等人宣布他們已經成功偽造了一個 X.509 證書，其擁有的證書權限能夠通過所有主流瀏覽器的驗證 [31] ，導致供應商立即廢棄 MD5。

之后，IOTA 開發人員替換了 IOTA 簽名方案中的哈希函數， Curl-P-27變成了基于 Keccak 的 Kerl。2017年10月，他們發現了一個名為13攻擊（也叫 M 攻擊）的無關漏洞[23]。對于哈希值在[-13，13]區間內的消息，數字13的簽名（又記作“M”）顯示明文是私鑰的衍生物，并可以被用于偽造所有的后續消息塊，由此造成漏洞。為解決此問題，IOTA 基金會要求用戶必須更改消息，直到摘要中沒有 13。另一種補救措施是，開發人員將可能受到損害的資金轉移到其他地址，用戶之后可以通過向基金會提出申請，并收回其資金[27]。

3背景

在本節中，為了讀者能更好地了解這個攻擊，讓我們首先簡要回顧一下 IOTA 的一些不常見的設計特性和術語。我們還會對 Curl-P 哈希函數和IOTA 簽名方案（ISS）進行概述。

3.1 IOTA設計

IOTA 有一些特別之處。首先，IOTA 使用平衡三進制而不是二進制；第二，IOTA 的付款被稱為bundle；第三，IOTA 使用一種稱為 tangle 的新數據結構而不是傳統的塊鏈；第四，IOTA 聘請一個稱為協調員的可信方來檢查狀態并批準付款。

IOTA 的數據結構使用平衡三進制而不是二進制，其中用于計數的符碼為{-1，0，1}，一個三進制字節由三位符碼組成，每個字節代表了 [-13,13] 的整數。 IOTA經常將三進制字節序列化為字母A-Z和數字9。

IOTA 內的付款方式用一種叫做 bundle 的數據結構來表示。Bundle 由多個交易組成，但 IOTA 交易與其他加密貨幣交易不同，它們是負責存儲輸入或輸出的緩存，除此之外還有地址，簽名，價值和標記等字段。在第 5 節中對這個攻擊進行描述時，我們也會詳細描述 IOTA 的 bundle 和交易格式。

IOTA 是基于 tangle 的概念建立的[26]，其類似于DAG鏈，其中每個塊可以引用多個塊父[29]。然而，在 IOTA 中，沒有塊可以匯總多筆付款。相反，每個交易必須有一個 nonce 以用于 PoW，還需要含有指向其他兩個交易的指針。為了將交易添加到 tangle 中，用戶從 tangle 中選擇兩個小費以在其交易中引用。一旦創建并且得到簽名，用戶就會有足夠的工作證明，并將交易（或bundle的情況下的交易）廣播到IOTA網絡。

在目前部署的IOTA中，bundle只能在獲得協調員的批準之后才可以被接收。協調員是由IOTA開發人員運營的可信方，檢查和批準tangle的狀態，并對tangle簽名。人們擔心IOTA是集成的，或者受到IOTA開發人員的控制 [33]。 IOTA開發人員稱IOTA不是集成的，協調員是一種臨時措施，且IOTA沒有公開其源代碼。由于我們沒有與IOTA溝通，我們無法確定協調員將如何影響我們發起的攻擊，但是據我們所知，協調員沒有機制可以防止本文提到的攻擊。

3.2 IOTA的簽名方案（ISS）

受到Winternitz一次性簽名（W-OTS）的啟發，IOTA使用了類似的簽名方案[25]。 W-OTS對Lamport簽名進行了優化 [22]，同時操作多位，不惜計算成本來縮短公鑰長度。

ISS與W-OTS有很多不同。首先，與傳統的W-OTS一樣，ISS操作的是消息的哈希值，而不是像 W-OTS那樣直接在消息上進行操作。其次，ISS沒有使用校驗和，而是對消息的哈希值進行規范化。

ISS有三個安全級別。安全級別1僅簽署消息的哈希值的三分之一，安全級別1簽署前三分之二，安全級別3簽署整個哈希值。因為我們的攻擊是針對最高安全級別的，所以它也應當適用于其他所有安全級別。因此，當下文涉及到ISS時，我們將默認其使用了安全級別3。

3.3 Curl-P

在本節中，我們將描述Curl-P哈希函數。 Curl-P（有時稱為Curl）是一種加密哈希函數，被用于設計IOTA。 它的用途包括創建交易地址、消息摘要，工作證明（PoW）和基于哈希的簽名。 在高層次上，Curl-P遵循海綿結構模式[2,18]，但在一些關鍵位置上有變化。 由于IOTA項目尚未提供任何官方規范說明或分析，我們對Curl-P的開源部分進行說明。

與大多數加密哈希函數不同，Curl-P使用的是平衡三進制。為表達清楚，我們用小寫字母表示單個三進制符碼，例如a; b; c; x; y; z, 再用大寫字母表示連續的三進制符碼，如S; N; X; Y。使用下標符號表示一個序列中的單個字符，例如Si。遵循IOTA慣例，Curl-P-R中的R表示輪次（例如，Curl-P-27表示27輪Curl-P）。

Curl-P運行過程如圖一所示：（1）Curl-P的初始化狀態S是一個長度為729的全零三進制序列。 （2）消息被分成消息塊mb0 · · · mbn，每塊長度為243。 Curl-P不使用消息填充，如果一條消息的長度不是243的倍數，允許最后一個消息塊小于243。4（3）每個消息塊mb0 · · · mbn依次被復制到狀態S的前三分之一，并由函數f r進行轉換。 （4）當沒有消息塊之后，Curl-P返回最終狀態的前三分之一。有關更詳細的描述，請參閱算法1。

現在來看負責轉換狀態S的函數fr 。轉換函數fr 就是將f函數遞歸調用r次，例如f 3(S) = f (f (f (S)))。 Curl-P-27就是Curl-P哈希函數，其變換函數是f27。

調用一次fr 就能獲得S的新狀態。 如算法2中所述，初始狀態中的每相鄰兩位符碼通過簡單函數g的轉換，變成新狀態中的一位數字。 當前狀態中的每一位都會被使用兩次，一次作為g的第一個參數（由a表示），一次作為g的第二個參數（由b表示）。 在表1中，我們給出g作為替換表（s-box）。

4 Curl-P的密碼分析

在本節中，我們應用常見的差分密碼分析法來構造完全碰撞。我們構造兩條相同長度的消息，設置他們只有一個符碼不同，而且他們通過 Curl-P-27 會映射到相同的值。我們可以控制碰撞消息的內容，包括任意消息前綴和后綴。在下一節中，我們將利用他們來偽造有效IOTA支付的簽名。

除了IOTA開源項目發布的一部分源代碼，我們無法找到 Curl-P 或 Curl-P-27 的正式規范文檔。此外，IOTA開發人員表示，Curl-P-27 旨在對特定的輸入組[5]進行碰撞。事實上，Curl-P-27 是非隨機的。正如[10]中詳細探討的那樣，可以在相同長度的消息中觀察到 Curl-P-27 的非隨機行為；碰撞和第二個預成像對于生成不同長度的消息是微不足道的。因此，為了確保我們真正破解了 Curl-P-27，我們表明我們的碰撞攻擊破壞了 Curl-P-27 的安全屬性（參見第5節）。

在高層次上，我們的攻擊工作如下所示。我們選擇兩條長度至少為三個消息塊的消息，并且他們只有一位符碼不同。為了降低困難，我們使這兩條消息滿足某些約束方程（在第 4.2 節中詳細說明）。一旦我們進入包含不同符碼的消息塊，我們就需要確保會發生碰撞。為此，我們在兩個消息中隨機翻轉一組三進制數，并且每組不能超出其所在的消息塊。我們的思路是對兩條消息做變換處理，并且使不同的那一位在轉換完成后處于結果狀態的前三分之一的位置。

f 27(S)[243,729] = f27(S‘)[243,729]

因為Curl-P用下一個消息塊替換了S的前三分之一，這導致原本的差異被覆蓋，造成完全碰撞。我們利用Curl-P-27的不同特性多次強制轉換函數，這樣的話，在最后一輪時這些差異可能還保持在狀態的前三分之一。經過多輪轉換之后還保持著一位差異，找到這樣的兩條消息需要調用Curl-P-27次數的上限是760 萬次或 22287次。

在圖2中，我們可以看到在Curl-P-27中，不同的輪數會導致不同的結果。我們用顏色代表發生碰撞的可能性，x軸表示差異點的位置，y軸表示在該輪數內差異沒有擴散。我們對每個位置和深度執行100個樣本（總共11 243 100 = 267300個樣本），每個樣品隨機初始化，差異點的內容設置也是隨機的。更多數學分析請參閱[10]中的復現。

我們設置差異符碼出現在第 17 位。根據實驗結果，知道了輪次和差異點的位置，我們可以計算碰撞的概率。在此條件下遞歸20次后，碰撞的概率是1.0。因此，只要我們保證差異不會擴散，我們就可以制造碰撞。這種攻擊應該同樣適用于輸入的消息塊中的其他位置（如[10]所示）。請注意，這是確保發生碰撞的上限，因為遞歸次數少于20次時也可能發生碰撞。

4.1 Curl-P變換函數f r的不同性質

在本節中，我們將展示如何找到目標狀態，將差異保持至少20輪。這需要我們分析Curl-P變換函數f的不同性質。

差分密碼分析涉及研究兩組及兩組以上的輸入之間的差異傳播模式。最常見的技術是尋找差異軌跡。差異軌跡是一組概率偏差，表示一組差異如何通過多輪加密函數傳播到另一組差異。這里我們只使用特定的差異軌跡，即在轉換函數f的重復應用下,兩個狀態S，S‘之間的某一位的差異。我們證明了 Curl-P 強烈偏向于保持一輪的單符碼差異（即f的應用）。

首先介紹其中涉及的術語。由于Curl-P使用三進制符碼∈{?1,0,1}，我們必須使用新的三元符號表示法。為了表示兩個符碼 x 和 x' 之間的差異，我們使用Θ ( 0Θ ?1 代表 x = 0 ，x’ = ?1 或者 x = ?1 ， x‘ = 0)。通過術語擴散，我們指出在調用f之后，兩個狀態之間的差異的數量已經增加（即，差異已被使用）。

我們的攻擊是圍繞著一個事實，即s-box g不會一直傳播差異。例如，考慮g的兩組輸入和輸出：g: a,b,c and a‘, b’, c‘ such that g( a, b ) = c and g( a', b' ) = c'。我們做出以下觀察：

1.對于所有可能的值，如果 a ≠ a' 且 b = b'，那么 c ≠ c' 。

2.如果a = a' 且 b ≠ b'，則可能有 c = c' 或 c≠c'（例如，a = a'= 1，b = 0且b' = 1，則c = c' = 0）。

每調用一次 f 就是更新一次狀態。如3.3節所述，g 中每兩位符碼經過轉換以后變成新狀態中的一位符碼。先前狀態的每一位最多被轉換兩次：一次作為第一個變量a，一次作為第二個變量b。這意味著單位符碼差異將延續到下一輪，因為當它是s-box g的第一個變量a時，g的輸出將與a不同（如圖1所示）。因此，如果將f應用于兩個狀態S，S'，更新后的狀態f（S），f（S'）將始終有一位或兩位的不同，不會出現無符碼差異。

我們模擬了狀態在k輪Curl-P后保持單位符碼差異的概率。 如圖3所示，此馬爾可夫模型列舉出了所有可能的輸入與其轉換后的結果。 例如，如果當前的差異為 0Θ1，那么它有 1/9 的概率在下一輪中保持不變（即0 1），2/9 的概率變為 -1Θ0，或者有 6/9 的概率使差異個數從1增加到2（標記為失敗狀態，因為它未能保持單符碼差異）。

頂行表示 0Θ1 的轉換到各個結果的概率，第二行是 -1Θ0，第三行 -1Θ1，第四行是差異由一位變為兩位。使用這個矩陣，我們計算了在調用 k 次 f 之后差異保持一位的概率的下界，因為我們沒有計算差異位數超過 1 位之后再變回1位的情況，所以這是一個下限。

因此，從 0Θ1 開始，通過將矩陣提高到我們希望的輪數并計算概率。例如我們將矩陣冪 3 次，那么得到的矩陣中的數字就是符碼在轉換 3 次以后變成對應新符碼的概率。因此，我們可以測量k輪后也不失敗的概率。

之前，我們通過實驗驗證了，如果經過 20 輪 Curl-P-27（即調用20次f）轉換仍保持單符碼差異，那么碰撞的概率是1.0。使用我們的狀態轉移矩陣，我們計算20輪，我們的攻擊有一個每個查詢成功概率下限為 2-42。也就是說，我們需要嘗試242次才有可能找到將差異保持到20輪以后的消息對，這樣的消息對可以產生碰撞。在下一節中，我們將展示如何顯著減少對 Curl-P-27 的必要查詢次數。

4.2差分求解

在本節中，我們將展示如何通過選擇具有特定屬性的消息來減少 Curl-P-27 的查詢次數。我們首先展示如何約束有一位差異符碼的狀態 S 和 S‘，使得他們需要至少9次遞歸才能保持一位的差異（即差異沒有擴散）。為此，我們將f表示為方程組，并求解狀態S和S’中的特定值。

我們可以將變換函數f r(S) 表示為一系列方程。例如，調用一次 f 可以寫為

f (S)0 = g(S0,S364),f (S)1 = g(S364,S728),...,f (S)728 = g(S365,S0)

其中f (S)0是調用f后獲得的新狀態的第0位的數字。由于每一輪只是f的遞歸應用，我們可以根據狀態S的初始值在f輪后寫出特定位的值。我們使用上標來表示輪次。例如，用

f 2(S)6 = g(g(S366,S1),g(S184,S548))

表示在位置6進行兩次遞歸運算。

使用這種表示，我們找到可以使得 0Θ1 的差異保持9輪的方程。然后我們找到滿足這些方程的消息前綴。 目前，我們可以在一秒之內查找到此消息前綴（有關我們的性能評估，請參見第 5.3 節）。 另外，給定一個特定的消息模板，我們只需要在兩個消息塊中更改一小組三進制位，便可以將其轉換為令人滿意的消息。

4.3 尋找碰撞

攻擊需要至少3個信息塊：mba, mbb, 和 mbc。其中mbb含有一個差異符碼。mba前面的消息塊數量沒有限制，mba和mbb之間也沒有，mbc總是跟在mbb之后并且重寫mbb在前三分之一制造的差異。mbc的取值不會對攻擊造成影響，可以取任意值。

完整的攻擊過程如下。首先，在我們攻擊的約束階段，我們通過調整mba和mbb來找到合適的消息前綴，這樣它們可以保證 9 輪的單位符碼差異。 接下來，在蠻力階段，我們在mbb中的特定位置隨機改變符碼，目的是找到兩個消息，使得從位置 17 開始的差異保持 20 輪。 由于約束階段確保蠻力階段的每次嘗試在 9 輪中保持單符碼差異不同，因此蠻力階段的攻擊復雜性從 20 輪減少到 11 輪。 結果，每個查詢的成功率的下限減少到大約2 -22.87或 760 萬分之一。

正如差分密碼所分析的，我們的概率計算簡化了假設，即輸入值是均勻隨機的。考慮到 Curl-P-27 的低擴散率和Curl-P 的非隨機性，這種假設可能不會總是成立。 但是，如第 5.3 節所示，本節給出的界限與實際結果相當接近。

5 利用Curl-P中的碰撞來偽造簽名

本節中，我們將使用Curl-P-27碰撞對IOTA簽名方案（ISS）執行簽名偽造攻擊。結合上一節的內容，我們將展示如何創建兩個有效的IOTA bundle（即支付），這兩個bundle最多只有兩位不同，并且他們具有相同的Curl-P-27哈希值。然后，我們將描述攻擊的設置，利用這些碰撞的 bundle 來偽造簽名。最后，我們將展示如何攻擊ISS多重簽名。

5.1 對ISS的選擇消息攻擊

我們的攻擊是一種選擇消息攻擊，惡意用戶 Eve 欺騙用戶Alice，先是要求Alice簽署b1，然后根據b1生成相應的b2，這個b2也能通過驗證。具體過程如下：

  1. Alice生成密鑰對（PK, SK）。

  2. Eve通過碰撞攻擊產生兩個bundle b1，b2，并使得 b1 ≠ b2 且 CurlHash（b1）= CurlHash（b2）。

  3. Eve將b1發送給Alice并要求Alice簽名。Alice檢查b1，確認它是安全的。

  4. Alice在夏娃上給b1簽名，即Sign（SK, b1）→ σ。

  5. Eve產生一個bundle對（σ，b2），使得 b1≠b2，b2是一個有效的 bundle，就算 Alice從未見過b2，b2也能夠通過Alice的公鑰驗證。

在4.3節中，我們介紹了攻擊的一般格式，它至少需要三個消息塊 mba，mbb和mbc。 為了執行攻擊的第一階段，我們將 mba 和 mbb 中的某些特性設置為特定值。 在暴力階段，我們每次嘗試更改 mbb 中的其他符碼并檢查我們是否已經實現了碰撞。 但是，bundle必須通過 IOTA 軟件中的有效性檢查才能被 IOTA 視作有效bundle，這限制了我們可以修改的位數。

要想計算 bundle 的哈希，需要對每個交易的地址，值，標記，時間戳，當前字節和最后字節的串聯結果計算哈希值。交易的格式如圖4所示。大多數字段的格式都有嚴格的規范格式。例如，bundle 中值的求和結果不能為負，時間戳必須在一定范圍內，并且索引必須與 bundle 中的交易對齊。標簽不會影響 bundle 的語義或有效性，并且可以包含任意的符碼。因此，對于約束階段和暴力階段中的每次嘗試，我們只更改 tag 中的符碼。

另一個重要的問題是要在哪里生成碰撞。在最初的漏洞報告中，我們展示了兩種不同攻擊方式的碰撞 bundle：一種將碰撞置于地址范圍內，使得 Alice 無意中簽署了一項交易，該交易將取走 Eve 的資金，Eve 可以聲明 Alice 犯了一個錯誤。第二次將兩個碰撞放在一個 bundle 中的兩個地方，導致 Alice 無意中簽署了一個交易，該交易比預期更多地支付 Eve。在下一節中，我們將詳細描述需要多個簽名的 bundle 的后一種攻擊方式，這些簽名是我們選擇的消息設置。

5.2 多重簽名攻擊

我們在漏洞報告[20]中偽造的攻擊是選擇消息攻擊，也就是說，Eve必須要求Alice簽署bundle。為了證明保障被簽署消息的安全性有多么重要，我們現在將攻擊擴展到 IOTA 多重簽名方案[28]。在多重簽名中，只有在多方簽名以后才可以支出資金。為了達到這個目的，一方創建一個bundle并要求另一方簽名，這便是選擇消息攻擊。 IOTA基金會鼓勵部署熱存儲/冷藏解決方案5，以達到使用多重簽名來安全存儲資金[12]的目的。多重簽名迫使攻擊者必須使多方妥協，這是它被使用在加密貨幣環境中的一個主要原因。我們的攻擊恰好消除了多重簽名的這種安全優勢。我們將考慮一個2-of-2 的簡單案例，其中兩方都簽署了花費資金。這個攻擊還會推廣到更復雜的設置。

考慮 Eve 和 Alice 各持一對 ISS 密鑰：（PKE， SKE）和（PKA，SKA），只有Eve的密鑰簽名和Alice的密鑰簽名同時存在才能取出資金。這意味著Eve和Alice之前已經進入了 2-of-2 的多重簽名，并且現在正共同使用這筆資金。我們的攻擊將做如下工作：Eve將計算兩個相互碰撞的bundle，一個向Alice支付資金，另一個向Eve支付資金。 Eve將簽署并發送bundle給Alice，這個bundle負責向Alice支付資金。一旦Eve擁有 Alice 的簽名，她就會在創建一個Alice從未見過或未授權的有效bundle，并且廣播這個bundle.6。在此設置中，Eve要么是惡意的，要么已被惡意方攻擊。

為了構造這樣的bundle，Eve將碰撞置于某個碰撞的某個value字段。圖5顯示了bundle的前四個消息塊。突出顯示的字段與攻擊相關。通過在碰撞前后操縱標記字段中的特征，Eve導致第二交易（消息塊3）中的value字段的第17位發生碰撞。這樣，Eve可以在第二個交易中生成兩個不同的bundle，這些值具有相同的哈希值。 Eve隨后在第四個交易（消息塊7）中生成了第二個碰撞，這次使兩個bundle的值仍然總和為零。這用于設置向誰支付多少金額。

為了生成這些碰撞，一般需要我們按順序進行兩次攻擊。在我們當前的碰撞工具中，我們在兩個交易之間還需要一個交易。滿足了這個要求，以及沖突不在第一個或最后一個交易中的要求，我們就可以處理具有不同數量的交易的bundle。我們的工具只能在消息塊的第17位中產生碰撞，不過這是工具的限制，而不是因為第 4 節中的密碼分析有誤。我們的工具在生成碰撞時不依賴于交易中特定的地址和值，但是必須保證對應位的符碼不同才能產生有效的bundle。例如，如果在 b1 中 Alice 和 Eve 的輸出值的 17 位為零，那么在b2中將Eve的輸出值的17位變為1會導致b2的總和不為0。在 b1 中，Alice 的輸出值的第 17 位應為1，Eve的應為零。

在附錄B中，我們展示了使用此技術創建的兩個示例bundle。其中bundle為支出500,000,000 IOTA貨幣，由Alice和Eve控制。Alice麗絲簽了一個bundle，它支付Eve 1 IOTA，其余的支付給其他地址。在碰撞的bundle中，Eve收到 129,140,164 IOTA貨幣，支出地址為Alice的地址。

碰撞單簽名bundle的生成方式與此類似。我們在漏洞報告中偽造了bundle的簽名，其向三個地址進行支付。在良性bundle b1中，Alice在她控制的兩個地址收到 50,000 和 810,021,667 IOTA 貨幣并向Eve支付100 IOTA貨幣。在惡意bundle b2 中， Eve進行了調整并且收到了 129,140,263 IOTA貨幣，這些是Alice的錢。我們還沒有研究在value和address字段之外制造碰撞會帶來哪些影響，可能會生成其他攻擊。

5.3 性能分析

我們在 64 位Linux 4.9.74 環境下，使用一臺配備了 8 個 2.4GHz 10 核 Intel 芯片和 256 GB RAM 的 Intel 機器運行此攻擊。 我們的攻擊占用了全部的 CPU，但占用的 RAM 空間可以忽略不計。 如第 4.3 節所述，碰撞包括兩個階段：約束階段計算約束集，而暴力階段在 tag 中產生隨機數以產生碰撞。

約束階段生成并求解十八個等式，前九輪 Curl-P-27 中的每一個都有兩個。 約束階段在 Python 中實現，并且是單核運行。 我們沒有嘗試優化第一階段。 表2 顯示了取第 17 位不同并且在第一階段運行 5000 次后所需要的平均，最小和最大時間。

表2 還顯示了強力階段的測試結果。該階段使用第一階段的符碼和模板來強制生成碰撞。因為這在 Go 中執行并且并行，因此我們需要使用服務器的所有 80 個核。 使用第一階段的輸出生成碰撞平均只需7.2秒。 一次碰撞平均需要測試 520 萬次，最小和最大嘗試次數分別超過 5000 次 1279 和 53M。 這證實了我們在4.3節中的分析。

為了實現第 5.2 節中描述的多重攻擊，我們必須順序地運行約束和強制階段，以生成兩次碰撞。 我們的碰撞工具平均 15.2 秒就可以生成兩個多重簽名的bundle。 表2 顯示了各階段運行5000次所對應的平均時間以及最小和最大時間。

6 討論

IOTA開發人員對漏洞的產生原因及其影響有過多次聲明，我們對其進行了總結，并對部分問題作出了回應。

IOTA開發人員認為我們的攻擊模型與IOTA網絡環境沒有聯系：具體來說就是，我們無法設置被簽署過的消息，因為“在IOTA中，攻擊者不會選擇簽名過的消息“[5]。為了應對這個問題，我們將攻擊擴展到多重簽名地址，因為多重簽名協議明確允許一個用戶選擇另一個用戶簽名的消息。

IOTA的開發人員還認為，”即使是大多數有效的攻擊“都會在IOTA網絡中失敗，因為在閉源協調員中存在”保護機制” [5,13]。漏洞報告和本文中提出的攻擊只單純考慮如何應對IOTA簽名方案，未在完整的IOTA系統的環境中分析這些攻擊。

此外，他們聲稱 Curl-P-27 可以接受碰撞輸入是他們有意為之，其目的是防止克隆欺詐。其原話是：“IOTA 團隊故意引入 Curl-P 哈希函數，以此預防[克隆欺詐]，這還使得克隆欺詐無法用于 DLT 協議，同時保證了整個 IOTA 協議和網絡的安全。”他們認為 “協調員會保護IOTA網絡，不受故意引入的影響，并且稱之為“復制保護機制”[13]。這么看來，我們除了發現一個新型攻擊，似乎還發現了一個故意放置的后門。

7 結論

本文介紹了如何通過偽造消息簽名來攻擊IOTA簽名方案。我們在兩條消息只有一位字符不同的情況下構造了全狀態碰撞。并且運用這個方法創建了兩個有效的IOTA bundle，這樣，就算兩個bundle互不相同也仍然會映射到相同的值，也就是同一個簽名將適用于兩個bundle。 作為示例，我們在bundle中設置了不同的符碼，攻擊者可以在幾十秒內使用簡單的設備生成符合要求的bundle。

8 致謝

在此我們對 Andy Sellars, Weijia Gu, Rachael Walker, Joi Ito, Vincenzo Iozzo, Sharon Goldberg, and Ward Heilman 致以感謝，感謝你們對此論文的指導與建議。

9 References

[1] Mihir Bellare and Phillip Rogaway. “The exact security of digital signaturesHow to sign with RSA and Rabin”. In: International Conference on the Theory and Applications of Cryptographic Techniques. Springer. 1996, pp. 399– 416.
[2] Guido Bertoni et al. “On the indi?erentiability of the sponge construction”. In: Lecture Notes in Computer Science 4965 (2008), pp. 181–197.
[3] Eli Biham and Adi Shamir. “Di?erential cryptanalysis of DES-like cryptosystems”. In: Journal of CRYPTOLOGY 4.1 (1991), pp. 3–72.
[4] Bit?nex. IOTA Protocol Upgrade August 08, 2017. https://www.bitfinex.com/posts/215, archived at https://web.archive.org/web/20180722235151/ https://www.bitfinex.com/posts/215.
[5] Tangle blog. Full Emails of Ethan Heilman and the Digital Currency Initiative with the IOTA Team Leaked. http://www.tangleblog.com/wpcontent/uploads/2018/02/letters.pdf, archived at https://web. archive.org/web/20180228182122/http://www.tangleblog.com/wpcontent/uploads/2018/02/letters.pdf, https://archive.is/6imWR.
[6] Bosch. Press release: Robert Bosch Venture Capital makes ?rst investment in distributed ledger technology. https://www.bosch- presse.de/pressportal/de/en/robert-bosch-venture-capital-makesfirst-investment-in-distributed-ledger-technology-137411.html, archived at https://web.archive.org/web/20180724022550/ https://www.bosch-presse.de/pressportal/de/en/robert-boschventure-capital-makes-first-investment-in-distributed-ledgertechnology-137411.html.
[7] Crypt Brie?ng. First VW IOTA Product Will Be Released Early Next Year. https://cryptobriefing.com/vw-iota-product-released/, archived at https://web.archive.org/web/20180724021409/https: //cryptobriefing.com/vw-iota-product-released/.
[8] Coindesk. City of Taipei Con?rms It’s Testing IOTA Tech for ID. https://www.coindesk.com/city-of-taipei-confirms-its-testing-iotablockchain-for-id/.
[9] CoinmarketCap. CoinmarketCap IOTA July 23 2018. https://coinmarketcap. com/currencies/iota/, archived at https://web.archive.org/web/ 20180724020019/https://coinmarketcap.com/currencies/iota/.
[10] Michael Colavita and Garrett Tanzer. “A Cryptanalysis of IOTA’s Curl Hash Function”. In: (2018).
[11] Don Coppersmith. “The Data Encryption Standard (DES) and its strength against attacks”. In: IBM journal of research and development 38.3 (1994), pp. 243–250.
[12] IOTA Foundation. IOTA Guide – Generating Secure Multisig Addresses (hot and coldwallet). https://domschiener.gitbooks.io/iota-guide/content/exchange-guidelines/generating-multisignature-addresses.html, archived at https://archive.is/087kP.
[13] IOTA Foundation. O?cial IOTA Foundation Response to the Digital Currency Initiative at the MIT Media LabPart 4 / 4. https://blog.iota.org/official-iota-foundation-response-to-the-digitalcurrency-initiative-at-the-mit-media-lab-part-4-11fdccc9eb6d, archived at http://web.archive.org/web/20180727155405/https://blog.iota.org/official-iota-foundation-response-to-thedigital-currency-initiative-at-the-mit-media-lab-part-411fdccc9eb6d?gi=4be3ca82ed48.
[14] IOTAledger (github). IOTA Kerl speci?cation. https://github.com/iotaledger/kerl/blob/master/IOTA-Kerl-spec.md, archived at https://web.archive.org/web/20180617175320/
https://github.com/iotaledger/kerl/blob/master/IOTA-Kerl-spec.md. 2017.
[15] Oded Goldreich. Foundations of Cryptography: Basic Applications. Vol. 2. New York, NY, USA: Cambridge University Press, 2004.
[16] Guang Gong and Shaoquan Jiang. “The editing generator and its cryptanalysis”. In: International Journal of Wireless and Mobile Computing 1.1 (2005), pp. 46–52.
[17] Leon Groot Bruinderink and Andreas Hu¨lsing. ““Oops, I Did It Again” – Security of One-Time Signatures Under Two-Message Attacks”. In: Selected Areas in Cryptography – SAC 2017. 2018, pp. 299–322.
[18] Bertoni Guido et al. Cryptographic sponge functions. 2011.
[19] Paul Handy. Merged Kerl Implementation. https://github.com/iotaledger/ iri/commit/539e413352a77b1db2042f46887e41d558f575e5, archived at https://archive.is/jCisX.
[20] Ethan Heilman et al. IOTA Vulnerability Report: Cryptanalysis of the Curl Hash Function Enabling Practical Signature Forgery Attacks on the IOTA Cryptocurrency.
[21] Jonathan Katz and Yehuda Lindell. Introduction to Modern Cryptography. Second Edition. CRC Press, 2014.
[22] Leslie Lamport. Constructing digital signatures from a one-way function. Tech. rep. Technical Report CSL-98, SRI International Palo Alto, 1979.
[23] Willem Pinckaers (Lekkertech). IOTA Signatures, Private Keys and Address Reuse? http://blog.lekkertech.net/blog/2018/03/07/iotasignatures/, archived at https://archive.is/CnydQ. 2018.
[24] Arjen K. Lenstra, Xiaoyun Wang, and Benne de Weger. Colliding X.509 Certi?cates. Cryptology ePrint Archive, Report 2005/067. https://eprint. iacr.org/2005/067. 2005.
[25] Ralph C Merkle. “A certi?ed digital signature”. In: Conference on the Theory and Application of Cryptology. Springer. 1989, pp. 218–238.
[26] Serguei Popov. “The tangle”. In: cit. on (2016), p. 131.
[27] Ralf Rottmann. IOTA Reclaim Identi?cation Veri?cation Process. https://blog.iota.org/iota-reclaim-identification-verificationprocess-e316647e06e6, archived at https://web.archive.org/web/ 20180710000243/https://blog.iota.org/iota-reclaim-identificationverification-process-e316647e06e6?gi=b8190e111e7f.
[28] Dominik Schiener. IOTA Multi-Signature Scheme. https://github.com/ iotaledger/wiki/blob/master/multisigs.mdIOTA Multi-Signature Scheme. 2017 (accessed February 3, 2018).
[29] Yonatan Sompolinsky and Aviv Zohar. “Secure high-rate transaction processing in bitcoin”. In: International Conference on Financial Cryptography and Data Security. Springer. 2015, pp. 507–527.
[30] Marc Stevens, Arjen Lenstra, and Benne de Weger. “Chosen-Pre?x Collisions for MD5 and Colliding X. 509 Certi?cates for Di?erent Identities”. In: Advances in Cryptology – EUROCRYPT 2007. Springer. 2007, pp. 1–22.
[31] Marc Stevens et al. “Short Chosen-Pre?x Collisions for MD5 and the Creation of a Rogue CA Certi?cate”. In: Advances in Cryptology – CRYPTO 2009. Springer, 2009, pp. 55–69.
[32] David Snsteb. Upgrades & Updates. https://blog.iota.org/upgradesupdates-d12145e381eb, archived at https://web.archive.org/web/ 20180722232608/
https://blog.iota.org/upgrades-updates-d12145e381eb?gi=51123f82db22.
[33] Eric Wall. IOTA is centralized. https://medium.com/@ercwl/iotais-centralized-6289246e7b4d, archived at https://web.archive.org/web/20180616231657/https://medium.com/@ercwl/iota-iscentralized-6289246e7b4d. 2017.
[34] Xiaoyun Wang and Hongbo Yu. “How to Break MD5 and Other Hash Functions”. In: Advances in Cryptology – EUROCRYPT 2005. Springer. 2005, pp. 19–35.
[35] Xiaoyun Wang et al. Collisions for Hash Functions MD4, MD5, HAVAL128 and RIPEMD. Cryptology ePrint Archive, Report 2004/199. https://eprint.iacr.org/2004/199.2004.

Paper 本文由 Seebug Paper 發布，如需轉載請注明來源。本文地址：http://www.bjnorthway.com/1015/