通过angr另类求解一道CISCN题目

admin

该题的精髓在于对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[v114];   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[3];   v126 = box2[5];   *(data - 2) ^= box2[0] ^ HIWORD(box2[5]) ^ (box2[3] << 16);   v127 = box2[7];   *(data - 1) ^= box2[2] ^ (v126 << 16) ^ HIWORD(box2[7]);   v128 = box2[1];   *data ^= box2[4] ^ (v127 << 16) ^ HIWORD(box2[1]);   data[1] ^= box2[6] ^ 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[0] + 4), *(_QWORD *)(v8 + 8)); Number_set((__int64)number5, v6); v9 = std::setw(box0, 3i64); (*(void (__fastcall **)(char *, _QWORD))v9)((char *)number3 + *(int *)(number3[0] + 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[0]     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[0] 是 box 的 5 字节输入
_box[1] 是 box 的 68 字节输出

本质上就是调用 claripy 的 eval 功能

1 2 3 4

def sbox(b5):     S=claripy.Solver()     S.add(_sbox[0]==claripy.BVV(b5,5*8))     return long_to_bytes(S.eval(_sbox[1],1)[0],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}