Maojui

POODLE Attack | Padding Oracle Attack

2017-05-11

冷知識：

  • Oracle (神諭) – 神明可以告訴你任何事情的答案
  • Padding Oracle – 用 Padding 告訴你 “你想知道的答案Ａ＿Ａ”

針對 CBC 的各種加密 ：

適用於：

  • CAST-cbc
  • aes-128-cbc
  • aes-192-cbc
  • aes-256-cbc
  • bf-cbc
  • camellia-128-cbc
  • camellia-192-cbc
  • camellia-256-cbc
  • cast-cbc
  • cast5-cbc
  • des-cbc
  • des-ede-cbc
  • des-ede3-cbc
  • desx-cbc
  • rc2-40-cbc
  • rc2-64-cbc
  • rc2-cbc
  • seed-cbc


攻擊重點 : CBC必須遵守 PKCS#7 的規定



PKCS #7 : Padding

不足幾bytes，就填幾格
而Padding的內容取決於剩餘的bytes。
EE EE EE EE EE EE EE 01
EE EE EE EE EE EE 02 02
EE EE EE EE EE 03 03 03
EE EE EE EE 04 04 04 04
……
…
如果剛好切完，會多放一格：
08 08 08 08 08 08 08 08


首先必須先瞭解有關CBC是如何加解密的


CBC加密：

image alt

$E$ 可以是 AES DES CAST BF(Blowfish) IDEA Camellia …

$C1 = E(P1 \oplus IV)$
$Cn = E(Pn \oplus Cn-1)$ # for all n > 1


CBC解密：

image alt

$D$ 對照 $E$

$P1 = D(C1) \oplus IV$
$Pn = D(Cn) \oplus Cn-1$ # for all n > 1


攻擊原理

變數 定義 定義 定義
$C$ 持有的密文 $P$ 實際的明文
$C_n$ 持有的密文的第 n 格 $P_n$ 實際明文的第 n 格
$C_n[k]$ 實際明文第 n 格的第 k byte $P_n[k]$ 實際明文第 n 格的第 k byte
$C’$ 自己設定的密文 $P’$ 由我們訂的密文解出來的 “偽明文”
$C’[k]$ 自己設定的密文的第 k byte $P’_n$ 偽明文的第 n 格
$C_n’[k]$ 自己設定的密文的第 n 格的第 k byte $P’_n[k]$ 偽明文的第 n 格的第 k byte

由上圖加密的方式可知 ：

$C’$ 是自訂的 $(C_0 : C_{n-1})$

把 $C’ + C_n$ 接起來拿去解密 => $D(C’||C_n)$


會得到一個 $P’_n$

$P’_n = D(C_n) \oplus C’$


從上圖我們可以知道 ：

$C_n = E(P_n \oplus C_{(n-1)})$


合起來：

$P’n = D(E(Pn \oplus C{(n-1)})) \oplus C’$


得到：

$P’n = P_n \oplus C{(n-1)} \oplus C’$


完成

=> $P_n = P’n \oplus C{(n-1)} \oplus C’$


Example :

有一個DES-CBC加密的Cipher是:

1
2
3
4
5
6
7
8
9
require 'openssl' 
c = OpenSSL::Cipher::Cipher.new('des-cbc')
c.encrypt 
c.key = "OAQXDOAO" 
c.iv = 0x00\x00\x00\x00\x00\x00\x00\x00"
data = c.update("Hello World") + c.final
data.unpack("H*")   

=> ["42de72147a35d3e2576ea2504e208117"]

CBC加密，每個Block為64bits (8 bytes)

1
2
3
C   = 0x42\xde\x72\x14\x7a\x35\xd3\xe2\x57\x6e\xa2\x50\x4e\x20\x81\x17
C1 (Block1)  = 0x42\xde\x72\x14\x7a\x35\xd3\xe2
C2 (Block2)  = 0x57\x6e\xa2\x50\x4e\x20\x81\x17

寫一個簡單的判斷Funciton :

