[原创]KCTF 2022 秋季赛第二题 wp - 98k战队-CTF对抗-看雪-安全社区|安全招聘|kanxue.com

[原创]KCTF 2022 秋季赛第二题 wp - 98k战队

2022-11-17 10:13 7600

[原创]KCTF 2022 秋季赛第二题 wp - 98k战队

GreatIchild 活跃值

2022-11-17 10:13

7600

拖入 ida ，分析：

int __cdecl main(int argc, const char **argv, const char **envp)
{
  int v3; // edi
  int v4; // eax
  int v6; // esi
  int v7; // eax
  int result; // eax
  char input[64]; // [esp+8h] [ebp-40h] BYREF
 
  input[0] = 0;
  memset(&input[1], 0, 0x3Cu);
  *(_WORD *)&input[61] = 0;
  input[63] = 0;
  printf("Input:");
  gets(input);
  v3 = -1;
  v4 = 0;
  if ( !input[0] )
    goto LABEL_20;
  do
  {
    if ( v4 >= 64 )
      break;
    if ( input[v4] == '-' )
      v3 = v4;
  }
  while ( input[++v4] );
  if ( v3 > 0
    && (v6 = v4 - v3, v4 - v3 > 0)
    && Bignum::from_str(&part1, input, v3, "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz") > 0
    && Bignum::from_str(
         &part2,
         &input[v3 + 1],
         v6 - 1,
         "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz") > 0
    && (Bignum::from_str(
          &a,
          "IRtzloZ6iuB",
          strlen("IRtzloZ6iuB"),
          "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz"),
        Bignum::from_int(&b, 0),
        Bignum::from_int(&c, 0),
        bignum::cmp(&part1, &part2) < 0)
    && bignum::cmp(&part1, &a) < 0
    && bignum::cmp(&part2, &a) < 0 )
  {
    v7 = 0;
    while ( 1 )
    {
      round = v7 + 1;
      bignum::add(&b, &b, &part1);
      bignum::add(&c, &c, &part2);
      bignum::mod(&b, &b, &a);
      bignum::mod(&c, &c, &a);
      Bignum::from_int(&d, 1);
      bignum::sub(&d, &b, &d);
      if ( !bignum::cmp(&d, &part1) )
      {
        ++match_count;
        bignum::mul(&d, &d, &part1);
      }
      Bignum::from_int(&e, 1);
      bignum::add(&e, &c, &e);
      if ( !bignum::cmp(&e, &part2) )
      {
        ++match_count;
        bignum::div(&e, &a, &part2);
      }
      if ( match_count == 10 )
        break;
      v7 = round;
      if ( round >= 0x200000 )
        goto LABEL_20;
    }
    printf("Success!\n");
    result = 0;
  }
  else
  {
LABEL_20:
    printf("Error.\n");
    result = 0;
  }
  return result;
}

需要输入两个62进制的数，以-分隔，并且第一个数比第二个数小、两个数均比给定的数 a 小。如果不考虑大数运算函数里的额外计算部分，后面的逻辑就是计算满足 part1 * round % a - 1 == part1 或者 part2 * round % a + 1 == part2 的round的个数，达到10个时成功。很容易构造part1和part2，使得满足等式的round值为2。没用数论分析这个值能否大于2，花了比较多时间在抄写大数运算函数里的额外计算部分。但是后来发现几乎所有的额外计算部分都与上面的主流程无关（没有修改a、b、c、part1、part2，sub不修改d，add不修改e，cmp不影响返回值），可以忽略。只有两个 ++match_count; 后面的语句， mul 和 div 很奇怪，有这样一不部分代码（二者相同）：

Bignum::from_int(&d, 4);
Bignum::shl(&e, &d, 3);
if ( match_count > 0 && *(_DWORD *)&a.buf[e.buf[0]] == e.buf[0] )
{
  bignum::add(&d, &d, &e);
  v13 = Bignum::mod_int(&d, round);
  a.buf[d.buf[0]] += 4;
  Bignum::shl(&d, &d, v13);
  bignum::sub(&e, &d, &e);
}

一开始以为会取 a 中的一部分值比较，之后修改 a ，比较复杂，没仔细看。之后调试时跳转到这里执行，发现 *(_DWORD *)&a.buf[e.buf[0]] 其实是round (e.buf[0] = 32)，a.buf[d.buf[0]]其实是match_count(d.buf[0] = 36)，这样2 + 4 * 2 = 10，条件就满足了。

所以是在round = 32时满足上面两个等式即可： part1 * 32 % a - 1 == part1 和 part2 * 32 % a + 1 == part2

化简一下得到 31 * part1 = k1 * a + 1 和 31 * part2 = k2 * a + 1 ， k1 和 k2 都是小于32的整数。直接穷举k得到part1和part2，再转成62进制即可：

def toint(s):
    table = '0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz'
    radix = len(table)
    x = 0
    for i in s[::-1]:
        x = x * radix + table.index(i)
    return x
 
def tostr(x):
    table = '0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz'
    radix = len(table)
    s = ''
    while x:
        s += table[x % 62]
        x //= 62
    return s
 
a = toint("IRtzloZ6iuB")
for i in range(32):
    if (i * a + 1) % 31 == 0:
        part1 = (i * a + 1) // 31
        break
else:
    assert False
 
for i in range(32):
    if (i * a - 1) % 31 == 0:
        part2 = (i * a - 1) // 31
        break
else:
    assert False
 
print(tostr(part1) + '-' + tostr(part2))
# ZSxZerX4xb4-jyvP7x12lI7