怎樣的Hash算法能對(duì)抗硬件破解？

作者：EtherDream 2017-02-28 19:39:48

用過暴力破解工具 hashcat 的都知道，這款軟件的強(qiáng)大之處在于它能充分利用 GPU 計(jì)算，比起 CPU 要快很多。所以在破解諸如 WiFi 握手包、數(shù)據(jù)庫(kù)中的口令 Hash 值時(shí)，能大幅提高計(jì)算效率。

前言

當(dāng)然 GPU 仍屬于通用硬件，顯然還不是最優(yōu)化的。要是為特定的算法打造特定的硬件，效率更是高出幾個(gè)量級(jí)。比特幣礦機(jī)就是很好的例子。

硬件的仍在不斷進(jìn)步，系統(tǒng)安全等級(jí)若不提高，暴力破解將會(huì)越來越容易。因此，一種能抵抗「硬件破解」的 Hash 算法，顯得很有必要。

時(shí)間成本

在探討如何對(duì)抗硬件之前，先來講解過去是如何對(duì)抗「暴力破解」的。

一些經(jīng)典的 Hash 算法，例如 MD5、SHA256 等，計(jì)算速度是非常快的。如果口令 Hash 用了這類函數(shù)，將來攻擊者跑字典時(shí)，可達(dá)到非常高的速度。那些強(qiáng)度不高的口令，很容易被破解。

為了緩解這種狀況，密碼學(xué)家引入了「拉伸」的概念：反復(fù) Hash 多次，從而增加計(jì)算時(shí)間。

例如 PBKDF2 算法就運(yùn)用了這種思想。它的原理很簡(jiǎn)單，對(duì)指定函數(shù) F 反復(fù)進(jìn)行 N 次：

function PBKDF2(F, ..., N)  
...  
for i = 0 to N  
...  
x = F(x, ...)  
...  
...  
return x

這樣就能靈活設(shè)定 Hash 的時(shí)間成本了。例如設(shè)定 10000，對(duì)開發(fā)者來說，只是多了幾十毫秒的計(jì)算;但對(duì)于攻擊者，破解速度就降低了一萬倍!

時(shí)間成本局限性

PBKDF2 確實(shí)有很大的效果，但對(duì)于硬件破解，卻無任何對(duì)抗措施。

因?yàn)?PBKDF2 只是對(duì)原函數(shù)簡(jiǎn)單封裝，多執(zhí)行幾次而已。如果原函數(shù)不能對(duì)抗硬件，那么套一層 PBKDF2 同樣也不能。

例如 WiFi 的 WPA2 協(xié)議，就是讓 HMAC-SHA1 重復(fù)執(zhí)行 4096 次：

DK = PBKDF2(HMAC−SHA1, Password, SSID, 4096, ...)

雖然相比單次 Hash 要慢上幾千倍，但這并不妨礙硬件破解。

硬件依然可發(fā)揮其「高并發(fā)」優(yōu)勢(shì)，讓每個(gè)線程分別計(jì)算不同口令的 PBKDF2：

雖然耗時(shí)確實(shí)增加了很多倍，但并沒有影響到硬件的發(fā)揮。同樣的破解，效率仍然遠(yuǎn)高于 CPU。

所以，時(shí)間成本并不能抵抗「硬件破解」。

空間成本

單論計(jì)算性能，硬件是非常逆天的，但再綜合一些其他因素，或許就未必那么強(qiáng)大了。

假如某個(gè)硬件可開啟 100 個(gè)線程同時(shí)破解，但總內(nèi)存卻只有 100M —— 這顯然是個(gè)很大的短板。

如果有種 PBKDF 算法空間復(fù)雜度為 2M，那將會(huì)有一半的線程，因內(nèi)存不足而無法運(yùn)行!

若再極端些，將空間復(fù)雜度提高到 100M，那么整個(gè)硬件只能開啟 1 個(gè)線程，99% 的算力都無法得到發(fā)揮!

這樣，即使硬件的計(jì)算性能再?gòu)?qiáng)勁，也終將卡在內(nèi)存這個(gè)瓶頸上。

不過，怎樣才能讓算法消耗這么多內(nèi)存，同時(shí)又不能被輕易繞過?這里舉個(gè)簡(jiǎn)單的例子：

function MemoryHard(..., M)  
int space[M]  
for i = 0 .. 10000  
x = Hash(x, ...)  
space[int(x) % M] ^= int(x)  
return Hash(space)

當(dāng)然這個(gè)例子是隨意寫的，并不嚴(yán)謹(jǐn)。但主要思想是：

引入了空間成本 M，并申請(qǐng)相應(yīng)的內(nèi)存
利用經(jīng)典 Hash 函數(shù)的結(jié)果，作為數(shù)組索引，對(duì)內(nèi)存進(jìn)行讀寫
每次內(nèi)存讀寫，都會(huì)影響到最終結(jié)果

