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