RainbowCrack

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

RainbowCrack文件說明：

RainbowCrack包含了下述實用程序：

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

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

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

首先使用彩虹表生成器（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 這是對"Brute-Force"和"Directory-Base"的一種折中的破解技術(shù)，在2003年瑞典的Philippe Oechslin 在Making a Faster Cryptanalytic Time-Memory Trade-Off一文 (文章開頭有給出鏈接)中首次被提出，它有效的利用了PreComputation的優(yōu)點，同時又克服了Diecretory-Based消耗太空磁盤空間的缺點，在這兩者中找到了一個平衡點。 

不過，它也有缺點，即: 　
1) password+salt: 加鹽 　
2) key stretching: 密碼擴展，包括輪數(shù)擴展和長度擴展 接下來，我們的文章會重點分析這個彩虹表破解的技術(shù)原理 

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

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

rainbowcrack使用教程：

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

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

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

4.1 彩虹表生成

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

我們分別看每一條鏈:

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

有幾個重點要關(guān)注:

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

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

3) R1、R2、R3....Rk(K代表每條鏈的長度，在這個例子中是3)，是K個不同的Reverse Hash函數(shù)，它存在的目的是為了避免出現(xiàn)不同的chain中出現(xiàn)重復(fù)的節(jié)點，我們可以思考一下，如果這個R在一條鏈中的每個節(jié)點都是一樣的，那如果假如在兩條鏈中的某兩個節(jié)點在進行R()之后，得到了相同的結(jié)果，則在這之后，H計算也會得到相同的結(jié)果，緊接著R計算又是相同的結(jié)果，則造成了重復(fù)存儲，浪費了存儲空間，也減低了這套破解系統(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 ... 注意這個重合一定是發(fā)生在不同鏈上的不同位置的節(jié)點，因為H的"非碰撞性"保證了這點(思考)，這個重合導(dǎo)致的是兩條鏈中的某一段發(fā)生了"重合"

會出現(xiàn)這個現(xiàn)象的原因是因為我們選擇的R函數(shù)很難保證"非碰撞性"，即無法保證不同的輸入在進行R計算不會得到不同的輸出，為了解決這個問題，將一條鏈上的不同節(jié)點的每次計算都使用不同的R函數(shù)，這樣，即使在不同鏈上的不同位置因為Rk是不一樣的，就不會發(fā)生重合了。

回到主題上來，這個鏈式的表生成好之后，我們之保存每條鏈的頭和尾的兩個明文節(jié)點，中間的點都是"可計算的"，故丟棄，把全部的鏈的頭尾節(jié)點保存起來，就成了所謂的彩虹表

4.2 使用彩虹表進行HASH密碼破解

再次回顧這張圖

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

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

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

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

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

彩虹表的缺點：

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

因為彩虹表需要針對算法變化的每一種形式都預(yù)生成一個對應(yīng)的字典，如果這個變化空間很大，就會使彩虹表的生成成本變得很大，這樣，彩虹表原本解決的空間成本問題又再次暴露出來。

而要達到"算法變化"的方式非常多，常見的有以下兩種方法

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

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