由于 Hash 函數(shù)的結(jié)果是不可預(yù)測(cè)的，因此事先無法知道哪些位置會(huì)被訪問。只有準(zhǔn)備充足的內(nèi)存，才能達(dá)到 O(1) 的訪問速度。

攻擊者要想達(dá)到同樣的速度，就不得不花費(fèi)同樣多的內(nèi)存!

時(shí)空權(quán)衡

通常硬件的「計(jì)算資源」要比「存儲(chǔ)資源」充足得多，因此可考慮「時(shí)間換空間」的策略 —— 使用更復(fù)雜的存儲(chǔ)管理機(jī)制，從而減少空間分配，這樣就能開啟更多的線程。

比如犧牲 40% 的速度，換取 50% 的空間：

由于空間成本是之前的一半，因此可多啟動(dòng)一倍的線程。算上折損，最終速度仍增加了 20%。

當(dāng)然，如果性能折損比例 > 空間壓縮比例，這個(gè)方案就沒有意義了。

訪問瓶頸

事實(shí)上，內(nèi)存除了容量外，訪問頻率也是有限制的。

就內(nèi)存本身而言，每秒讀寫次數(shù)是有上限的。其次，計(jì)算單元和內(nèi)存之間的交互，更是一大瓶頸。

像 MD5、SHA256 這類 Hash 函數(shù)，空間復(fù)雜度非常低。硬件破解時(shí)，每個(gè)計(jì)算單元光靠自身的寄存器以及高速緩存，就差不多夠用了，很少需要訪問內(nèi)存。

但對(duì)于 Memory-Hard 函數(shù)，就沒那么順利了。它不僅很占內(nèi)存，而且還十分頻繁地「隨機(jī)訪問」內(nèi)存，因此很難命中高速緩存。這使得每次訪問，幾乎都會(huì)和內(nèi)存進(jìn)行交互，從而占用大量帶寬。

如果有多個(gè)計(jì)算單元頻繁訪問，那么內(nèi)存帶寬就會(huì)成為瓶頸。這樣，也能起到抑制并發(fā)的效果!

例如 bcrypt 算法就運(yùn)用了類似思想，它在計(jì)算過程中頻繁訪問 4KB 的內(nèi)存空間，從而消耗帶寬資源。

不過隨著硬件發(fā)展，bcrypt 的優(yōu)勢(shì)也在逐漸降低。為了能更靈活地設(shè)定內(nèi)存大小，scrypt 算法出現(xiàn)了 —— 它既有時(shí)間成本，還有空間成本，這樣就能更持久地對(duì)抗。

當(dāng)然，空間成本也不是絕對(duì)有效的。如果攻擊者不惜代價(jià)，制造出存儲(chǔ)「容量」和「帶寬」都很充足的硬件設(shè)備，那么仍能高效地進(jìn)行破解。

并行維度

十幾年來，內(nèi)存容量翻了好幾翻，但 CPU 主頻卻沒有很大提升。由于受到物理因素的制約，主頻已很難提升，只能朝著多核發(fā)展。

然而像 PBKDF2 這樣的算法，卻只能使用單線程計(jì)算 —— 因?yàn)樗看?Hash 都依賴上一次的 Hash 結(jié)果。這種串行的模式，是無法拆解成多個(gè)任務(wù)的，也就無法享受多線程的優(yōu)勢(shì)。

這就意味著 —— 時(shí)間成本，終將達(dá)到一個(gè)瓶頸!

對(duì)此，多線程真的無能為力嗎?

盡管單次 PBKDF 不能被拆解，但可以要求多次 PBKDF，并且互相沒有依賴。這樣多線程就能派上用場(chǎng)了。

例如我們對(duì) PBKDF 進(jìn)行封裝，要求執(zhí)行 4 次完全獨(dú)立的計(jì)算，最后再將結(jié)果融合到一起：

function Parall(Password, Salt, ...)  
-- 該部分可被并行 --  
for i = 0 .. 4  
DK[i] = PBKDF(Password, Salt + i, ...)  
------------------  
return Hash(DK)

這樣，我們即可開啟 4 個(gè)線程，同時(shí)計(jì)算這 4 個(gè) PBKDF。

現(xiàn)在就能用 1 秒的時(shí)間，獲得之前 4 秒的強(qiáng)度!攻擊者破解時(shí)，成本就增加了 4 倍。

如今主流的口令 Hash 函數(shù)都支持「并行維度」。例如 scrypt 以及更先進(jìn)的 argon2，都可通過參數(shù) p 設(shè)定。

線程開銷

現(xiàn)實(shí)中，「線程數(shù)」未必要和「并行維度」一樣多，因?yàn)檫€得考慮「空間成本」。

假設(shè)上述的 PBKDF 空間成本有 512MB，如果開啟 4 個(gè)線程，就得占用 2GB 的內(nèi)存!若用戶只有 1.5 GB 的空閑內(nèi)存，還不如只開 2 個(gè)線程，反而會(huì)更順暢。

