0×00 前言
天下武功,唯快不破。但密碼加密不同。算法越快,越容易破。
0×01 暴力破解
密碼破解,就是把加密后的密碼還原成明文密碼。似乎有不少方法,但最終都得走一條路:暴力窮舉。也許你會說還可以查表,瞬間就出結(jié)果。雖然查表不用窮舉,但表的制造過程仍然需要。查表只是將窮舉提前了而已。
密碼加密,用的都是單向散列計算。既然單向,那就是不可逆,那只能窮舉。窮舉的原理很簡單。只要知道密文是用什么算法加密的,我們也用相同的算法,把常用的詞組跑一遍。若有結(jié)果和密文一樣,那就猜中了。
窮舉的速度有多快?這和加密算法有關。加密一次有多快,猜一次也這么快。例如 MD5 加密是非常快的。加密一次耗費 1 微秒,那破解時隨便猜一個詞組,也只需 1 微秒(假設機器性能一樣,詞組長度也差不多)。攻擊者一秒鐘就可以猜 100 萬個,而且這還只是單線程的速度。
所以,加密算法越快,破解起來就越容易。
?。}圖來自: netdna-ssl.com)
0×02 慢加密
如果能提高加密時間,顯然也能增加破解時間。如果加密一次提高到 10 毫秒,那么攻擊者每秒只能猜 100 個,破解速度就慢了一萬倍。怎樣才能讓加密變慢?最簡單的,就是對加密后的結(jié)果再加密,重復多次。
例如,原本 1 微秒的加密,重復一萬次,就慢一萬倍了:
for i = 0 ~ 10000 x = md5(x) end加密時多花一點時間,就可以換取攻擊者大量的破解時間。
事實上,這樣的「慢加密」算法早已存在,例如 bcrypt、PBKDF2 等等。它們都有一個難度系數(shù)因子,可以控制加密時間,想多慢就多慢。
加密越慢,破解時間越長。
0×03 慢加密應用
最需要慢加密的場合,就是網(wǎng)站數(shù)據(jù)庫里的密碼。
近幾年,經(jīng)常能聽到網(wǎng)站被「拖庫」的新聞。用戶資料都是明文存儲,泄露了也無法挽回。唯獨密碼,還可以和攻擊者對抗一下。然而不少網(wǎng)站,使用的都是 快速加密算法,因此輕易就能破解出一堆弱口令賬號。當然,有時只想破解某個特定人物的賬號。只要不是特別復雜的詞匯,跑上幾天,很可能就破出來。
但網(wǎng)站用了慢加密,結(jié)果可能就不一樣了。如果把加密時間提高 100 倍,破解時間就得長達數(shù)月,變得難以接受。即使數(shù)據(jù)泄露,也能保障「密碼」這最后一道隱私。
0×04 慢加密缺點
不過,慢加密也有明顯的缺點:消耗大量計算資源。使用慢加密的網(wǎng)站,如果同時來了多個用戶,服務器 CPU 可能就不夠用了。要是遇到惡意用戶,發(fā)起大量的登錄請求,甚至造成資源被耗盡。性能和安全總是難以兼得。所以,一般也不會使用太高的強度。
一些大型網(wǎng)站,甚至為此投入集群,用來處理大量的加密計算。但這需要不少的成本。
有沒有什么方法,可以讓我們使用算力強勁、同時又免費的計算資源?
0×05 前端加密
在過去,個人電腦和服務器的速度,還是有較大差距的。但如今,隨著硬件發(fā)展進入瓶頸,這個差距正縮小。在單線任務處理上,甚至不相上下??蛻舳藫碛袕姶蟮乃懔Γ懿荒芊謸恍┓掌鞯墓ぷ??尤其像「慢加密」這種算法開源、但計算沉重的任務,為何不交給客戶端來完成?
過去,提交的是明文密碼;現(xiàn)在,提交的則是明文密碼的「慢加密結(jié)果」。無論是注冊,還是登錄。而服務端,無需任何改動。將收到的「慢加密結(jié)果」,當做原來的明文密碼 就行。以前是怎么保存的,現(xiàn)在還是怎么保存。這樣就算被拖庫,攻擊者破解出來的也只是「慢加密結(jié)果」,還需再破解一次,才能還原出「明文密碼」。
事實上,「慢加密結(jié)果」這個中間值,是不可能破解出來的!因為它是一個散列值 —— 毫無規(guī)律的隨機串,例如 32 位十六進制字符串,而字典都是有意義的詞組,幾乎不可能跑到它!除非字節(jié)逐個窮舉。但這有 16^32 種組合,是個天文數(shù)字。所以「慢加密結(jié)果」是無法通過數(shù)據(jù)庫里泄露的密文「逆推」出來的。
或許你在想,即使不知道明文密碼,也可以直接用「慢加密結(jié)果」來登錄。事實上后端儲存時再次加密,就無法逆推出這個散列值了。
當然,不能逆推,但可以順推。把字典里的詞組,用前后端的算法依次執(zhí)行一次:
back_fast_hash( front_slow_hash(password) )然后對比密文,即可判斷有沒有猜中。這樣就可以用跑字典來破解。但是有 front_slow_hash 這個障礙,破解速度就大幅降低了。
0×06 對抗預先計算
不過,前端的一切都是公開的。所以 front_slow_hash 的算法大家都知道。攻擊者可以用這套算法,把常用詞組的「慢加密結(jié)果」提前算出來,制作成一個「新字典」。將來拖庫后,就可以直接跑這個新字典了。
對抗這種方法,還得用經(jīng)典的手段:加鹽。最簡單的,將用戶名作為鹽值:
front_slow_hash(password + username)這樣,即使相同的密碼,對于不同的用戶,「慢加密結(jié)果」也不一樣了。也許你會說,這個鹽值不合理,因為用戶名是公開的。攻擊者可以對某個重要人物的賬號,單獨為他建立一個字典。
那么,是否可以提供一個隱蔽的鹽值?答案是:不可以。
因為這是在前端。用戶還沒登錄,那返回誰的鹽值?登錄前就能獲得賬號的鹽值,這不還是公開的嗎。所以,前端加密的鹽值無法隱藏,只能公開。當然,即使公開,單獨提供一個鹽值參數(shù),也比用戶名要好。因為用戶名永遠不變,而獨立的鹽值可以定期更換。
鹽值可以由前端生成。例如注冊時:
# 前端生成鹽值
salt = rand()
password = front_slow_hash(password + salt)
# 提交時帶上鹽值
submit(..., password, salt)
后端將用戶的鹽值也儲存起來。登錄時,輸完用戶名,就可以開始查詢用戶對應的鹽值:
當然要注意的是,這個接口可以測試用戶是否存在,所以得有一定的控制。
鹽值的更換,也非常簡單,甚至可以自動完成:
前端在加密當前密碼時,同時開啟一個新線程,計算新鹽值和新密碼。提交時,將它們?nèi)紟?。如果「當前密碼」驗證成功,則用「新密碼」和「新鹽值」覆蓋舊的。這樣更換鹽值,還是只用到前端的算力。
這一切都是自動的,相當于 在用戶無感知的情況下,定期幫他更換密碼!
密文變了,針對「特定鹽值」制作的字典,也就失效了。攻擊者得重新制作一次。
0×07 強度策略
密碼學上的問題到此結(jié)束,下面討論實現(xiàn)上的問題。
現(xiàn)實中,用戶的算力是不均衡的。有人用的是神級配置,也有的是古董機。這樣,加密強度就很難設定。如果古董機用戶登錄會卡上幾十秒,那肯定是不行的。對于這種情況,只有以下選擇:
強度固定
強度可變
1.強度固定
根據(jù)大眾的配置,制定一個適中的強度,絕大多數(shù)用戶都可接受。但如果超過規(guī)定時間還沒完成,就把算到一半的 Hash 和步數(shù)提交上來,剩余部分讓服務器來完成。
[前端] 完成 70% ----> [后端] 計算 30%
不過,這需要「可序列化」的算法,才能在服務端還原進度。如果計算中會有大量的臨時內(nèi)存,這種方案就不可行了。相比過去 100% 后端慢加密,這種少量用戶「前后參半」的方式,可以節(jié)省不少服務器資源。
對于請求協(xié)助的用戶,也必須有一定的限制,防止惡意透支服務器資源。
2.強度可變
如果后端不提供任何協(xié)助,那只能根據(jù)自身條件做取舍了。配置差的用戶,就少加密一點。用戶注冊時,加密算法不限步數(shù)放開跑,看看特定時間里能算到多少步:
# [注冊階段] 算力評估(線程 1 秒后中止) while x = hash(x) step = step + 1 end這個步數(shù),就是加密強度,會保存到他的賬號信息里。和鹽值一樣,強度也是公開的。因為在登錄時,前端加密需要知道這個強度值。
# [登錄階段] 先獲得 step for i = 0 ~ step x = hash(x) end這個方案,可以讓高配置的用戶享受更高的安全性;低配置的用戶,也不會影響基本使用。(用上好電腦還能提升安全性,很有優(yōu)越感吧~)
但這有個重要的前提:注冊和登錄,必須在性能相近的設備上。如果是在高配置電腦上注冊的賬號,某天去古董機登錄,那就悲劇了,可能半天都算不出來。。。
3.動態(tài)調(diào)整方案
上述情況,現(xiàn)實中是普遍存在的。比如 PC 端注冊的賬號,在移動端登錄,算力可能就不夠用。如果沒有后端協(xié)助,那只能等。要是經(jīng)常在低端設備上登錄,那每次都得干等嗎?等一兩次就算了,如果每次都 等,不如重新估量下自己的能力吧。把加密強度動態(tài)調(diào)低,更好的適應當前環(huán)境。將來如果不用低端設備了,再自動的調(diào)整回來。讓加密強度,能動態(tài)適應常用的設 備的算力。
實現(xiàn)原理,和上一節(jié)的自動更換鹽值類似。
4.異想天開方案
下面 YY 一個腦洞大開的方案,前提是網(wǎng)站有足夠大的訪問量。如果當前有很多在線用戶,它們不就是一堆免費的計算節(jié)點嗎?計算量大的問題,扔給他們來解決。
不過這樣做也有一些疑慮,萬一正好推送給了壞人怎么辦?顯然,不能把太多的敏感數(shù)據(jù)放出去。節(jié)點只管計算,完全不用知道、也不能知道這個任務的最終目的。
但是,如果遇到惡作劇節(jié)點,故意把數(shù)據(jù)算錯怎么辦?所以不能只推送給一個節(jié)點。多選幾個,最終結(jié)果一致才算正確。這樣風險概率就降低了。
相比 P2P 計算,網(wǎng)站是有中心、實名的,管理起來會容易一些。對于惡作劇用戶,可以進行懲罰;參與過幫助的用戶,也給予一定獎勵。
想象就到此,繼續(xù)討論實際的。
0×08 性能優(yōu)化
1.為什么要優(yōu)化
或許你會問,「慢加密」不就是希望計算更慢嗎,為什么還要去優(yōu)化?
假如這是一個自創(chuàng)的隱蔽式算法,并且混淆到外人根本無法讀懂,那不優(yōu)化也沒事。甚至可以在里面放一些空循環(huán),故意消耗時間。但事實上,我們選擇的肯 定是「密碼學家推薦」的公開算法。它們每一個操作,都是有數(shù)學上的意義的。原本一個操作只需一條 CPU 指令,因為不夠優(yōu)化,用了兩條指令,那么額外的時間就是內(nèi)耗。導致加密用時更久,強度卻未提升。
2.前端計算軟肋
如果是本地程序,根本不用考慮這個問題,交給編譯器就行。但在 Web 環(huán)境里,我們只能用瀏覽器計算!相比本地程序,腳本要慢的多,因此內(nèi)耗會很大。
腳本為什么慢?主要還是這幾點:
弱類型
解釋型
沙箱
3.弱類型
腳本,是用來處理簡單邏輯的,并不是用來密集計算的,所以沒必要強類型。不過如今有了一個黑科技:asm.js。它能通過語法糖,為 JS 提供真正的強類型。這樣計算速度就大幅提升了,可以接近本地程序的性能!
但是不支持 asm.js 的瀏覽器怎么辦?例如,國內(nèi)還有大量的 IE 用戶,他們的算力是非常低的。好在還有個后補方案 —— Flash,它有各種高性能語言的特征。類型,自然不在話下。
相比 asm.js,F(xiàn)lash 還是要慢一些,但比 IE 還是快多了。
4.解釋型
解釋型語言,不僅需要語法分析,更是失去了「編譯時深度優(yōu)化」帶來的性能提升。好在 Mozilla 提供了一個可以從 C/C++ 編譯成 asm.js 的工具:emscripten。有了它,就不用裸寫了。而且編譯時經(jīng)過 LLVM 的優(yōu)化,生成的代碼質(zhì)量會更高。
事實上,這個概念在 Flash 里早有了。曾經(jīng)有個叫 Alchemy 的工具,能把 C/C++ 交叉編譯成 Flash 虛擬機指令,速度比 ActionScript 快不少。
Alchemy 現(xiàn)在改名 FlasCC,還有開源版的 crossbridge
5.沙箱
一些本地語言看似很簡單的操作,在沙箱里就未必如此。例如數(shù)組操作:
vector[k] = v虛擬機首先得檢查索引是否越界,否則會有嚴重的問題。如果「前端慢加密」算法涉及到大量內(nèi)存隨機訪問,那就會有很多無意義的內(nèi)耗,因此得慎重考慮。不過有些特殊場合,腳本速度甚至能超過本地程序!例如開頭提到的 MD5 大量反復計算。
這其實不難解釋:
首先,MD5 算法很簡單。沒有查表這樣的內(nèi)存操作,使用的都是局部變量。局部變量的位置都是固定的,避免了越界檢查開銷。其次,emscripten 的優(yōu)化能力,并不比本地編譯器差。最后,本地程序編譯之后,機器指令就不會再變了;而如今腳本引擎,都有 JIT 這個利器。它會根據(jù)運行時的情況,實時生成更優(yōu)化的機器指令。
所以選擇加密算法時,還得兼顧實際運行環(huán)境,揚長避短,發(fā)揮出最大功效。
0×09 對抗 GPU
眾所周知,跑密碼使用 GPU 可以快很多倍。GPU 可以想象成一個有幾百上千核的處理器,但只能執(zhí)行一些簡單的指令。雖然單核速度不及 CPU,但可以通過數(shù)量取勝。暴力窮舉時,可以從字典里取出上千個詞匯同時跑,破解效率就提高了。
那能否在算法里添加一些特征,正好命中 GPU 的軟肋呢?
1.顯存瓶頸
大家聽過說「萊特幣」吧。不同于比特幣,萊特幣挖礦使用了 scrypt 算法。這種算法對內(nèi)存依賴非常大,需要頻繁讀寫一個表。GPU 雖然每個線程都能獨立計算,但顯存只有一個,大家共享使用。這意味著,同時只有一個線程能操作顯存,其他有需要的只能等待了。這樣,就極大遏制了并發(fā)的優(yōu) 勢。
2.移植難度
山寨幣遍地開花的時候,還出現(xiàn)了一個叫 X11Coin 的幣,據(jù)稱能對抗 ASIC。它的原理很簡單,里面摻雜了 11 種不同的加密算法。這樣,制造出相應的 ASIC 復雜度大幅增加了。盡管這不是一個長久的對抗方案,但思路還是可以借鑒的。如果一件事過于復雜,很多攻擊者就望而生畏了,不如去做更容易到手的事。
3.其他想法
之所以 GPU 能大行其道,是因為目前的加密算法,都是簡單的公式運算。這對 CPU 并沒太大的優(yōu)勢。能否設計一個算法,充分依賴 CPU 的優(yōu)勢?CPU 有很多隱藏的強項,例如流水線。如果算法中有大量的條件分支,也許 GPU 就不擅長了。
當然,這里只是設想。自己創(chuàng)造加密算法,是非常困難的,也不推薦這么做。
0x0A 額外意義
除了能降低密碼破解速度,前端慢加密還有一些其他意義:
1.減少泄露風險
用戶輸入的明文密碼,在前端內(nèi)存里就已加密。離開瀏覽器,泄露風險就已結(jié)束。即使通信被竊聽,或是服務器上的惡意中間件,都無法拿到明文密碼。除非網(wǎng)頁本身有惡意代碼,或是用戶系統(tǒng)存在惡意軟件。
2.無法私藏明文
盡管大部分網(wǎng)站都聲稱,不會存儲用戶的明文密碼。但這并沒有證據(jù),也許私下里仍在悄悄儲存。如果在前端加密,網(wǎng)站就無法拿到用戶的明文密碼了。也許正是這一點,很多網(wǎng)站不愿意使用前端加密。
事實上,其實網(wǎng)站不愿意也沒關系,我們可以自己做一個單機版的慢加密插件。當選中網(wǎng)頁密碼框時,彈出我們插件。在插件里輸入密碼后,開始慢加密計算。最后將結(jié)果填入頁面密碼框里。這樣,所有的網(wǎng)站都可以使用了。當然,已注冊的賬號是不行的,得手動調(diào)整一下。
3.增加撞庫成本
「前端慢加密」需要消耗用戶的計算力,這個缺點有時也是件好事。
對于正常用戶來說,登錄時多等一秒影響并不大。但對于頻繁登錄的用戶來說,這就是一個障礙了。誰會頻繁登錄?也許就是撞庫攻擊者。他們無法拖下這個 網(wǎng)站的數(shù)據(jù)庫,于是就用在線登錄的方式,不斷的測試弱口令賬號。如果通過 IP 來控制頻率,攻擊者可以找大量的代理 —— 網(wǎng)速有多快,就能試多快。
但使用了前端慢加密,攻擊者每試一個密碼,就得消耗大量的計算,于是將瓶頸卡在硬件上 —— 能算多快,才能試多快。所以,這里有點類似 PoW(Proof-of-Work,工作量證明)的意義。關于 PoW,以后我們會詳細介紹。
0x0B 無法做到的
盡管「前端慢加密」有不少優(yōu)勢,但也不是萬能的。上一節(jié)也提到,能減少風險,而不是消除風險。如果本地環(huán)境有問題,那任何密碼輸入都有風險。
下面我們來思考一個場景:某網(wǎng)站使用了「前端慢加密」,但沒有使用 HTTPS —— 這會導致鏈路被竊聽?;仡?0×05 小節(jié),如果拿到「慢加密結(jié)果」,就可以直接登上賬號,即使不知道明文密碼。的確如此。但請仔細想一想,這不也降低損失了嗎?
本來不僅賬號被盜用,而且明文密碼也會泄露;而如今,只是賬號被盜用,明文密碼對方仍無法獲得。所以,前端慢加密的真正保護的是「密碼」而不是「賬號」。賬號被盜,密碼拿不到!
如果攻擊者不僅能竊聽,還能控制流量的話,就可以往頁面注入攻擊腳本,從而獲得明文密碼。當然,這和電腦中毒、鍵盤偷窺一樣,都屬于「環(huán)境有問題」,不在本文討論范圍內(nèi)。本文討論的是數(shù)據(jù)庫泄露的場景。
0x0C 多線程慢加密
用戶的配置越來越好,不少都是四核、八核處理器。能否利用多線程的優(yōu)勢,將慢加密計算進行分解?如果每一步計算都依賴之前的結(jié)果,是無法進行拆解的。例如:
for i = 0 ~ 10000 x = hash(x) end這是一個串行的計算。然而只有并行的問題,才能分解成多個小任務。不過,換一種方式的多線程也是可以的。例如我們使用 4 個線程:
# 線程 1 x1 = hash(password + "salt1") for i = 0 ~ 2500 x1 = hash(x1) end # 線程 2 x2 = hash(password + "salt2") for i = 0 ~ 2500 x2 = hash(x2) end # ...最終將 4 個結(jié)果合并起來,再做一次加密,作為慢加密結(jié)果。但這樣會導致更容易破解嗎?留著給大家思考。
0x0D 總結(jié)
前端慢加密,就是讓每個用戶貢獻少量的計算資源,使加密變得更強勁。即使數(shù)據(jù)泄露,其中也凝聚了全網(wǎng)站用戶的算力,從而大幅增加破解成本。
0xFF 后記
前些年比特幣流行時,突發(fā)奇想用瀏覽器來挖礦。雖然沒做成,不過獲得了一些密碼學姿勢。近期重新進行了整理,并添加了一些新想法,于是寫篇詳細的文章分享一下。因為密碼學屬于傳統(tǒng)領域,所以結(jié)合當下流行的 Web 技術(shù),才能更有新意。
如果你對算法有疑惑,可以先仔細看 0×05 這節(jié)。
如果你是耐心看完本文的,希望能有收獲: )