Padding Oracle Attack

Coursera 上 Jonathan Katz 的密码课程里的 Week4 PA
Padding Oracle Attack 的复现

背景

CBC 模式是一种分组链接模式，目的是为了使原本独立的分组密码加密过程形成迭代，使每次加密的结果影响到下一次加密。初始化向量 IV 与第一组明文(分组 1)异或后，再经过运算得到的结果作为新的 IV，用于下一分组(分组 2)，不断迭代下去：
加密

解密过程是加密过程的逆过程：
解密

在实际运用中，明文的长度并不会刚好为 16 字节的倍数，这时，分组的最后一块的长度必然小于 16 字节。这时，就需要使用填充(padding)。题目给的是 PKCS #7 填充方式，规则是需要填充 n 个字节，那么这 n 个填充位就填上 n 的 16 进制数。如
缺少 1 位(1 个 Padding)， 填充位为： 0x01
缺少 5 位(5 个 Padding)， 填充位为： 0x05 0x05 0x05 0x05 0x05

原理

当我们提交 IV+密文到服务端时，服务端便会按照字符串的第一组为 IV，之后为密文进行解密。如此题中：
IV： 9F0B13944841A832B2421B9EAF6D9836
C_Block1：813EC9D944A5C8347A7CA69AA34D8DC0
C_Block2：DF70E343C4000A2AE35874CE75E64C31

解密后，若最后的 Padding 不正确(值和数量不一致)，则解密程序往往会抛出异常(Padding Error)。在这题里就是返回 0。而利用此回显，我们就可以判断出 Paddig 是否正确(这里为了方便显示，只展示了后 8 个字节)：
过程

可以看到，padding 为 0x17，却只填充了一位，那么这种情况下，服务端就会返回 0。
接下来要利用选择密文攻击的思想，不断调整，修正 IV。来对 IValue 进行猜测。不断地调整 IV 的值，目的是解密后，最后一个字节的值为正确的 Padding。第一次进行穷举时，是 0×01。因为 IValue 是固定的(未知)，所以从 0×00~0xFF 之间，只可能有一个 IV 的值与 IValue 的最后一个字节进行 XOR 后，结果是 0×01。
在 CBC 模式下进行解密时，第一组密文还原成明文时需要先用密钥解密得到一个中间结果(记为 IVALUE)，然后将 IVALUE 与 IV 进行异或得到明文
而我们通过穷举 IV，利用服务端检测 padding 是否正确的返回值来判断 IV 是否正确，一旦正确，就立即可以通过 IV 异或 padding 来求得 IVALUE 值。

解密

如对密文第一块进行第一轮求解：
Padding：0x01
IV： 00000000000000000000000000000000

第一轮爆破求得 IV 的最后一个字节为 0x17 时，服务端返回 1。由于第一次我们要使得 padding 为 0x01（这里有个坑点），所以，我们便立刻可以求出 IVALUE 的最后一个字节为 0x01⊕0x17=0x16。
那么此时有

Padding：0x01
IV： 00000000000000000000000000000017
Ivalue：******************************16

为什么说这里有个坑点呢？首先要明白我们将什么作为 IV 没出错的标志：服务端返回 0 还是 1。这个地方我们期望服务器得到的 padding 为 0x01，这样服务器就认为 IV 没问题，返回 1。
但是实际上，如果服务器得到的 padding 为 0x02 0x02，服务器同样也会认为 IV 没错，也返回 1。这样会有错误的情况出现。
不过没事，如果爆破的过程中某一步因为这样的原因出错了，那么下一位的爆破就不会有结果，我们可以察觉到这个坑点。
另一种避免错误的方法就是不在循环里写 break，即使找到了 IV 的最后一个字节为 0x17，也继续跑，这样如果发现有 2 个值都是对的，就要注意了。

第二轮爆破时，要使得 padding 为 0x02，所以，由于 Ivalue 的最后一位已知，我们可以求得此时 IV 最后一位为 0x16⊕0x02=0x16。即

Padding：0x02
IV： 00000000000000000000000000000014

第二轮爆破时求得 IV 的倒数第二个字节为 0xF4 时， 服务端返回 1。而此时 padding 为 0x02，所以，Ivalue 的倒数第二位也可以求出来了 0xF4⊕0x02=0xF6。即

Padding：0x02
IV： 0000000000000000000000000000F414
Ivalue：****************************F616

不断地进行以上过程，就可以把 Ivalue 全部求出。最后，将 Ivalue 与题目给出的初始 IV 进行异或，就可以得到第一组的明文（下划线代表空格）
IV： 9F0B13944841A832B2421B9EAF6D9836
Ivalue1： C66A6AB56818C74792257EEA8F0CF616
M_Block1：Yay!_You_get_an_

