攻防notsequence

攻防notsequence 杨辉三角

https://baike.baidu.com/item/%E6%9D%A8%E8%BE%89%E4%B8%89%E8%A7%92/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 
  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是 第i个数字所打头 的行的数字之和，后面判断是否等于2的v5次方

这个if判断是根据 杨辉三角形 的性质： 第n行数字的和为2^（n-1）

分析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 
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判断的是根据杨辉三角形的一条性质： 斜线上数字的和等于其向左（从左上方到右下方的斜线）或向右拐弯（从右上方到左下方的斜线），拐角上的数字。

1+1=2，1+1+1=3，1+1+1+1=4，1+2=3，1+2+3=6，1+2+3+4=10，1+3=4，1+3+6=10，1+4=5。

分析总体

所以两个函数就是判断输入的字符串是否是杨辉三角形

下面就是和flag直接相关的判断，判断v2（杨辉三角形行数） == 20

if ( v2 == 20 )
  {
    puts("Congratulations! fl4g is :\nRCTF{md5(/*what you input without space or \n~*/)}");
    exit(0);

所以解密就是将杨辉三角形的前20行进行MD5

杨辉三角形代码

#include 
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}

自己的算法水平几乎没有，不看答案根本不知道是杨辉三角，只能看出来有一定的规律，接下来慢慢加强下自己的算法能力