0xGame-解方程

alexzhu 2023-10-28 18:57:54 715 0


0xGame-解方程

分析

使用IDA64反编译程序,可以看到使用scanf接收了输入,长度为28:
scanf("%28s", Str);

以及一串计算:

v5[0] = 34 * (unsigned __int8)Str[3]
        + 12 * (unsigned __int8)Str[0]
        + 53 * (unsigned __int8)Str[1]
        + 6 * (unsigned __int8)Str[2]
        + 58 * (unsigned __int8)Str[4]
        + 36 * (unsigned __int8)Str[5]
        + (unsigned __int8)Str[6];
  v5[1] = 83 * (unsigned __int8)Str[0]
        + 73 * (unsigned __int8)Str[3]
        + 27 * (unsigned __int8)Str[4]
        + 12 * (unsigned __int8)Str[2]
        + 85 * (unsigned __int8)Str[1]
        + 96 * (unsigned __int8)Str[5]
        + 52 * (unsigned __int8)Str[6];
  v5[2] = 78 * (unsigned __int8)Str[0]
        + 24 * (unsigned __int8)Str[2]
        + 53 * (unsigned __int8)Str[1]
        + 36 * (unsigned __int8)Str[3]
        + 86 * (unsigned __int8)Str[4]
        + 25 * (unsigned __int8)Str[5]
        + 46 * (unsigned __int8)Str[6];
  v5[3] = 39 * (unsigned __int8)Str[0]
        + 78 * (unsigned __int8)Str[1]
        + 52 * (unsigned __int8)Str[2]
        + 9 * (unsigned __int8)Str[3]
        + 62 * (unsigned __int8)Str[4]
        + 37 * (unsigned __int8)Str[5]
        + 84 * (unsigned __int8)Str[6];
  v5[4] = 48 * (unsigned __int8)Str[4]
        + 14 * (unsigned __int8)Str[2]
        + 23 * (unsigned __int8)Str[0]
        + 6 * (unsigned __int8)Str[1]
        + 74 * (unsigned __int8)Str[3]
        + 12 * (unsigned __int8)Str[5]
        + 83 * (unsigned __int8)Str[6];
  v5[5] = 92 * (unsigned __int8)Str[2]
        + 15 * (unsigned __int8)Str[5]
        + 48 * (unsigned __int8)Str[4]
        + 85 * (unsigned __int8)Str[1]
        + 27 * (unsigned __int8)Str[0]
        + 42 * (unsigned __int8)Str[3]
        + 72 * (unsigned __int8)Str[6];
  v5[6] = 26 * (unsigned __int8)Str[5]
        + 67 * (unsigned __int8)Str[3]
        + 6 * (unsigned __int8)Str[1]
        + 4 * (unsigned __int8)Str[0]
        + 3 * (unsigned __int8)Str[2]
        + 68 * (unsigned __int8)Str[6];
  v5[7] = 34 * (unsigned __int8)Str[10]
        + 12 * (unsigned __int8)Str[7]
        + 53 * (unsigned __int8)Str[8]
        + 6 * (unsigned __int8)Str[9]
        + 58 * (unsigned __int8)Str[11]
        + 36 * (unsigned __int8)Str[12]
        + (unsigned __int8)Str[13];
  v5[8] = 83 * (unsigned __int8)Str[7]
        + 73 * (unsigned __int8)Str[10]
        + 27 * (unsigned __int8)Str[11]
        + 12 * (unsigned __int8)Str[9]
        + 85 * (unsigned __int8)Str[8]
        + 96 * (unsigned __int8)Str[12]
        + 52 * (unsigned __int8)Str[13];
  v5[9] = 78 * (unsigned __int8)Str[7]
        + 24 * (unsigned __int8)Str[9]
        + 53 * (unsigned __int8)Str[8]
        + 36 * (unsigned __int8)Str[10]
        + 86 * (unsigned __int8)Str[11]
        + 25 * (unsigned __int8)Str[12]
        + 46 * (unsigned __int8)Str[13];
  v5[10] = 39 * (unsigned __int8)Str[7]
         + 78 * (unsigned __int8)Str[8]
         + 52 * (unsigned __int8)Str[9]
         + 9 * (unsigned __int8)Str[10]
         + 62 * (unsigned __int8)Str[11]
         + 37 * (unsigned __int8)Str[12]
         + 84 * (unsigned __int8)Str[13];
  v5[11] = 48 * (unsigned __int8)Str[11]
         + 14 * (unsigned __int8)Str[9]
         + 23 * (unsigned __int8)Str[7]
         + 6 * (unsigned __int8)Str[8]
         + 74 * (unsigned __int8)Str[10]
         + 12 * (unsigned __int8)Str[12]
         + 83 * (unsigned __int8)Str[13];
  v5[12] = 92 * (unsigned __int8)Str[9]
         + 15 * (unsigned __int8)Str[12]
         + 48 * (unsigned __int8)Str[11]
         + 85 * (unsigned __int8)Str[8]
         + 27 * (unsigned __int8)Str[7]
         + 42 * (unsigned __int8)Str[10]
         + 72 * (unsigned __int8)Str[13];
  v5[13] = 26 * (unsigned __int8)Str[12]
         + 67 * (unsigned __int8)Str[10]
         + 6 * (unsigned __int8)Str[8]
         + 4 * (unsigned __int8)Str[7]
         + 3 * (unsigned __int8)Str[9]
         + 68 * (unsigned __int8)Str[13];
  v5[14] = 34 * (unsigned __int8)Str[17]
         + 12 * (unsigned __int8)Str[14]
         + 53 * (unsigned __int8)Str[15]
         + 6 * (unsigned __int8)Str[16]
         + 58 * (unsigned __int8)Str[18]
         + 36 * (unsigned __int8)Str[19]
         + (unsigned __int8)Str[20];
  v5[15] = 83 * (unsigned __int8)Str[14]
         + 73 * (unsigned __int8)Str[17]
         + 27 * (unsigned __int8)Str[18]
         + 12 * (unsigned __int8)Str[16]
         + 85 * (unsigned __int8)Str[15]
         + 96 * (unsigned __int8)Str[19]
         + 52 * (unsigned __int8)Str[20];
  v5[16] = 78 * (unsigned __int8)Str[14]
         + 24 * (unsigned __int8)Str[16]
         + 53 * (unsigned __int8)Str[15]
         + 36 * (unsigned __int8)Str[17]
         + 86 * (unsigned __int8)Str[18]
         + 25 * (unsigned __int8)Str[19]
         + 46 * (unsigned __int8)Str[20];
  v5[17] = 39 * (unsigned __int8)Str[14]
         + 78 * (unsigned __int8)Str[15]
         + 52 * (unsigned __int8)Str[16]
         + 9 * (unsigned __int8)Str[17]
         + 62 * (unsigned __int8)Str[18]
         + 37 * (unsigned __int8)Str[19]
         + 84 * (unsigned __int8)Str[20];
  v5[18] = 48 * (unsigned __int8)Str[18]
         + 14 * (unsigned __int8)Str[16]
         + 23 * (unsigned __int8)Str[14]
         + 6 * (unsigned __int8)Str[15]
         + 74 * (unsigned __int8)Str[17]
         + 12 * (unsigned __int8)Str[19]
         + 83 * (unsigned __int8)Str[20];
  v5[19] = 92 * (unsigned __int8)Str[16]
         + 15 * (unsigned __int8)Str[19]
         + 48 * (unsigned __int8)Str[18]
         + 85 * (unsigned __int8)Str[15]
         + 27 * (unsigned __int8)Str[14]
         + 42 * (unsigned __int8)Str[17]
         + 72 * (unsigned __int8)Str[20];
  v5[20] = 26 * (unsigned __int8)Str[19]
         + 67 * (unsigned __int8)Str[17]
         + 6 * (unsigned __int8)Str[15]
         + 4 * (unsigned __int8)Str[14]
         + 3 * (unsigned __int8)Str[16]
         + 68 * (unsigned __int8)Str[20];
  v5[21] = 34 * (unsigned __int8)Str[24]
         + 12 * (unsigned __int8)Str[21]
         + 53 * (unsigned __int8)Str[22]
         + 6 * (unsigned __int8)Str[23]
         + 58 * (unsigned __int8)Str[25]
         + 36 * (unsigned __int8)Str[26]
         + (unsigned __int8)Str[27];
  v5[22] = 83 * (unsigned __int8)Str[21]
         + 73 * (unsigned __int8)Str[24]
         + 27 * (unsigned __int8)Str[25]
         + 12 * (unsigned __int8)Str[23]
         + 85 * (unsigned __int8)Str[22]
         + 96 * (unsigned __int8)Str[26]
         + 52 * (unsigned __int8)Str[27];
  v5[23] = 78 * (unsigned __int8)Str[21]
         + 24 * (unsigned __int8)Str[23]
         + 53 * (unsigned __int8)Str[22]
         + 36 * (unsigned __int8)Str[24]
         + 86 * (unsigned __int8)Str[25]
         + 25 * (unsigned __int8)Str[26]
         + 46 * (unsigned __int8)Str[27];
  v5[24] = 39 * (unsigned __int8)Str[21]
         + 78 * (unsigned __int8)Str[22]
         + 52 * (unsigned __int8)Str[23]
         + 9 * (unsigned __int8)Str[24]
         + 62 * (unsigned __int8)Str[25]
         + 37 * (unsigned __int8)Str[26]
         + 84 * (unsigned __int8)Str[27];
  v5[25] = 48 * (unsigned __int8)Str[25]
         + 14 * (unsigned __int8)Str[23]
         + 23 * (unsigned __int8)Str[21]
         + 6 * (unsigned __int8)Str[22]
         + 74 * (unsigned __int8)Str[24]
         + 12 * (unsigned __int8)Str[26]
         + 83 * (unsigned __int8)Str[27];
  v5[26] = 92 * (unsigned __int8)Str[23]
         + 15 * (unsigned __int8)Str[26]
         + 48 * (unsigned __int8)Str[25]
         + 85 * (unsigned __int8)Str[22]
         + 27 * (unsigned __int8)Str[21]
         + 42 * (unsigned __int8)Str[24]
         + 72 * (unsigned __int8)Str[27];
  v5[27] = 26 * (unsigned __int8)Str[26]
         + 67 * (unsigned __int8)Str[24]
         + 6 * (unsigned __int8)Str[22]
         + 4 * (unsigned __int8)Str[21]
         + 3 * (unsigned __int8)Str[23]
         + 68 * (unsigned __int8)Str[27];

