簡介
Merkle–Damgård結構簡稱為MD結構，主要用在hash算法中抵禦碰撞攻擊。這個結構是一些優秀的hash算法，比如MD5,SHA-1和SHA-2的基礎。今天給大家講解一下這個MD結構和對他進行的長度延展攻擊。
MD結構
MD結構是Ralph Merkle在1979年的博士論文中描述的。因為Ralph Merkle 和 Ivan Damgård 分别證明了這個結構的合理性，是以這個結構被稱為Merkle–Damgård結構。
接下來，我們看下MD結構是怎麼工作的。
MD結構首先對輸入消息進行填充，讓消息變成固定長度的整數倍（比如512或者1024）。這是因為壓縮算法是不能對任意長度的消息進行處理的，是以在處理之前必須進行填充。
通常來說，我們會使用恒定的資料，比如說0來填充整個消息塊。
舉個例子，假如我們的消息是“HashInput”，壓縮塊的大小是8位元組（64位），那麼我們的消息将會被分成兩個塊，後面一個塊使用0來填充，将會得到：“HashInpu t0000000”。
但是這樣做往往是不夠的，因為通常對于壓縮函數來說，會删除掉最後面的額外的0，是以導緻填充和不填充最後計算出來的hash值是一樣的。
為避免這種情況，必須更改填充常量資料的第一位。由于常量填充通常由零組成，是以第一個填充位将強制更改為“ 1”。
也就是“HashInpu t1000000”。
我們還可以對填充進行進一步的增強，比如使用一個額外的block來填充消息的長度。
但是額外的使用一個block往往有點浪費，一個更加節約空間的做法就是，如果填充到最後一個block的0中有住夠的空間的話，那麼可以消息的長度放在那裡。
填充好block之後，接下來就可以對消息進行壓縮了，我們看下一下MD的流程圖：
消息被分成了很多個block，最開始的初始化向量和第一個block進行f操作，得到了的結果再和第二個block進行操作，如此循環進行，最終得到了最後的結果。
長度延展攻擊
在密碼學中長度延展攻擊就是指攻擊者通過已知的hash(message1)和message1的長度，進而能夠知道hash（message1‖message2）的值。其中‖ 表示的是連接配接符。并且攻擊性并需要知道message1到底是什麼。
上一節我們講到的MD結構，是将消息分成一個一個的block，前一個block 運算出來的值會跟下一個block再次進行運算，這種結構可以很友善的進行長度延展攻擊。前提是我們需要知道原消息的長度。
我們舉個例子，假設我們有下面的請求：
Original Data: count=10&lat=37.351&user_id=1&long=-119.827&waffle=eggo
Original Signature: 6d5f807e23db210bc254a28be2d6759a0f5f5d99
上面的例子是給編号為1的使用者發送雞蛋餡的華夫餅，并附帶了消息簽名，以保證消息的正确性。這裡消息簽名使用的MAC算法。
假如惡意攻擊者想把waffle的值從eggo修改成為liege。
那麼新的資料将會是這樣的：
count=10&lat=37.351&user_id=1&long=-119.827&waffle=eggo&waffle=liege
為了對該新消息進行簽名，通常，攻擊者需要知道該消息簽名使用的密鑰，并通過生成新的MAC來生成新的簽名。但是，通過長度擴充攻擊，可以将哈希（上面給出的簽名）作為輸入，并在原始請求已中斷的地方繼續進行hash輸出，隻要知道原始請求的長度即可。
如果考慮到padding（消息填充）的影響的話，我們還需要恢複原始消息的填充内容，然後在恢複過後的内容之後再添加我們的攻擊代碼：
New Data: count=10&lat=37.351&user_id=1&long=-119.827&waffle=eggo\x80\x00\x00
\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00
\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00
\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00
\x00\x00\x02\x28&waffle=liege
這樣我們就可以得到新的MAC值：
New Signature: 0e41270260895979317fff3898ab85668953aaa2
Wide pipe
為了避免長度延展攻擊，我們可以對MD結構進行一些變形。
先看一下Wide Pipe結構：
wide pipe和MD的流程基本上是一緻的，不同的是生成的中間臨時的加密後的消息長度是最終生成消息長度的兩倍。
這也就是為什麼上圖中會有兩個初始向量IV1 和 IV2。假如最終的結果長度是n的話，那麼在中間生成的結果的長度就是2n。我們需要在最後的final 這一步中，将2n長度的資料縮減為n長度的資料。
SHA-512/224 和 SHA-512/256 隻是簡單的丢棄掉一半資料。
Fast wide pipe
還有一種比wide pipe更快的算法叫做fast wide pipe：