然后对第二组密文进行以上过程，就可以把 M_Block2 求出。这里的 IV 为第一组的密文：

IV： 813EC9D944A5C8347A7CA69AA34D8DC0
Ivalue2： C010E9E46DAEC33F7177AD91A84686CB
M_Block2：A._=)（已删去末尾填充字符）

所以，总的密文就为：
M：Yay!_You_get_an_ A._=)

代码

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
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
# -*- coding: cp936 -*-
from oracle import *
from Crypto.Util import strxor
import re

C = '9F0B13944841A832B2421B9EAF6D9836813EC9D944A5C8347A7CA69AA34D8DC0DF70E343C4000A2AE35874CE75E64C31'
BLOCK = 2
div = len(C) / (BLOCK + 1)
C = re.findall('.{' + str(div) + '}', C)

Oracle_Connect()
M = []
IVALUE = []
for b in range(BLOCK): #对 2 组密文分别求解
    print '[*] Detecting Block',b+1
    IV = C[b]
    Ivalue = []
    iv = '00000000000000000000000000000000' #初始化 iv
    iv = re.findall('.{2}', iv)[::-1]
    padding = 1

    for l in range(16):
        print "  [+] Detecting IVALUE's last", l + 1 , 'block'
        for ll in range(l):
            iv[ll] = hex(int(Ivalue[ll], 16) ^ padding)[2:].zfill(2) #更新 iv

        for n in range(256): #遍历 0x00-0xFF
            iv[l] = hex(n)[2:].zfill(2)
            data = ''.join(iv[::-1]) + C[b + 1]
            
            ctext = [(int(data[i:i + 2], 16)) for i in range(0, len(data), 2)]
            rc = Oracle_Send(ctext, 2)
            
            if str(rc) == '1': #Padding 正确时, 记录 Ivalue, 结束爆破
                Ivalue += [hex(n ^ padding)[2:].zfill(2)]
                break

        print '    [-]', ''.join(iv[::-1])
        print '    [-]', ''.join(Ivalue[::-1])
        
        padding += 1

    Ivalue = ''.join(Ivalue[::-1])
    IVALUE += [Ivalue]

    #IV 与 Ivalue 异或求密文
    m = re.findall('[0-9a-f]+', str(hex(int(IV, 16) ^ int(''.join(Ivalue), 16))))[1].decode('hex')
    M += [m]

    print '[#] Detecting Block', b + 1 ,'-- Done!'
    print '[#]', 'The IValue' + str(b + 1), 'is:', Ivalue
    print '[#]', 'The M' + str(b + 1) , 'is:', m
    print '-' * 50
    
Oracle_Disconnect()

print '[!] The Intermediary Value is:', ''.join(IVALUE)
print '[!] The M is:', ''.join(M)

结果

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
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
[*] Detecting Block 1
  [+] Detecting IVALUE's last 1 block
    [-] 00000000000000000000000000000017
    [-] 16
  [+] Detecting IVALUE's last 2 block
    [-] 0000000000000000000000000000f414
    [-] f616
  [+] Detecting IVALUE's last 3 block
    [-] 000000000000000000000000000ff515
    [-] 0cf616
  [+] Detecting IVALUE's last 4 block
    [-] 0000000000000000000000008b08f212
    [-] 8f0cf616
  [+] Detecting IVALUE's last 5 block
    [-] 0000000000000000000000ef8a09f313
    [-] ea8f0cf616
  [+] Detecting IVALUE's last 6 block
    [-] 0000000000000000000078ec890af010
    [-] 7eea8f0cf616
  [+] Detecting IVALUE's last 7 block
    [-] 0000000000000000002279ed880bf111
    [-] 257eea8f0cf616
  [+] Detecting IVALUE's last 8 block
    [-] 00000000000000009a2d76e28704fe1e
    [-] 92257eea8f0cf616
  [+] Detecting IVALUE's last 9 block
    [-] 000000000000004e9b2c77e38605ff1f
    [-] 4792257eea8f0cf616
  [+] Detecting IVALUE's last 10 block
    [-] 000000000000cd4d982f74e08506fc1c
    [-] c74792257eea8f0cf616
  [+] Detecting IVALUE's last 11 block
    [-] 000000000013cc4c992e75e18407fd1d
    [-] 18c74792257eea8f0cf616
  [+] Detecting IVALUE's last 12 block
    [-] 000000006414cb4b9e2972e68300fa1a
    [-] 6818c74792257eea8f0cf616
  [+] Detecting IVALUE's last 13 block
    [-] 000000b86515ca4a9f2873e78201fb1b
    [-] b56818c74792257eea8f0cf616
  [+] Detecting IVALUE's last 14 block
    [-] 000064bb6616c9499c2b70e48102f818
    [-] 6ab56818c74792257eea8f0cf616
  [+] Detecting IVALUE's last 15 block
    [-] 006565ba6717c8489d2a71e58003f919
    [-] 6a6ab56818c74792257eea8f0cf616
  [+] Detecting IVALUE's last 16 block
    [-] d67a7aa57808d75782356efa9f1ce606
    [-] c66a6ab56818c74792257eea8f0cf616
