技術的突破是推動區塊鏈行業前進的引擎,幣安中國區塊鏈研究院與鏈聞 ChainNews 同爲密切關注區塊鏈與密碼學等領域技術發展前沿的組織,故而聯合推出「他山之石」專欄,向中文世界讀者介紹全球範圍最值得關注的區塊鏈技術進展,以及在金融等產業最新的應用分析與動態,以期爲中國的區塊鏈行業「攻玉」提供借鑑和思考。

區塊鏈開發公司 Pyrofex CTO、密碼學專家 Mike Stay 講述他如何用 11 天時間幫助客戶找回丟失的比特幣私鑰。

撰文:Mike Stay,區塊鏈開發公司 Pyrofex CTO,谷歌前軟件工程師
翻譯:Chen Bo Yu、Hsu Tzu Hsiu

原文發表於 2020 年 4 月 3 日,彼時比特幣約 6918 美元,價值 30 萬美元即約 43 枚 BTC。

原本預想需要花費數十萬年、十萬美元建造 GPU 農場才能找回的比特幣密鑰,幸運地在短時間內被密碼學專家 Mike Stay 找回,或許奧地利經濟學派支持者、黃金支持者、比特幣反對人士 Peter Schiff 可以考慮聯繫一下 Stay 找回他丟失的比特幣。

大約二十年前,我在楊百翰大學 BYU 攻讀物理學學位的同時,也在 AccessData 公司做逆向工程和密碼分析師。當時是 90 年代末和 2000 年代初,美國政府已經逐漸放寬了對含有密碼學的軟件出口限制,但大多數軟件仍然包含着相當脆弱的密碼保護。我們會去買桌面辦公軟件,對它進行逆向工程,弄清楚它是用什麼算法進行訪問控制,然後破解密碼。這是一個有趣且永無止境但並非不可能的數學難題。我在那裏的時候寫了大約 40 個密碼破解器,我們會把它們賣給家庭用戶、系統管理員,以及地方和聯邦執法機構,我就去過了幾次位於 Glynco 的聯邦執法培訓中心,給特勤局、FBI 和 ATF 教授密碼學和我們產品的使用方法。

他山之石丨價值百萬美元的比特幣密鑰追回記Mike Stay,區塊鏈開發公司 Pyrofex CTO,谷歌前軟件工程師

從 Word 97 與 zip 的加密算法講起

在我的記憶中,有兩個項目讓我特別印象深刻。第一個是 Microsoft Word 97。在 Word 97 之前,文件的加密方式是用密碼衍生的 16 字節字符串對文件進行 xor 加密。Word 文件中最常見的字節通常是 0x00、0xFF 或 0x20 (空格),所以我們只需查看每列中最常見的字符,然後嘗試這些字符的 3^16 種可能組合。找回密鑰通常是瞬間的事,但爲了幫助人們覺得自己的錢花得值,我們會像好萊塢中出現的黑客場景一樣,用大量隨機字符上演一個小動畫,逐漸揭示破解出的正確密碼。

Microsoft Word 97 改變了這個加密算法。也許可以通過 MSDN 找出微軟使用的加密格式,但我們當時規模小,沒錢訂閱,也不清楚我們從他們那裏得到的信息是否足以讓我們寫出破解器。爲了弄清它的工作原理,我用 SoftICE 在輸入密碼後立即停止軟件,然後在堆棧上慢慢一步一步執行,直到找到加密算法。這都是在 IDA Pro 誕生

之前,所以我打印了幾十頁彙編代碼貼在牆上,用紅色蠟筆在上面畫滿了我的註記。當我終於把它的模式找出來的時候高興極了。當時微軟只允許輸出 40 位比特的密碼算法,所以他們在允許的範圍內做了很多事情:他們會用「鹽」(salt,隨機選取存儲在文件中的字節)反覆對密碼進行 MD5 哈希,得到 40 位的輸出,然後在此基礎上加鹽,再反覆哈希。在當時的電腦上運行這個過程測試一個密碼大概需要半秒鐘的時間,我們不得不採用字典攻擊的方式,因爲直接破解它幾乎是不可能的,我們最終也確實爲大公司和機構寫了一個破解器,利用 Intel Pentium 處理器上那些花哨的 MMX 指令集,強行破解了 40 位哈希值的組合。我聽說過有人花了九個月才破解了這個軟件。

另一個非常有趣的是 zip 檔案。PKZIP 的開發者 Phil Katz 做出了一個決定:將他的檔案格式記錄下來,並將其包含在他的軟件中,這在當時是很不常見的,這也因此使其成爲了開發者的最愛。Roger Schlafly 設計了用於加密壓縮檔案的流密碼,zip 標準也很快就成爲 Windows 上最流行的壓縮格式,許多其他格式如 Java 的 jar 檔案和 OpenOffice 的文檔格式,其實都是內部有特定目錄結構的 zip 文件。而 InfoZIP 是一個開源版本的軟件,它 zip 的實作方式幾乎被作爲其他所有知名壓縮軟件的基礎,比如 WinZip。在我當時試圖破解它的時候,WinZip 佔據了 95% 的市場。

