首页
社区
课程
招聘
问答 CTF 排行榜 知识库 工具下载 峰会 看雪商城 证书查询
  1. 社区
  2. CTF对抗
    3. 发新帖
[第11题][原创]2023 KCTF 竞赛
发表于: 2023-8-19 23:21 5158

[第11题][原创]2023 KCTF 竞赛

ww-rm 活跃值
2023-8-19 23:21
5158

简单试错以及使用 IDA 获取伪代码可以知道题目的输入是一个不超过 10 位的十进制数字, 并且将范围限制在了 4K (0x1000) 至 4G (0x100000000) 之间 (包含两头端点). 所以解出此题的关键在于弄清楚题目如何对输入的数字进行验证.

如果输入错误, 则弹框提示 Wrong answer!, 输入正确则弹框提示 Accepted!.

程序只有一些简单的反调试检测, 没有太多 anti, 主要难度还是在算法原理上, 因此可以比较容易逆向出算法流程和对应的伪代码.

核心部分是一个编码算法和一个解码算法, 而输入的序列号是两个算法的参数, 程序通过对随机输入进行编码与解码操作, 并检测是否能正确还原出原始输入序列来判断序列号是否正确.

用 IDA 可以还原出编码和解码算法的伪代码如下:

编码部分

解码部分

算法流程不是太复杂, 可以看出是一种自定义的混合进制编解码算法, 而输入的序列号作为参数来控制算法正确运行, 算法涉及到的关键参数如下图:

解码算法流程与编码算法几乎一致, 但是把编码的输入和输出交换了一下, 同时进行了倒序处理, 并对解码序列与原始随机输入序列进行比较, 判断是否还原成功.

而验证步骤的关键伪代码还原如下:

要求对于输入的 b 能够使算法正确工作, 但是 b - 1 不能使算法正确工作.

此题的输入数据范围是介于 4K 到 4G 之间的一个整数, 可以考虑把核心算法单独摘出来整理重写, 然后进行暴力枚举.

但是枚举的难度在于, 原程序使用的随机输入序列长度为 10000, 且使用多线程进行了约 10000 轮测试, 也就是说纯随机情况下, 如果数据量不够大, 很可能造成误判, 从而无法枚举出正确的序列号, 因此枚举的时间成本很高, 只是一个保底下策.

程序的算法是一个用于混合进制序列的编解码算法, 且需要一个控制参数来使算法正确工作. 而程序的验证机制是 b 正确且 b - 1 错误, 可以合理推测能够使算法正确工作的参数不止一个, 应该是一个连续区间, 且题目的正确答案是这个区间的左端点, 因此我们需要找出参数的取值规律, 从而快速求解答案.

翻一下逆向后的代码, 可以找到程序使用的进制集是 { 2, 4, 5, 6, 7, 8, 13 }, 且输入和输出使用了同一组进制.

猜想 b 的取值与进制组合有关, 因此可以从简单的入手, 暴力枚举小区间, 寻找规律.

分别设置以下几种方式去进行枚举, 可以得到正确的取值区间如下:

观察一下可以发现, 对于混合进制的情况, 正确的取值区间是通过单个的输入输出进制的取值区间取交集得到的:

因此, 只要能找出单个的输入输出进制的取值区间规律就能解出题目.

继续观察寻找规律, 可以发现规律:

因此可以得到通项公式为: [r1 * r2 * n^2 - (r1 * r2 + 2) * n + 3, r1 * r2 * n^2 + n]

而题目使用了 7 种不同的进制, 且输入输出进制相同, 因此共需要枚举 21 种情况, 然后取交集最终得到题目里正确的取值范围, 并取左端点作为序列号.

这里需要注意的是, 取交集这个操作并不高效, 但是可以翻过来操作, 每次将错误取值区间筛去, 能够更快速的计算出正确答案, 这里贴一下核心计算代码.

最后算出来题目的进制组合下 100 亿范围内只有这些正确区间:

题目要求范围在 4K 到 4G 的范围, 因此序列号为 1898766093, 输入之后得到正确结果 Accepted!.

/***** 省略前文 *****/
  printf("Please input: ");
  v0 = 0;
  while ( 1 )
  {
    v1 = _getchar();
    if ( v1 == 10 )
      break;
    v2 = v0 + 1;
    _Buffer[v0] = v1;
    if ( v0 + 1 >= 0xB )
      goto LABEL_43;
    _Buffer[v2] = 0;
    if ( v0 == 9 && _getchar() != 10 )
      goto LABEL_41;
    ++v0;
    if ( v2 >= 10 )
      goto LABEL_10;
  }
  if ( v0 >= 0xB )
  {
LABEL_43:
    __report_rangecheckfailure();
    __debugbreak();
    JUMPOUT(*(_DWORD *)__security_check_cookie);
  }
  _Buffer[v0] = 0;
LABEL_10:
  v3 = 0;
  if ( _Buffer[0] )
  {
    while ( ++v3 <= 10 )
    {
      if ( !_Buffer[v3] )
        goto LABEL_15;
    }
    v3 = -1;
  }
