Wintermute 遭黑客攻擊損失 1.6 億美金背後密碼技術詳解

作者：Max @ Safeheron Team

從最近的黑客攻擊說起

9 月 20 日，數字資產做市商 Wintermute 首席執行官 Evgeny Gaevoy 宣布其 DeFi 相關業務遭到黑客攻擊，損失約 1.622 億美元，疑因其合約地址「私鑰」遭到暴力破解，引發強烈的市場反響。無獨有偶，9 月 19 日，據 The Block 報導，一名黑客利用 Profanity 漏洞從多個通過 Profanity 建立的以太坊地址中盜取 330 萬美元資產。

Safeheron 密碼學安全團隊跟進分析發現，Wintermute 合約地址採用 Profanity 開源庫生成，而該類 0x000000 開頭的靚號地址，存在被暴力破解的可能性。此前 1inch 曾發文披露該漏洞潛在的安全威脅， 那麼，這一系列攻擊究竟是怎麼發生的呢？靚號地址生成開源庫 Profanity 在其中又起到什麼作用呢？接下來，Safeheron 團隊將從以下幾個方面，硬核還原靚號地址被攻擊的全技術過程。

  • 什麼是靚號地址？
  • Profanity 的靚號地址生成原理
  • Profanity 的理想安全性
  • 直覺上 Profanity 存在的問題
  • Profanity 算法的形式化描述
  • 靚號地址的私鑰攻擊原理
  • 靚號地址的私鑰攻擊示例
  • 攻擊效率分析
  • 安全改進建議
  • 進一步思考

什麼是靚號地址？

所謂靚號地址，是加密貨幣生態中的很多參與者用以凸顯個性的一種方式。具體來說，它是指這樣的一些地址：

  • 開頭 8 個 8：
0x88888888bc27358faea388cdf91fa9b67606820
  • 開頭 7 個 0： 
0x0000000925e311792debae85befaa946200ffc67
  • 開頭指定單詞：
0xdead9b096ec34c35e45b5a2aab5337805916ac1e
  • 鏡像地址：
0x5b4d6554bd4d 89dfcd0bb0dcfd98 c3e73ab05f69

這些靚號地址不僅彰顯個性，也帶來一些其它的好處，比如方便記憶，讓人印象深刻，不容易錯判等等。

為生成這些靚號地址，開發者們提供各式各樣的開源生成工具，而 Profanity 就是以太坊生態中最著名的開源生成工具之一。下面我們將介紹 Profanity 的具體原理。

Profanity 靚號地址生成原理

Profanity 到底是如何生成靚號地址的呢？通過分析 Profanity 開源庫，可以整理出原理圖：

生成步驟如下：

  1. 獲取安全隨機數（從硬件或者熵池），作為偽隨機數算法 mt19937 的種子。
  2. 利用偽隨機數算法 mt19937 生成種子私鑰（Seed Private Key），然後計算出種子公鑰（Seed Public Key）。
  3. 調用 OpenCL 並行計算平台，調用基於種子公鑰（Seed Public Key）的多輪迭代算法，計算大量的候選公鑰（Candidate Public Key）和 eth 地址（Address）。
  4. 調用指定靚號篩選器，篩出靚號，並輸出靚號私鑰（Vanity Private Key）和靚號地址（Vanity Address）。

Profanity 庫支持並行計算架構，不僅靚號模式選擇多樣，而且生成效率極高，受到社區廣泛歡迎。然而這也為後面的攻擊埋下伏筆。

Profanity 的理想安全性

理想中的 Profanity 安全性有多高呢？我們一起來看看，如果需要暴力破解這樣一個靚號地址的私鑰，到底需要多長時間。

0x88888888bc27358faea388cdf91fa9b676068207

我們可以大概評估一下總的計算次數。原始種子範圍是 ，開頭是 8 個 8，假設用戶選擇使用首次匹配地址，則需要計算次數為 次，而這已經是個不小的量級。

接著評估一下破解時間。以我本地電腦為例，計算首次靚號地址耗時平均大概是 10 秒（簡單三次評估），那麼暴力破解靚號地址私鑰需要耗時（以月計) 月。

如果使用並發加速，同時使用 1000 台跟我個人 PC 同配置的機器，則需要日夜不斷的跑 16 個月。

