SHA-256 的 Length extension attack

在 Hacker News 上看到「Breaking SHA256: length extension attacks in practice (kerkour.com)」，在講不當使用 SHA-256 會導致 Length extension attack 類的安全漏洞，主要是因為 MD5、SHA-1 以及 SHA-2 類的 hash function 最後生出 hash 值時會暴露出 hash function 的內部狀態而導致的問題。

這邊講的不當使用是指你沒有使用標準的 MAC，而是自己用字串組合實作造成的問題，通常是 S = H(secret || message) 這樣的形式，這邊的 || 是指字串相接。

拿 MD5 為例子，在維基百科上面可以看到 MD5 演算法對應的 pseudo code，最後輸出的部分可以看到是把 a0、a1、a2、a3 這四個 32-bit variable 接起來，也就是把內部的狀態丟出來了：

// Process the message in successive 512-bit chunks:
for each 512-bit chunk of padded message do
// …

// Add this chunk’s hash to result so far:
a0 := a0 + A
b0 := b0 + B
c0 := c0 + C
d0 := d0 + D
end for

var char digest[16] := a0 append b0 append c0 append d0 // (Output is in little-endian)

於是你在可以反推 padding 的結構之後 (會需要知道 secret 的長度)，就可以往後接東西繼續算下去，這就是被稱作 length extension attack。

本來只有 S = H(secret || message)，你在不知道 secret 的情況下就可以疊字串到後面而且算出對應的 hash 值，變成 S' = H(secret || message || evildata)。

維基百科給的例子也示範了怎麼「用」，這是原始的資料以及 server 端簽出來的 hash 值：

Original Data: count=10&lat=37.351&user_id=1&long=-119.827&waffle=eggo
Original Signature: 6d5f807e23db210bc254a28be2d6759a0f5f5d99

於是我們想要蓋 waffle 參數，就變成：

Desired New Data: count=10&lat=37.351&user_id=1&long=-119.827&waffle=eggo&waffle=liege

攻擊者則可以不斷的嘗試，去猜測 padding 的結構，把計算出來對應的 hash 值丟到 server 看反應，直到看到 200 OK 的回應：

New Data: count=10&lat=37.351&user_id=1&long=-119.827&waffle=eggox80x00x00x00x00x00x00x00x00x00x00x00x00x00x00x00x00x00x00x00x00x00x00x00x00x00x00x00x00x00x00x00x00x00x00x00x00x00x00x00x00x00x00x00x00x00x00x00x00x00x00x00x00x00x00x00x00x02x28&waffle=liege
New Signature: 0e41270260895979317fff3898ab85668953aaa2

如同前面提到的，這是 hash function 在最後把內部狀態直接暴露出來造成的問題，在 MD5、SHA-1、SHA-2 (SHA-256、SHA-384、SHA-512) 都有類似的問題，而比較新的 hash function 在設計時就已經有考慮到了，不會出現這個問題，像是 SHA-3。

另外一方面，不要自己發明演算法，使用標準的 MAC 演算法通常是比較好的選擇。這邊用的比較廣泛的應該就是 HMAC，超過 25 年了。

結論是 SHA-256 還是堪用，儘量拿現成的演算法套，不要自己搞。

Read More