2025 KCTF 2025-08-20 17:59 上海
本题共有8支战队成功提交flag
2025 KCTF 于8月15日中午12点正式开赛!比赛设置了多维度的评分体系,包括难度值、火力值和精致度积分。今天中午12点,第三题《邪影显现》已截止答题。
*注意:签到题《废柴少年觉醒》持续开放,整个比赛期间均可提交答案获得积分
本题共有8支战队成功提交flag,其中前3名分别是:【hzqmwne】、【Namikaze】、【COMPASS】
KCTF评委团队点评:
这题考查RSA逆向与大数运算理解。核心逻辑是对输入串执行多轮模逆与扰动操作,幂次依次为质数序列(-3、-7、-11…-37)。
结合常量"KCTF2025"与MD5(name)进行对齐校验,整体流程可还原为可逆的RSA运算。题目重点在模数分解、逐步推演可逆性以及大数库差异识别,既考数学功底也考工程实现,非常适合作为进阶逆向练习。
一起来看看本题的设计思路和解题思路吧~
一、
设计思路
出题战队:金左韭
战队成员ID:ccfer、KevinsBobo、大帅锅、linhanshi、Lyxk
题目描述
easy rsa192
运行环境
WIN10,VCRUNTIME140
公开组序列号
name: EA35B2C3F2B5FCE4
code: 20DB698F803FB15F6DFFBADD0E125ABEBE96494B0CCCA620
python版验证逻辑
def kctf2025_cm(name, code):
n = 0x56F67550F16A00390DCF0B2715708E61C5B3F23101862FC1
e = [0x03,0x07,0x0B,0x11,0x13,0x17,0x1D,0x1F,0x25]
a = 2 ** 184
x = int.from_bytes(bytes.fromhex(code), byteorder='big')
for i in e:
x = pow(x,i,n)
x = gmpy2.invert(x,n)
x = x + a
h = 'KCTF2025'.encode('utf-8') + hashlib.md5(name.encode('utf-8')).digest()
r = int.from_bytes(h, byteorder='big')
if x == r:
print('ok')
else:
print('error')
二、
赛题解析
该解析由论坛会员ID:【mb_mgodlfyn】提供
主要逻辑在 sub_402380 里,此函数非常长,不过 AI 的初步分析还是给出了很多有价值的信息:
a1 是你要输入的原始 flag。
程序会把 a1 经过 MD5 和一系列自定义变换(和 "KCTF2025"、常量混合)生成一个 中间密文 v262。
然后要求你给出的 a2 等于 v262 的 hex 编码。
如果 a1、a2 对不上,函数就 goto LABEL_209(失败)。
后续部分(没贴完)大概率还会用 a1 的 MD5、v262、KCTF2025 再混合校验,确保不是随便伪造。
接下来提示AI,a1是已知的name,a2是待求的serial,AI给出了进一步的分析:
将某个由 a2 推导出来的大数 v234 导出为 24 字节、再整体反转成 v262,随后把 v262 的前 20 字节作为比较对象(但先把前 4 字节视作一个 32 位整型整体 +1),它们必须等于"KCTF2025" || MD5(a1)[0..11]
注意:有一个“++v262[0]”对前 4 字节(小端视角)做了 +1 的扰动——这意味着你在实际对齐这 20 字节时,要考虑这个 +1
这里的函数族 sub_43B620 / sub_43BBA0 / sub_43BEB0 / sub_43C460 / sub_41C1B0 / sub_41D9C0 / sub_41C4F0 / sub_41BB50 ... 很像是椭圆曲线点/有限域元素的装配与组合(乘法、加法、标量乘、归约、序列化等等)
sub_4362A0/435DA0/436270/436960/436980/435BC0 这组看起来是大整数/点的构造、加/乘、导入导出
从最终情况看,其中关于椭圆曲线/有限域的结论是错误的,但其他分析结论完全正确(而且此时提供给AI的上下文只包含 sub_402380 的反编译伪代码,还不包含任何它调用的子函数,因此这只是对sub_402380整体逻辑的初步印象),特别的是给出了a1(name)参数经过运算的比较串
"KCTF2025" || MD5(a1)[0..11]、大数运算、++v262[0]的扰动这三项提示,对后续的人工分析启发很大。
优先查看 AI 指出的几个子函数,注意到引用了常量区的一些字符串:
.rdata:0045A7E8 ; const char aFatalErrorSExi[].rdata:0045A7E8 aFatalErrorSExi db 'fatal error:',0Ah ; DATA XREF: zhalt+6↑o.rdata:0045A7F5 db ' %s',0Ah.rdata:0045A7FB db 'exit...',0Ah,0.rdata:0045A804 ; const char aDBytesReallocF[].rdata:0045A804 aDBytesReallocF db '%d bytes realloc failed',0Ah,0.rdata:0045A804 ; DATA XREF: zsetlength+7F↑o.rdata:0045A81D align 10h.rdata:0045A820 aReallocationFa_0 db 'reallocation failed in zsetlength',0.rdata:0045A820 ; DATA XREF: zsetlength+98↑o.rdata:0045A842 align 4.rdata:0045A844 ; const char aDBytesCallocFa[].rdata:0045A844 aDBytesCallocFa db '%d bytes calloc failed',0Ah,0.rdata:0045A844 ; DATA XREF: zsetlength+AA↑o.rdata:0045A85C aAllocationFail db 'allocation failed in zsetlength',0.rdata:0045A85C ; DATA XREF: zsetlength+C3↑o.rdata:0045A87C aNegativeSizeAl_0 db 'negative size allocation in zsetlength',0.rdata:0045A87C ; DATA XREF: zsetlength:loc_454EFD↑o.rdata:0045A8A3 align 4.rdata:0045A8A4 ; const char aZstartFailureR[].rdata:0045A8A4 aZstartFailureR db 'zstart failure: recompile with smaller NBITS',0Ah,0.rdata:0045A8A4 ; DATA XREF: zstart+4D↑o.rdata:0045A8D2 align 4.rdata:0045A8D4 aInZzeroFirstAr db 'in zzero, first argument',0.rdata:0045A8D4 ; DATA XREF: z2div+E5↑o.rdata:0045A8D4 ; z2mul+1B↑o ....rdata:0045A8ED align 10h.rdata:0045A8F0 aInZcopySecondA db 'in zcopy, second argument',0.rdata:0045A8F0 ; DATA XREF: zcopy+4E↑o.rdata:0045A90A align 4.rdata:0045A90C aInZintozSecond db 'in zintoz, second argument',0.rdata:0045A90C ; DATA XREF: zintoz+14↑o.rdata:0045A927 align 4.rdata:0045A928 aInZuintozSecon db 'in zuintoz, second argument',0.rdata:0045A928 ; DATA XREF: zultoz+28↑o.rdata:0045A944 aInZsubposThird db 'in zsubpos, third argument',0.rdata:0045A944 ; DATA XREF: sub_4555A0+1B↑o.rdata:0045A95F align 10h.rdata:0045A960 aInZaddThirdArg db 'in zadd, third argument',0.rdata:0045A960 ; DATA XREF: zadd+76↑o.rdata:0045A978 aInZsubThirdArg db 'in zsub, third argument',0.rdata:0045A978 ; DATA XREF: zsub+106↑o.rdata:0045A990 aInZsmulThirdAr db 'in zsmul, third argument',0.rdata:0045A990 ; DATA XREF: sub_454F60+72↑o.rdata:0045A9A9 align 4.rdata:0045A9AC aInKarMulThirdA db 'in kar_mul, third argument',0.rdata:0045A9AC ; DATA XREF: sub_452D20+14↑o.rdata:0045A9C7 align 4.rdata:0045A9C8 aInKarMulLocals db 'in kar_mul, locals',0Ah,0.rdata:0045A9C8 ; DATA XREF: sub_452D20+7C↑o.rdata:0045A9DC aInKarSqSecondA db 'in kar_sq, second argument',0.rdata:0045A9DC ; DATA XREF: sub_453230+F↑o.rdata:0045A9F7 align 4.rdata:0045A9F8 aInKarSqLocals db 'in kar_sq, locals',0Ah,0.rdata:0045A9F8 ; DATA XREF: sub_453230+5D↑o.rdata:0045AA0B align 4.rdata:0045AA0C aDivisionByZero_4 db 'division by zero in zsdiv',0.rdata:0045AA0C ; DATA XREF: zsdiv:loc_454E81↑o.rdata:0045AA26 align 4.rdata:0045AA28 aInZsdivThirdAr db 'in zsdiv, third argument',0.rdata:0045AA28 ; DATA XREF: zsdiv+6F↑o.rdata:0045AA41 align 4.rdata:0045AA44 aDivisionByZero_1 db 'division by zero in zdiv',0.rdata:0045AA44 ; DATA XREF: zdiv:loc_4540C3↑o.rdata:0045AA5D align 10h.rdata:0045AA60 aInZdivLocals db 'in zdiv, locals',0Ah,0 ; DATA XREF: zdiv+108↑o.rdata:0045AA71 align 4.rdata:0045AA74 aInZdivThirdArg db 'in zdiv, third argument',0.rdata:0045AA74 ; DATA XREF: zdiv+12C↑o.rdata:0045AA8C aInZdivFourthAr db 'in zdiv, fourth argument',0.rdata:0045AA8C ; DATA XREF: zdiv+141↑o.rdata:0045AAA5 align 4.rdata:0045AAA8 aDivisionByZero_3 db 'division by zero in zmod',0.rdata:0045AAA8 ; DATA XREF: zmod:loc_4547D1↑o.rdata:0045AAC1 align 4.rdata:0045AAC4 aInZmodLocal db 'in zmod, local',0 ; DATA XREF: zmod+D8↑o.rdata:0045AAD3 align 4.rdata:0045AAD4 aInZmodThirdArg db 'in zmod, third argument',0.rdata:0045AAD4 ; DATA XREF: zmod+EC↑o.rdata:0045AAEC aModulusZeroInZ db 'modulus zero in zinvmod',0.rdata:0045AAEC ; DATA XREF: zinvmod:loc_454214↑o.rdata:0045AB04 aDivisionByZero_2 db 'division by zero in zinvmod',0.rdata:0045AB04 ; DATA XREF: zinvmod:loc_45421E↑o.rdata:0045AB20 aUndefinedInver db 'undefined inverse in zinvmod',0.rdata:0045AB20 ; DATA XREF: zinvmod:loc_454228↑o.rdata:0045AB3D align 10h.rdata:0045AB40 aInZxxeuclLocal db 'in zxxeucl, locals',0Ah,0.rdata:0045AB40 ; DATA XREF: sub_455960+31↑o.rdata:0045AB54 aInZxxeuclThird db 'in zxxeucl, third argument',0.rdata:0045AB54 ; DATA XREF: sub_455960:loc_455A2F↑o.rdata:0045AB6F align 10h.rdata:0045AB70 aInZxxeuclFourt db 'in zxxeucl, fourth argument',0.rdata:0045AB70 ; DATA XREF: sub_455960+E4↑o.rdata:0045AB8C aZeroOrNegative db 'zero or negative argument(s) in zinv',0.rdata:0045AB8C ; DATA XREF: sub_454190:loc_4541DB↑o.rdata:0045ABB1 align 4.rdata:0045ABB4 aInZ2mulSecondA db 'in z2mul, second argument',0.rdata:0045ABB4 ; DATA XREF: z2mul+52↑o.rdata:0045ABCE align 10h.rdata:0045ABD0 aInZ2divSecondA db 'in z2div, second argument',0.rdata:0045ABD0 ; DATA XREF: z2div+35↑o.rdata:0045ABEA align 4.rdata:0045ABEC aInZlshiftThird db 'in zlshift, third argument',0.rdata:0045ABEC ; DATA XREF: zlshift+B9↑o.rdata:0045AC07 align 4.rdata:0045AC08 aInZrshiftThird db 'in zrshift, third argument',0.rdata:0045AC08 ; DATA XREF: zrshift+116↑o.rdata:0045AC23 align 4.rdata:0045AC24 aInZlowbitsThir db 'in zlowbits, third argument',0.rdata:0045AC24 ; DATA XREF: ztoul:loc_455780↑o
容易查到这些字符串出自 freelip 大数计算库(https://github.com/lrobot/freelip/blob/master/lip.c)而在对a2(serial)参数做hexdecode的代码后面,第一段代码恰好调用到了这些函数:
zultoz((int)v275, 6, &v191);
v26 = Buffer;
if ( strlen(Buffer) == 48 )
{
for ( j = 0; j < 24; ++j )
{
v28 = *v26;
if ( (*v26 < 48 || v28 > 57) && (unsigned __int8)(v28 - 65) > 5u )
goto LABEL_209;
v29 = v26[1];
if ( (v29 < 48 || v29 > 57) && (unsigned __int8)(v29 - 65) > 5u )
goto LABEL_209;
if ( sscanf(v26, "%02X", &v275[j]) != 1 )
goto LABEL_209;
v26 += 2;
}
v30 = 0;
v31 = &v275[23];
do
{
v32 = *v31--;
v274[v30++] = v32;
}
while ( v30 < 24 );
v227 = 0;
zultoz((int)v274, 6, &v227); // sub_455880, v274 (first arg) is reversed hexdecoded a2 , which is serial
zmul(v227, v227, &v245); // sub_4547E0, v245 = v227 * v227 = x * x = x**2
zmul(v227, v245, &v263); // sub_4547E0, v263 = v227 * v245 = x* x**2 = x**3
zmod(v263, v191, &v245); // sub_454440
zinvmod(v245, v191, &v245); // sub_4541F0, tmp2 = pow(tmp1, -3, pp)
v266 = 6;
ztoul(v245, (int *)v274, &v266); // sub_4556D0, now v274 (second arg) is serial ** (-3) % pp
v33 = 0;
v34 = 4 * v266;
v266 = v34;
if ( v34 > 0 )
{
do
{
v275[v33] = v273[v34 - v33 + 255];
++v33;
}
while ( v33 < v34 );
}
++*(_DWORD *)v275; // ?? tmp1 -> tmp2
...
其中sub_454440和sub_4541F0可以直接从函数里面引用的常量字符串确认是zmod和zinvmod,头尾的sub_455880和sub_4556D0按照常理应该是大数的导入和导出(与源代码对照后可以确认是zultoz和ztoul),那么中间的sub_4547E0必然是某种大数运算函数。
freelip这个库的大数内部表示有些奇怪,它内部的int数组好像每一项只使用了30bit左右,导致经过zultoz后内部的数组与原始字节并不一致,这点与其他常见库完全不同,导致不太方便通过调试判断sub_4547E0的变换,但是可以猜测大概率不是加法就是乘法
不过既然前面的zultoz以及后面的zmod和zinvmod已知,那么可以先从最上面0x402ADC处的zultoz导出v275的内存值确认v191的模数的值(记为pp),再分别测试一下x*(-3)%pp和x**(-3)%pp,然后调试查看ztoul导出的v274,即可确定sub_4547E0是zmul,执行的是乘法运算。
顺便导出了模数为0x56f67550f16a00390dcf0b2715708e61c5b3f23101862fc1,是0x402780附近的赋值的常量。
通过yafu或factordb可以得到模数的质因数分解,它恰好可以分解为两个质数的乘积:
1 |
|
根据RSA的计算原理,对于 c = pow(m, e, n) ,在已知n的分解为p*q时,可以由c反向计算出m:phi = (p-1)*(q-1) , d = pow(e, -1, phi) , m = pow(c, d, n)
因此,这里对a2(serial)的第一次运算tmp1 = pow(a2, -3, pp)完全可逆。
再注意到 0x402C47 出的运算 ++*(_DWORD *)v275; (回顾开始,AI也注意到了这处扰动) ,在 tmp1 的大端内存表示的前四个字节做了一次自增。虽然运算很奇怪,但可逆,于是暂记结果为 tmp2。
再看接下来的一段代码:
v35 = &v275[23];
v220[0] = 0;
for ( k = 0; k < 24; ++k )
{
v37 = *v35--;
*((_BYTE *)v221 + k) = v37;
}
v220[0] = 6;
v220[2] = 0;
sub_4065C0(v220);
v38 = (_DWORD *)v220[0];
v238[1] = bignumber_mul___((int)v221, (int)v221, v220[0], (int)v239, (int)v238);// sub_406450, v232 = v214 * v214 = x ** 2
v238[2] = 0;
sub_4065C0(v238);
v256[1] = bignumber_mul___((int)v221, (int)v239, v238[0], (int)v257, (int)v256);// v250 = v214 * v232 = x ** 3
v256[2] = v220[2] ^ v238[2];
sub_4065C0(v256);
v203[0] = bignumber_mul___((int)v257, (int)v257, v256[0], (int)v204, (int)&v202);// v199 = v250 * v250 = x ** 6
v203[1] = 0;
sub_4065C0(&v202);
v256[1] = bignumber_mul___((int)v204, (int)v221, (int)v38, (int)v257, (int)v256);// v250 = v199 * v214 = x ** 7
v256[2] = v220[2] ^ v203[1];
sub_4065C0(v256);
bignumber_mod(v256, v188, v238); // sub_4067B0, first arg v245 is x ** 7 , second arg v185 is pp (same as above)
bignumber_invmod(v238, v188, v238); // sub_4074B0, tmp3 = pow(tmp2, -7, pp)
v39 = (v238[1] + 7) >> 3;
v266 = v39;
sub_4065C0(v238);
memset(v275, 0, v39);
for ( m = 0; m < v39; v274[v42 + 255] = v41 )
{
v41 = v239[m];
v42 = v39 - m++;
}
++*(_DWORD *)v275; // // ?? tmp3 -> tmp4
sub_406450函数被多次调用,它的传入参数有点混乱(除了栈,还包含ecx和eax)。在最后还调用了sub_4067B0和sub_4074B0,整体的调用模式与第一段看起来非常相似。
这里仍然先猜测是大数运算,这里应该是换了一个大数库,但经过调试验证,容易验证sub_406450、sub_4067B0、sub_4074B0分别是mul、mod、invmod,模数与上面相同,计算结果为tmp3 = pow(tmp2, -7, pp),加上最后0x402E19处的++*(_DWORD *)v275;,仍然是大端序高位DWORD自增扰动得到的tmp4。
接下来的一组sub_41A180、sub_41AB20、sub_41AF50分别也是mul、mod、invmod,以及0x402FC7处相同的扰动,得到tmp5 = pow(tmp4, -11, pp)和tmp6
以 ++*(_DWORD *)v275; 为支点,发现 sub_402380 大函数里相同的计算模式反复出现了9次,每次都换了一个大数库,但都是先对上一轮的结果做若干次乘法累加(后面几轮的中间穿插了取模)、一次取模、一次模逆、一次扰动。
因此,后面的逻辑无需再仔细逆向,直接找到每组重复次数最多的函数记为mul,然后静态计算出每轮mul的次数(这里也很有规律,每一轮最终的mul指数构成了递增的质数序列)并通过调试验证即可。
以下整理出每轮的三个大数运算函数以及最终的幂次:
(注意不同库的参数不同(例如,有的是三参数且出参可以分别位于三个位置或返回值,有的是两参数且出参复用某个入参的位置,还有多参数包含一些额外的长度信息等),中间还会穿插大数构造/析构/复制等辅助函数,排除干扰即可)
sub_402380的校验逻辑整理为python后非常短小:
def b2i(s):
return int.from_bytes(s, "big")
def i2b(n):
r = n.to_bytes((n.bit_length()+7)//8, "big")
return r
def perturbation(v):
bb = i2b(v)
f = int.from_bytes(bb[:4], 'little')
f = (f + 1) & 0xffffffff
bbb = f.to_bytes(4, 'little') + bb[4:]
return b2i(bbb)
name = "..."
serial = "..."
n = 2132319876367679106148824069448800305036941072478331350977
tmp = b2i(bytes.fromhex(serial))
for e in [-3, -7, -11, -17, -19, -23, -29, -31, -37]:
tmp = pow(tmp, e, n)
tmp = perturbation(tmp)
assert b"KCTF2025" + hashlib.md5(name.encode()).digest() == b2i(tmp)
根据name计算serial的反向代码为:
def b2i(s):
return int.from_bytes(s, "big")
def i2b(n):
r = n.to_bytes((n.bit_length()+7)//8, "big")
return r
def inverse_pow(v, e):
p = 45424490472579293708671645907
q = 46942075831425428541187578011
n = p * q
phi = (p-1) * (q-1)
d = pow(e, -1, phi)
m = pow(v, d, n)
return m
def inverse_perturbation(v):
bb = i2b(v)
f = int.from_bytes(bb[:4], 'little')
f = (f - 1) & 0xffffffff
bbb = f.to_bytes(4, 'little') + bb[4:]
return b2i(bbb)
name = "KCTF"
tmp = b2i(b"KCTF2025" + hashlib.md5(name.encode()).digest())
for e in [-37, -31, -29, -23, -19, -17, -11, -7, -3]:
tmp = inverse_perturbation(tmp)
tmp = inverse_pow(tmp, e)
serial = i2b(tmp).hex().upper()
print(serial)
最终答案:
1 2 |
|
1
扫码参赛
第四题《血色试炼》火热挑战中
关于KCTF
看雪CTF(简称KCTF)是圈内知名度最高的技术竞技,从原CrackMe攻防大赛中发展而来,采取线上PK的方式,规则设置严格周全,题目涵盖Windows、Android、iOS、Pwn、智能设备、Web等众多领域。
扫码进入2025 KCTF
主办方
支持单位
看雪CTF比赛分为两个阶段,所有论坛会员均可参与,第一阶段是防守篇,防守方根据比赛要求制作题目,根据题目被破解的时间排名,被破解时间长者胜出。第二阶段为攻击篇,攻击第一阶段的题目,根据攻击成功的时间与题目排名,破解时间短且破解题目数多者胜。既给了防守方足够的施展空间,也避免过度浪费攻击方的时间。从攻防两个角度看,都是个难得的竞技和学习机会。
看雪CTF比赛历史悠久、影响广泛。自2007年以来,看雪已经举办十多个比赛,与包括金山、360、腾讯、阿里等在内的各大公司共同合作举办赛事。比赛吸引了国内一大批安全人士的广泛关注,历年来CTF中人才辈出,汇聚了来自国内众多安全人才,高手对决,精彩异常,成为安全圈的一次比赛盛宴,突出了看雪论坛复合型人才多的优势,成为企业挑选人才的重要途径,在社会安全事业发展中产生了巨大的影响力。
- End -
球分享
球点赞
球在看
戳“阅读原文”一起来充电吧!
