Padding Oracle Attack

Author Avatar
Tr0y 10月 06, 2017 20:28:15 本文共 2k 字
  • 文为知己者书
  • 在其它设备中阅读本文章

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._=)

代码

# -*- 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)

结果

[*] 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 机制,来进行防御。

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

End

What do you think?

本文标题: Padding Oracle Attack
原始链接: http://www.tr0y.wang/2017/10/06/Crypto1/
发布时间: 2017.10.06-20:28
最后更新: 2019.05.31-16:36
版权声明: 本站文章均采用CC BY-NC-SA 4.0协议进行许可。转载请注明出处!