-
-
[原创][2020 KCTF] 题目提交
-
2020-9-7 10:52
-
团队名称： 金左手
参赛题目： 内个内个内个
题目答案： AECCC0DE0C3256F75E37A6BFA227A2ED3D54AC964B43544632303230466C6167826B49EB0A305A72C2E92C18A0901280F47791BAE00932B0
题目类型： Window平台CrackMe
系统需求： WIN10/64
成功提示： Success!
================================================================================================================================================================
【设计说明】
游戏原型是熄灯拼图，通过若干次的操作，每次切换某方块及其上下左右四个相邻方块的开关状态，直到全部状态完成翻转。
首先是个10*10的熄灯拼图，这规模小能直接搜到答案，需要最少44次操作，实现完全翻转，得到的解(开关操作位置图)是：
1 2 3 4 5 6 7 8 9 | 防止直接搜到答案，后面又加了一个40*40的，需要解线性方程组（用sage很快就跑出结果），详情参考hxxps://mathworld.wolfram.com/LightsOutPuzzle.html然后这个10*10的解7位一组转成15个字节，每个字节最高位补充了校验位，最后再补充1个字节，变成16字节的key，用k表示，为了压缩输入长度，40*40的解因为也是左右上下及对角线对称，可以用一个八分之一的局部三角形经三次镜像得到40*40的矩阵，输入只需要(1+19)*19/2=190位，8位一组转成24个字节用e表示整个完整key是56字节，可以表示为：aaaakkkkkkkkkkkkkkkkbbbbccccddddeeeeeeeeeeeeeeeeeeeeeeee其中aaaa,bbbb,cccc,dddd是固定常数，a部分的DWORD经过8轮Koopman多项式的crc运算k，b，c，d部分的28字节组成14个WORD，用ECC做一次点乘运算,ECC参数：p=65011，a=65008，b=6，G=(1,2)这个微型ECC直接穷举即可求解，每个点会有两个解，收集所有最高位排除多解 |
【难度提升】
算法用C语言实现，然后用一个简单的C编译器编译成opcode，再解释执行，相当于一个简单的虚拟机，感觉这个虚拟机也是相当简单了，于是把解释器也编译一遍，做一次嵌套的解释执行，大概意思是：从前有座山，山上有座庙，庙里有个老和尚，老和尚在给小和尚讲故事，故事讲的是。。。
【解题思路】
虚拟机比较简单，先把第一层opcode还原出来，发现逻辑竟然等同于解释器自身，只是opcode定义有些乱序，然后再还原出第二层和第三层，最后第四层里就只剩下简单的验证逻辑了
然后ECC的p只有16位，直接穷举即可求解
LightsOut求解直接用sage也是迅速得出结果
crc暴力穷举会慢点，不过4字节得相当于可逆，有快速破解方法。
[CTF入门培训]顶尖高校博士及硕士团队亲授《30小时教你玩转CTF》，视频+靶场+题目！助力进入CTF世界
