战队名称：兔斯基保护协会

手机：（需要的话找我要，这个帖子是比赛结束后要公开的，就不在这里写了）

参赛题目：街机少年

题目答案：IRrBJtrsJi@dBWnwvyppwIpswIygxJzz（对应的用户名是KCTF）

crackme程序见附件，

压缩包内容：

    Totoro.exe 主程序

    readme.txt 公开的用户名和Key，以及一些其它介绍

题目设计：

（如有需要，可以联系我提供源代码）

本题目采用规则二

题目架构：

获取用户输入->转码->小游戏（对战AI）->出结果

难度声明：

由VS2017编译链接无后续处理、没有使用虚拟机、没有使用反调试。

使用了 SetUnhandledExceptionFilter，是烟雾弹，加不加调试器都跑不到，不是反调试。

小游戏部分

本题的主体是一个小游戏——经典游戏捡石子。笔者小时候特别喜欢和同学玩这个游戏，现在笔者把这个游戏的玩法做成了AI。（鉴于AI就在程序里，破解者如果自己没有发现制胜方法，也可以把AI逆了，得到必胜玩法）

捡石子规则如下：

1）有n堆石子，对于我的程序来说，我设置了15堆石子，是个数组。此数组由用户名参与初始化，来实现用户名/游戏的多样性。（用户名只用在两个地方，一个是这里，另一处是用用户名的第一字节参与初始化了一个字符转换算法的底数，下文“转码部分”会再次提到）

2）玩家和AI轮流拿走其中一些石子，每次只能从其中一堆石子中拿，拿走的数量至少是1，最多可以把这堆拿空，但不能拿成负数。在此限制下，拿哪堆拿多少任意。

3）谁把最后一堆石子拿空，谁赢。（AI赢自然就是玩家输了，玩家都输了我就赢了，哈哈哈哈）

比如，有石子量为 3，4 的两堆石子。玩家操作后，变成 1，4 两堆。AI 操作后变成 1，1 两堆。玩家操作后，又变成 0，1 两堆。最后 AI 操作，变成 0，0两堆，AI胜！

现在问题来了，怎么保证玩家有必胜解呢？我通过数学方法，在初始化过程中确定了先手有利，即玩家必胜。

怎么保证唯一解呢？数学上可以证明，如果拿其中某一堆石子能保证胜利，那么拿这堆其它数量的石子，则是把必胜的地位交给对方。对于人类来说，可以寄希望于对方失误。而我的AI一旦拿到必胜的机会，绝不会失去。由此可见必胜操作序列由操作的堆序号来决定，因为对序号决定了操作数量。那么我规定人类玩家必须以可作为必胜操作的堆中最右侧（序号最大）的堆作为操作对象，其它都是违规。那么就保证了对序号的序列唯一性，进而保证了不存在多解。

我的AI是左优先，与用户相反，所以破解者需要真正破解AI，而不能简单的修改程序流让AI对战直接出Key.

这里，“可作为必胜操作的堆”的判断逻辑也可做为破解者掌握必胜序列的入手点。“右侧是否有其它可用于必胜操作的堆”的判断我写的很隐晦，程序内的大数组就是干这个的，不然破解者就没必要去分析AI了。我觉得直接分析AI更加容易。

破解这部分有4条路可走：

Path 1，逆向AI。不用自研算法。

Path 2，把AI修改成右优先，让AI对战。不用自研算法，也不用彻底逆向AI。（推荐）

Path 3，自研算法，破解者只需要针对KCTF用户这一个特殊的场景得出解即可。（有效，但不好玩）

Path 4，自研通用算法，自写AI，不用逆向AI。（推荐）

转码部分

转码部分分为两个部分，第一部分纯粹为了把用户输入转变为二进制数组，采用的是base64算法的变体。除了正文对应是变体之外，为了避免多解翻车，尾部转码是特殊的。

第二部分是为了增加破解难度的转码。通过用户名第一字节初始化base。假设此步转码前是A，转码后是B，用 B = pow(base, A) % p（p为素数） 来完成 A -> B 的转换（费尔马小定理）。由于 A，B，p都小于32。离散对数可轻易求出。每次转码后更新base.

这部分特征太明显，为了抵抗IDA，我用编程技巧进行了处理。

破解这部分有2条路可走：

Path 1，识别出模幂运算，利用32以内离散对数逆向。

Path 2，不识别什么运算，直接构造逆运算数组。（推荐）

总结

破解本程序，有好多方法。一款好游戏，常常是开放式的。在此致敬塞尔达传说和勇者斗恶龙！

[CTF入门培训]顶尖高校博士及硕士团队亲授《30小时教你玩转CTF》，视频+靶场+题目！助力进入CTF世界