2018年11月17日 星期六

因為無知,所以出糗--淺談彩虹表原理

鄭重聲明:本篇只是淺談彩虹表的基礎原理,同時也釐清筆者多年的錯誤觀念,不涉及彩虹實作細節。
彩虹表就是一個龐大的、針對各種可能的字母組合預先計算好的哈希值的集合,不一定是針對MD5演算法的,各種演算法的都有,有了它可以快速的破解各類密碼。越是複雜的密碼,需要的彩虹表就越大,現在主流的彩虹表都是100G以上。
(摘自TWWORD的「彩虹表」詞條)
上面這段話一直是我所認為的彩虹表。幾年前,老師上課也是這樣教的,在當初對一名初踏入滲透測試領域的新人,雖然很懷疑這種的說法(註),但因基礎不扎實,也將就延用到現在。只因最近讀了一本外文書,才驚覺書中敘述和我的印象有出入。
註:若按照上面的說法,一套8字元長的大小寫英數字混合密碼,做出一套彩虹表至少要5000TB的儲存空間,以每顆3TB的硬碟估算,大約是1400顆,這是我當初心中的疑惑!?
原來彩虹表不是赤裸裸的將明文密碼與雜湊值照單全收,而是以time-memory trade off(以時間換空間)的策略,只儲存計算結果的串鏈(姑且稱它為彩虹鏈)的頭尾,至於中間的值則在破解時再重新計算。
彩虹鏈只存頭尾,那要如何維持完整的彩虹鏈的關係?這涉及兩個函式:雜湊值的計算函式(雜湊函式)及雜函值反轉函式(歸約函式 [reduction function])
  • 雜湊函式將明文密碼轉換成雜湊值,用 H( ) 代替。
  • 歸約函式將雜湊值對應到某個明文密碼,用 R( ) 代替。
歸約函式並不是解出雜湊值的原始明文密碼,只是儘量不重複地從可能的明文密碼中,找出一筆資料來和雜湊值對應。舉個例子,假設明文密碼只有1字元長,可能值為大寫字母 A到Z (即26種組合),這些密碼的雜湊值就有:
Ha = H(A) , Hb = H(B), ... ..., Hz = H(Z)   # Ha 即明文密碼A經過雜湊後的結果。
歸約函式就是從給定的雜湊值,找出一個對應的明文密碼,若R(Ha) 可以得 M,就將它記成  Rm = R(Ha),依此,假設上述所有雜湊值運算後得到如下結果:
Rm = R(Ha)=MRl = R(Hb)=LRg = R(Hc)=GRo = R(Hd)=O
Rp = R(He)=QRc = R(Hf)=CRr = R(Hg)=RRd = R(Hh)=D
Rn = R(Hi)=NRx = R(Hj)=XRe = R(Hk)=ERs = R(Hl)=S
Rf = R(Hm)=FRj = R(Hn)=JRk = R(Ho)=KRu = R(Hp)=U
Rv = R(Hq)=VRi = R(Hr)=IRq = R(Hs)=QRb = R(Ht)=B
Rh = R(Hu)=HRw = R(Hv)=WRt = R(Hw)=TRa = R(Hx)=A
Rp = R(Hy)=PRd = R(Hz)=D  
雜湊函式有碰撞(collision)問題,歸約函式依然有撞問題,由上面的對照表可見 HhHz在通過歸約時都會對應到D;同樣的,HeHs則對應到Q,因為碰撞問題,也看到雜湊值歸約的結果並沒有YZ,以這個範例來說,當拿到Y或Z的雜湊值,而利用此例的彩虹表將會解不出來。
好了,解釋了雜湊函式歸約函式之後,來看如何產生彩虹鏈表。
  1. 從明文密碼中隨機選擇一項(假設為 M),由雜湊函式計算其雜湊值得到Hm
  2. Hm送給歸約函式計算,反轉得到 F
  3. 再將F交給雜湊函式,又得一組雜湊值Hf
  4. 再將Hf送給歸約函式計算,反轉得到 C
一直循環下去就可以得到一條彩虹鏈,但這一條鏈到底要多長呢? 鏈的長短會影響彩虹表的大小及破解時所耗的時間:鏈愈長,愈節省空間,但破解時會增加重算的次數,所以破解速度較慢,下面用短鏈(三階)和長鏈(七階)來解釋。
若以三階製作彩虹鏈,可能得到的結果:
M H()
Hm R()
F H()
Hf R()
C H()
Hc R()
G
I H()
Hi R()
N H()
Hn R()
J H()
Hj R()
X
Q H()
Hq R()
V H()
Hv R()
W H()
Hw R()
T
D H()
Hd R()
O H()
Ho R()
K H()
Hk R()
E
~~底下還有,省略~~
若以七階製作彩虹鏈,可能得到的結果:
M H()
Hm R()
F H()
Hf R()
C H()
Hc R()
G H()
Hg R()
R H()
Hr R()
I H()
Hi R()
N H()
Hn R()
J
K H()
Hk R()
E H()
He R()
Q H()
Hq R()
V H()
Hv R()
W H()
Hw R()
T H()
Ht R()
B H()
Hb R()
L
P H()
Hp R()
U H()
Hu R()
H H()
Hh R()
D H()
Hd R()
O H()
Ho R()
K H()
Hk R()
E H()
He R()
Q
~~底下還有,省略~~
彩虹表最後只會儲存每條鏈的頭尾,即上面兩張表紅字部分,這樣就可以不必儲存所有對照表,而達到節省空間 的目的。那麼在破解時,要如何應用彩虹表呢?假設我們拿到一組雜湊值Hw,利用三階的彩虹表破解:
  1. Hw歸約函式得到T
  2. 比對每條彩虹鍵的尾端,在第三條鏈找到T,因而得知該鏈的頭是Q
  3. Q計算得雜湊HqHq≠Hw
  4. Hq歸約函式計算得V,用V計算得雜湊HvHv≠Hw
  5. Hv歸約函式計算得W,用W計算得雜湊HwHw=Hw,所以求得答案為W
同樣的,若用七階彩虹表破解:
  1. Hw歸約函式得到T
  2. T比對每條彩虹鍵的尾端,都沒有找到T
  3. T雜湊Ht,再將Ht歸約B
  4. B 比對每條彩虹鍵的尾端,都沒有找到B
  5. B雜湊Hb,再將Hb歸約L
  6. L比對每條彩虹鍵的尾端,在第二條鏈找到L,因而得知該鏈的頭是K
  7. K計算得雜湊HkHk≠Hw
  8. Hk歸約函式計算得E,用E計算得雜湊HeHe≠Hw
  9. He歸約函式計算得Q,用Q計算得雜湊HqHq≠Hw
  10. Hq歸約函式計算得V,用V計算得雜湊HvHv≠Hw
  11. Hv歸約函式計算得W,用W計算得雜湊HwHw=Hw ,所以求得答案為W
如果不巧拿到Hy的雜湊值呢?會重複上述步驟1 到2,如果七階鏈就重複七回三階鏈重複三回,如果都沒有找到相符的尾值,就表示該雜湊值在目前的彩虹表是解不出來的。
上述是彩虹表大略的工作原理,終於知道它並不是完全的明文-雜湊對照表。

2 則留言:

  1. 實作可參考python開源https://github.com/jfmengels/rainbowtable-python

    回覆刪除