[原创] 第四题：达芬奇密码-CTF对抗-看雪-安全社区|安全招聘|kanxue.com

[原创] 第四题：达芬奇密码

2019-6-21 13:15 3039

[原创] 第四题：达芬奇密码

alaaal

2019-6-21 13:15

3039

简单地说，本题核心验证逻辑是佩尔方程+数组实现128 bit数的运算。

使用xspy，或者IDA搜索unicode字符串"Wrong"再查找交叉引用，都可以找到关键函数sub_401EA0，事实上是按钮check的响应函数，内存地址0xAE1EA0（每次运行不一定一样）

int __thiscall sub_401EA0(CWnd *this)
{
  CWnd *v1; // esi
  int v2; // eax
  WCHAR String; // [esp+Ch] [ebp-310h]
  char v5; // [esp+Eh] [ebp-30Eh]
  char v6; // [esp+20Ch] [ebp-110h]
  char v7; // [esp+20Dh] [ebp-10Fh]
  DWORD v8; // [esp+30Ch] [ebp-10h]
  CWnd *v9; // [esp+310h] [ebp-Ch]
  int v10; // [esp+314h] [ebp-8h]
  DWORD flOldProtect; // [esp+318h] [ebp-4h]

  v1 = this;
  v9 = this;
  String = 0;
  memset(&v5, 0, 0x1FEu);
  v6 = 0;
  memset(&v7, 0, 0xFFu);
  CWnd::GetDlgItemTextW(v1, 1000, &String, 20);
  if ( wcslen(&String) == 16 )
  {
    v2 = 0;
    while ( !(*(&String + v2) & 0xFF00) )
    {
      *(&v6 + v2) = *((_BYTE *)&String + 2 * v2);
      if ( ++v2 >= 16 )
      {
        v8 = 64;
        flOldProtect = 0;
        VirtualProtect(sub_4010E0, 0xD17u, 0x40u, &flOldProtect);
        if ( GetLastError() )
          return CWnd::MessageBoxW(v1, L"Wrong!", 0, 0);
        qmemcpy(sub_4010E0, &byte_5647B8, 0x330u);
        VirtualProtect(sub_4010E0, 0xD17u, flOldProtect, &v8);
        if ( !GetLastError() )
        {
          v10 = 0;
          v10 = sub_4010E0(&v6);
          if ( v10 == 1 )
            return CWnd::MessageBoxW(v9, L"Congratulations! You are right!", 0, 0);
        }
        v1 = v9;
        return CWnd::MessageBoxW(v1, L"Wrong!", 0, 0);
      }
    }
  }
  return CWnd::MessageBoxW(v1, L"Wrong!", 0, 0);
}

函数sub_401EA0中可以看到输入字符串长度应该为16。

函数sub_4010E0作为本题关键的验证函数在运行过程中被修改了，是通过函数VirtualProtect和qmemcpy配合使用实现的。我选择dump内存后使用IDA打开：