1
2
3
4
5
6
7
8
9
10
11
12
13
def try_decrypt(data)
   begin
     c = OpenSSL::Cipher::Cipher.new('des-cbc')
     c.decrypt
     c.key = "OAQXDOAO"
     c.iv = 0x00\x00\x00\x00\x00\x00\x00\x00
     c.update(data)
     c.final
     return true
   rescue OpenSSL::Cipher::CipherError
     return false
   end
end

現在我們隨機訂一個 $C’$

1
C' = 0x00\x00\x00\x00\x00\x00\x00\x00

$C’||C_n$ = 0x00\x00\x00\x00\x00\x00\x00\x00\x57\x6e\xa2\x50\x4e\x20\x81\x17”

放進 try_decrypt(data) => false

1
2
3
4
5
0.upto(255) do |i|
   cprime = 0x00\x00\x00\x00\x00\x00\x00#{i.chr}" 
   0x57\x6e\xa2\x50\x4e\x20\x81\x17
   puts("#{i}: #{cprime.unpack("H*")}: #{try_decrypt(cprime)}") 
end
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
0: ["0000000000000000576ea2504e208117"]: false
1: ["0000000000000001576ea2504e208117"]: false
2: ["0000000000000002576ea2504e208117"]: false
3: ["0000000000000003576ea2504e208117"]: false
4: ["0000000000000004576ea2504e208117"]: false
5: ["0000000000000005576ea2504e208117"]: false
6: ["0000000000000006576ea2504e208117"]: false
7: ["0000000000000007576ea2504e208117"]: false
8: ["0000000000000008576ea2504e208117"]: false
9: ["0000000000000009576ea2504e208117"]: false
10: ["000000000000000a576ea2504e208117"]: false
...
...
220: ["00000000000000dc576ea2504e208117"]: false
221: ["00000000000000dd576ea2504e208117"]: false
222: ["00000000000000de576ea2504e208117"]: false
223: ["00000000000000df576ea2504e208117"]: false
224: ["00000000000000e0576ea2504e208117"]: false
225: ["00000000000000e1576ea2504e208117"]: true
226: ["00000000000000e2576ea2504e208117"]: false
227: ["00000000000000e3576ea2504e208117"]: false
228: ["00000000000000e4576ea2504e208117"]: false
229: ["00000000000000e5576ea2504e208117"]: false
230: ["00000000000000e6576ea2504e208117"]: false
...
...

當$C’$的最後一位為 \xe1 (225) 的時候 pass 了

當 try_decrypt(data) 回傳 True
代表解密的結果正確
這也意味著 “解密出來的明文” 的 Padding 是正確的
由於我們從頭到尾只有控制最後一個 byte

回傳 True 就代表著：

  1. $P’_n[8]=$ 0x01
  2. 與原本 Padding 相符 [這只發生在第一次ww]

$P_n = P’n \oplus C{(n-1)}\oplus C’$

=> $P_n[8] = P’n[8] \oplus C{(n-1)}[8]\oplus C’[8n]$

[✓] $P’n[8]$ : 必須是 0x01
[✓] $C{(n-1)}[8]$ : 密文有給 0xe2
[✓] $C’[8n]$ : 測試的結果 0xe1 (225)

=> $P_n[8]$ = 0x02

有了第n格的最後一個 byte
現在改變 $C’$，好讓 $P’_n[8]$ 的值為 0x02” ，繼續找倒數第二

$C’[8n] = P_n[8] \oplus P’n[8] \oplus C(n-1)[8]$
$C’[8n] =$ 0x02 $\oplus$ 0x02 $\oplus$ 0xe2 = 0xe2 $(226)$

$C’||C_n$ = 0x00\x00\x00\x00\x00\x00\x00\xe8\x57\x6e\xa2\x50\x4e\x20\x81\x17”

