一个安卓逆向题。拿到一个 APK, 跑起来会让你输入一个字符串, 点 CHECK 报 Invalid flag。
静态分析
jadx 打开,看 MainActivity 的点击处理:
public void button_click(View view) {
String input = ((EditText) findViewById(...)).getText().toString();
if (!input.startsWith("flag{") || !input.endsWith("}")
|| input.length() != 38 || !check(input.substring(5, 37))) {
Toast.makeText(this, "Invalid flag", 0).show();
} else {
Toast.makeText(this, "Congratz", 0).show();
}
}
格式约束:
- 以
flag{开头、}结尾, 长 38 check()拿中间 32 个字符
check 干了什么
check() 里是双层 for 循环(每层 32 次),对输入逐字符做变换。
返回 true 的条件是:双层 for 循环每一轮都不能 return false,也就是每一轮都要满足这条等式(反编译代码原文):
((114514.0d - Math.sqrt(d - (4.0d * deep))) / 2.0d) + ((Math.sqrt(d2 - (4.0d * dark)) + 114514.0d) / 2.0d) == 114514.0d
简化：
(114514 - √(d - 4·deep) + √(d2 - 4·dark) + 114514) / 2 = 114514
⇒ √(d2 - 4·dark) = √(d - 4·deep)
⇒ d2 - 4dark = d - 4deep
double d = (double) ehhh;
double d2 = (double) ehhh;
Double.isNaN(deep);
Double.isNaN(d);
Double.isNaN(dark);
Double.isNaN(d2);
...
double deep = (double) (1919810 - ahhhhh[ohh][0]); // 内置期望值
double dark = (double) (1919810 - thats); // 输入实际算出来的
从代码中可以看出: d == d2 dark = deep thats == ahhhhh[ohh][0]
d 和 d2 其实是同一个常数,与输入无关——v7 从 0 开始把 114514 自加了 114514 次,int32 溢出后是 228,554,308,每轮相同,再转成 double。正因为两边是同一个数,等式才会塌缩成 dark == deep。
观察
thats 是每轮外层循环(每一行)一个的累加结果:内层 j 从 0 走到 31,对每个字符做 thats += (charAt(j) & 255) * wow[ohh][j]。
实现上是嵌套自增循环:对每个 j,先把 thats 自增 char 值那么多次,再整体重复 wow[ohh][j] 轮——纯 int 运算,效果等价于乘加。设 32 个字符为 a1..a32(ASCII 值):
thats = (int)a1 * wow[ohh][0] + (int)a2 * wow[ohh][1] + ... + (int)a32 * wow[ohh][31]
求解
解矩阵，把 32×32 系数矩阵(wow)每一行末尾拼上对应常数(ahhhhh),得到增广矩阵, 然后高斯消元。
simple()— 高斯消元:逐列把主元归一,消掉下面行changeRow()— 对角线主元为 0 时和下面的行交换(否则除数为 0)getResult()— 回代求解,Math.round()后当 char 输出
for (int k = 0; k < n; k++) {
if (matrix[k][k] == 0) changeRow(n, k, matrix);
for (int i = 0; i < n; i++) {
float temp = matrix[i][k];
for (int j = 0; j < n + 1; j++) {
if (i < k) break; // 上面的行已经算完
if (temp == 0) continue;
if (temp != 1) matrix[i][j] /= temp;
if (i > k) matrix[i][j] -= matrix[k][j];
}
}
}
Flag
补回 flag{ 和 }:
flag{fd954d994c4955f5e9c0901460b38aee}