LABEL_15:
  if ( sscanf_s(_Buffer, "%lld", &x) == 1 )
  {
    v4 = sprintf_s(v18, 0xBu, "%lld", x);
    if ( v3 > 0 && v4 > 0 && v3 == v4 )
    {
      v5 = 0;
      while ( _Buffer[v5] == v18[v5] )
      {
        if ( ++v5 >= v3 )
        {
          if ( SHIDWORD(x) >= 0 && (SHIDWORD(x) > 0 || (_DWORD)x) )
          {
            v6 = FindWindowW(L"OLLYDBG", 0);
            v7 = HIDWORD(x);
            v8 = x;
            if ( v6 )
            {
              v8 = x | 0xFFFF;
              LODWORD(x) = x | 0xFFFF;
            }
            if ( __PAIR__(HIDWORD(x), v8) - 4096 <= 0xFFFFF000 )
/***** 省略后文 *****/
/***** 省略前文 *****/
  printf("Please input: ");
  v0 = 0;
  while ( 1 )
  {
    v1 = _getchar();
    if ( v1 == 10 )
      break;
    v2 = v0 + 1;
    _Buffer[v0] = v1;
    if ( v0 + 1 >= 0xB )
      goto LABEL_43;
    _Buffer[v2] = 0;
    if ( v0 == 9 && _getchar() != 10 )
      goto LABEL_41;
    ++v0;
    if ( v2 >= 10 )
      goto LABEL_10;
  }
  if ( v0 >= 0xB )
  {
LABEL_43:
    __report_rangecheckfailure();
    __debugbreak();
    JUMPOUT(*(_DWORD *)__security_check_cookie);
  }
  _Buffer[v0] = 0;
LABEL_10:
  v3 = 0;
  if ( _Buffer[0] )
  {
    while ( ++v3 <= 10 )
    {
      if ( !_Buffer[v3] )
        goto LABEL_15;
    }
    v3 = -1;
  }
LABEL_15:
  if ( sscanf_s(_Buffer, "%lld", &x) == 1 )
  {
    v4 = sprintf_s(v18, 0xBu, "%lld", x);
    if ( v3 > 0 && v4 > 0 && v3 == v4 )
    {
      v5 = 0;
      while ( _Buffer[v5] == v18[v5] )
      {
        if ( ++v5 >= v3 )
        {
          if ( SHIDWORD(x) >= 0 && (SHIDWORD(x) > 0 || (_DWORD)x) )
          {
            v6 = FindWindowW(L"OLLYDBG", 0);
            v7 = HIDWORD(x);
            v8 = x;
            if ( v6 )
            {
              v8 = x | 0xFFFF;
              LODWORD(x) = x | 0xFFFF;
            }
            if ( __PAIR__(HIDWORD(x), v8) - 4096 <= 0xFFFFF000 )
/***** 省略后文 *****/
/***** 省略前文 *****/
                    MessageBoxW(0, L"Accepted!", L"Result", 0x40u);
                    return 0;
                  }
                }
              }
            }
          }
          break;
        }
      }
    }
  }
LABEL_41:
  MessageBoxW(0, L"Wrong answer!", L"Result", 0x10u);
/***** 省略后文 *****/
/***** 省略前文 *****/
                    MessageBoxW(0, L"Accepted!", L"Result", 0x40u);
                    return 0;
                  }
                }
              }
            }
          }
          break;
        }
      }
    }
  }
LABEL_41:
  MessageBoxW(0, L"Wrong answer!", L"Result", 0x10u);
/***** 省略后文 *****/
/***** 省略前文 *****/
    while ( 1 )
    {
      v51 = v16;
      v43 = v15;
      if ( v18 >= 10000 && (v15 < 0 || v15 <= 0 && !v16) )
        break;
      if ( v19 >= 20000 )
      {
LABEL_38:
        WaitForSingleObject(g_worker_mutex, 0xFFFFFFFF);
        g_has_error = 1;
        ReleaseMutex(g_worker_mutex);
        v2 = v49;
        goto LABEL_39;
      }
      if ( v18 >= 10000 )
      {
        v22 = *(_DWORD *)&v14[4 * v19];
        v23 = __PAIR__(v15, v16) % v22;
        HIDWORD(v53) = HIDWORD(v23);
        v24 = __PAIR__(v15, v51) / v22;
        v15 = (unsigned __int64)(__PAIR__(v15, v51) / v22) >> 32;
        v16 = v24;
        v14 = v45;
        *(_DWORD *)&v50[4 * v19++] = v23;
        v18 = v46;
        v17 = (int)v40;
      }
      else
      {
        v20 = *v40 + *(_DWORD *)(v17 + v54) * __PAIR__(v15, v16);
        v15 = HIDWORD(v20);
        v55 = v20;
        v39 = *(_DWORD *)&v45[4 * v19];
        v16 = v20;
        v53 = (signed __int64)__PAIR__(v43, v51) % v39;
        if ( (signed __int64)((signed __int64)__PAIR__(v43, v51) / v39 * v20) < (signed __int64)__PAIR__(v56, v58) )
        {
          v18 = v46 + 1;
          v14 = v45;
          v17 = (int)(v40 + 1);
          goto LABEL_12;
        }
        v21 = (signed __int64)__PAIR__(v43, v51) / v39;
        v15 = v21 >> 32;
        v16 = v21;
        v14 = v45;
        *(_DWORD *)&v50[4 * v19++] = v53;
        v18 = v46;
        v17 = (int)v40;
      }
    }
