雜湊 - MD5

MD5全稱『MD5 Message-Digest Algorithm』。

MD5訊息摘要的算法，目前很多人所使用的算法。

但目前已經被證實無法防止碰撞，雖然機率很小，但之前有論文做出了『不同的pdf』但確有相同的MD5數值，這樣一來就會有造假的可能性。

在2009年時有研究指出，只需要一般電腦的數秒鐘，就可以做出碰撞。

（論文的部分一樣放在補充資料。）

而數學家們也提出過MD5有很多弱點與不安全的地方。

雖然那麼說，但事實上目前依然是十分流行的算法之一。

MD5算法

這邊的話就是參考RFC 1321的標準。

其實本質上也不難懂，無非就是做位移跟替換而已。

前置步驟

接下來的算法中會需要一些常數來跟算法做混合，因此我們先生成這一系列的常數，這常數先給個代號我們稱為K：

而這個K是一個陣列，內部有64個空間從0到63。

接著使用正弦整數常數，生成如下：

i是0到63。
K[i] = abs(sin(i + 1)) × 2^32

Hash流程

我們一樣一步一步來看。

1. 加入填充位元

   這個不難懂，就是要讓資料與之後處理的長度統一。

   在原本資料加入1位元的'1'後，加入'0'直到資料長度去mod 512後得到448。

   01101101....10110（長度440）
   440 mod 512 = 440
   448 - 440 = 8（必須補充8位元的資料）
   因此：
   01101101....10110 10000000（長度448）
   

   這邊有一個條件那就是『最少附加1位』到『最多附加512位』的資料。

   例如：

   00101...0010（長度448）
   448 mod 512 = 448
   448 - 448 = 0 （則補充512為資料）
   因此：
   00101...0010 10000...000（長度960）
   

2. 填充長度

   這步驟也很簡單。
   將資料的長度（有填充過），將『長度』換成2進制後，取後面的64位元合併串接到資料當中。

   例如：

   00101...0010 10000...000（長度960）
   960 ＝ 1111000000
   
   最後：
   00101...0010 10000...0001111000000（長度1024）
   

   到了這邊，將資料以每32位元做成一個塊。
   大家也發現了，最後出來的結果能整除512，同時也能整除32位元。
   到時候我們必須：

   1. 將資料做成16小塊，唯一大塊。
   2. 每一小塊32位元。
      因此將資料做成W[0 1 2....][0、1、2...15]。

3. 初始化緩衝區

   這邊就是做圖片上每一個容器A、B、C、D的初始化。

   每一個容器裡面都是32位元的資料。
   最初的資料：

   H1: 0x01 0x23 0x45 0x67
   H2: 0x89 0xab 0xcd 0xef
   H3: 0xfe 0xdc 0xba 0x98
   H4: 0x76 0x54 0x32 0x10
   

   最初的初始化A、B、C、D：

   A ＝ H1
   B ＝ H2
   C ＝ H3
   D ＝ H4
   

