彩虹表原理詳解及工具介紹

NO IMAGE

PS:這玩意偶前幾天用了一下,確實強悍無比,在這個表面前,md5等公開的加密演算法不堪一擊啊。記得我之前的公司開發的遊戲賬號都用修改過的特有MD5加密演算法,建議開發人員都這樣搞,這樣安全性就大大提高。如給雜湊表加個字首字尾之類的。

彩虹表(Rainbow Table)是一種破解雜湊演算法的技術,是一款跨平臺密碼破解器,主要可以破解MD5、HASH等多種密碼。它的效能非常讓人震驚,在一臺普通PC上輔以NVidia CUDA技術,對於NTLM演算法可以達到最高每秒103,820,000,000次明文嘗試(超過一千億次),對於廣泛使用的MD5也接近一千億次。更神奇的是,彩虹表技術並非針對某種雜湊演算法的漏洞進行攻擊,而是類似暴力破解,對於任何雜湊演算法都有效。

一、彩虹表原理

先講述一些基本概念:

Tables

可以說長期進行密碼學研究的人很少有不知道這個的。在很多年前,國外的黑客們就發現單純地通過匯入字典,採用和目標同等演算法破解,其速度其實是非常緩慢的,就效率而言根本不能滿足實戰需要。之後通過大量的嘗試和總結,黑客們發現如果能夠實現直接建立出一個資料檔案,裡面事先記錄了採用和目標採用同樣演算法計算後生成的Hash雜湊數值,在需要破解的時候直接呼叫這樣的檔案進行比對,破解效率就可以大幅度地,甚至成百近千近萬倍地提高,這樣事先構造的Hash雜湊資料檔案在安全界被稱之為Table表(檔案)。

Rainbow Tables

最出名的Tables是Rainbow Tables,即安全界中常提及的彩虹表,它是以Windows的使用者帳戶LM/NTLM雜湊為主要破解物件的。簡單說明一下,在
Windows2000/XP/2003系統下,賬戶密碼並不是明文儲存的,而是通過微軟所定義的演算法,儲存為一種無法直接識別的檔案,即通常所說的SAM檔案,這個檔案在系統工作時因為被呼叫所以不能夠被直接破解。但我們可以將其以Hash即雜湊的方式提取,以方便匯入到專業工具破解,提取出來的密碼雜湊類似於下面:


Administrator:500:96e95ed6bad37454aad3b435b51404ee:64e2d1e9b06cb8c8b05e42f0e6605c74:::
Guest:501:aad3b435b51404eeaad3b435b51404ee:31d6cfe0d16ae931b73c59d7e0c089c0:::
user1:1001:732b2c9a2934e481cd0a8808b19097ef:778620d5d5de064154e689fa4790129f:::
user2:1002:a042f67a99758fd727b99b2375d829f9:6127ee12a83da34fc19953e538e4d580:::

若是以傳統破解方式而言,無論是本地,還是內網線上破解,效率都不是很高。據實際測試,單機環境下,破解一個14位長包含大小寫字母以及數字的無規律密碼,一般是需要3~~9小時的,這個時間值會隨著密碼的複雜度及計算機效能差異提升到幾天甚至數月不等。雖然說大部分人都不會使用這樣複雜的密碼,但對於目前很多密碼足夠複雜並且長度超過10位的密碼比如“Y1a9n7g9z0h7e”,還是會令黑客們頭痛不已。

2003年7月瑞士洛桑聯邦技術學院Philippe Oechslin公佈了一些實驗結果,他及其所屬的安全及密碼學實驗室(LASEC)採用了時間記憶體替換的方法,使得密碼破解的效率大大提高。作為一個例子,他們將一個常用作業系統的密碼破解速度由1分41秒,提升到13.6秒。這一方法使用了大型查詢表對加密的密碼和由人輸入的文字進行匹配,從而加速瞭解密所需要的計算。這種被稱作“記憶體-時間平衡”的方法意味著使用大量記憶體的黑客能夠減少破解密碼所需要的時間。

於是,一些受到啟發的黑客們事先製作出包含幾乎所有可能密碼的字典,然後再將其全部轉換成NTLM Hash檔案,這樣,在實際破解的時候,就不需要再進行密碼與Hash之間的轉換,直接就可以通過檔案中的Hash雜湊比對來破解Windows帳戶密碼,節省了大量的系統資源,使得效率能夠大幅度提升。當然,這只是簡單的表述,採用的這個方法在國際上就被稱為Time-Memory
Trade-Off ,即剛才所說的“記憶體-時間平衡”法,有的地方也會翻譯成“時間—記憶體交替運演算法”。其原理可以理解為以記憶體換取時間,可由下圖3表示:

