本文總結了Profanity 的漏洞成因，同時也分析了對這類隨機性問題的破解可能性。
By: 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_DEBUG cl_ulong4 r; rs[0] = 1; rs[1] = 1; rs[2] = 1; rs[3] = 1; return r;#else // Randomize private keysstd::random_device rd; std::mt19937_64 eng(rd()); std::uniform_int_distribution
這裡使用了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 位私鑰進行足夠隨機播種，導致私鑰取值範圍嚴重降低。同時也分析了對這類隨機性問題的破解可能性，希望能給大家一些啟發。
展開全文打開碳鏈價值APP 查看更多精彩資訊