4. 混亂處理資料（核心）
   這邊才是MD5的核心，但說起來也很簡單。

   先看四個等等會用到的公式：

   F(X,Y,Z) = XY v not(X) Z
   G(X,Y,Z) = XZ v Y not(Z)
   H(X,Y,Z) = X xor Y xor Z
   I(X,Y,Z) = Y xor (X v not(Z))
   

   一樣數學證明看文檔或等大神來解釋。

   MD5會每一回合的資料循環64次，而每16次換一個公式，公式就是上面那幾個。

   也就是說（i循環次數0～63）：
   資料在做一回時，都是同一大塊的資料。
   如：W[0][i]這樣。

   1. 0～15：F公式。
      • 這邊的選取資料為第i小塊。
   2. 16～31：G公式。
      • 這邊的選取資料為第(i*5+1 mod 16)小塊。
   3. 32～47：H公式。
      • 這邊的選取資料為第(i*3+1 mod 16)小塊。
   4. 48～63：I公式。
      • 這邊的選取資料為第(i*7+1 mod 16)小塊。

   ---

   這邊我們一樣要先做一件事情，資料W不是有很多筆，同時切割了資料塊，因此：
   每一大塊做一回，也就是每一大塊做64次循環。

   那接下來就簡單點了，看圖片。
   先是位移區塊：

   1. 『緩衝B』會變成『緩衝C』。
      • C = B。
   2. 『緩衝C』會變成『緩衝D』。
      • D ＝ C。
   3. 『緩衝D』會變成『緩衝A』。
      • A = D。

   ---

   再來處理『緩衝A』的流程：

   1. 先做公式，得出『R』。
   2. 將公式得出的『R』、『緩衝A』、『K[i]』和最重要的『資料W』做相加。
      • 這邊的i指的是循環次數，還記得我們的前置步驟吧，0-63就是為了這時使用的。
      • 資料在做一回時，都是同一大塊的資料。
   3. 接著向左循環位移。
      • 這邊請對照表，會告訴你要向左位做循環移幾位。
      • r[0..15]={7,12,17,22,7,12,17,22,7,12,17,22,7,12,17,22}
      • r[16..31]={5,9,14,20,5,9,14,20,5,9,14,20,5,9,14,20}
      • r[32..47]={4,11,16,23,4,11,16,23,4,11,16,23,4,11,16,23}
      • r[48..63]={6,10,15,21,6,10,15,21,6,10,15,21,6,10,15,21}
   4. 把結果跟原本的B相加（不是位移區塊後的B喔，請看圖）。
   5. 最後把結果放到『緩衝B』。

5. 做完全部回合後輸出。
   這邊其實就是把步驟4的動作，依序每個大塊做完。
   輸出結果的方式是由『D串接C串接B串接A這樣』。

   當每一次做完64次的循環後，會有128位元的資料。
   而也將512位元的一大塊資料hash完了。
   接著如果有另一塊大塊資料的話：

   1. 更新初始緩衝的資料，如下：
      將結果的A、B、C、D與H1、H2、H3、H4相加。
      如：

      H1 = H1 + A
      H2 = H2 + B
      H3 = H3 + C
      H4 = H4 + D
      

   2. 每一次更新都會將會改變H1～H4
      • 請『不要』一直拿『最初的初始化』來更新喔～。
      • 第一回結束後，的確要拿最初的初始化來更新。
      • 但第二回結束後，要拿被第一次相加過後的資料來更新。
      • 其實也就是：

        第一回：
        A ＝ H1
        B ＝ H2
        C ＝ H3
        D ＝ H4
        第二回：
        A ＝ H1 + A（第一回結束的結果）
        B ＝ H2 + B（第一回結束的結果）
        C ＝ H3 + C（第一回結束的結果）
        D ＝ H4 + D（第一回結束的結果）
        第三回：
        A ＝ H1 + A（第一回結束的結果） + A（第二回結束的結果）
        B ＝ H2 + B（第一回結束的結果） + A（第二回結束的結果）
        C ＝ H3 + C（第一回結束的結果） + A（第二回結束的結果）
        D ＝ H4 + D（第一回結束的結果） + A（第二回結束的結果）
        

        不斷地累加更新後的結果。

MD5結論

說說起來不難，很多人會覺得，這樣加下去會不會有問題。

其實我們也沒有要還原，不如說不能還原。

而熵意旨亂度，當小小改變一點點，也應該使整個輸出完全不同。

在前言的時候也提到過了。

但由於很多安全上問題，現在不應該繼續使用MD5。

碰撞、偽造等問題，導致其實整個過程中，是能故意使兩個不同的資料產出同一個MD5的。

所以我們接下來要介紹SHA家族。

也就是簡介中提到的，目前安全Hash算法標準了。

參考資料

RFC 1321

MD5

補充資料

How To Find Weak Input Differences For MD5 Collision Attacks