/***** 省略后文 *****/
/***** 省略前文 *****/
    while ( 1 )
    {
      v51 = v16;
      v43 = v15;
      if ( v18 >= 10000 && (v15 < 0 || v15 <= 0 && !v16) )
        break;
      if ( v19 >= 20000 )
      {
LABEL_38:
        WaitForSingleObject(g_worker_mutex, 0xFFFFFFFF);
        g_has_error = 1;
        ReleaseMutex(g_worker_mutex);
        v2 = v49;
        goto LABEL_39;
      }
      if ( v18 >= 10000 )
      {
        v22 = *(_DWORD *)&v14[4 * v19];
        v23 = __PAIR__(v15, v16) % v22;
        HIDWORD(v53) = HIDWORD(v23);
        v24 = __PAIR__(v15, v51) / v22;
        v15 = (unsigned __int64)(__PAIR__(v15, v51) / v22) >> 32;
        v16 = v24;
        v14 = v45;
        *(_DWORD *)&v50[4 * v19++] = v23;
        v18 = v46;
        v17 = (int)v40;
      }
      else
      {
        v20 = *v40 + *(_DWORD *)(v17 + v54) * __PAIR__(v15, v16);
        v15 = HIDWORD(v20);
        v55 = v20;
        v39 = *(_DWORD *)&v45[4 * v19];
        v16 = v20;
        v53 = (signed __int64)__PAIR__(v43, v51) % v39;
        if ( (signed __int64)((signed __int64)__PAIR__(v43, v51) / v39 * v20) < (signed __int64)__PAIR__(v56, v58) )
        {
          v18 = v46 + 1;
          v14 = v45;
          v17 = (int)(v40 + 1);
          goto LABEL_12;
        }
        v21 = (signed __int64)__PAIR__(v43, v51) / v39;
        v15 = v21 >> 32;
        v16 = v21;
        v14 = v45;
        *(_DWORD *)&v50[4 * v19++] = v53;
        v18 = v46;
        v17 = (int)v40;
      }
    }
/***** 省略后文 *****/
/***** 省略前文 *****/
    while ( 1 )
    {
      v54 = v30;
      v52 = v27;
      if ( v25 < 0 && (v27 < 0 || v27 <= 0 && !v30) )
        break;
      if ( v28 < 0 )
        goto LABEL_38;
      if ( v25 < 0 )
      {
        v34 = *((_DWORD *)in_r + v28);
        HIDWORD(v53) = (unsigned __int64)(__PAIR__(v27, v54) % v34) >> 32;
        v35 = __PAIR__(v27, v54) / v34;
        v27 = (unsigned __int64)(__PAIR__(v27, v54) / v34) >> 32;
        v30 = v35;
        v33 = (unsigned int)(__PAIR__(v52, v54) % v34) == v49[v28];
LABEL_34:
        if ( !v33 )
          goto LABEL_38;
        v25 = v47;
        --v28;
        v29 = (int)v41;
        v26 = v44;
      }
      else
      {
        v31 = *(_DWORD *)v41 + *(_DWORD *)(v26 + v29) * __PAIR__(v27, v30);
        v27 = HIDWORD(v31);
        LODWORD(v53) = v31;
        v32 = *((_DWORD *)in_r + v28);
        v30 = v31;
        v55 = __PAIR__(v52, v54) % v32;
        b_high = (unsigned __int64)(__PAIR__(v52, v54) / v32) >> 32;
        b_low = __PAIR__(v52, v54) / v32;
        if ( (signed __int64)(__PAIR__(v52, v54) / v32 * v31) >= *(_QWORD *)parameters )
        {
          v30 = b_low;
          v27 = b_high;
          v33 = v55 == v49[v28];
          goto LABEL_34;
        }
        v25 = v47 - 1;
        v26 = v44;
        v29 = (int)(v41 - 4);
        --v47;
        v41 -= 4;
      }
    }
/***** 省略后文 *****/
/***** 省略前文 *****/
    while ( 1 )
    {
      v54 = v30;
      v52 = v27;
      if ( v25 < 0 && (v27 < 0 || v27 <= 0 && !v30) )
        break;

[注意]传递专业知识、拓宽行业人脉——看雪讲师团队等你加入！

最后于 2023-9-29 12:09 被kanxue编辑 ，原因：
上传的附件：
收藏
免费 ・1
支持
分享
最新回复 (1)
kanxue
雪    币： 47147
活跃值： (20450)
能力值： (RANK：350 )
在线值：
发帖
回帖
粉丝
私信
2 楼

第十一题  步步逼近

最后于 2023-8-27 15:58 被kanxue编辑 ，原因：
2023-8-27 09:39
0
游客
登录 | 注册 方可回帖
回帖 表情 雪币赚取及消费
高级回复
返回
//