signed int __cdecl sub_AE10E0(int a1)
{
  signed int v1; // eax
  char v2; // cl
  signed int v3; // ecx
  signed int v4; // eax
  signed int v5; // eax
  signed int v6; // esi
  signed int v7; // ecx
  __int16 v8; // dx
  char *v9; // edi
  __int16 v10; // ax
  signed int v11; // eax
  signed int v12; // ecx
  unsigned __int16 v13; // bx
  signed int v14; // esi
  signed int v15; // ecx
  __int16 v16; // dx
  char *v17; // edi
  __int16 v18; // ax
  signed int v19; // eax
  signed int v20; // ecx
  unsigned __int16 v21; // bx
  unsigned int v22; // eax
  signed int v23; // ecx
  unsigned __int16 v24; // dx
  char v25; // dl
  signed int v26; // eax
  __int16 v27; // si
  int v28; // eax
  int v30; // [esp+8h] [ebp-90h]
  int v31; // [esp+Ch] [ebp-8Ch]
  int v32; // [esp+10h] [ebp-88h]
  int v33; // [esp+14h] [ebp-84h]
  int v34; // [esp+18h] [ebp-80h]
  int v35; // [esp+1Ch] [ebp-7Ch]
  int v36; // [esp+20h] [ebp-78h]
  int v37; // [esp+24h] [ebp-74h]
  int v38; // [esp+28h] [ebp-70h]
  int v39; // [esp+2Ch] [ebp-6Ch]
  int v40; // [esp+30h] [ebp-68h]
  int v41; // [esp+34h] [ebp-64h]
  int v42; // [esp+38h] [ebp-60h]
  int v43; // [esp+3Ch] [ebp-5Ch]
  int v44; // [esp+40h] [ebp-58h]
  int v45; // [esp+44h] [ebp-54h]
  int v46; // [esp+48h] [ebp-50h]
  int v47; // [esp+4Ch] [ebp-4Ch]
  int v48; // [esp+50h] [ebp-48h]
  int v49; // [esp+54h] [ebp-44h]
  char v50; // [esp+58h] [ebp-40h]
  int v51; // [esp+5Ch] [ebp-3Ch]
  int v52; // [esp+60h] [ebp-38h]
  int v53; // [esp+64h] [ebp-34h]
  int v54; // [esp+68h] [ebp-30h]
  char v55; // [esp+6Ch] [ebp-2Ch]
  int v56; // [esp+70h] [ebp-28h]
  int v57; // [esp+74h] [ebp-24h]
  int v58; // [esp+78h] [ebp-20h]
  int v59; // [esp+7Ch] [ebp-1Ch]
  char v60; // [esp+80h] [ebp-18h]
  int v61; // [esp+84h] [ebp-14h]
  int v62; // [esp+88h] [ebp-10h]
  int v63; // [esp+8Ch] [ebp-Ch]
  int v64; // [esp+90h] [ebp-8h]
  char v65; // [esp+94h] [ebp-4h]

  v31 = 1684969601;
  v1 = 0;
  v30 = 3817641494;
  v32 = 2178680964;
  v33 = 1330138558;
  v34 = 0;
  v35 = 0;
  v36 = 0;
  v37 = 0;
  v38 = 0;
  v39 = 0;
  v44 = 0;
  v45 = 0;
  do
  {
    v2 = *((_BYTE *)&v32 + v1) ^ *(_BYTE *)(a1 + v1 + 8);
    *((_BYTE *)&v38 + v1) = *((_BYTE *)&v30 + v1) ^ *((_BYTE *)&v30 + v1 + a1 - (_DWORD)&v30);
    *((_BYTE *)&v44 + v1++) = v2;
  }
  while ( v1 < 8 );//循环赋值v38数组与v44数组，分别为8字节即2个int。程序输入key为16字节，前后两段分别与v30 v31和v32 v33异或
  v30 = 0;
  v56 = 0;
  v57 = 0;
  v58 = 0;
  v59 = 0;
  v60 = 0;
  v61 = 0;
  v62 = 0;
  v63 = 0;
  v64 = 0;
  v65 = 0;
  v46 = 0;
  v47 = 0;
  v48 = 0;
  v49 = 0;
  v50 = 0;
  v51 = 0;
  v52 = 0;
  v53 = 0;
  v54 = 0;
  v55 = 0;
  v31 = 0;
  v32 = 0;
  v33 = 0;
  LOBYTE(v34) = 0;
  v3 = 8;
  LOBYTE(v30) = 8;
  v4 = 7;
  do
  {
    if ( *((_BYTE *)&v38 + v4) )
      break;
    --v3;
    --v4;
  }
  while ( v4 >= 0 );
  if ( v3 == 8 )//验证。一开始觉得很怪，理解到大数运算之后，这是要求大数v38大于等于2**56
  {
    v5 = 7;
    do
    {
      if ( *((_BYTE *)&v44 + v5) )
        break;
      --v3;
      --v5;
    }
    while ( v5 >= 0 );
    if ( v3 == 8 && !(v39 & 0xF0000000) )//验证。理解到大数运算之后，这是要求大数v44大于等于2**56且大数v38小于2**60
    {
      v6 = 0;
      do
      {
        v40 = 0;
        v41 = 0;
        v42 = 0;
        v43 = 0;
        v7 = 0;
        v8 = *((unsigned __int8 *)&v38 + v6);
        v9 = (char *)&v40 + v6;
        do
        {
          v10 = *((unsigned __int8 *)&v42 + v6) + v8 * *((unsigned __int8 *)&v38 + v7);
          v9[v7] = *((_BYTE *)&v42 + v6) + v8 * *((_BYTE *)&v38 + v7);
          ++v7;
          *((_BYTE *)&v42 + v6) = HIBYTE(v10);
        }
        while ( v7 < 8 );
        LOBYTE(v11) = 0;
        v12 = 0;
        do
        {
          v13 = (char)v11 + *((unsigned __int8 *)&v56 + v12 + v6) + (unsigned __int8)v9[v12];
          *((_BYTE *)&v56 + v12++ + v6) = v13;
          v11 = (signed int)v13 >> 8;
        }
        while ( v12 < 9 );
        ++v6;
      }
      while ( v6 < 8 );//大数v56等于大数v38的平方
      v14 = 0;
      do
      {
        v40 = 0;
        v41 = 0;
        v42 = 0;
        v43 = 0;
        v15 = 0;
        v16 = *((unsigned __int8 *)&v44 + v14);
        v17 = (char *)&v40 + v14;
        do
        {
          v18 = *((unsigned __int8 *)&v42 + v14) + v16 * *((unsigned __int8 *)&v44 + v15);
          v17[v15] = *((_BYTE *)&v42 + v14) + v16 * *((_BYTE *)&v44 + v15);
          ++v15;
          *((_BYTE *)&v42 + v14) = HIBYTE(v18);
        }
        while ( v15 < 8 );
        LOBYTE(v19) = 0;
        v20 = 0;
        do
        {
          v21 = (char)v19 + *((unsigned __int8 *)&v61 + v20 + v14) + (unsigned __int8)v17[v20];
          *((_BYTE *)&v61 + v20++ + v14) = v21;
          v19 = (signed int)v21 >> 8;
        }
        while ( v20 < 9 );
        ++v14;
      }
      while ( v14 < 8 );//大数v61等于大数v44的平方
      LOBYTE(v22) = v50;//此时v50==0，给下面的循环初始化参数
      v23 = 0;
      do
      {
        v24 = (unsigned __int8)v22 + 7 * *((unsigned __int8 *)&v61 + v23);
        *((_BYTE *)&v46 + v23++) = v24;
        v22 = (unsigned int)v24 >> 8;
      }
      while ( v23 < 17 );//大数v46等于大数v61*7，取16位，进位抛弃
      v50 = HIBYTE(v24);
      v25 = 0;
      v26 = 0;
      do
      {
        v27 = *((unsigned __int8 *)&v56 + v26) - *((unsigned __int8 *)&v46 + v26) - v25;
        *((_BYTE *)&v51 + v26) = v27;
        if ( v27 < 0 )
          v25 = 1;
        ++v26;
      }
      while ( v26 < 17 );//v56每一字节对应数都大于v46
      if ( !v25 )
      {
        v28 = 0;
        while ( *((_BYTE *)&v51 + v28) == *((_BYTE *)&v30 + v28) )
        {
          if ( ++v28 >= 17 )
            return 1;
        }
      }
    }
  }
  return 0;
}