看起來，要暴力破解似乎也是非常困難的事情。那麼，是否真的安全麼？

直覺上 Profanity 所存在的安全風險點

乍一看來，調用安全隨機數，也進行大量計算，似乎沒有明顯的問題。可是黑客畢竟成功開展攻擊，那麼，問題究竟在哪裡呢？

直覺上看，Profanity 至少有兩大風險點：

  • 從硬件或者熵池獲取隨機數時，僅僅獲取 32 bit，這是非常短的。要知道，常見私鑰的長度是 256 bit，遠遠超出 32 bit。

在後續的並行多輪計算時，其迭代算法並非使用單向函數（比如 hash 函數）。單向函數會帶來更高的安全性，而不使用單向函數則意味著逆向追溯的可能。

單獨一個風險點未必會立刻致命，但是當兩個一起出現，則可能地覆天翻。

Profanity 算法的形式化描述

在描述攻擊原理之前，我們首先將整個 Profanity 原理抽像一下。

Step 1: 計算種子公鑰（Seed Public Key）

從隨機設備（Random Device）到種子公鑰，中間有兩步：

  • 獲取 32 bit 安全隨機數（從硬件或者熵池），作為偽隨機數算法 mt19937 的種子。
  • 利用偽隨機數算法 mt19937 生成種子私鑰（Seed Private Key），然後計算出種子公鑰。

對應 32 bit 安全隨機數，我們定義隨機種子空間， ；由於偽隨機數算法 mt19937 本質上是個確定性算法，因此種子私鑰的計算就是確定性的，種子公鑰的計算也是確定性的。如下所示：

為簡化表述，我們定義函數：

記種子公鑰集合為 ，那麼有：

顯然，種子公鑰的數量是 。

Step 2: 計算候選公鑰（Candidate Public Key）

Profanity 從種子公鑰開始進行並發多輪迭代（Iteration）操作，生成一系列的候選公鑰。整個迭代操作本質上是一個以指定種子公鑰為中心的公鑰搜索和遍曆算法。具體的，迭代是基於輪序號（，記為）和輪內序號（，記為 ) 兩個維度下的線性搜索操作。

迭代算法如下：

其中迭代偏移函數定義為：

其中 和 是兩個常數， 是橢圓曲線基點。

迭代計算的結果，備選公鑰集合可以定義為：

代入 定義，即： 其中 和 分別是輪序號上限和輪內序號上限，定義迭代搜索空間的大小。

   取不同的值，就會生成不同的備選公鑰集合。例如 ，則有：

注意: 根據迭代偏移函數定義，以下等式成立:  

Step 3: 過濾靚號

基於每個備選公鑰，計算 eth 地址。隨後使用模式過濾器，篩出靚號地址。這裡，我們把靚號地址所構成的集合記為 。

靚號地址的私鑰攻擊原理

現在我們考慮如何對上圖中的私鑰機制進行攻擊。

Step 1: 窮舉種子公鑰集合

種子公鑰集合 的元素個數上限也是 個，這不是個很大的數字，將其窮舉出來，整個集合 ，包括其對應私鑰，所佔存儲空間大概是 300 G，一台電腦就可以存儲下來。

Step 2: 計算真實靚號公鑰

找到靚號地址，從其線上任何一筆交易中的簽名，即可恢復出靚號公鑰，不妨設為 。

具體算法參見 https://en.wikipedia.org/wiki/Elliptic_Curve_Digital_Signature_Algorithm。

Step 3: 計算候選公鑰集合的一個平移集（Shift Set）

我們定義候選公鑰集合關於靚號公鑰 的一個平移集：

為了更好的說明，不妨假設有一個 3 輪、輪內迭代次數也是 3 的例子，以下是基於種子公鑰 的一個候選公鑰集合:

候選公鑰集合中的某個公鑰將被篩選出來為靚號公鑰，不妨設被選出來的靚號公鑰為:

下面將演示，如何通過求平移集合 來求出種子公鑰 ：

如圖所示，我們求出平移集合：

其包含靚號公鑰對應的種子公鑰 ，細心的人可以發現，靚號私鑰相對與種子私鑰的偏移為 。