还有一个for循环用于检查Str的正确性:

for ( i = 0; i <= 27; ++i )
{
  if ( v5[i] != check[i] )
  {
    puts("wrong");
    exit(0);
  }
}

由此可以知道Str有效字符长度为28,且需要满足计算出来的v5和check数组相等。

check数组如下:

check dd 51C5h, 0A240h, 8359h, 9590h, 69D9h, 9EC9h, 4916h, 48B9h
      dd 0A376h, 8CF0h, 8985h, 70D8h, 8DFAh, 4979h, 5135h, 99ACh
      dd 7C3Bh, 835Dh, 5F62h, 8558h, 4078h, 4CB6h, 9E43h, 8E2Ch
      dd 93CFh, 713Ah, 0A2EFh, 48ADh, 4 dup(0)

其中有效数据也是28个。

条件有28条,未知的字符也是28个,如果28个条件线性无关,则结果应当具有唯一的解。

求解

使用SageMath编写求解脚本,为了方便起见,直接复制原文的式子后使用正则表达式生成我们的等式

求解的变量X为长度为28的向量,限定为整数范围(domain=ZZ)

xnames = [f"x{i}" for i in range(28)]
X = var(xnames, domain=ZZ)
eq = [None for _ in range(28)]
eq[0] = (34 * X[3] + 12 * X[0] + 53 * X[1] + 6 * X[2] + 58 * X[4] + 36 * X[5] + X[6] == 0x51c5)
eq[1] = (83 * X[0] + 73 * X[3] + 27 * X[4] + 12 * X[2] + 85 * X[1] + 96 * X[5] + 52 * X[6] == 0xa240)
eq[2] = (78 * X[0] + 24 * X[2] + 53 * X[1] + 36 * X[3] + 86 * X[4] + 25 * X[5] + 46 * X[6] == 0x8359)
eq[3] = (39 * X[0] + 78 * X[1] + 52 * X[2] + 9 * X[3] + 62 * X[4] + 37 * X[5] + 84 * X[6] == 0x9590)
eq[4] = (48 * X[4] + 14 * X[2] + 23 * X[0] + 6 * X[1] + 74 * X[3] + 12 * X[5] + 83 * X[6] == 0x69d9)
eq[5] = (92 * X[2] + 15 * X[5] + 48 * X[4] + 85 * X[1] + 27 * X[0] + 42 * X[3] + 72 * X[6] == 0x9ec9)
eq[6] = (26 * X[5] + 67 * X[3] + 6 * X[1] + 4 * X[0] + 3 * X[2] + 68 * X[6] == 0x4916)
eq[7] = (34 * X[10] + 12 * X[7] + 53 * X[8] + 6 * X[9] + 58 * X[11] + 36 * X[12] + X[13] == 0x48b9)
eq[8] = (83 * X[7] + 73 * X[10] + 27 * X[11] + 12 * X[9] + 85 * X[8] + 96 * X[12] + 52 * X[13] == 0xa376)
eq[9] = (78 * X[7] + 24 * X[9] + 53 * X[8] + 36 * X[10] + 86 * X[11] + 25 * X[12] + 46 * X[13] == 0x8cf0)
eq[10] = (39 * X[7] + 78 * X[8] + 52 * X[9] + 9 * X[10] + 62 * X[11] + 37 * X[12] + 84 * X[13] == 0x8985)
eq[11] = (48 * X[11] + 14 * X[9] + 23 * X[7] + 6 * X[8] + 74 * X[10] + 12 * X[12] + 83 * X[13] == 0x70d8)
eq[12] = (92 * X[9] + 15 * X[12] + 48 * X[11] + 85 * X[8] + 27 * X[7] + 42 * X[10] + 72 * X[13] == 0x8dfa)
eq[13] = (26 * X[12] + 67 * X[10] + 6 * X[8] + 4 * X[7] + 3 * X[9] + 68 * X[13] == 0x4979)
eq[14] = (34 * X[17] + 12 * X[14] + 53 * X[15] + 6 * X[16] + 58 * X[18] + 36 * X[19] + X[20] == 0x5135)
eq[15] = (83 * X[14] + 73 * X[17] + 27 * X[18] + 12 * X[16] + 85 * X[15] + 96 * X[19] + 52 * X[20] == 0x99ac)
eq[16] = (78 * X[14] + 24 * X[16] + 53 * X[15] + 36 * X[17] + 86 * X[18] + 25 * X[19] + 46 * X[20] == 0x7c3b)
eq[17] = (39 * X[14] + 78 * X[15] + 52 * X[16] + 9 * X[17] + 62 * X[18] + 37 * X[19] + 84 * X[20] == 0x835d)
eq[18] = (48 * X[18] + 14 * X[16] + 23 * X[14] + 6 * X[15] + 74 * X[17] + 12 * X[19] + 83 * X[20] == 0x5f62)
eq[19] = (92 * X[16] + 15 * X[19] + 48 * X[18] + 85 * X[15] + 27 * X[14] + 42 * X[17] + 72 * X[20] == 0x8558)
eq[20] = (26 * X[19] + 67 * X[17] + 6 * X[15] + 4 * X[14] + 3 * X[16] + 68 * X[20] == 0x4078)
eq[21] = (34 * X[24] + 12 * X[21] + 53 * X[22] + 6 * X[23] + 58 * X[25] + 36 * X[26] + X[27] == 0x4cb6)
eq[22] = (83 * X[21] + 73 * X[24] + 27 * X[25] + 12 * X[23] + 85 * X[22] + 96 * X[26] + 52 * X[27] == 0x9e43)
eq[23] = (78 * X[21] + 24 * X[23] + 53 * X[22] + 36 * X[24] + 86 * X[25] + 25 * X[26] + 46 * X[27] == 0x8e2c)
eq[24] = (39 * X[21] + 78 * X[22] + 52 * X[23] + 9 * X[24] + 62 * X[25] + 37 * X[26] + 84 * X[27] == 0x93cf)
eq[25] = (48 * X[25] + 14 * X[23] + 23 * X[21] + 6 * X[22] + 74 * X[24] + 12 * X[26] + 83 * X[27] == 0x713a)
eq[26] = (92 * X[23] + 15 * X[26] + 48 * X[25] + 85 * X[22] + 27 * X[21] + 42 * X[24] + 72 * X[27] == 0xa2ef)
eq[27] = (26 * X[26] + 67 * X[24] + 6 * X[22] + 4 * X[21] + 3 * X[23] + 68 * X[27] == 0x48ad)
ans = solve(eq, X)[0]
ans = [res.right() for res in ans]
print(bytes(ans).decode())

即可解出答案


分类:Reverse
image
作者:alexzhu

2

提交

6

收入

相关WriteUP

  • 2018网鼎杯3-babyre

    ***收费WriteUP请购买后查看,VIP用户可免费查看***

    • Reverse
    • 3年前
  • EasyXor

    ***收费WriteUP请购买后查看,VIP用户可免费查看***

    • Reverse
    • 1年前
  • EasyReverse

    ***收费WriteUP请购买后查看,VIP用户可免费查看***

    • Reverse
    • 1年前
  • [NUAACTF-2017] [Reverse]robots解法

    ***收费WriteUP请购买后查看,VIP用户可免费查看***

    • Reverse
    • 1年前
  • 2018-网鼎杯-advance

    ***收费WriteUP请购买后查看,VIP用户可免费查看***

    • Reverse
    • 1年前
问题反馈