函数sub_4010E0，也就是内存中的sub_AE10E0，其实是简单地实现了2**128以内的大数运算，有乘法、减法、判断相等。怎么看出来的呢？

首先观察该函数的几个数组之间的关系，也就是观察数据流

v30（magic number）异或a1（key）得到v38 v44
v38得到v56
v44得到v61得到v46
v56减v46与v30（值8）相等则代表a1正确

判等只有一处。理解大数运算之后发现原来是不定方程。

随后从一个比较简单的部分开始读，这里选择的是v61得到v46的部分。思考这段代码如何求逆，发现它完全类似于乘法进位的方法，相当于v61乘7得v46。于是猜测整个函数内都是大数运算。由此重新阅读以上函数就可以理解整个验证过程。

      do
      {
        v24 = (unsigned __int8)v22 + 7 * *((unsigned __int8 *)&v61 + v23);
        *((_BYTE *)&v46 + v23++) = v24;
        v22 = (unsigned int)v24 >> 8;
      }
      while ( v23 < 17 );//v61得到v46

于是验证过程的核心问题是一个数学问题：

p，q为正整数
(p*p)%(2**128) - (q*q*7)%(2**128) == 8
p >= 2**56
p < 2**60
q >= 2**56
q < 2**64

其实程序当中还有一些约束条件，我暂时把这些当作次要部分：

(p*p)%(2**8) >= (q*q*7)%(2**8)
...

尝试使用z3求解问题，跑了十多分钟没有出结果，估计是在暴力，然而暴力法2**32以上都接受不了，此时显然只能放弃。于是开始寻求数学方法。

如果看成一个数学问题，上面这个核心问题还需要简化，因为搜索了解了一些不定方程的知识以后，发现若不考虑取余数运算，则为一种佩尔方程（pell）。于是猜想此处取余数运算没有用。

于是需要求解以下问题。

p，q为正整数
(p*p) - (q*q*7) == 8
p >= 2**56
p < 2**60
q >= 2**56
q < 2**64

佩尔方程有一种递推解的方法，可以用一组特解产生多组解，于是可以尝试是否能恰好找到符合p，q上下界的解，果然找到了。数学过程大致如下：

佩尔方程从一个特解递推获得多个解

以上，取d=7，k=8，式1特解a=8，b=3，式3特解x3=6，y3=2，带入式4迭代14次即可。说明一下我用numpy然后溢出了，好像numpy不支持128 bit整数。于是手动写了一个很难看的代码……

p=385044246406735194
q=145533045678356702

然后从p，q逆推回去，细心一点，注册码为L3mZ2k9aZ0a36DMM

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

最后于 2019-6-25 13:01 被alaaal编辑，原因：

收藏・0

点赞・3

打赏

最新回复 (0)
	游客登录 \| 注册方可回帖　回帖　表情雪币赚取及消费高级回复

alaaal

发帖

回帖

143

RANK

关注

私信

他的文章

[原创] 第九题：绝地逃生

[原创] 第二题：沉睡的敦煌

[原创] 第三题：金字塔的诅咒

[原创] 第四题：达芬奇密码

[原创] 第六题：消失的岛屿

关于我们

联系我们

企业服务

看雪公众号