Eli Biham 和 Paul Kocher 曾發表過對其密碼算法的已知明文攻擊,但已知明文通常就是壓縮明文中的一部分,要想透過一個 zip 加密壓縮文件獲得壓縮明文,你基本會上需要整個文件,所以這種攻擊對執法機構來說幾乎是無用的。

zip 的加密算法有 96 位比特的內部狀態,分成三個 32 位的小塊,分別稱爲 key0、key1 和 key2。而 key0 和 key2 是兩組線性反饋移位寄存器 CRC32 算法的內部狀態,如果要用一個新的數據字節更新狀態,你要將所有的字節向下移動一個字節(捨棄低字節),然後與查找表中的一個常數進行 xor 操作,這個常數在查找表中的索引是被捨棄低字節與該數據字節 xor 後的結果。key1 是截斷線性同餘方法(linear congruential generator)的內部狀態,要更新它的內部狀態,輸入一個數據字節,乘以一個我稱之爲 c 的常數,然後加 1。而這個加密算法的工作原理是這樣的:你向第一個 CRC32 輸入一個數據字節,然後取其捨棄的低字節並將其輸入 TLCG,然後取其產生的高字節並將其輸入第二個 CRC32,然後取其狀態並(粗略地)平方,然後輸出結果的第二個字節作爲流字節。最一開始的 96 位狀態是已知的,接着加密密碼,然後加密十個字節長的鹽(salt)。

PKZIP 通過直接分配未經初始化的內存來獲得它的 salt 字節,所以它可能實際上包含了你運行的其他程序上的一些內容,也可能是圖像或文檔等等。這在 Windows 上工作得很好,沒遇到什麼問題,但在許多 Unix 系統上,當內存被分配時它會自動初始化。InfoZIP 通過使用 C 語言的 rand 函數來選擇鹽字節,它將通過 xor 時間戳和進程 ID 來初始化隨機數生成器的狀態,然後爲每個文件生成 10 個字節。如果他們只有這樣做的話,那麼知道時間戳和進程 ID 後就足以恢復部分信息,接着就能夠發動 Biham 和 Kocher 的已知名文攻擊。看來 InfoZIP 的作者知道這種攻擊,因爲他們更進一步,用密碼對頭文件加密了一次。這樣一來,攻擊者就只有雙重加密的明文,他們的攻擊就無法得逞了。

我注意到由於兩次使用密碼都是一樣的,所以每次密碼的第一個流字節都是一樣的。就像電燈開關兩次操作會讓它停留在開始的地方一樣,用相同的數據流字節 xor 一個字節兩次會讓它回到初始狀態。這讓我可以發動一個非常強大且只針對密碼文本的攻擊:給定一個檔案中的五個加密文件,我可以推導出 C 的 rand 函數中的內部狀態,而無需查看時間戳或知道進程 ID 。這就得以讓我可以生成原始、未加密的頭文件。而因爲密碼的每一部分只有幾位影響下一部分,所以我也只能猜測狀態的幾位,並檢查兩次解密一個字節是否給了我預期的答案。隨着我的繼續,我需要猜測的內容越來越少,每一個額外的檔案也讓我排除了更多潛在的可能。當時這個過程在一臺臺式機上花了幾個小時。我之後發表了一篇關於這個攻擊的論文,並在 2001 年日本的快速軟件加密會議(Fast Software Encryption)上公開發表。

2002 年我離開了 AccessData,接着在一家神經網絡初創公司工作了一年,在奧克蘭大學和 Cris Calude 一起讀了三年計算機科學碩士,在加州大學河濱分校和數學物理學家 John Baez 一起讀博士,在 Google 的應用安全團隊工作了六年並完成了博士學業,又過了幾年,最後成爲一家初創公司的 CTO。

比特幣來敲門

大約半年前,我在 LinkedIn 上突然收到了一個俄羅斯人的消息。他看了我 19 年前寫的那篇論文,想知道攻擊是否能在只有兩個檔案的場景上發揮作用。我分析了一下後表示,沒有巨大的計算能力和大量的金錢是行不通的。因爲我只有兩個檔案可以使用,所以每個階段都會有更多的假設需要去計算驗證。最後會有 2^73 個可能的密鑰需要測試,將近 10^22 這麼大。我估計需要一個大型的 GPU 農場一年才能攻破,成本在 10 萬美金左右。可是他讓我大喫一驚,因爲他表示願意花這麼多錢來找回密鑰。

早在 2016 年 1 月,他就花了 1 萬或 1.5 萬美元買了左右的比特幣,並把密鑰放在一個加密的壓縮文件中。現在它們的價值高達 30 多萬美元,而他卻不記得密碼了。幸運的是,他還保留着原來的筆記本電腦,並且知道加密發生的確切時間。因爲 InfoZip 使用了時間戳作爲熵的種子,這就大大地減少了工作量,只需要 10^19 次測試,並使它變得相當可行,在一箇中等的 GPU 農場上只需要幾個月的時間。我們簽訂了合同,我就開始工作了。

