Padding Orcale Attack 運作原理

November 12, 2016

2 minute read

簡單介紹的 Padding Orcale Attack 運作原理。

從基礎的 Block cipher CBC mode 講起，到 PKCS#7 padding 的實做，再闡述如何利用兩者，加上任意解密的系統，得到明文。

CBC Mode

用 AES, DES 等block cipher 時，因為明文通常遠大於 block size，這時候勢必就需要把明文切割，然後一個一個加密。但如果真的分別加密，每個 block 就會變成是獨立的，這樣同一組明文會產生同一組密文，安全性大幅度降低，這也是為什麼 ECB mode 不安全的原因。那該如何保障確保安全性呢？答案就是增加不同 block 之間的相依性，許多的加密模式例如 CBC，CFB，OFB，CTR，都會讓不同 block 之間有些關聯，避免同組明文產生相同密文的問題。

其中 CBC mode 加密運作原理如下，$P$ (plaintext)是明文，$C$ (ciphertext) 是密文，$\oplus$ 是 XOR，$IV$ 是 Initialization vector (因為沒有 $P_0$ ，明文從 $P_1$ 開始，，但我們又需要 $C_0$ 幫之後的 $P_1$ 加密)：

\[C_i = E_k(P_i \oplus C_{i-1}) \\\\ C_0 = IV\]

解密也很簡單，只是上面倒過來做，其中解密後的 C ，$E_k^{-1}(C_i)$ 我們稱之為 intermediate value ：

\[E_k^{-1}(C_i) \oplus C_{i-1} = P_i \\\\ E_k^{-1}(C_i) : intermediate\ vlaue\]

Reference: Block cipher mode of operation - Wikipedia

PKCS #7 Padding

在用上面介紹的 mode 加密時，如果全部的明文的長度不是 block size 的倍數，那麼最後一個 block 就會遇到input 長度不夠的問題。長度不夠就只好 padding，補上一些字讓它的長度達到 block size，其中最常用的就是 PKCS #7 Padding，他的 padding 方式很簡單，如果有 K bytes 需要 padding，那就讓每個 byte 都等於 K。

# Block size = 8 but 4 bytes plaintext
0A 0B 0C 0D __ __ __ __
# Padding 4 bytes
0A 0B 0C 0D 04 04 04 04

Reference: RFC - 2562

Padding Orcale

由於明文會 Padding 的關係，在解密之後，通常會先把明文拿去做檢查，看看最後幾個 bytes 是否符合 PKCS#7 Padding，如果不符合就會噴出錯誤。

如果我們可以不停的讓對方解密，又可以知道它會不會解密錯誤，我們就能利用這個性質，並且搭配 PKCS#7 的特性，一個 byte 一個 byte 猜出明文！

以下假設我們有 $C_0, C_1$，想要解密 $P_1$，並且可以讓對方解密任意字串：

解密會檢查 $P_1$ 的最後幾個 byte 是否符合 padding，先假設 padding 長度是 1 的話，表示它會檢查 $P_1[-1]$ (最後一個 byte) 是否等於 $01$
$E_k^{-1}(C_1) \oplus C_0 = P_1$，雖然無法直接得到 intermediate value，但 $C_0$ 是可控的， $P_1$ 對方又會檢查最後一個 byte，我們可以利用這個特性猜出 intermediate value

Guess Intermediate Value

首先，我們傳入 $C_0, C_1$ 讓對方解密，並讓 $C_0[-1] = g \oplus 01$ ，目標是先猜出 intermediate value，這裡的 $g$ 就是要猜的 intermediate value 的最後一個 byte

Server 端先解密 $C_1$，獲得 intermediate value $M_1 = E_k^{-1}(C_1)$
接下來跟 $C_0$ 做 XOR，$M_1 \oplus C_0 = P_1$
檢查 $P_1$ padding 是否正確，也就是確定 $P_1[-1] == 01$，如果不相等則回傳解密錯誤

假如我們的 $g$ 猜中了，也就是恰巧 $g == M_1[-1]$ ，因為 $M_1[-1] \oplus C_0[-1] = M_1[-1] \oplus (g \oplus 01) == 01$，padding 是正確的，那麼 server 就不會回傳任何錯誤；反之猜錯的話，就會在不通過 padding 的檢查。

於是我們可以利用這個手法，最多嘗試 256 (1 byte) 次就可以得到 $M_1[-1]$。

接下來的要猜出倒數第二個 byte，首先讓 $C_0[-2] = g \oplus 02$， $C_0[-1] = M_1[-1] \oplus 02$ ($M_1[-1]$ 剛剛已經猜到了)。

server 一樣會檢查 $M_1[-1] \oplus (M_1[-1] \oplus 02) == 02$，這當然會對，因為值根本就是特別設計好的
server 還會檢查 $M_1[-2] \oplus (g \oplus 02) == 02$，如果錯誤的話就換個 $g$ ，用類似的手法猜出倒數第二個 byte

重複以上步驟，就可以得到全部的 intermediate value $M_i$

Get Plaintext

不要忘記一開始解密的公式，$M_i \oplus C_{i-1} = P_i$，現在有了猜到的 $M_i$，密文 $C_i$ 也都有了，只要一個一個 XOR 就能得到明文 $P_i$ 。

如果沒有 $IV$ 的話也沒關係，這樣只有 $M_1 \oplus C_0 = P_1$ 第一塊解不出來而已，其他還是可以解的。

Reference: [ASP.NET] 了解Padding Oracle Attacks的細節 (二) - 小Kevin