Maojui

長度擴充攻擊 | Length Extension Attack (LEA)

2019-04-10

常見的雜湊函數 md5, sha1, sha2, sha256, …

其中的過程其實跟 CBC 長得蠻像的,先切成一塊一塊的 block 去做 Hash (blocksize = 128, 256, 512, … 依算法而定)

與 Blockcipher 一樣,最後一塊長度不足的部分會用 Padding 補齊,再填上整段文字的長度。

前一個 block Hash 完的結果會作為下一個 block 的輸入來輸出下一個 Hash

$$Hash(m) =$$

$$N \rightarrow Hash(m1) \rightarrow Hash(m2) \rightarrow … \rightarrow Hash(m_k + padding + length)$$

前面的這個 N 是 Magic number

不同的演算法,內部有定義一個 Magic number ,就是以這個開始做計算的


Length Extension Attack

該攻擊手法就是把得到的 Hash 值,作為 Magic number 繼續 hash 下去 。

舉個例子,當我把 $m$ 拿去做 Hash 時,實際上還是以 Magic number $(N)$ 為初始值,並把 $m$ 做成多個 block 一段一段算過去。

$$N \rightarrow Hash(m1) \rightarrow … \rightarrow Hash(mk + padding + length) \rightarrow V$$

所以,如果我把結果的 $(V)$ 作為起始值 $(N)$ 並且隨便輸入個 $(E)$ 來 Hash

$$V \rightarrow Hash(E) \rightarrow V’$$

由於前方的 $V$ 就是 $Hash(m)$ 的結果,展開就會變成:

$$N \rightarrow Hash(m) \rightarrow Hash(E) \rightarrow V’$$


結論

我們可以透過輸入 m 得到的 $V$

來預測出輸入 m + padding + length + E 的 $V’$,以通過一些驗證

padding 的部分有一定的格式,照做就好

大部分的 Server 會在做 Hash 之前加個 salt 或是 secret 之類的,以致於 length 無法確定,不過可以透過暴力搜尋,來找到這個長度的值

接下來就可以任意偽造 $E$ 來達到自己的目的囉