我花了一會兒時間根據當初論文中的概述重建了這次的破解。令我懊惱的是,有一些棘手的細節在我撰寫論文時忽略了,不過我又順利把它們解決了。然而我發現我在估算工作時犯了一個可怕的錯誤!

在我最初的攻擊中,我會去猜測 key1*c、key1*c^2、key1*c^3 和 key1*c^4 的高字節。當我猜到第四個字節的時候,我已經知道了密碼其餘部分的完整狀態,我只需要把這四個字節轉換成原始的 key1 就可以了。我會嘗試在 key1 的 32 位空間中找出所有可能,並檢查每一個狀態是否給出了正確的高字節。不過在這裏,我有 10^19 個密鑰要檢查,如果我必須對每個密鑰進行 2^32 次測試,那就需要花上幾十萬年的時間。

我隱隱約約記得,曾經有人用晶格還原法對 TLCGs 進行過加密分析,於是我挖出了原始論文,發現實在是太完美了!我只需要定義一個由 2^32 和 TLCG 中的常數冪給定的基向量的網格,然後進行網格還原。給定了還原後的基數,我只要做一個矩陣乘法就可以從高字節中恢復原始狀態。

至少,這是我的想法。但我需要五個字節才能將其限制在單一結果上,而在攻擊的那個點上,我只有四個字節。根據論文中描述的過程這幾乎不會算出正確的答案。然而,我知道答案會很接近正確的答案,所以我跑遍了所有可能的 key1 值,並檢查它給我的答案和真實答案的差異,發現了差值總是 36 個向量中的其中一個!這就是我的優化,有了這個優化,我可以只運行 36 種可能性,而不是 40 億個。

接下來,我們遇到的是在機器上的 GPU 之間傳輸數據的問題。我的業務夥伴 Nash Foster 研究了 GPU 的實現,告訴我不同操作 GPU 操作的速度是多少,併爲了將加密破解代碼放入其中的應用程序編寫了很多支持結構。我們如何將這些 PB 級的候選密鑰送到 GPU 上進行測試?我突然想到,我的攻擊的每個階段都在猜測大量的比特,然後只在大約六萬五千個的候選密鑰中選定一個。如果我有某種方法能夠透過這些信息來推導比特,而不是僅僅去猜測和檢查,我就可以節省很多工作,更重要的是可以節省很多網絡流量。但這個想法的問題是數學太複雜了,它涉及到將有限域的數學和整數環的數學混合在一起,而這並不是什麼容易的事情。

我想了想我所知道的其他密碼攻擊,其中有一種似乎可以派上用場,那就是中間相遇攻擊。中間相遇攻擊適用於塊加密,當它使用一部分密鑰做前半部分的加密,而另一部分密鑰做後半部分的加密。這基本上適用於壓縮密碼,但密鑰的數量遠遠超過了中間的位數。後來我想到可以利用 CRC32 的線性優勢:把最後一個 CRC32 的兩個輸出 xor 在一起,結果就可以不受 key2 的影響了 ! 與其計算加密的中間狀態並將其存儲在表中,我不如計算兩個中間狀態的 xor 結果並將其存儲。

我寫出了差分的中間相遇攻擊,並在我的筆記本電腦上運行。之前在我的筆記本電腦上需要幾個小時的階段,現在只用了幾秒鐘就完成了。下一個階段,我預計在 GPU 農場上需要一週的時間,在強大的 CPU 上只用了幾個小時就完成了。我沒辦法讓它在第三階段計算得更快,以至於對加速整體攻擊有用,但它完全避免了移動數據的需要:我們只需在每個 GPU 的電腦上計算出候選組合並讓它們運算。Nash 編寫了 GPU 代碼,運行速度快得驚人。

攻擊運行了十天,失敗了。

我傷心極了。難道我們漏掉了哪些候選密鑰?我們回去看了看他筆記本上的最大進程 ID,發現它比我們預期的大了幾個位,因此 rand 還有其他幾個可能的初始種子。我還回去仔細檢查了我們所有的測試。是否有我們遺漏的東西?基於 CPU 的版本和 GPU 版本的表現有什麼不同嗎?我們的客戶重新運行了我們的測試,發現 GPU 版本在正確的答案排在候選列表中的第二位時,無法找到正確的密鑰,但在排在第一位的時候卻能找到。仔細研究代碼,我們發現我們在計算偏移到數據結構中的數據塊索引和線程索引時,將數據塊索引和線程索引互換了。

我們修復了這個錯誤,接着重新運行代碼,並在一天之內找到了正確的密鑰。我們的客戶非常高興,給了我們一大筆獎金,因爲我們很快就找到了密鑰,所花的費用遠小於最初的估計。

來源鏈接:reperiendi.wordpress.com