1
2
3
4
5
0.upto(255) do |i|
   cprime = 0x00\x00\x00\x00\x00\x00#{i.chr}\xe2" 
   0x57\x6e\xa2\x50\x4e\x20\x81\x17
   puts("#{i}: #{cprime.unpack("H*")}: #{try_decrypt(cprime)}") 
end
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
....
...
205: ["000000000000cde2576ea2504e208117"]: false
206: ["000000000000cee2576ea2504e208117"]: false
207: ["000000000000cfe2576ea2504e208117"]: false
208: ["000000000000d0e2576ea2504e208117"]: false
209: ["000000000000d1e2576ea2504e208117"]: false
210: ["000000000000d2e2576ea2504e208117"]: false
211: ["000000000000d3e2576ea2504e208117"]: true
212: ["000000000000d4e2576ea2504e208117"]: false
213: ["000000000000d5e2576ea2504e208117"]: false
214: ["000000000000d6e2576ea2504e208117"]: false
215: ["000000000000d7e2576ea2504e208117"]: false
...
....

=> $P_n[7] = P’n[7] \oplus C{(n-1)}[7] \oplus C’[8n-1]$

[✓] $P’n[7]$ : 必須是 0x02
[✓] $C{(n-1)}[7]$ : 密文有給 0xd3
[✓] $C’[8n-1]$ : 測試的結果 0xd3 (211)

=> $P_n[7]$ = 0x02

有了第n格的最後兩個 byte
現在改變 $C’$，好讓 $P’_n[8]$ 和 $P’_n[7]$ 的值都是 \x03 ，繼續去倒數第三個

$C’[8n] = P_n[8] \oplus P’n[8] \oplus C{(n-1)}[8]$
$C’[8n] =$ 0x02 $\oplus$ 0x03 $\oplus$ 0xe2 = 0xe3 $(227)$

$C’[8n-1] = P_n[7] \oplus P’n[7] \oplus C{(n-1)}[7]$
$C’[8n-1] =$ 0x02 $\oplus$ 0x03 $\oplus$ 0xd3 = 0xd2 $(210)$

1
2
3
4
5
0.upto(255) do |i|
   cprime = 0x00\x00\x00\x00\x00#{i.chr}\xd2\xe3" 
   0x57\x6e\xa2\x50\x4e\x20\x81\x17
   puts("#{i}: #{cprime.unpack("H*")}: #{try_decrypt(cprime)}") 
end
1
2
3
4
5
80: ["000000000050d2e3576ea2504e208117"]: false
81: ["000000000051d2e3576ea2504e208117"]: false
82: ["000000000052d2e3576ea2504e208117"]: true
83: ["000000000053d2e3576ea2504e208117"]: false
84: ["000000000054d2e3576ea2504e208117"]: false

=> $Pn[6]=Pn’[6] \oplus C_{n-1}[6] \oplus C’[8n-2]$

[✓] $P’n[6]$ : 必須是 0x03
[✓] $C{(n-1)}[6]$ : 密文有給 0x35
[✓] $C’[8n-2]$ : 測試的結果 0x52(82)

=> $P_n[7]$ = 0x64

現在已經知道 $P_n = ?????\x64\x02\x02$
繼續下去就可以算出整格 $P_n$
然後同理 $P_{(n-1)}$，$P_{(n-2)}$….
. . . .
. . .
. .
.

最後 $P_1$ ….. 

1
P1 = D(C1) \oplus IV

IV的值是多少.. 只能猜了

  • 試試看，預設IV，大部分的人都懶的設定
  • 從別的管道挖出IV
  • 猜測可能的值….
  • 暴力破解……

如果上述都沒用… 反正才 8bytes 將就一下囉XDDD


結論：
因為只經過 $\oplus$ 的運算，只要 $\oplus$ 兩次就可以還原
所以只要有人幫我們驗算（試著解密）檢查Padding 是對或錯，我們可以完全不用理會加密的方式以及Key，而得到明文

Tags: Intro Padding Oracle
← Multi-prime RSA 中國餘數定理 | Chinese Remainder Theorem (CRT) →