當(dāng)然，也可以開 3 個(gè)線程，但這樣會(huì)更快嗎?顯然不會(huì)!

因?yàn)?4 個(gè)任務(wù)分給 3 個(gè)線程，總有一個(gè)線程得做兩份，所以最終用時(shí)并沒有縮短。反而增加了線程創(chuàng)建、內(nèi)存申請(qǐng)等開銷。

這里有個(gè) scrypt 算法在線演示：https://etherdream.github.io/webscrypt/example/basic/

大家可體會(huì)下時(shí)空成本(N)、并行維度(P)、線程數(shù)(Thread)對(duì)計(jì)算的影響。

小結(jié)

到此，我們講解了 3 個(gè)對(duì)抗破解的因素：

時(shí)間成本(迭代次數(shù))
空間成本(內(nèi)存容量、帶寬)
并行維度(多線程資源)

或許你已感悟到這其中的理念 —— 讓 Hash 算法牽涉更多的硬件能力。這樣，只有綜合性能高的硬件，才能順利運(yùn)行;專為某個(gè)功能打造的硬件，就會(huì)出現(xiàn)瓶頸!

照這個(gè)思路，我們也可發(fā)揮想象：假如有個(gè)算法使用了不少條件分支指令，而 CPU 正好擁有強(qiáng)大的分支預(yù)測(cè)功能。這樣該算法在 CPU 上運(yùn)行時(shí)，就能獲得很高的性能;而在其他精簡(jiǎn)過的硬件上，就沒有這么好的效果了。

當(dāng)然這里純屬想象，自創(chuàng)密碼學(xué)算法是不推薦的。現(xiàn)實(shí)中還是得用更權(quán)威的算法，例如 argon2、scrypt 等。

應(yīng)用

本文提到的對(duì)抗方案，都是從硬件消耗上進(jìn)行的。不過，這樣傷敵一千也會(huì)自損八百。

假如服務(wù)器每 Hash 一次口令，就得花 1 秒時(shí)間加 1GB 內(nèi)存，那么一旦有幾十個(gè)人同時(shí)訪問，系統(tǒng)可能就支撐不住了。

有什么辦法，既能使用高成本的 Hash，又不耗費(fèi)服務(wù)器資源?事實(shí)上，口令 Hash 完全可以在客戶端計(jì)算：

DK = Client_PBKDF(Password, Username, Cost ...)

因?yàn)榭诹钆c DK 的對(duì)應(yīng)關(guān)系是唯一的。賬號(hào)注冊(cè)時(shí)，提交的就是 DK;登錄時(shí)，如果提交的 DK 相同，也就證明口令是相同的。

所以客戶端無需提供原始口令，服務(wù)端也能認(rèn)證，這就是「零知識(shí)證明」。使用這種方案，還能進(jìn)一步減少口令泄露的環(huán)節(jié)，例如網(wǎng)絡(luò)被竊聽、服務(wù)端惡意程序等。

當(dāng)然，服務(wù)端收到 DK 后，還不能立即存儲(chǔ)。因?yàn)槿f一 DK 泄露了，攻擊者還是能用它登上用戶的賬號(hào) —— 盡管不知道口令。

因此，服務(wù)端需對(duì) DK 再進(jìn)行 Hash 處理。

不過這一次，只需快速的 Hash 函數(shù)即可。因?yàn)?DK 是無規(guī)律的數(shù)據(jù)(熵很高)，無法通過跑字典還原，所以用簡(jiǎn)單的 Hash 就能保護(hù)。

這樣，服務(wù)器只需極小的計(jì)算開銷，就能實(shí)現(xiàn)高強(qiáng)度的口令安全了!

將來即使被拖庫(kù)，攻擊者也只能使用如下 Hash 函數(shù)跑字典：

f(x) => server_hash( client_hash(x) )

因?yàn)槠渲杏玫搅?client_hash，所以這個(gè)最終函數(shù)同樣能對(duì)抗硬件破解!

演示

根據(jù)上述思想，這里做個(gè)簡(jiǎn)單的演示，放在我的虛擬空間里：http://www.etherdream.com/webscrypt/example/login/

(并且后臺(tái)程序和數(shù)據(jù) 都是公開的，模擬被拖庫(kù)的場(chǎng)景)

事實(shí)上，這個(gè)虛擬空間的配置非常低，但這并不影響高強(qiáng)度口令的實(shí)現(xiàn) —— 只要你的電腦配置高、瀏覽器版本新，那就夠了!

盡管這其中都是不能再弱的數(shù)字口令，不過相比簡(jiǎn)單使用 MD5、SHA256 這些的，成本至少高百萬倍以上!大家試試多久能破解，成功了會(huì)顯示紅包哦。

責(zé)任編輯：未麗燕來源： FreeBuf.COM

Hash GPU 數(shù)據(jù)破解