算法分析：西湖论剑2019预赛题
本帖最后由 Panel 于 2022-3-17 21:41 编辑# 算法分析：西湖论剑2019预赛题
#### Tip:CTF普遍做题思维：
- ##### 尽可能查找可疑字符串，并分析所引用函数
- ##### 找到关键验证点，比如提示失败成功之类的逻辑处
- ##### 查看main函数逻辑结合运行cm大致分析得到程序整体运行逻辑
- ##### 跟踪分析flag最后一次加密结果作位左值的任何地方
- ##### 查找分析最后一次flag加密结果与任何我们人为操作数据的关系（比如最后一次flag加密结果和我们输入的字符串的关系）
- ##### 综合上面的方法便可排除干扰项从而利用最后一次flag加密结果逆向推导得到人为操作数据（通常就是正确的flag）
### 0x1:下载附件查壳发现是一个64位ELF文件，那么我们用虚拟机跑一下
##### 运行了一下，发现有输入，输入之后回车就结束了进程
### 0x2:使用IDA Pro 进行静态分析
##### shift+F12查找是否存在关键字符串
##### 发现字符串“correct!”,按照以往的经验来看这就是flag正确后的提示字符，那我们查看应用函数
##### 发现关键验证逻辑：只要if满足那么就会输出“correct！”，否则执行一系列运算后返回到了调用者main函数
##### 回到main函数后发现：ELF释放了内存后就结束了进程，也就证明了我们刚才在kali上跑的时候为啥输入了以后直接结束了进程而没有提示任何错误信息；
### 0x3:回到sub_400700函数分析刚才的关键验证判断
```
if ( !strncmp((const char *)s, "D9", 2uLL)
&& !strncmp((const char *)s + 20, "Mp", 2uLL)
&& !strncmp((const char *)s + 18, "MR", 2uLL)
&& !strncmp((const char *)s + 2, "cS9N", 4uLL)
&& !strncmp((const char *)s + 6, "9iHjM", 5uLL)
&& !strncmp((const char *)s + 11, "LTdA8YS", 7uLL) )
{
v6 = puts("correct!");
}
```
##### 可以看到s就是flag最后一轮加密的结果，也就是只要s满足以上条件则就证明了s就是正确的flag加密后得到的结果，那么可以先将s的正确字符写出(注意顺序)：
#### **char *s = "D9cS9N9iHjMLTdA8YSMRMp"**
### 0x4:老规矩，根据已知推未知，最后的目的都是找到s（最后一次flag加密结果）与我们的输入字符串之间的关系
##### 所以此时我们需要先找到我们输入的字符串放到了哪里？
```
__int64 __fastcall sub_400700(void *a1, _QWORD *a2, __int64 a3, size_t a4)
{
unsigned __int8 *v4; // rcx
_DWORD v6; // BYREF
int c; //
char v8; //
int v9; //
bool v10; //
unsigned __int8 *v11; //
char v12; //
int v13; //
int v14; //
unsigned __int64 i; //
size_t n; //
size_t v17; //
size_t v18; //
size_t j; //
size_t v20; //
int v21; //
unsigned __int64 v22; //
int v23; //
_DWORD *v24; //
__int64 v25; //
void *v26; //
int v27; //
size_t v28; //
__int64 v29; //
_QWORD *v30; //
void *s; //
char v32; //
s = a1;
v30 = a2;
v29 = a3;
v28 = a4;
v27 = -559038737;
v26 = malloc(0x100uLL);
v25 = v29; // v25是用户输入
v24 = v6;
v22 = 0LL;
v17 = 0LL;
for ( i = 0LL; i < v28; ++i )
{
v13 = *(unsigned __int8 *)(v25 + i);
*((_BYTE *)v26 + i) = byte_400E90 ^ v13;
*((_BYTE *)v26 + i) += *(_BYTE *)(v25 + i);
}
while ( 1 )
{
v12 = 0;
if ( v17 < v28 )
v12 = ~(*(_BYTE *)(v25 + v17) != 0);
if ( (v12 & 1) == 0 )
break;
++v17;
}
n = 138 * (v28 - v17) / 0x64 + 1;
v23 = ((v17 + v28) << 6) / 0x30 - 1;
v11 = (unsigned __int8 *)v6 - ((138 * (v28 - v17) / 0x64 + 16) & 0xFFFFFFFFFFFFFFF0LL);
memset(v11, 0, n);
v20 = v17;
v18 = n - 1;
while ( v20 < v28 )
{
v21 = *(unsigned __int8 *)(v25 + v20);
for ( j = n - 1; ; --j )
{
v10 = 1;
if ( j <= v18 )
v10 = v21 != 0;
if ( !v10 )
break;
v22 = v11 << 6;
v21 += v11 << 8;
v9 = 64;
v11 = v21 % 58;
*((_BYTE *)v26 + j) = v22 & 0x3F;
v22 >>= 6;
v21 /= 58;
v27 /= v9;
if ( !j )
break;
}
++v20;
v18 = j;
}
for ( j = 0LL; ; ++j )
{
v8 = 0;
if ( j < n )
v8 = ~(v11 != 0);
if ( (v8 & 1) == 0 )
break;
}
if ( *v30 > n + v17 - j )
{
if ( v17 )
{
c = 61;
memset(s, 49, v17);
memset(v26, c, v17);
}
v20 = v17;
while ( j < n )
{
v4 = v11;
*((_BYTE *)s + v20) = byte_400EB0];
*((_BYTE *)v26 + v20++) = byte_400EF0];
}
*((_BYTE *)s + v20) = 0;
*v30 = v20 + 1;
if ( !strncmp((const char *)s, "D9", 2uLL)
&& !strncmp((const char *)s + 20, "Mp", 2uLL)
&& !strncmp((const char *)s + 18, "MR", 2uLL)
&& !strncmp((const char *)s + 2, "cS9N", 4uLL)
&& !strncmp((const char *)s + 6, "9iHjM", 5uLL)
&& !strncmp((const char *)s + 11, "LTdA8YS", 7uLL) )
{
v6 = puts("correct!");
}
v32 = 1;
v14 = 1;
}
else
{
*v30 = n + v17 - j + 1;
v32 = 0;
v14 = 1;
}
return v32 & 1;
}
```
##### 阅读整个sub_400700函数并没有找到输入功能逻辑，所以回到main中去找
```
__int64 __fastcall main(int a1, char **a2, char **a3)
{
void *ptr; //
__int64 v5; // BYREF
char v6; // BYREF
int v7; //
v7 = 0;
v5 = 256LL;
sub_400D00(v6, 17LL, a3);
ptr = malloc(0x100uLL);
sub_400700(ptr, &v5, (__int64)v6, 0x10uLL);
free(ptr);
return 0LL;
}
```
##### 阅读main函数发现并没有直观看到任何输入逻辑，那还剩下一个sub_400D00函数，那十有八九可以确定输入逻辑在这个里面，那我们就进去看看；
```
__int64 __fastcall sub_400D00(__int64 a1, unsigned __int64 a2)
{
char buf; // BYREF
unsigned __int64 i; //
unsigned __int64 v5; //
__int64 v6; //
v6 = a1;
v5 = a2;
for ( i = 0LL; i < v5; ++i )
{
read(0, &buf, 1uLL);
*(_BYTE *)(v6 + i) = buf;
}
*(_BYTE *)(v6 + v5 - 1) = 0;
fflush(stdout);
return (unsigned int)i;
}
```
##### 果然循环read(0, &buf, 1uLL)了v5-1(a2= 17-1)次后将我们的输入字符串存到了v6(a1)中，回到main中查看便可知道我们输入的字符串存在了main局部变量的v6中；
##### 再看sub_400700(ptr, &v5, (__int64)v6, 0x10uLL)，第一个参数是申请得到256大小内存的首地址，&v5是一个变量256的地址，v6是我们输入的字符串所在地址，最后一个参数便是16，好，此时已经找到了我们输入的字符串和刚才的flag最后一次加密结果s的最基本关系在sub_400700函数中；
### 0x5:到sub_400700中顺藤摸瓜找到flag最后加密结果与我们输入字符的具体关系
- ##### 找到s作为左值的所有逻辑，只有这三处
##### 列出与当s作为左值时右值变量有哪些：
1. ##### byte_400EB0：123456789ABCDEFGHJKLMNPQRSTUVWXYZabcdefghijkmnopqrstuvwxyz；
2. ##### v11：未知的变量；
- ##### 寻找我们输入字符串作右值；
##### 首先，我们先看我们输入的字符串在main中的v6在sub_400700叫啥名；
##### v25 = v29 = a3 = v6；
##### 好，已经知道我们输入的字符串地址在这里叫v25,那开始找其作右值的地方；
```
//第一处
for ( i = 0LL; i < v28; ++i )
{
v13 = *(unsigned __int8 *)(v25 + i);
*((_BYTE *)v26 + i) = byte_400E90 ^ v13;
*((_BYTE *)v26 + i) += *(_BYTE *)(v25 + i);
}
//第二处
while ( 1 )
{
v12 = 0;
if ( v17 < v28 )
v12 = ~(*(_BYTE *)(v25 + v17) != 0);
if ( (v12 & 1) == 0 )
break;
++v17;
}
//第三处
while ( v20 < v28 )
{
v21 = *(unsigned __int8 *)(v25 + v20);
for ( j = n - 1; ; --j )
{
v10 = 1;
if ( j <= v18 )
v10 = v21 != 0;
if ( !v10 )
break;
v22 = v11 << 6;
v21 += v11 << 8;
v9 = 64;
v11 = v21 % 58;
*((_BYTE *)v26 + j) = v22 & 0x3F;
v22 >>= 6;
v21 /= 58;
v27 /= v9;
if ( !j )
break;
}
++v20;
v18 = j;
}
```
##### 既然找到了这两个变量作左右值对应逻辑位置后，那我们就开始寻找s和v25的关联了；
##### 从上面可以知道，s作左值的时的未知右值只有v11，v11是一个数组
```
*((_BYTE *)s + v20) = byte_400EB0];
*((_BYTE *)v26 + v20++) = byte_400EF0];
```
##### 从以上两行代码可以知道s数组的值来自于byte_400EB0中下标为v11的值，这里其实密码学做得多的就可以看出，这属于一种编码,其实就是base系列的编码，我们可以查看编码表的长度确定是什么编码，那我们就去算一下byte_400EB0的长度123456789ABCDEFGHJKLMNPQRSTUVWXYZabcdefghijkmnopqrstuvwxyz可以知道byte_400EB0的长度是58，而且这串编码表中没有O0l/+,所以可以直接确定以上两行代码输入base58加密的最后一步,为了严谨我们只需验证v11的由来是v25产生的（base58加密过程中产生编码表数组的下角标）便可以验证此加密就是base58加密，从而便验证知道s就是我们输入的字符base58加密后的结果
##### 此时，我们需要先知道base58的加密过程：
“**将ascii编码的字符串（256进制），转换成58进制。然后按照58进制的码表转换成相应的字符。**
1、将字符串的每个字节换算成ASCII(0-255) (字符串实际上就是256进制的数字组合)：
- 源字符串为：ABD
- 换算后： 65 66 68
2、将256进制的数字转换成10进制数字：
- 256进制数：65 66 68
- 转成10进制：(65 * 256 + 66) * 256 + 68 = 4276804
3、将10进制数字转换成58进制数字：
- 10进制数：4276804
- 58进制数： 21 53 20 0
4、将58进制数字的每一位按照表格转换成对应的字符：
- 58进制数：21 53 20 0
- 码表：123456789abcdefghijkmnopqrstuvwxyzABCDEFGHJKLMNPQRSTUVWXYZ
- 转换后的字符：nVm1
【注】任意进制之间的转换，先将数字转10进制再转其它进制“
转自：[编码算法-Base58 - 简书 (jianshu.com)](https://www.jianshu.com/p/d8af38e091be)
#### 阅读v11作左值源码：
```
while ( v20 < v28 )
{
v21 = *(unsigned __int8 *)(v25 + v20);
for ( j = n - 1; ; --j )
{
v10 = 1;
if ( j <= v18 )
v10 = v21 != 0;
if ( !v10 )
break;
v22 = v11 << 6;
v21 += v11 << 8;
v9 = 64;
v11 = v21 % 58;
*((_BYTE *)v26 + j) = v22 & 0x3F;
v22 >>= 6;
v21 /= 58;
v27 /= v9;
if ( !j )
break;
}
++v20;
v18 = j;
}
```
##### v28是我们main中传过来的16，v20小于16就执行那么就可以执行循环，那我们知道在main中我们输入的字符长度就是16个，所以不由而知这里的v20在循环之前为0
##### ***(unsigned __int8 *)(v25 + v20)**便是将我们输入的字符依次赋值给v21
##### 接下来的整个for循环便是上面所说的base58的加密过程的2、3以及第四步中产生58进制数那里，产生的58进制数便放到了v11中作为上面所说的base58的加密过程中的第四步来编码我们输入的字符串；
### 0x6:最终逻辑梳理，得出结果
##### 通过以上分析，可以得知我们整个程序的逻辑：输入字符串v6----->v6进行字符串编码,结果放入s----->对比s是否等于指定字符串（其实也就是正确flag进行base58加密后的字符串）------>对比相等则提示“correct!”，否则释放内存结束程序
### 0x7:结果
### 0x8:总结
#### 记住做这种题的时候一律采用顺腾摸瓜的思想，找对应的左右值分析所在逻辑，不要分析所有逻辑，会浪费很多时间而且造成干扰（因为我这个题就应为分析所有逻辑浪费了很多时间）
##### 现在看我来分析是不是感觉很简单？因为我把坑踩完了做对了才来写的，我这个题花了好几个小时，因为傻白甜去分析，没有顺腾摸瓜！
Panel 发表于 2022-3-18 16:08
@Hmily h大，请问以后是否这种贴都选择CTF分区？刚看到有CTF分区
嗯，都放ctf分类里面。 赞，学习了！ 感谢分享 感谢楼主的分享 学习了学习了，真香！ 看着眼困呀，高手，支持 感谢分享,学习了 感谢分享,学习了，赞 看着眼困呀，高手，支持
学到了学到了
页:
[1]
2