Tips：

  • 為什麼命名為「平移集合」？這是因為平移集合和候選公鑰集合在二維空間中就是兩個矩陣，這兩個矩陣大小相等，可能相鄰，也可能有一部分元素重合。看起來，基於靚號公鑰，對候選公鑰集合做平移，即可得到平移集合。如下圖所示。
  • 為什麼求平移集合？因為平移集合中包括種子公鑰。比如上圖中的 就是種子公鑰。

Step 4: 集合求交

將平移集合的計算的迭代搜索範圍記為 ，用戶靚號公鑰當初的迭代坐標為 ，則有以下命題成立：

  • 命題：如果 ，   ，則基於靚號公鑰所計算的平移集合與種子公鑰集合一定存在交集。 

該命題保證一定能夠找到與靚號公鑰關聯的種子公鑰。

計算交集 。

交集中至少存在一個元素，它是一個種子公鑰，不妨記為 ，從 Step 1 預存的數據中能獲取對應的私鑰。由於 ，因此 相對於 的私鑰偏移 也在 Step 3 中記錄下來的，通過查詢可得。

以 Step 3 中為例，如上圖所示， 交集為 ，查詢可知種子公鑰相對於靚號公鑰的私鑰偏移 。

注意：集合求交很多不同的實現方法，比如數據量不大是可以直接通過查數據庫，如果數據量太大，可以結合一些成熟算法解決。

Step 5: 計算靚號私鑰

至此，可輕易計算出來靚號公鑰 的私鑰：

以 Step 3、Step 4 中的示例，可直接計算靚號私鑰：

靚號地址攻擊示例

現在我們通過一個具體的例子，來展示如何獲取靚號地址的私鑰。待破解的靚號地址如下，這是一個以「dead」單詞開頭的地址：

0xdead9b096ec34c35e45b5a2aab5337805916ac1e

Step 1: 窮舉種子公鑰集合

預生成種子公鑰集合 並存儲起來，注意此時所有種子公鑰對應的私鑰也同樣存儲了。

Step 2: 計算真實靚號公鑰

找到該地址的鏈上交易，從簽名中恢復公鑰，如下所示：

0x0488dff9528cc2fc582e11688abce90cd84d8c805424fa3c761f50ad96b877a8cf3c3b0796ec099a05403562a4e0f8ecec9c511265e12ae45793bad11111e11e4d

Step 3: 計算候選公鑰集合的一個平移集（Shift Set）

記 為 Step 2 得到的公鑰，指定 。

此時平移集合元素個數為： ，這是一個很小的集合，也意味這很小的搜索空間。

計算平移集合：

其中  

Tips:

  1. 計算平移集合的過程中，平移集合中所有元素（即公鑰點）相對於靚號公鑰的偏移也被記錄下來。
  2. 關於平移集合的 ， 參數的選擇，可以根據"靚號地址” 的難度來設計平移集的大小。

Step 4: 集合求交

計算 與 的交集，得到集合 。

集合中的種子公鑰 為： 

0x04f316acd6890440bb7ed841e9c9d0a69dbd3545ef390947ad55248cd90719ff84e897f3359caf934fc2d6835f02038a00305aa2f823376e963afe42cfa159384c

通過查詢預存儲信息，可以獲取對應的種子私鑰 為：

0x045c2f14d04b94b99f64c1c36e984311d2fdb49c9b39f8aa272b92da72e323e0

由於 ，因此 相對於 的私鑰偏移也在 Step 3 中記錄下來的，查詢可得：

Step 5: 計算靚號私鑰 

  從靚號私鑰計算靚號公鑰，用於復驗，複驗正確，至此攻擊成功結束。

攻擊效率分析

詳細分析

攻擊步驟一共 5 步，Step 2 和 Step 5 基本不耗時，Step 1 可以預先計算，所以也可以省去 Step 1 的耗時。最終，主要耗時都在 Step 3 和 Step 4。

為分析計算規模，我們可以定義候選公鑰集合計算的輪數上限為 ，輪內序數上限為 。

Step 4 中，需要解決兩個集合求交的問題，一個集合大小是 ，另一個集合大小為 。集合求交是一個成熟的問題，有一些成熟的解決方案，此處不必贅言。