圖 著名的“記憶體-時間平衡”法運算原理圖

  具體演算法方面的內容本文就不再涉及,對於想進行更高深層次探究的讀者,可以仔細參考2003年的這篇詳細文件《Making a Faster Crytanalytical Time-Memory Trade-Off》以及2005年的文件《Time-Memory Trade-Offs: False Alarm Detection Using Checkpoints》。

正是由於Rainbow Tables的存在,使得普通電腦在5分鐘內破解14位長足夠複雜的Windows帳戶密碼成為可能。

圖 對Windows賬戶進行Rainbow Tables破解

  如上圖4可以看到,類似於c78j33c6hnws、yemawangluo178、38911770這樣的Windows帳戶密碼幾乎全部在180秒即3分鐘內破出,最短只用了5秒,個別稍長的密碼破解開也沒有超過3分鐘。

這幾乎是令人難以置信的,Roger迫不及待的去看了 http://www.project-rainbowcrack.com 所介紹的原理。這其實已經不是新的技術了,但是很遺憾的是,搜尋“彩虹表原理”出來的文章對彩虹表原理的介紹都有不太正確,Roger就在這裡簡單的介紹一下,主要參考的是Wiki上的這篇 http://en.wikipedia.org/wiki/Rainbow_tables,英文好的可以去看這篇論文http://lasecwww.epfl.ch/pub/lasec/doc/Oech03.pdf

我們先來做點科普,雜湊(Hash)演算法就是單向雜湊演算法,它把某個較大的集合P對映到另一個較小的集合Q中,假如這個演算法叫H,那麼就有Q = H(P)。對於P中任何一個值p都有唯一確定的q與之對應,但是一個q可以對應多個p。作為一個有用的Hash演算法,H還應該滿足:H(p)速度比較快; 給出一個q,很難算出一個p滿足q = H(p);給出一個p1,很難算出一個不等於p1的p2使得 H(p1)=H(p2)。正因為有這樣的特性,Hash演算法經常被用來儲存密碼————這樣不會洩露密碼明文,又可以校驗輸入的密碼是否正確。常用的
Hash演算法有MD5、SHA1等。

破解Hash的任務就是,對於給出的一個q,反算出一個p來滿足q = H(p)。通常我們能想到的兩種辦法,一種就是暴力破解法,把P中的每一個p都算一下H(p),直到結果等於q;另一種辦法是查表法,搞一個很大的資料 庫,把每個p和對應的q都記錄下來,按q做一下索引,到時候查一下就知道了。這兩種辦法理論上都是可以的,但是前一種可能需要海量的時間,後一種需要海量 的儲存空間,以至於以目前的人類資源無法實現。

我們可以簡單的算一下,對於14位的大小寫加數字(先不算特殊字元了)組成的密碼的集合有多大?自然就是(26*2 10)^14 = 62^14 = 1.24 * 10^25,這個就約等於12億億億,即使我們每納秒可以校驗一個p(一秒鐘10億次,目前PC做不到),暴力破解法也大概需要4億年;如果我們採用查表 法,假定Hash的結果是128Bit即16位元組的,光存放Hash(不存放明文P)就需要10^26位元組的儲存空間。什麼?現在硬碟很便宜?沒錯現在 1GB硬碟大概是五毛錢,那麼按這個來算光儲存這個Hash大概需要5億億人民幣來買硬碟。所以有些文章說彩虹表就是依賴查一個巨大的表來破解Hash,
簡直是個無知的玩笑。

也正因為如此,我們一直都認為Hash是足夠安全的,十幾位的密碼也是強度足夠的,直到彩虹表的出現。現在我們來看看彩虹表是怎麼幹的。

彩虹表的根本原理就是組合了暴力法和查表法,並在這兩者之中取得一個折中,用我們可以承受的時間和儲存空間進行破解。它的做法是,對於一個Q = H(P),建立另一個演算法R使得 P = R(Q),然後對於一個p,這樣進行計算:

p0 -H-> q1 -R->p1 -H-> q2 -R->p2 -H-> q3 -R->p3  … -H-> q(n-1) -R->p(n-1) -H-> qn -R->pn

簡單的說,就是把q用H、R依次迭代運算,最後得到pn,n可能比較大。最後我們把p0和pn都儲存下來,把其他的結果都丟棄。然後用不同的p0代入計算,得到多個這樣的p的對子。

我們在做破解的時候,給出了一個q,我們來尋找p。我們先把q做一次R運算得到一個值例如叫c1,然後把c1和每一個p對的最後一個做比較,假如和某一個 pn相等,那麼有可能這個pn所對應的p(n-1)就是我們在追尋的q,為了驗證我們把pn對應的p0再做一次鏈式計算,比對qn是否就是給出的q,如果 是,很明顯p(n-1)就是我們在追尋的p,因為 p(n-1) -H-> qn。如果不是就繼續尋找直到遍歷所有的q0qn對。

事情還剛剛開始,我們再算q -R-> c1 -H-> -R-> c2,再比對c2是否是qn,如果是,那麼p(n-2)就可能是p;再算c3、c4直到c(n-1),不知道這樣說你明白了嗎?

總的來說,就是用一個p0pn對來儲存了一個鏈子的資料,如果n很大,就可以大大減小了儲存的空間。這樣帶來的問題是必須做n次比對,時間更長,但是我們不需要瞬間破解,等待幾秒乃至幾天破解一個密碼都是可以接受的。

當然這裡只是講述了最粗淺的原理,仔細想一下還有很多的問題,例如R的選擇,Hash衝突的處理,如何選擇p0來實現足夠的覆蓋,如何在有限資源下生成彩虹表等等。對這些感興趣的可以去看看RainbowCrack的原始碼 http://www.project-rainbowcrack.com

二、獲得彩虹表

彩虹表可以使用RainbowCrack或Cain來生成。表分割得越細,成功率就越高,生成的表體積也越大,所需時間也越長。但下載比生成快得多,有人做過測試,4核4GB記憶體的機器,生成2GB彩虹表,需要花費7天時間,而7天按2MB的頻寬(256K/S左右)幾乎可以下載48GB左右,效率明顯要超過生成。當然,你要是有超級計算機群生成的話,也不妨自己生成。對於廣大網路安全愛好者來說,還是直接下載來得靠譜!

Ophcrack彩虹表
官方下載地址:
http://ophcrack.sourceforge.net/

120G彩虹表BT下載(這是種子檔案,迅雷上有資源,如果是會員使用迅雷下載還是很快的,我8M頻寬,下了3天左右下完了。):
http://www.ha97.com/code/tables.rar

三、彩虹表的使用

彩虹表工具很多,常用到的彩虹表工具有Ophcrack、rcracki_mt、Cain、RainbowCrack等,主流的彩虹表有以下四種。

Cain: http://www.onlinedown.net/soft/53494.htm

Free Rainbow Tables
官方網址:http://www.freerainbowtables.com/en/tables/
映象下載:http://tbhost.eu/rt.php
提供了多種型別的彩虹表下載,LM、NTLM、MD5、SHA1等。千萬別把人家法語字元的表也下了,對國人來說,幾乎沒什麼用,不過如果你有特殊需要,那就下吧……這裡提供的都是.rti格式的,有別於傳統的.ri格式,.rti比.rt的多了一個目錄.index檔案,據說遍列速度比.rt的更快(未曾對比過,無法確定是否屬實)。
比較新的,用的索引和壓縮,所以速度更快,體積更小,而且支援分散式破解。
支援HASH型別:LM,MD5,NTLM,SHA1,HALFLMCHALL
網上有已經生成好的表可供下載,真是造福於民。
副檔名:rti

Ophcrack
官網網址:http://ophcrack.sourceforge.net/tables.php
最常用的,介面友好,與眾不同,壓縮儲存,有自己獨特的彩虹表結構,還有Live CD。
支援的HASH型別:LM,NTLM
副檔名:亂七八糟的。

高階的表要花錢買,免費的表有(推薦只下2和5,要求高的可以下載3和5):
1.XP free(LM表:包含大小寫 數字)380MB(官網免費下載)
2.XP free fast(和前一個一樣,但是速度更快)703MB(官網免費下載)
3.XP special(LM表:大小寫 數字 所有符號包括空格)7.5G
4.Vista free (NTLM表:包含常用密碼)461MB(官網免費下載)
5.Vista special(NTLM表:包含6位的全部可列印字元,7位的大小寫字母數字,8位的小寫和數字)8G

RainbowCrack
官網網址:http://project-rainbowcrack.com/table.htm
通用的,一般的破解軟體如saminside都支援,命令列介面,黑客的最愛,支援CUDA。
可以自己生成表,不要錢,傳說中的120G就來自於此。
支援HASH型別:LM, NTLM, MD5, SHA1, MYSQLSHA1, HALFLMCHALL, NTLMCHALL.
副檔名:rt

最小彩虹表是最基本的字母數字表,就這樣它的大小就有388MB,這是Ophcrack啟動盤預設的表,該表可以在11分鐘內破解所有可能14位數字字母密碼組合中的99.9%。國內有比較流行的傳說中的120G的彩虹表,國外還有幾T的海量彩虹表。win2003及以前的windows作業系統的密碼採用的LM演算法加密,而Vista、Win7、Win2008/R2採用的是NTLM,NTLM比LM安全得多。

LM和NTLM詳解:

1、話說在遠古時期,DES當道。微軟在考慮9X系統口令加密的時候就自然地採用了國家標準DES一次加密8位元組,留一位校檢,還剩7位元組(下文有解釋), 也就是LM(Lan Manage)的核心。

2、那有人要問了,萬一我的口令是8位怎麼辦呢?不用怕,微軟的程式設計師很“聰明”:先把前7位加密,後一位補6個0,再當7位一起加密不就可以了嗎,結果就真的這麼做了。

3、這就導致破解LM密碼只需7位一分割,然後再逐塊破解,這大大減低了破解的難度。因為最後一塊往往不夠7位,一般瞬間即可得出結果。也就是7位和13位的密碼,在破解者眼裡幾乎是一樣的,因為13位的後6位很快就能破解出來,而且可以根據後6位猜測出前7位的密碼,這就是為什麼我們破解XP和2003密碼很快的原因,因為他們都使用了LM加密方式。

4、由於LM的種種不安全性,微軟在設計NT系列作業系統時採用了新的口令儲存手段,即NTLM技術(New Technology Lan Manage),採用MD4 RSA儲存,立馬安全性要高很多。但是為了保證相容性,直到2003微軟仍然保持著LM的加密方式,也就是在2000、2003和XP中,我們的口令同時儲存了兩份,一份LM一份NTLM,我們仍然可以通過LM破解2003的口令。

5、在Vista和2008、Win7中,微軟終於下定決心對LM斬草除根,只留下NTLM,破解難度增大。

6、回到彩虹表,由於LM最多隻有7位,所以它的彩虹表很小。而NTLM用了雜湊函式,所以理論上口令是可以無限長的,所以NTLM的彩虹表往往很大,120G肯定是不夠完成所有可列印字元的,最大的彩虹表已經是T量級了。

LM和NTLM驗證機制:http://www.nsfocus.net/index.php?act=magazine&do=view&mid=1665

某人用彩虹表測試破解MD5的小結:

ophcrack的表不支援破解md5,具體講.rt .rtc .rti格式的,只需對比一組資料就可以。同樣是破解12位的純數字密碼:

.rt的需要20GB .rtc的需要8.75GB .rti的需要1.67 1.67 1.68 1.71=6.72GB

明顯是.rti的小,但是我試過,我下了上面.rti格式破解12位的6.72GB的表中的1.67GB,其破解效果很讓我驚訝,我本以為純數字的破解出來的可能性是四分之一,因為我只下了4個表中的一個,我只下了那1.67GB,但我試著破解了幾個12位數字加密的32位md5,結果大多數都能跑出來,很少有跑不出的,汗。但當我驚喜時發現他並不支援破解16位的md5,然後去那國外的官方論壇去逛了逛,才發現這並不支援破解16位的md5。原來老外不來16位這一套,但我們國內的網站用16位的md5佔絕大多數,所以入侵時大部分得到的是16位的MD5密碼,而老外的就不來16位的,鬱悶。

Ophcrack文件描述了它所能使用的彩虹表之間的差異:

字母數字表 10k 388MB 包含所有字母數字混合密碼中99.9%的LanManager表。這些都是用大小寫字母和數字組成的密碼(大約800億組合)。
由於LanManager雜湊表將密碼截成每份7個字元的兩份,我們就可以用該表破解長度在1到14之間的密碼。由於LanManager雜湊表也是不區分大小寫的,該表中的800億的組合就相當於12*10的11次方(或者2的83次方)個密碼。

字母數字表 5k 720MB 包含所有字母數字組合的密碼中99.9%的LanManager表。但是,由於表變成2倍大,如果你的計算機有1GB以上的RAM空間的話,它的破解速度是前一個的4倍。

擴充套件表 7.5GB —xp special包含最長14個大小寫字母(密碼大於14 LM-HASH會全顯示0或以AA3D開頭,詳見另一篇文章Windows
LM/NTLM HASH加密
)、數字以及下列33個特殊字元(!”#$%&’()* ,-./:;[email protected][]^_`{|} ~)組成的密碼中96%的LanManager表。該表中大約有7兆的組合,5*10的12次方(或者2的92次方)密碼。

NT 8.5 GB–vista special 我們可以使用該表來破解計算機上的NT雜湊表,這是LanManager 雜湊表所做不到的。該表包含了用如下字元組成的可能密碼組合的90%:
·最高6位字元由大小寫字母、數字以及33個特殊字元(同上面列舉的一樣)
·7 大小寫字母及數字
·8 小寫字母及數字
該表包含7兆種組合,對應7兆的密碼(NT雜湊表不存在LanManager雜湊表的弱點)。

注意:所有這些彩虹表都有其特定適用的密碼長度和字母組合。太長的密碼(如數十位),或者包含表中沒有的字元,那麼用彩虹表就無法破解。