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)問題，歸約函式依然有撞問題，由上面的對照表可見 Hh和Hz在通過歸約時都會對應到D；同樣的，He和Hs則對應到Q，因為碰撞問題，也看到雜湊值歸約的結果並沒有Y和Z，以這個範例來說，當拿到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計算得雜湊值Hq，Hq≠Hw
  4. 將Hq送歸約函式計算得V，用V計算得雜湊值Hv，Hv≠Hw
  5. 將Hv送歸約函式計算得W，用W計算得雜湊值Hw，Hw=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計算得雜湊值Hk，Hk≠Hw
  8. 將Hk送歸約函式計算得E，用E計算得雜湊值He，He≠Hw
  9. 將He送歸約函式計算得Q，用Q計算得雜湊值Hq，Hq≠Hw
  10. 將Hq送歸約函式計算得V，用V計算得雜湊值Hv，Hv≠Hw
  11. 將Hv送歸約函式計算得W，用W計算得雜湊值Hw，Hw=Hw ，所以求得答案為W
如果不巧拿到Hy的雜湊值呢？會重複上述步驟1 到2，如果七階鏈就重複七回、三階鏈就重複三回，如果都沒有找到相符的尾值，就表示該雜湊值在目前的彩虹表是解不出來的。
上述是彩虹表大略的工作原理，終於知道它並不是完全的明文-雜湊對照表。
標籤： , , ,

2 則留言:

  1. pythonman2019年2月19日 下午2:01:00

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

    回覆刪除

訂閱： 張貼留言 (Atom)