通过angr另类求解一道CISCN题目
该题的精髓在于对5字节密钥的爆破而爆破又需要我们复现其算法以这篇随笔记录一个利用约束求解“偷懒”的办法思路看附件显然是对 PNG 进行加解密造一个假 PNG 给它加密
可以发现对同一个文件而言
每次加密结果都不一样在 main 函数输入的地方调试
这是和一个长度为 3 的 key 进行循环 XOR
1
2
3
4
5
6
7
8
9
10
11
do
{
v114 = 0i64;
if ( v112 < 3 )
v114 = v112;
*v113 ^= key3;
v112 = v114 + 1;
++v113;
--v111;
}
while ( v111 ); // OTP key3
在 main 函数输出的地方调试
这是和一个 box 做流加密
步长 16 字节
每次步进都对 box 做一次混淆
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
do
{
mix(box2);
v125 = box2;
v126 = box2;
*(data - 2) ^= box2 ^ HIWORD(box2) ^ (box2 << 16);
v127 = box2;
*(data - 1) ^= box2 ^ (v126 << 16) ^ HIWORD(box2);
v128 = box2;
*data ^= box2 ^ (v127 << 16) ^ HIWORD(box2);
data ^= box2 ^ HIWORD(v125) ^ (v128 << 16);
data += 4;
v124 += 16;
}
while ( v124 < (unsigned __int64)v133 );
追溯 box 的来源可以在 main 函数开头看到
box 的种子长度为 5
并且通过 debug 可以知道
这两个数字都属于 0-9 不过 box 种子对一个码表取了下标
码表是 qscfthnjik
如果数字为 12345
则种子为 scfth
1
2
3
4
5
6
v8 = std::setw(box0, 5i64);
(*(void (__fastcall **)(char *, _QWORD))v8)((char *)number5 + *(int *)(number5 + 4), *(_QWORD *)(v8 + 8));
Number_set((__int64)number5, v6);
v9 = std::setw(box0, 3i64);
(*(void (__fastcall **)(char *, _QWORD))v9)((char *)number3 + *(int *)(number3 + 4), *(_QWORD *)(v9 + 8));
Number_set((__int64)number3, (v7 >> 63) + v7 - 1000 * v6);
两个数字均来源于时间
因此必须爆破
考虑到对 PNG 头进行 OTP 时使用的密钥在一个很小的范围内
可以利用这一点进行爆破我的规则：
[*]pt 是 \x89PNG
[*]ct 来自题目 \x7B\x92\x1F\x3E
[*]pt^ct 的前三位每位均属于 0-9
[*]pt^ct 的第四位和第一位相同（因为是循环 OTP）
爆破时需要顺着逆向出 box 的生成算法正文box 的生成算法并不是很”密码学”
然而它却很长很繁琐考虑到 box 的生成过程中没有任何外界干扰
可以借助 angr 偷个大懒众所周知 angr 提供了 FFI (Foreign Function Interface) 功能
将相同的思路运用在任意代码上：
对一连串基本块模拟执行可以得到两个相关联的 BitVec
一个是这串基本块的输入（可视为已知 因为要爆破）一个是输出
其之间的约束等效于加密算法这个流程只需调用一次取得 2 个 BitVec 即可
暂且叫这两个 BitVec 为“模型”在其他地方可以随意调用这个模型而且，
根本不需要知道算法具体是什么（一般来讲都不可名状）不过这样做的难点是：
angr 对 windows 平台的支持不太完备
为了稳定且快速的运行，我们需要手动设置上下文（包括栈）以 box 的生成为例
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
def symbolic_sbox():
begin_addr=0x3980+base_addr
end_addr=0x3c35+base_addr
begin_state=project.factory.blank_state(addr=begin_addr)
begin_state.options.update({angr.options.ZERO_FILL_UNCONSTRAINED_MEMORY, angr.options.ZERO_FILL_UNCONSTRAINED_REGISTERS})
A=claripy.BVS('A',5*8)
stack_addr=0x600000
data_addr=0x500000
begin_state.memory.store(data_addr,A)
begin_state.regs.r12=data_addr
begin_state.regs.rbp=stack_addr
begin_state.regs.rsp=stack_addr-0x100
simgr=project.factory.simgr(begin_state)
simgr.explore(find=end_addr)
end_state=simgr.found
B=end_state.memory.load(begin_state.regs.rsp+0x420,17*4)
return (A, B)
其中
长度为 5 的种子地址位于 r12
rbp 和 rsp 之间的差值是 0x100
box 最终的长度是 17 个 uint
位于 rsp + 0x420下面是调用模型的示例
这里通过获得的模型 _box 伪造了 box 的生成函数
_box 是 box 的 5 字节输入
_box 是 box 的 68 字节输出本质上就是调用 claripy 的 eval 功能
1
2
3
4
def sbox(b5):
S=claripy.Solver()
S.add(_sbox==claripy.BVV(b5,5*8))
return long_to_bytes(S.eval(_sbox,1),blocksize=17*4)
为了爆破还需获得 mix 的模型
它的要求很简单
rcx 中存储 68 字节的 box 数据即可
原理同上最后一个问题上述做法还有一个缺点：相比原生算法可能会更慢
借助 pwnlib 的 mbruteforce 是一个好办法然而在 Windows 环境中使用 multiprocessing 会有一些小小的问题
可以用 pickle 把 box 和 mix 的模型存到硬盘
在硬件条件更好的 Linux 服务器中导入这也是该做法的一个优势：可持久化，无需次次符号执行接下来应用上述爆破规则从码表 qscfthnjik 中选取 5 个
如果 mbruteforce 的进度条失效
可以使用 tqdm 和分段功能手搓一个进度条
1
2
3
4
5
6
7
context.log_level='CRITICAL'
for i in tqdm(range(1000)):
x=mbruteforce(f,charset,length=5,method="fixed",start=(i+1,1000))
if x is not None:
print(i)
print(x)
break
在我的机器上大约 20 分钟后得出结果
种子为 iqsqn
三位数为 002通过最后一步的流加密复原 PNG 得到 flag
flag{2ed562e6-36fc-435e-9d97-2738d3774954}
页:
[1]