老实说一看到是安卓题我还是挺怵的，因为算法一般都是arm类型的so文件，而我一直都没有一个合适的arm调试环境。
不管怎么样，先上手用jadx查看一下吧。
果然，界面直接导入了kctf2021这个动态库并声明了stringFromJNI这个native函数，并且直接用它对输入进行了判断。
用IDA打开libkctf2021.so，定位到目标函数
看来关键算法就在sub_39998这个函数里了。在ida里看到这个函数这么清晰明白的显示出来，我的第一感觉是哪里又藏着hook会修改这个函数，于是先简单检查了一下，确定so没有预加载可疑的函数。

关键函数逻辑很清楚，当输入字符串长度为14时，初始化一个表（这个表对我解题并没有用，下面略过不说），然后将输入每4bit转成一个dword，变成一个长为28的数组。
然后调用sub_39658处理一个固定字符串，根据字符串的首行搜索可以得知是这是boost的一个序列化。为了弄清楚反序列化后的对象是什么东西，我这里有两个选择：1是下载boost开发库开发实验一下，2是找个东西模拟运行一下。
因为unidbg比boost更快下载完，因此我最终模拟运行了这个反序列化函数并打印了对象的内存
序列化后的对象v13继续使用sub_39910进行处理
首次看这个函数并没有看懂，只能推断他应该是一个很多层的递归处理，并且会根据输入去反序列化其他16个序列化对象中的一个。

结合sub_39614函数可以分析出v13这个对象应该是一个比较大的类似二叉树一样的结构，具有非常多的节点，但是每个节点非常简单，只占16个字节内存。这里发现了一个比较复杂的函数sub_39570（但是这个函数同样对我解题并没有用，下面略过不说……因为我最后都没看懂这个函数）。
最后看一下本题check的逻辑：结尾虽然有一堆的判断跳转，实际归纳起来就是判断最终的v13是不是只有3个特定节点了。
因此梳理一下这道题的思路：作者定制了一棵非常大的二叉树，然后用sub_39910把拆为4bit后的28个输入转为16棵小树中的一颗并插入到二叉树值为122的对应节点中，形成一棵不带122节点的树。然后使用sub_39614对这个树的所有节点进行删减，如果最后只剩3个节点就算成功（3个节点应该是这道题理论上能删减到的最少节点吧）。
那么这道题的破题之处就在于，因为用户输入选择的分支必然是散布到整棵树的不同部位，那对其中某分支能独自占据的最大分支来说，其删减结果其实都与其他输入无关。因此用户的每个输入相对其他输入很可能都是独立的，整个大题可以拆分成为28道相同的小题，而每道小题的解合起来就是整个大题的解。因此我们的目标转换为了在保持27个输入不变时，求剩下那个输入能使最终节点数最少的值。
因为unidbg在运行UXTB16指令时会报错，因此模拟执行的办法在这里就中断了。


幸好整个程序可以转为等效的C代码，通过查询arm汇编指令集，把clz和UXTB16转为相应的函数或代码，实现了每个输入的暴力破解。实际代码中分成两次，第一次是所有的低4bit，第二次是所有的高4bit（因为可见字符最高位为0，所以其实只有3bit），实际使用的指标也不是节点数最少，而是二叉树层数最少（从结果看应该是等效的）。

[培训]内核驱动高级班，冲击BAT一流互联网大厂工作，每周日13:00-18:00直播授课