Rainbow Hash Table 與密碼破解

跨平台密碼破解器Ophcrack的破解速度簡直是不可思議。到底有多快呢?它能在160秒內破解『Fgpyyih804423』這個密碼。很多人都認為這個密碼已經相當安全了,例如微軟的密碼強度檢查工具認為該密碼的安全級別是

「強」;而Geekwisdom密碼強度測量工具認為該密碼的安全強度是「普通」。

Ophcrack的破解速度為什麼會這麼快呢?這是因為它使用了Rainbow Tables,我說的可不是天上的那種彩虹。


不過,Rainbow Tables也是很美的。


要想理解Rainbow Tables的工作原理,首先你得明白電腦是如何儲存密碼的,不管是在你自己用的桌上型電腦還是在遠端的網路伺服器那裡。


一般而言,密碼決不會儲存在純文字檔案中。至少我們不應該這麼做,除非你用的是世界上最幼稚的程式,而且你的目的就是構建世界上最不安全的系統。實際上,我們應當用雜湊(Hash)函數的輸出值來儲存密碼。雜湊是不可逆(單向)運算,即使攻擊者能夠讀取密碼的雜湊表,他也不可能僅僅透過那個雜湊表來重建密碼。


但是攻擊者可以用Rainbow Hash Tables來攻擊密碼的雜湊表:透過龐大的、針對各種可能的字母組合,預先計算好其雜湊值。雖然攻擊者也可以即時計算雜湊值,但是利用這個預先算好的龐 大雜湊表,顯然能夠使攻擊的速度快上無數倍——假設攻擊機器有足夠的記憶體來載入整個表格(或至少是大部分),這就是個很典型的時間-記憶體取捨問題 (time-memory trade-off),尤其是駭客更傾向於使用這種捷徑。


Rainbow Tables有多龐大呢?Ophcrack的預設安裝畫面會讓你有個大致上的概念:


產生這些龐大的Rainbow Tables需要花很長時間,但是一旦完成,每個發動攻擊的電腦破解密碼能力都將大幅增強。


現有最小Rainbow Tables涵蓋了最基本的英文字母及數字,光這樣它的大小就有388MB。這是Ophcrack開機光碟預設使用的雜湊表。但即使這個最小的表格也具有相當的效力。我曾用它來攻擊一個Windows XP虛擬機器上的密碼,結果如下:



能找到? 花費秒數
Password1!
700
Fgpyyih804423 yes 159
Fgpyyih80442%
700
saMejus9 yes 140
thequickbrownfoxjumpsoverthelazydog
700


當然,用這種最小的Rainbow Tables無法破解那種帶有特殊字元的密碼(比如%&^$#),因為表格里根本沒有包含這些字元。你可能也注意到了那些passphrase (我特別鍾愛使用它們),由於本身的長度關係,passphrase對此項技術是免疫的。但是,話又說回來了,該攻擊可以在11分鍾內破解所有14位元數 字及英文字密碼組合中的99.9%,這還是用了最小的Rainbow Tables。表格越大、越完整,攻擊破解能力越強。Ophcrack檔案描述了它所能使用的Rainbow Tables之間的差異:


數字及英文字母表格(10k) 388MB 包含所有英文字母及數字混合密碼中99.9%的LanManager表,由於LanManager會將密碼拆成兩組7個字元的設計,長度1~14個字的密 碼都可以用這個表格破解,而且LanManager的雜湊不分大小寫,這個表格中所含的800億個雜湊值可用以破解2的83次方種密碼組合)。


數字及英文字母表格(5k) 720MB 包含所有英文字母及數字組合的密碼中99.9%的LanManager表。但是,由於表格變成2倍大,如果你的電腦有1GB以上的記憶體空間的話,它的破解速度是前一個的4倍。


延伸表格 7.5GB 包含最長14個大小寫字母、數字以及下列33個特殊字元(!"#$%&'()*+,-./:;<=>?@[\]^_`{|} ~)組成的LanManager雜湊表中的96%密碼。該表格中大約有7兆種的組合,可以涵蓋5*10的12次方(或2的92次方)種密碼。


NT 8.5 GB 當LanManager雜湊被停用時,我們可以使用此表格來破解電腦上的NT雜湊表。該表包含了以下組合中的90%密碼:

•長度1~6,由大小寫字母、數字以及33個特殊字元組合的密碼
•長度為7,由大小寫字母及數字組成的密碼
•長度為8,由小寫字母及數字組成的密碼


該表格包含7兆種組合,亦對應7兆種密碼(NT雜湊表不存在LanManager雜湊表的弱點)。


需要注意的是,所有這些Rainbow Tables都有其特定適用的密碼長度和字母組合。太長的密碼,或者用了表格中沒有的字元,那麼用Rainbow Tables就無法破解。


不幸的是,由於舊式LanManager雜湊表不可原諒的缺點,Windows伺服器特別容易被Rainbow Tables攻擊。令我吃驚的是,Windows Server 2003在預設狀態下竟然還支援那些舊式Lan Manager雜湊表。我強烈建議大家停用Lan Manager雜湊表,尤其是在那些儲存所有使用者認證的伺服器上(如 DC)。雖然這將對你的Windows 98使用者造成很大的不便,但是我覺得為了提高安全性,這麼做是值得的。


我聽說明年發佈的Windows Server 2008會將LanManager雜湊表去掉。Windows Vista已經不支援持這些過時的雜湊表了。在Vista系統中執行OphCrack的話結果請看下列對話方塊:


All LM hashes are empty. Please use NT hash tables to crack the remaining hashes.


對某些人而言,Ophcrack可能彈性不足,像是它不允許你自己產生Rainbow Tables,因此,你得用Project Rainbow Crack, 該工具能用來破解幾乎所有字母組合以及任何雜湊演算法。但你得當心,Rainbow Tables攻擊最近才盛行的原因是由於電腦的2~4GB記憶體最近才降到了讓人能接受的價格。我想說的是這些表格很龐大,對於攻擊安全性更高的NT雜湊 表所需的Rainbow Tables大小如下:


字元集 長度 表格大小
ABCDEFGHIJKLMNOPQRSTUVWXYZ
14

0.6 GB
ABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789
14

3 GB
ABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789!@#$%^&*()-_+=
14

24 GB
ABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789
!@#$%^&*()-_+=~`[]{}|\:;"'<>,.?/

14

64 GB



用Rainbow Tables對付桌上型電腦有點殺雞用牛刀,如果駭客能接觸實體主機,那麼就沒有任何安全性可言了,這是不變的10項電腦安全法則中的第3條。一旦駭客可以存取實體主機,那麼他可以用很多工具來重設密碼。


但是如果駭客從遠端伺服器或資料庫獲得大量密碼雜湊表,我們就有麻煩了,這種情況下,遭受Rainbow Tables攻擊的風險非常大。因此你決不能只依靠雜湊技術——你必須給雜湊表加些花樣(Salting),這樣得到的雜湊值就與眾不同了。給雜湊表加花 樣,聽起來很複雜,但其實很簡單。在產生雜湊表之前,給密碼加個唯一的值即可:


hash = md5('deliciously-salty-' + password)


這樣,攻擊者就無法用Rainbow Tables來攻擊你了——「密碼」和「deliciously-salty」產生的雜湊結果是不匹配的。除非駭客能知道你所選用的值,即使真的知道,他 也得專門針對你的機器產生一個專屬的Rainbow Tables。(編輯:資安之眼)


資安專家 Thomas Ptacek 針對這篇文章提出了更多深入的探討,我推薦大家能前往閱讀。



出處:
Jeff Atwood, Coding Horror


0 意見: