RainbowCrack

RainbowCrack是一個(gè)使用內(nèi)存時(shí)間交換技術(shù)（Time-Memory Trade-Off Technique）加速口令破解過(guò)程的口令破解器。RainbowCrack使用了彩虹表，也就是一張預(yù)先計(jì)算好的明文和散列值的對(duì)照表。通過(guò)預(yù)先花費(fèi)時(shí)間創(chuàng)建這樣的彩虹表，能夠在以后破解口令時(shí)節(jié)約大量的時(shí)間。

RainbowCrack文件說(shuō)明：

RainbowCrack包含了下述實(shí)用程序：

— rtgen.exe——彩虹表生成器，生成口令、散列值對(duì)照表。

— rtsort.exe——排序彩虹表，為rcrack.exe提供輸入。

— rcrack.exe——使用排好序的彩虹表進(jìn)行口令破解。

首先使用彩虹表生成器（rtgen.exe）生成自己的彩虹表。其命令行格式為：

rtgen hash_algorithm
plain_charset plain_len_min plain_len_max
rainbow_table_index
rainbow_chain_length rainbow_chain_count
file_title_suffix
rtgen hash_algorithm
plain_charset plain_len_min plain_len_max
rainbow_table_index
-bench

Rainbow-Table-Attack 這是對(duì)"Brute-Force"和"Directory-Base"的一種折中的破解技術(shù)，在2003年瑞典的Philippe Oechslin 在Making a Faster Cryptanalytic Time-Memory Trade-Off一文 (文章開頭有給出鏈接)中首次被提出，它有效的利用了PreComputation的優(yōu)點(diǎn)，同時(shí)又克服了Diecretory-Based消耗太空磁盤空間的缺點(diǎn)，在這兩者中找到了一個(gè)平衡點(diǎn)。 

不過(guò)，它也有缺點(diǎn)，即: 　
1) password+salt: 加鹽 　
2) key stretching: 密碼擴(kuò)展，包括輪數(shù)擴(kuò)展和長(zhǎng)度擴(kuò)展 接下來(lái)，我們的文章會(huì)重點(diǎn)分析這個(gè)彩虹表破解的技術(shù)原理 

3. 這幾種密碼破解方式的應(yīng)用場(chǎng)景

在開始研究Rainbow Table-Attack的技術(shù)之前，我們有必要先明白一個(gè)問(wèn)題，雖然說(shuō)彩虹表破解技術(shù)比"Brute-Force-Attack"、"Directory-Based-Attack"都要好，但并不是所有場(chǎng)景下都能使用彩虹表進(jìn)行破解的。

rainbowcrack使用教程：

其它的加密方式破解也可以很容易地添加到該軟件中。
軟件同時(shí)支持windows和linux系統(tǒng)
而且在一個(gè)系統(tǒng)上生成的表單可以直接轉(zhuǎn)換到另一種系統(tǒng)上使用
用它來(lái)破解md5密碼，數(shù)分鐘即可讓十位數(shù)內(nèi)與字符密碼還原，
它的功能雖然強(qiáng)大，但是在使用時(shí)卻是比較復(fù)雜的，因此我要詳細(xì)的介紹一番
第一步：
生成表單文件
下載來(lái)的軟件壓縮包中有幾個(gè)執(zhí)行程序，。
我們?cè)谄平鈓d5密碼時(shí)，要用到的是前兩個(gè)可執(zhí)行文件，是rcrack.exe rtgen.exe
其中的"rtgen.exe"程序就是用來(lái)生成包含預(yù)設(shè)密碼表單文件的
表單文件中有許多大量的md5加密密文，rainbowcrack的原理不是暴力破解
而是通過(guò)查詢預(yù)先做好的密碼與密文一一對(duì)應(yīng)的文件來(lái)快速破解密。優(yōu)點(diǎn)是速度快，
缺點(diǎn)是生成的文件非常大，
在命令提示符窗口中，運(yùn)行"rtgen.exe"命令
也可以輸入cmd在那里面，找到，你解壓縮文件的路徑，然后運(yùn)行
由于rainbowcrack是一個(gè)多功能的密碼破解器，因此提示信息比較復(fù)雜，
我們只需破解md5密碼，在這里可以按下面的格式生成md5密碼表單：
"rtgen md5 byte 1 7 5 2400 40000 all";
命令執(zhí)行后，提示"generateing...."正在生成密碼文件
其中"md5"參數(shù)指定生成md5表單。
如果是破解windows密碼之類的，還可以使用相應(yīng)的"lm/sha1"參數(shù)
詳細(xì)的，可以看幫助文件。
"byte"參數(shù)用來(lái)指定生成密碼表單中所包含的明密類型為所有字符和數(shù)字
如果想破解的是純數(shù)字密碼或是純字符密碼。
可以將其改為相應(yīng)的"numeric"或"alpha"參數(shù)
具體的參數(shù)可見(jiàn)目錄下"charset.txt"文件
其中1和7分別代表密碼最小和最大長(zhǎng)度
2400代表每個(gè)表單文件中密碼串的長(zhǎng)度
數(shù)字5用來(lái)表示生成表單文件的數(shù)目
而40000則代表每個(gè)表單文件中的密碼數(shù)目
后面這兩個(gè)數(shù)目越大，生成表單文件的速度越慢
但是表單文件中的密碼就越多。
相應(yīng)的破解速度也會(huì)越快
命令執(zhí)行后，提示"generateing...."正在生成密碼文件
執(zhí)行完畢后。就會(huì)在當(dāng)前目錄下生成5個(gè)文件名類似為"md5_byte#1-7_5_2004X40000_all.rt"的文件
其中"all"是我們剛才在生成命令中指定用來(lái)添加標(biāo)識(shí)文件的參數(shù)
有點(diǎn)慢.我們先繼續(xù)(這是剛才生成的表單文件)
第二步：
瞬間破解密碼
生成密碼表單文件后，就可以利用"rcrack.exe"文件來(lái)查詢表單文件，
快速破解出指定的密碼了。
直接執(zhí)行命令后，即可看到程序使用幫助
從幫助信息中，我們可以看到能對(duì)單個(gè)md5密文件進(jìn)行破解
也可以一次破解多個(gè)密文。
當(dāng)我們要破解單個(gè)md5密碼時(shí)，可以使用"-h"參數(shù)來(lái)指定要破解的密文，
假設(shè)這里要破解密文為"49ba59abbe56e057"可以輸入如下命令
"rcrack *.rt -h 49ba59abbe56e057";
其中"*.rt"參數(shù)表示查詢當(dāng)前目錄下所有密碼表單文件。
如果密碼表單文件制作 得好
命令執(zhí)行后很快就可以從這些表單文件中找到要還原后的密碼明文了
如果要一次破解多個(gè)密碼。首先打開記事本。
將所有待破解的密碼按行輸入
保存為一個(gè)沒(méi)有后綴的文件中。
這里文件名為"mima"然后執(zhí)行命令：
"rcrack *.rt -l mama";
程序?qū)��?huì)查詢所有的表單文件，并將其與待破解密碼文件中的密文一一對(duì)比，很快就可以將大部分的密碼破
解出來(lái)了
提示一下：rainbowcrack軟件可以說(shuō)是md5密碼的克星。我們完全可以在平時(shí)計(jì)算機(jī)不工作時(shí)，利用相當(dāng)長(zhǎng)的時(shí)間來(lái)生成個(gè)比較大的密碼表單文件庫(kù)

Rainbow Table彩虹表破解技術(shù)原理：

Rainbow Table相比Directory做的第一個(gè)改進(jìn)就是將龐大的明文密文對(duì)"分成"了"明-密文對(duì)鏈chain"，鏈條的長(zhǎng)度越長(zhǎng)，空間的縮減效果就越大。為了使用彩虹表技術(shù)，需要事先確定兩個(gè) 函數(shù)： H(HASH函數(shù)): 密碼的加密方式，不同的彩虹表對(duì)應(yīng)于不同的加密方式(這點(diǎn)和Directory-Based的道理是一樣的) 常見(jiàn)的H函數(shù)有: MD4、MD5、SHA1、 R(Reverse Hash函數(shù)): 逆HASH函數(shù)，并不是真的對(duì)HASH函數(shù)求逆(我們都知道HASH函數(shù)是不可逆的)，這里所謂的R函數(shù)，只是一個(gè)映射Mapping函數(shù)，將H()得到的密文再次映射回一個(gè)對(duì)應(yīng) 的明文，不一定是原來(lái)的明文，只要是明文就行

4.1 彩虹表生成

要注意，彩虹表的核心思想還是PreComputation的字典思想，所以生成彩虹表就是在生成一個(gè)字典，只是這個(gè)生成過(guò)程不再是單一的H計(jì)算，并保存明-密文對(duì)那么簡(jiǎn)單了。

我們分別看每一條鏈:

H(wikiedia)=ao4kd -> R1(ao4kd)=secret -> H(secret)=9kpmw -> R2(9kpmw)=jimbo -> H(jimbo)=v0d$x -> R3(v0d$x)=rootroot H(abcdefgh)=1vn6s-> R1(1vn6s)=bernie-> H(bernie)=kolscx-> R2(kolscx)=zurich-> H(zurich)=8ntpy -> R3(8ntpy)=myname .... H(passwd)=dlcm4-> R1(dlcm4)=culture-> H(culture)=re3xes-> R2(re3xes)=crypto-> H(crypto)=1tik0-> R3(1tik0)=linux23

有幾個(gè)重點(diǎn)要關(guān)注:

1) 在這個(gè)例子中，彩虹表的chain length是3，也就是說(shuō)一條鏈包含3個(gè)節(jié)點(diǎn)，也即這種情況可以以原本 1/3 的磁盤空間保存同等規(guī)模的字典

2) wikiedia稱為"頭結(jié)點(diǎn)"，rootroot稱為"尾節(jié)點(diǎn)"。我們最后需要保存的也就是這個(gè)頭-尾節(jié)點(diǎn)對(duì)，而中間的中間值全都不用保存，這也是彩虹表省空間的原因

3) R1、R2、R3....Rk(K代表每條鏈的長(zhǎng)度，在這個(gè)例子中是3)，是K個(gè)不同的Reverse Hash函數(shù)，它存在的目的是為了避免出現(xiàn)不同的chain中出現(xiàn)重復(fù)的節(jié)點(diǎn)，我們可以思考一下，如果這個(gè)R在一條鏈中的每個(gè)節(jié)點(diǎn)都是一樣的，那如果假如在兩條鏈中的某兩個(gè)節(jié)點(diǎn)在進(jìn)行R()之后，得到了相同的結(jié)果，則在這之后，H計(jì)算也會(huì)得到相同的結(jié)果，緊接著R計(jì)算又是相同的結(jié)果，則造成了重復(fù)存儲(chǔ)，浪費(fèi)了存儲(chǔ)空間，也減低了這套破解系統(tǒng)的明文空間覆蓋度，從而間接影響了破解效果。

假如R是不變的: H(startpoint1)=median1 -> R(median1)=median12 ...... -> R(median1x)=same -> H(same)=same1 -> .... same_end H(startpoint2)=median2 -> R(median1)=same -> H(same)=same1 -> .... same_end ... 注意這個(gè)重合一定是發(fā)生在不同鏈上的不同位置的節(jié)點(diǎn)，因?yàn)镠的"非碰撞性"保證了這點(diǎn)(思考)，這個(gè)重合導(dǎo)致的是兩條鏈中的某一段發(fā)生了"重合"

會(huì)出現(xiàn)這個(gè)現(xiàn)象的原因是因?yàn)槲覀冞x擇的R函數(shù)很難保證"非碰撞性"，即無(wú)法保證不同的輸入在進(jìn)行R計(jì)算不會(huì)得到不同的輸出，為了解決這個(gè)問(wèn)題，將一條鏈上的不同節(jié)點(diǎn)的每次計(jì)算都使用不同的R函數(shù)，這樣，即使在不同鏈上的不同位置因?yàn)镽k是不一樣的，就不會(huì)發(fā)生重合了。

回到主題上來(lái)，這個(gè)鏈?zhǔn)降谋砩�成好之后，我們之保存每條鏈的頭和尾的兩個(gè)明文節(jié)點(diǎn)，中間的點(diǎn)都是"可計(jì)算的"，故丟棄，把全部的鏈的頭尾節(jié)點(diǎn)保存起來(lái)，就成了所謂的彩虹表

4.2 使用彩虹表進(jìn)行HASH密碼破解

再次回顧這張圖

假如我們要破解的HASH密文為re3xes1) 對(duì)密文re3xes進(jìn)行Rk(k代表最后一個(gè)R函數(shù)，這里是R3)運(yùn)算，得到一個(gè)臨時(shí)結(jié)果 I，將這個(gè)臨時(shí)結(jié)果I和每條鏈的尾節(jié)點(diǎn)進(jìn)行比較，檢測(cè)是否是某一條鏈的尾節(jié)點(diǎn)

1.1) 如果匹配成功，則破解成功，我們知道了這個(gè)待破解的密文屬于某一條鏈，就可以利用這條鏈的頭尾節(jié)點(diǎn)重現(xiàn)(再次計(jì)算)出這條鏈上的每個(gè)明密文對(duì)，自然也包括了待破解密文的明文 　　

1.2) 如果匹配失敗，在所有鏈的尾節(jié)點(diǎn)上都沒(méi)有這個(gè)臨時(shí)結(jié)果 I，則繼續(xù)進(jìn)行(2)2) 對(duì)密文re3xes進(jìn)行Rk-1(k-1代表倒數(shù)第二個(gè)R函數(shù)，這里是R2)，這里又得到一個(gè)臨時(shí)結(jié)果: crypto，再對(duì)臨時(shí)結(jié)果crypto進(jìn)行H計(jì)算，得到: 1tik0，再對(duì)1tik0進(jìn)行Rk 　　(k代表最后一個(gè)R函數(shù)，這里是R3)得到一個(gè)臨時(shí)結(jié)果: linux23。將這個(gè)臨時(shí)結(jié)果和每條鏈的尾節(jié)點(diǎn)進(jìn)行比較，檢測(cè)是否是某一條鏈的尾節(jié)點(diǎn) 　　

1.1) 如果匹配成功，則破解成功，在這個(gè)例子中我們知道匹配成功，就可以利用這條鏈的頭節(jié)點(diǎn): passwd重現(xiàn)(再次計(jì)算)出這條鏈上的每個(gè)明密文對(duì)，自然也包括了待破解密文的明文: culture　　 　　

2.1) 如果匹配失敗，則繼續(xù)調(diào)用Rk-2進(jìn)行搜索，步驟都是類似的 ... 直到完成了R1的搜索，如果還沒(méi)有找到匹配的，則宣布本次破解失敗，需要增大彩虹表文件大小、重組字典

彩虹表的缺點(diǎn)：

我們知道，彩虹表的核心思想是"PreComputation預(yù)計(jì)算"，而預(yù)計(jì)算的一個(gè)最大大問(wèn)題就是"當(dāng)加密的形式發(fā)生變化，這個(gè)預(yù)生成的字典從某種程度上就無(wú)用了"。這么說(shuō)有些不太準(zhǔn)確，我想表達(dá)的意思是預(yù)計(jì)算對(duì)算法的變化非常敏感，這也是對(duì)抗彩虹表技術(shù)的一個(gè)思考方式。

因?yàn)椴屎绫硇枰�針�?duì)算法變化的每一種形式都預(yù)生成一個(gè)對(duì)應(yīng)的字典，如果這個(gè)變化空間很大，就會(huì)使彩虹表的生成成本變得很大，這樣，彩虹表原本解決的空間成本問(wèn)題又再次暴露出來(lái)。

而要達(dá)到"算法變化"的方式非常多，常見(jiàn)的有以下兩種方法

1) 加鹽 saltedhash(password) = hash(password+salt) Or saltedhash(password) = hash(hash(password)+salt) 需要對(duì)付這種加密方式，彩虹表就需要針對(duì)salt的每一種可能的取值都生成一套字典，當(dāng)salt的長(zhǎng)度很長(zhǎng)時(shí)，彩虹表的生成成本和破解效率都會(huì)大幅下降

2) 密碼增強(qiáng) key stretching 是加密方式變化除了"加鹽"，加密輪數(shù)也是一個(gè)可變化的點(diǎn)，MD5-Crypt and in bcryp中都使用了Crypt Loop技術(shù)，即使用同一個(gè)算法，或不同的算法組合對(duì)一個(gè)明文進(jìn)行迭代的 多次(1000以上)加密，這樣，加密的輪數(shù)和加密方式的組合本身也構(gòu)成了一個(gè)"變化空間"需要對(duì)付這種加密方式，彩虹表就需要針對(duì)每一個(gè)加密輪數(shù)+加密方式的組合都生成一套字典，同樣，彩虹表的生成成本和破解效率都會(huì)大幅下降