首页
论坛
课程
招聘
[原创]KCTF2021秋 第十一题 图穷匕见 writeup
2021-12-15 01:07 15336

[原创]KCTF2021秋 第十一题 图穷匕见 writeup

2021-12-15 01:07
15336


======================逆向篇==========================


依靠强大的IDA,一边DOTA2,一边逆向,一局还没打完,就把程序逆完了,实在太小了


大致逻辑:


先处理输入,转成16字节binary,然后 aes subbytes, 倒序一下


整个crackme,都是以 uint64 为block来处理的,所以输入的 serial 被拆成了 s0, s1 两个数


然后 进入 crypt

用 a0, a1, k0-k4, s0, s1, 计算出 v0, v1 校验两个常数

用 b0, b1, k0-k4, s0, s1, 计算出 v2, v3 校验两个常数


其中crypt代码也非常简单,一共5轮计算,注意中间3组都是异或,结果一模一样



其中 Xor很容易看出来,下面一个Mul,长这个样子


根据 a2&1 != 0 就 xor a1,得出这是一个乘法,xor意味着 GF(2) 的加法

根据 a1 的最高位确定是否需要异或一个magic,得出这是一个多项式模乘,64位,模数 = 0x10000000247F43CB7



======================算法篇==========================


综合一下,大概就是这样的

有两个未知数的多项式环,系数是GF(2^64)的多项式,分别做了5次迭代运算


`

i0 = a0;
i1 = a1;
i2 = i0 + (i1 + k0 + s0)^3;
i3 = i1 + (i2 + k1 + s1)^3;
i4 = i2 + (i3 + k2 + s0)^3;
i5 = i3 + (i4 + k3 + s1)^3;
i6 = i4 + (i5 + k4 + s0)^3;
验证 i5 == v0, i6 == v1

i0 = b0;
i1 = b1;
i2 = i0 + (i1 + k0 + s0)^3;
i3 = i1 + (i2 + k1 + s1)^3;
i4 = i2 + (i3 + k2 + s0)^3;
i5 = i3 + (i4 + k3 + s1)^3;
i6 = i4 + (i5 + k4 + s0)^3;
验证 i5 == v2, i6 == v3



由于迭代了5次,次数太高,完全不知道怎么解,看论坛大牛们都在玩sagemath,所以我也下了一个学习一下


找到多元多项式,看看文档与例子。。。一边看一边练习


突然看到这个:


这个神级操作,居然让两个未知数少了一个,可以消元!!

死马当活马医,试试看呗


上面的crypt流程,i5, i6已知具体的值,所以 (i5 - v[0]) == (i6 - v[1]) 

那么,用 resultant 方法处理一下 (i5 - v[0]) 和 (i6 - v[1]) ,应该可以消元

消元后,就变成 s0或者 s1 的单变量多项式了,假设消去s0, 变成 s1的单变量高次多项式 ===> 设为 1(太长,不贴出来了)

但突然想到下面还有一遍 crypt的流程,一样可以消元出另一个s1的单变量高次多项式 ====> 设为 2 (太长,不贴出来了)

1与2是两个关于s1的单变量多项式,他们有共同的因子式,求一下他们的最大公共因子,就得出了关于s1的线性方程,求解得到 s1,同理得到s0


======================求解篇==========================


sage脚本如下


F.<x>=GF(2^64, modulus=0x10000000247F43CB7.bits())
R.<s0, s1>=PolynomialRing(F)
k = [
    F.fetch_int(0x20F4641148FA59A5),
    F.fetch_int(0x96950F0D368EB90D),
    F.fetch_int(0x7467551A8419E0B5),
    F.fetch_int(0x1A61218FE968D86),
    F.fetch_int(0x192DB7EB78969270)
]
o = [
    F.fetch_int(0x73C51960EF361B30),
    F.fetch_int(0xFBD5C824382C435D),
    F.fetch_int(0x79EEBA9CCF47A451),
    F.fetch_int(0x55B4D0E1061D12D0)
]
v = [
    F.fetch_int(0x55250D8CEEDFFB35),
    F.fetch_int(0xDBAFC899D2AAD5EC),
    F.fetch_int(0xD30CE81D5CFD183E),
    F.fetch_int(0x3C205341A484C650)
]

a, b = o[0], o[1]
for i in range(5):
    a, b = b, a + (b + k[i] + [s0, s1][i % 2])^3
p0, p1 = a - v[0], b - v[1]

a, b = o[2], o[3]
for i in range(5):
    a, b = b, a + (b + k[i] + [s0, s1][i % 2])^3
q0, q1 = a - v[2], b - v[3]

r1, r2 = p0.resultant(p1, s0), q0.resultant(q1, s0)
r3, r4 = p0.resultant(p1, s1), q0.resultant(q1, s1)

fy = gcd(r1, r2)
fx = gcd(r3, r4)

[x0, x1] = fx.coefficients()
[y0, y1] = fy.coefficients()

x = hex((x1/x0).integer_representation())
y = hex((y1/y0).integer_representation())

print(x, y)





有了s0, s1,就很容易得出全小写的flag

de23f9d82798377ea01743d43d5353cd



【公告】看雪招聘大学实习生!看雪20年安全圈的口碑,助你快速成长!

最后于 2021-12-15 11:49 被海风月影编辑 ,原因:
收藏
点赞1
打赏
分享
最新回复 (0)
游客
登录 | 注册 方可回帖
返回