本文總結了 Profanity 的漏洞成因，同時分析了對這類隨機性問題的破解可能性。
作者： Johan
近日，Wintermute 錢包遭攻擊損失約 1.6 億美元，被盜原因是 Wintermute 為了節省 Gas 費使用了 Profanity 來創建 Vanity 錢包（開頭 0x0000000），此前去中心化交易所聚合器 1inch 發布了一份安全披露報告，聲稱通過名為 Profanity 的工具創建的某些以太坊地址存在嚴重漏洞。慢霧安全團隊對此事件進行了深入分析，並分享給大家。
橢圓曲線加密（ECC）是區塊鏈領域最常用的加密算法，ECC 是一個加密算法大類，它包含了多種不同的曲線和加密算法，例如 secp256k1/secp256r1/ed25519/schnorr 等，比特幣和以太坊都是使用 secp256k1 加密。
在使用以太坊時，我們首先會生成一個私人賬號（以 0x 開頭+ 40 字母），具體過程如下：
（1）生成一個不可預測的隨機數種子，通常基於系統的/dev/urandom 隨機發生器；
（2）利用隨機種子生成一個私鑰（256 位，32 字節）
（3）通過私鑰生成公鑰（64 字節）
（4）公鑰使用 keccak-256 哈希算法，取哈希值十六進製字符串後 40 個字母，開頭加上 0x 生成最終的以太坊地址。
特別記一下這些公私鑰的大小，因為它關乎我們後面要做的計算量。
這裡需要提的一個關鍵公式：
Q = kG
這是私鑰推導出公鑰的核心算法，私鑰推出公鑰計算很簡單，但反向推導幾乎不可能。
Q 是公鑰，k 是私鑰，k 由有限域內的大整數構成，相當相當大，以致於幾乎不可能去猜測，G 是橢圓曲線上的一個點，默認是一個固定的值，kG 就是 k 個 G 點相加（橢圓曲線的點相加不是簡單的實數相加，計算方法這裡不展開討論）。
如果我們想要窮舉以太坊賬號，找到 Vitalik 的私鑰，那麼在知道他的公鑰後，最多需要進行 2^256（2 的 256 次方）次的 Q = kG 計算，對大數字我們天然不敏感，所以我把它換算成工作量，就是目前一台蘋果 M1 電腦大概 40M/s 的速率，那麼大概需要的年份是 8 後面跟上 62 個零。一萬年太久，只爭朝夕。
有一些錯誤的私鑰生成方法，會導致私鑰的取值範圍變成更小範圍內的數值，變得可猜解。常見的原因有：
（1）隨機數種子不夠隨機，例如使用了時間戳做為隨機數種子，那麼我們只要窮舉過去一段時間所有的時間戳就能找到生成公鑰所用的種子和私鑰；
（2）軟件算法存在缺陷，導致隨機強度不夠（Profanity 正是存在這樣的缺陷）；
Profanity 的設計目的，是幫助人們生成一個具有特殊視覺效果的賬號，比如以特殊字符開頭或者結尾的賬號，另一方面，一些開發者使用它來生成開頭為很多個 0 的賬號，如 0x00000000ae347930bd1e7b0f35588b92280f9e75，它可以在調用智能合約時達到節省 Gas 的效果。
Profanity 為了更快地爆破出 Vanity Address，只在程序的開頭獲取了一次隨機數，後續所有的私鑰都是基於這個隨機數迭代擴展而來，我們來看一下它的隨機數生成算法：
Dispatcher.cppcl_ulong4 Dispatcher::Device::createSeed() {#ifdef PROFANITY_DEBUGcl_ulong4 r;r.s[0] = 1;r.s[1] = 1;r.s[2] = 1;r.s[3] = 1;return r;#else// Randomize private keysstd::random_device rd;std::mt19937_64 eng(rd());std::uniform_int_distribution<cl_ulong> distr;cl_ulong4 r;r.s[0] = distr(eng);r.s[1] = distr(eng);r.s[2] = distr(eng);r.s[3] = distr(eng);return r;#endif}
這裡使用了 random_device 來獲取系統提供的隨機數，這個隨機數源是滿足加密所需要的強度的。但是當我們注意到變量類型時，我們發現 rd() 返回的是一個 32 位長度的隨機值，上文我們提到一個私鑰是 256 位長度，那麼一次獲取隨機數的過程並不能填充整個私鑰，於是 Profanity 使用 mt19937_64 產生隨機數來填充整個私鑰。mt19937_64 和 random_device 的隨機算法有著本質的區別，mt19937_64 是確定性的，它的隨機性依賴於輸入的隨機數，並不產出新的隨機性。
也就是說，如果 rd() 傳遞給 mt19937_64 的值在某個範圍，那麼 distr(eng) 的值也在對應的某個範圍，createSeed 函數返回的 r 值自然也是在某一個範圍。
關鍵點來了： rd() 的所有可能性是 2^32，離私鑰的安全性（2^256）相差了 224 個數量級，但是 2^32 這個數量級也挺大的，那麼它需要多少計算量才能破解出私鑰？
Profanity 在獲取到第一個私鑰 SeedPrivateKey 以後，為了碰撞出需要的賬號地址，會通過一個固定的算法不斷跌代這個私鑰，最多 200 萬次（數值來源於 1inch 披露的文章），這個公鑰的計算方式可表示為：
PublicKey = kG = (SeedPrivateKey + Iterator)*G
Iterator 是一個遞增的數字，當 PublicKey 已知時，我們可以通過窮舉 SeedPrivateKey 和 Iterator 來得到 SeedPrivateKey，計算量大概為 2^32 乘以 200 萬次，在 1 台 M1 電腦上需要 60 多年時間，看上去這輩子有希望:D。如果我用大量算力更大的顯卡進行並行計算，那麼在幾天甚至幾個小時碰撞出想要的結果也完全可以。
剛好最近以太坊轉 PoS 共識，存在大量的閒置的顯卡算力，如果礦工拿顯卡來破解這個私鑰，那不是分分鐘就能成功？當然這個陰謀論沒有意義，我們只想研究破解的可能性。我們更希望能用不那麼暴力的方法來解開私鑰。
我們稍微移動一下等式兩邊，對上面的公式進行變換，可得：
SeedPrivateKey*G = PublicKey - Iterator*G
我們可以思考另一種攻擊方法，如果首先預計算 SeedPrivateKey*G，需要最多 256 G 左右的內存空間去存儲計算結果，在一台普通的服務器上完全可以做到，所需要的計算是 2^32 次，大概幾十分鐘就可以完成。然後我們再把需要破解的 PublicKey 代入等式右邊，然後對 Iterator 跌代碰撞，所需要的計算量大概是 200 萬次，還有 200 萬次的查表，所需要的時間是秒級。這，就有意思了，原來 32 位的隨機數是這麼的微不足道，任何人都有可能在幾十分鐘內還原出私鑰。
至此，我們總結出了 Profanity 的漏洞成因，是由於未對 256 位私鑰進行足夠隨機播種，導致私鑰取值範圍嚴重降低。同時也分析了對這類隨機性問題的破解可能性，希望能給大家一些啟發。
免責聲明：作為區塊鏈信息平台，本站所發布文章僅代表作者及嘉賓個人觀點，與 Web3Caff 立場無關。本文內容僅用於信息分享，均不構成任何投資建議及要約，並請您遵守所在國家或地區的相關法律法規。
