攻防notsequence
杨辉三角
https://baike.baidu.com/item/杨辉三角/215098
拖入ida 看main函数
int __cdecl main() {
_DWORD *v0; // eax int v2; // [esp 14h] [ebp-Ch] _DWORD *v3; // [esp 1Ch] [ebp-4h] memset(&unk_8049BE0, 0, 0x4000u); puts("input raw_flag please:"); v3 = &unk_8049BE0; do {
v0 = v3 ; scanf("%d", v0); } while ( *(v3 - 1) ); v2 = check1(&unk_8049BE0); if ( v2 == -1 ) {
printf("check1 not pass"); system("pause"); } if ( check2(&unk_8049BE0, v2) != 1 ) {
printf("check2 not pass!"); exit(0); } if ( v2 == 20 ) {
puts("Congratulations! fl4g is :\nRCTF{md5(/*what you input without space or \\n~*/)}");
exit(0);
}
return 0;
}
看到两个关键函数
分析check1
int __cdecl sub_80486CD(int a1)
{
int j; // [esp+0h] [ebp-14h]
int v3; // [esp+4h] [ebp-10h]
int i; // [esp+8h] [ebp-Ch]
int v5; // [esp+Ch] [ebp-8h]
v5 = 0;
for ( i = 0; i <= 1024 && *(4 * i + a1); i = v5 * (v5 + 1) / 2 )
{
v3 = 0;
for ( j = 0; j <= v5; ++j )
v3 += *(4 * (j + i) + a1);
if ( 1 << v5 != v3 )
return -1;
++v5;
}
return v5;
}
用c语言复现一下
#include <stdio.h>
int main()
{
int j; // [esp+0h] [ebp-14h]
int v3; // [esp+4h] [ebp-10h]
int i; // [esp+8h] [ebp-Ch]
int v5; // [esp+Ch] [ebp-8h]
int a1[20] = {
0};
v5 = 0;
for ( i = 0; i <= 20 ; i = v5 * (v5 + 1) / 2 ) //i是前v5项和
{
v3 = 0;
for ( j = 0; j <= v5; ++j )
{
v3+=a1[j+i]; //v3代表a1数组中第i项之后v5+1个数之和sum(a1[i],a[i+1],...,a[i+v5])
printf("%d ",j);
}
if ( 1 << v5 != v3 ) //判断v3是否 == 2的v5次方
return -1;
++v5;
printf("%d\n",i);
}
return 0;
}
运行输出：输出 i 和 j
0 0
0 1 1
0 1 2 3
0 1 2 3 6
0 1 2 3 4 10
0 1 2 3 4 5 15
所以可以看作有v5行，，每行的开头是第 v5 * (v5 + 1) / 2 个数
v3是 的行的数字之和，后面判断是否等于2的v5次方
这个if判断是根据 的性质：
分析check2
int __cdecl sub_8048783(int a1, int a2)
{
int v3; // [esp+10h] [ebp-10h]
int v4; // [esp+14h] [ebp-Ch]
int i; // [esp+18h] [ebp-8h]
int v6; // [esp+1Ch] [ebp-4h]
v6 = 0;
for ( i = 1; i < a2; ++i )
{
v4 = 0;
v3 = i - 1;
if ( !*(4 * i + a1) )
return 0;
while ( a2 - 1 > v3 )
{
v4 += *(4 * (v3 * (v3 + 1) / 2 + v6) + a1);
++v3;
}
if ( *(4 * (v3 * (v3 + 1) / 2 + i) + a1) != v4 )
return 0;
++v6;
}
return 1;
}
复现为c代码
#include <stdio.h>
int main()
{
int v3; // [esp+10h] [ebp-10h]
int v4; // [esp+14h] [ebp-Ch]
int i; // [esp+18h] [ebp-8h]
int v6; // [esp+1Ch] [ebp-4h]
int a2 = 20;
int a1[200] = {
0};
v6 = 0;
for ( i = 1; i < a2; ++i )
{
v4 = 0;
v3 = i - 1;
while ( v3 < a2 - 1 )
{
v4 += a1[v3 * (v3 + 1) / 2 + v6]; // v4 += a1[0,1,3,6...] v4+=a1[2,4,7,11]（a1下标是杨辉三角形的左边和右边的位置下标（第几个））
//所以v4就是杨辉三角形从第一到第n行最左（或最右）的数字的和
printf("%d \n ",v3 * (v3 + 1) / 2 + v6);
++v3;
}
if(a1[v3 * (v3 + 1) / 2 + v6] != v4)
{
return 0;
}
++v6;
}
return 0;
}
if判断的是根据杨辉三角形的一条性质：
分析总体
所以两个函数就是判断输入的字符串是否是杨辉三角形
下面就是和flag直接相关的判断，判断v2（杨辉三角形行数） == 20
if ( v2 == 20 )
{
puts("Congratulations! fl4g is :\nRCTF{md5(/*what you input without space or \\n~*/)}");
exit(0);
所以解密就是将杨辉三角形的前20行进行MD5
杨辉三角形代码
#include <stdio.h>
void print(int a[],int m);
void print(int a[],int m)
{
int i,j;
for(i=0;i<m;i++)
{
printf("%d ",a[i]);
}
printf("\n");
}
int main()
{
int a[200] = {
1,1};
int i,j,n;
printf("input: ");
scanf("%d",&n);
printf("1\n1 1\n");
for(i=2;i<n;i++)
{
a[i] = 1;
for(j=i-1;j>0;j--)
{
a[j] += a[j-1];
}
print(a,i+1);
}
return 0;
}
去掉空格和换行输出：
1111211331146411510105116152015611721353521711828567056288119368412612684369111045120210252210120451011115516533046246233016555111112662204957929247924952206612111378286715128717161716128771528678131114913641001200230033432300320021001364911411151054551365300350056435643550053003136545510515111612056018204368800811440128701144080084368182056012016111713668023806188123761944824310243101944812376618823806801361711181538163060856818564318244375848620437583182418564856830608161531811191719693876116282713250388755829237892378755825038827132116283876969171191
MD5加密
后
37894beff1c632010dd6d524aa9604db
flag：RCTF{37894beff1c632010dd6d524aa9604db}
自己的算法水平几乎没有，不看答案根本不知道是杨辉三角，只能看出来有一定的规律，接下来慢慢加强下自己的算法能力