Padding Orcale Attack 運作原理

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 ,$E_k^{-1}(C_i)$ 我們稱之為 intermediate value

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