著重說一下 Step 3，Step 3 是需要計算候選集合的一個平移，理想狀態下其規模跟候選公鑰集合一樣，因此計算次數為 。這是個什麼概念呢？它意味著，如果不考慮集合求交的耗時，私鑰破解耗時跟靚號地址生成耗時大致是一樣的。

Tips:

  • 平移集合的設計和計算方式直接影響到攻擊的效率。
  • 在實際攻擊操作時，由於候選公鑰集合是未知，我們可以根據靚號難度來估算候選公鑰集合的大小，從而設計平移集合。
  • 平移集合基數可能會略大於候選公鑰集合。

實例分析

我們給一些具體的例子，讓大家有個直觀的印象：

通過實驗觀察發現：大部分時候，對於 Profanity 中指定模式下的前 2～3 個靚號地址，輪序號小於 ，輪內序號小於 。這表明著大部分的平移集合的基數（元素總數），意味著，大部分時候，你最多只需要進行 6 千萬次窮舉就能完成破解。

還有不少的情況，平移集甚至只有百萬量級大小，更是反手可破。

效率總評

基本結論是攻擊效率極高，不用付出太高的代價，就能破解幾乎所有的 Profanity 靚號地址私鑰。

  • 如果不考慮集合求交的耗時，私鑰的破解速度可以逼近靚號地址的生成速度，這是非常可怕的，完全摧毀 Profanity。
  • 用戶的不好的使用習慣會大大提升私鑰破解的風險，一般來說，Profanity 越早生成出來的地址，搜索空間越小，風險越大，越容易破解。由於大部分用戶都喜歡用最早生成出來的幾個靚號地址，導致大部分 Profanity 用戶的靚號地址私鑰隨時可能被破解。

Profanity 的安全改進建議

主要是兩點建議：

  • 從硬件或者熵池獲取隨機數作為種子時，直接取出 256 bit。
  • 並行多輪迭代計算時，使用單向函數（比如 hash 函數）。

進一步思考

如果 Profanity 算法中生成候選公鑰時使用單向函數，算法是否安全？

答案是否定的。生成備選 Public Key 使用單向函數，確實能防止本文中提出的攻擊方法，但是它不能阻止生日攻擊。因為種子長度為 32bit 那麼碰撞概率 50% 時， 。這說明如果選擇同樣的靚號策略，只要 Profanity 的用戶數接近 8 萬，就有 50% 的概率生成重複私鑰。

如果隨機種子的長度提高到 64 bit，我們是不是就能用呢？

答案是否定的。64 bit 並不是足夠長的隨機數，同樣存在生日攻擊的問題，只不過 50% 碰撞概率的人數提高到大約 50 億而已，這依然不夠安全。

我們還能使用靚號麼？

首先，Profanity 生成的靚號地址都存在致命的風險，因此我們強烈建議，所有的 Profanity 用戶都應該將資產轉移到其它安全的地址上。其次，我們還是可以使用靚號地址的。並不是所有的靚號地址都有問題，如果不一味強調效率，選擇用更安全的算法來計算，那麼就能生成安全的靚號地址。

關於私鑰的安全生成有什麼更好的建議？

私鑰就是隨機數，要想讓私鑰足夠安全，就要足夠隨機。獲取安全隨機私鑰的方法多種多樣。

  • 如果有經過認證的安全硬件，可以使用安全硬件提供的安全隨機數。
  • 對於足夠複雜的運算平台，包括常見的各類 PC 和移動端，環境噪聲足夠複雜，使用平台自帶的熵池和偽隨機數發生器便已足夠隨機。
  • 如果是簡單平台，比某些硬件錢包，則需要從外部導入隨機種子。方式包括不限於導入隨機文件、環境照片、語音、視頻等等。
  • 還有一種更安全的方式，通過 MPC 聚合多平台的隨機性。基於 MPC 從多平台生成私鑰分片，即便單平台私鑰不夠隨機或者遭遇黑客攻擊，整個 MPC 錢包私鑰依然是安全的。

免責聲明：作為區塊鏈信息平台，本站所發布文章僅代表作者及嘉賓個人觀點，與 Web3Caff 立場無關。本文內容僅用於信息分享，均不構成任何投資建議及要約，並請您遵守所在國家或地區的相關法律法規。