[Crypto] Length Extension Attack

Length Extension Attack 允許攻擊者將惡意訊息的雜湊值偽裝成正常訊息的雜湊值。

首先我們要先了解 Merkle–Damgård construction

這個方法被證明說如果滿足下面兩個條件，則產生的雜湊函式也不會發生碰撞。

1. 有適當的 padding 方式
2. 壓縮函式 (compression function) 不會產生碰撞

Merkle–Damgård construction 大致上的流程式這樣的

1.  把輸入的資料分成 512 bit 的區塊，最後一塊根據不同雜湊函式有不同的 padding  方式
2. 一開始先給定一個初始向量 （initial vector, IV), 當作 input 1 
3. 區塊當作 input 2 ，兩個輸入放到雜湊函式 f 裏面，產生輸出 output
4. 產生的這個輸出再當下一次的 input 1，下一個區塊當作 input 2
5. 重複這樣的動作直到結束

使用這種方法產生雜湊值的雜湊函數都有這個弱點

大致了解 Merkle–Damgård construction 後，就要進到主題啦！

情境

有些網站會在下載的網址加上一個簽名 (signature)，用來防止使用者隨便下載主機裏面的檔案

看起來大概會像這樣

https://www.abc.com/?file=myfile&sig=2d59213a73edf47d93c1e23073b7e458

在主機端會有一個自己才知道的祕密金鑰 secret。

當請求發送過來時，他會把金鑰和檔案名稱連在一起，檢查是不是符合後面的那個簽名。

hash(secret+file) = sig

如果 file 名稱改變, 對應的雜湊值也會不同。因為使用者不知道 secret 是什麼，所以也沒辦法自己計算出對應的 signature。

弱點

使用 Merkle–Damgård construction 的雜湊函數 (e.g. MD5, SHA-1, SHA-2) 會有這個弱點

想法是這樣的，如果我們不知道 secret 是多少，為什麼不要拿他最後產生的那個 hash 來操作呢？

當我們可以自己算出那個 padding，就可以把想要放的訊息 (msg2)  放在新的區塊。

這樣得到的雜湊值就可以由原本的 secret 來成功驗證。

實作

網路上有許多工具可以幫我們計算出偽造的訊息還有他對應的雜湊值，在這邊以 HashPump 當作例子示範一次


我們先定義 secret，注意到這邊的 secret 在之後是看不見的
就讓 secret = 1d2s51fasfeekk 好了，長度是 14

再定義正常的輸入，並計算 md5(secret|msg)
這邊我讓 msg = hello?hello!，得到雜湊值 28bee5502040e7a934dd9f4c2dc62e1b

接下來我們使用 hashpump 這個工具，把必要的資料都填上去後得到
第一行是新的 signature
第二行則是 payload

為了驗證這個攻擊是有效的，我們看看 md5(secret|evil_msg) 的值會是多少

$ echo -n "echo -n "1d2s51fasfeekkhello?hello\!\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\xd0\x00\x00\x00\x00\x00\x00\x00__evil__" > file"

$ md5sum file
60ee6e563d955946c640ea778af836ec  file

發現計算出來的雜湊值和 hashpump 幫我們算出來的一樣！實作成功~

* 要特別注意到計算雜湊值輸入字串是不是正確的，之前被最後面的換行坑了好久....QQ