[#] Detecting Block 1 -- Done!
[#] The IValue1 is: c66a6ab56818c74792257eea8f0cf616
[#] The M1 is Yay! You get an 
--------------------------------------------------
[*] Detecting Block 2
  [+] Detecting IVALUE's last 1 block
    [-] 000000000000000000000000000000ca
    [-] cb
  [+] Detecting IVALUE's last 2 block
    [-] 000000000000000000000000000084c9
    [-] 86cb
  [+] Detecting IVALUE's last 3 block
    [-] 000000000000000000000000004585c8
    [-] 4686cb
  [+] Detecting IVALUE's last 4 block
    [-] 000000000000000000000000ac4282cf
    [-] a84686cb
  [+] Detecting IVALUE's last 5 block
    [-] 000000000000000000000094ad4383ce
    [-] 91a84686cb
  [+] Detecting IVALUE's last 6 block
    [-] 00000000000000000000ab97ae4080cd
    [-] ad91a84686cb
  [+] Detecting IVALUE's last 7 block
    [-] 00000000000000000070aa96af4181cc
    [-] 77ad91a84686cb
  [+] Detecting IVALUE's last 8 block
    [-] 0000000000000000797fa599a04e8ec3
    [-] 7177ad91a84686cb
  [+] Detecting IVALUE's last 9 block
    [-] 0000000000000036787ea498a14f8fc2
    [-] 3f7177ad91a84686cb
  [+] Detecting IVALUE's last 10 block
    [-] 000000000000c9357b7da79ba24c8cc1
    [-] c33f7177ad91a84686cb
  [+] Detecting IVALUE's last 11 block
    [-] 0000000000a5c8347a7ca69aa34d8dc0
    [-] aec33f7177ad91a84686cb
  [+] Detecting IVALUE's last 12 block
    [-] 0000000061a2cf337d7ba19da44a8ac7
    [-] 6daec33f7177ad91a84686cb
  [+] Detecting IVALUE's last 13 block
    [-] 000000e960a3ce327c7aa09ca54b8bc6
    [-] e46daec33f7177ad91a84686cb
  [+] Detecting IVALUE's last 14 block
    [-] 0000e7ea63a0cd317f79a39fa64888c5
    [-] e9e46daec33f7177ad91a84686cb
  [+] Detecting IVALUE's last 15 block
    [-] 001fe6eb62a1cc307e78a29ea74989c4
    [-] 10e9e46daec33f7177ad91a84686cb
  [+] Detecting IVALUE's last 16 block
    [-] d000f9f47dbed32f6167bd81b85696db
    [-] c010e9e46daec33f7177ad91a84686cb
[#] Detecting Block 2 -- Done!
[#] The IValue2 is: c010e9e46daec33f7177ad91a84686cb
[#] The M2 is A. =)
--------------------------------------------------
[!] The Intermediary Value is: c66a6ab56818c74792257eea8f0cf616c010e9e46daec33f7177ad91a84686cb
[!] The M is: Yay! You get an A. =)

最后

这种 Padding Oracle Attack 的攻击方式，在 2011 年的 Pwnie Rewards 上被评为“最具价值的服务器漏洞”。在实现过程中，利用选择密文攻击的思想，不断调整，修正 IV，来对 Intermediary Value 进行猜测，这部分是最难理解的，也是这种攻击方式的精髓。 Padding Oracle Attack 的关键在于攻击者能够获知解密的结果是否符合 Padding。
在实现和使用 CBC 模式的分组加密算法时，注意异常捕获即可，比如加上 try catch 机制，来进行防御。

好玩好玩~
就是服务器换地址了挺坑的...


来呀快活呀

过程记录
#工具 #Python #密码学 #Web #Vuln #Poc&Exp
Padding Oracle Attack
https://www.tr0y.wang/2017/10/06/Crypto1/
作者
Tr0y
发布于
2017年10月6日
更新于
2024年4月12日
许可协议