这个算法是可逆的吗?

逆向工程 艾达
2021-06-25 18:32:48

我正在尝试解决 Crackme 挑战。它需要我输入的密码并进行以下操作。

最后,它将输出与 0x1928F914

如何反转此算法以获取有效密码。

  Result = 0;
  for ( counter = 0; counter < 10; ++counter )
    Result = __ROR4__(Result, 9) ^ *(counter + Passwd);
  return Result;
1个回答

从某种意义上说,由于旋转会重叠而丢失信息,您可以为给定的目标数字计算单个输入,这是不可逆的,但您可以找到导致该数字的输入。

我喜欢通过感受输入和输出位的依赖性来应对这样的挑战。为此,我通常会编写脚本来象征性地运行算法并打印所发生事件的文本再现。

对于这里的挑战,我编写了以下 Python 脚本:

#!/usr/bin/env python3
def ror9_list(l):
    return l[9:] + l[:9]

def getbit(d,n):
    return (d & (1 << n)) != 0

def gen():
    target = 0x1928F914

    bits = []
    for i in range(32):
        bits.append("0")

    for i in range(10):
        # ror
        bits = ror9_list(bits)
        
        # then xor in new char
        for n in range(8):
            bits[n] += "^ C(%d,%d) " % (i,n)

    for i in range(32):
        print("bit %2d = %-30s must be %d" % (i,bits[i][3:],getbit(target,i)))

gen()

生成以下文本:

bit  0 = C(5,4) ^ C(9,0)                must be 0
bit  1 = C(2,0) ^ C(5,5) ^ C(9,1)       must be 0
bit  2 = C(2,1) ^ C(5,6) ^ C(9,2)       must be 1
bit  3 = C(2,2) ^ C(5,7) ^ C(9,3)       must be 0
bit  4 = C(2,3) ^ C(9,4)                must be 1
bit  5 = C(2,4) ^ C(6,0) ^ C(9,5)       must be 0
bit  6 = C(2,5) ^ C(6,1) ^ C(9,6)       must be 0
bit  7 = C(2,6) ^ C(6,2) ^ C(9,7)       must be 0
bit  8 = C(2,7) ^ C(6,3)                must be 1
bit  9 = C(6,4)                         must be 0
bit 10 = C(3,0) ^ C(6,5)                must be 0
bit 11 = C(3,1) ^ C(6,6)                must be 1
bit 12 = C(3,2) ^ C(6,7)                must be 1
bit 13 = C(3,3)                         must be 1
bit 14 = C(3,4) ^ C(7,0)                must be 1
bit 15 = C(0,0) ^ C(3,5) ^ C(7,1)       must be 1
bit 16 = C(0,1) ^ C(3,6) ^ C(7,2)       must be 0
bit 17 = C(0,2) ^ C(3,7) ^ C(7,3)       must be 0
bit 18 = C(0,3) ^ C(7,4)                must be 0
bit 19 = C(0,4) ^ C(4,0) ^ C(7,5)       must be 1
bit 20 = C(0,5) ^ C(4,1) ^ C(7,6)       must be 0
bit 21 = C(0,6) ^ C(4,2) ^ C(7,7)       must be 1
bit 22 = C(0,7) ^ C(4,3)                must be 0
bit 23 = C(4,4) ^ C(8,0)                must be 0
bit 24 = C(1,0) ^ C(4,5) ^ C(8,1)       must be 1
bit 25 = C(1,1) ^ C(4,6) ^ C(8,2)       must be 0
bit 26 = C(1,2) ^ C(4,7) ^ C(8,3)       must be 0
bit 27 = C(1,3) ^ C(8,4)                must be 1
bit 28 = C(1,4) ^ C(5,0) ^ C(8,5)       must be 1
bit 29 = C(1,5) ^ C(5,1) ^ C(8,6)       must be 0
bit 30 = C(1,6) ^ C(5,2) ^ C(8,7)       must be 0
bit 31 = C(1,7) ^ C(5,3)                must be 0

该脚本模拟 10 个字符长输入的哈希算法,其中C(x,y)从 0 开始y的字符x

例如,最后一行

bit 31 = C(1,7) ^ C(5,3)                must be 0

表示与第 6 个字符的第 4 位异或的第 2 个字符的第 8 位必须为 0 才能匹配目标数字的第 32 位,即 0。所以该行告诉您(由于 xor 的特性) 这 2 位必须相等,但您可以自由选择两者是 0 还是 1。

因此,文本表示为您的输入字符提供了必要的约束,以便产生正确的数字。

您可以手动选择正确的字符或编写自己的小程序,但这对于像 Z3 这样的约束求解器来说可能是一个很好的练习。

只需给它一些约束,让求解器找出一个有效的输入。您可能想要添加输入字符是可打印 ASCII 的约束,以便您可以通过键盘输入解决方案。