识别密码生成算法

逆向工程 加密 解密 异或
2021-06-10 04:20:09

我是一个新手，刚刚通过逆向工程开始自己的方式，所以如果我的问题不合适，我深表歉意。目前我正在经历不同的 Crackme 谜题，现在我被卡住了。我花了几天时间试图解决它，但我不能。

我们输入登录名和密码。然后我们在登录时应用算法#1。以及关于密码的算法#2。在这两种情况下，我们都会得到一个数字。如果两个数字相等，则密码正确。我试图找到一种方法来为任何给定的登录生成正确的密码。

我已经用 IDA 找出了这两种算法，并用 C++ 编写了一个程序来测试我的解决方案。

登录算法

登录名应至少为 4 个字符。

login = "Vasya_Pupkin"

1）从登录我们得到两个第一个字符（“Va”）和两个最后一个（“in”）并将其 ASCII 代码写入十六进制数：

V = 0x56, a = 0x61, i = 0x69, n = 0x6e
hexVain = 0x5661696e

2）我们通过登录字符串并将所有ASCII码相加：

for (int j = 0; j < login.length(); j++)        
    asciiSum += login[j];

因为Vasya_Pupkin我们得到 asciiSum = 0x4da

3）我们将这些值与某个数字 0xfec0135a 进行异或：

hexVain ^ asciiSum ^ 0xfec0135a
magicValueLogin = 0xa8a17eee

密码算法

密码应至少为 12 个字符，并且应仅包含 'a'-'f'、'A'-'F'、'0'-'9'。我们输入密码作为字符串。然后我们将长度除以 2。

password_str = "011c0d0f090e00";
n = password_str.length() / 2;  // n = 7

然后我们将字符串表示转换为十六进制并应用这个算法：我们从左到右遍历每个字节并计算新的魔术值。

password = 0x011c0d0f090e00;
magicValuePass = 0xadde;
for (int i = 0; i < n; i++)
{
    // we count bytes from left to right
    passByte = getByte(password, i);    

    // multiplication by 32 is left shift for 5 bytes
    magicValuePass = passByte ^ (32 * magicValuePass + 1) ^ 0xdeadbeef;
}

此函数的输出如下：

Byte:  01
Magic: deb8052f

Byte:  1c
Magic: 9ad1b12

Byte:  0d
Magic: eb0edca3

Byte:  0f
Magic: bf762a81

Byte:  09
Magic: 3068eec7

Byte:  0e
Magic: d3b06600

Byte:  00
Magic: a8a17eee

最后我们得到magicValuePass = 0xa8a17eee的值与登录时得到的值相同，因此密码是正确的。

我试过的

我想过逆转magicValuePass一代，但得出的结论是这是一个坏主意。

2个回答

由于您刚刚开始使用 RE，请尝试研究 SAT 求解器。Z3是一个很棒的工具，它将帮助您使用所有主要语言的 API 完成如此简单的任务。这是我在 python 中尝试的解决方案。

password = BitVec("password",64)
magicValuePass = BitVec("magicValuePass",64)

s = Solver()
idx = 7
magicValuePass =  (((password&(0xff<<(8*idx)))>>(8*idx))^ (32 * 0xadde + 1) ^ 0xdeadbeef) & 0xffffffff
for i in xrange(6,0,-1):
    magicValuePass =  (((password&(0xff<<(8*i)))>>(8*i))^ (32 * magicValuePass + 1) ^ 0xdeadbeef) & 0xffffffff

s.add(magicValuePass == magicValueLogin)

if s.check() == sat:
    print hex(s.model()[password].as_long())

首先声明password为64位变量。然后逐字节迭代计算中间值，最后设置magicValuePass等于magicValueLogin。如果存在针对此类条件的解决方案，Z3 将运行一段时间并给出打印的解决方案。 完整的脚本在这里运行时给出了这样的输出

$ python test-so.py Vasya_Pupkin
0x11c0d0f090e0000
$ python test-so.py ABCD        
0x1171f0902111a00
$ python test-so.py DEfg
0x1150f070b1a0500

如何从密码生成多个登录名？

首先，算法 1 看起来是最薄弱的环节。算法 2 是一个单向哈希函数，您无法仅通过知道幻数和密码偏差来提取字符。它涉及一些高级数学工作和时间。我在第二部分解释了破解算法2的过程。

认为 ：

log_bias = 0xfec0135a

pass_bias = 0xdeadbeef

让我们看看算法1：

1) log_chunk = 0xlogin(0)login(1)login(n - 2)login(n - 1);

2) log_checksum = Sum(login, 0, n);

3) log_magicnumber = log_chunk ^ log_checksum ^ log_bias;

该算法显示了两个潜在的弱点。一，如果你把幻数和log_bias常数异或你得到： log_chunk ^ log_checksum。二、log_chunk是前两个字符和后两个字符的十六进制拼接，为登录提供一个框架；因此，我们可以生成自己的字符并为该变量赋值。

在消除偏差并为块选择一个值后，我们可以获得log_checksum的值。

log_checksum = (log_magicnumber ^ log_bias) ^ log_chunk;

剩下要做的是找到表示字符的数字序列，其总和是校验和。

如何？

好吧，如果您查看ASCII表，您会看到可打印字符从 33 到 126。如果我们生成一个介于 33 和 126 之间的随机值b并将其从校验和中减去，我们将获得一个字符值b并减少校验和值通过b：log_checksum -= b。重复此操作，直到校验和值低于 126，并且只存储diff = (log_checksum - b)大于或等于 33 的字符。这样，所有字符都可以打印。

填写登录字符串的中间后，可以表示如下：

登录= AB b 0 b 1 b 2 ... b j CD

其中 A、B、C、D 是我们选择的字符，而b是从校验和生成的字符。

这种逆向工程方法是一种廉价的智能黑客，它针对过程中最弱的哈希函数，它肯定会起作用并节省您的时间。通过一个密码，您将获得多次登录：这称为哈希冲突。

这是此代码的示例输出：

Login: Vasya_Pupkin
Password: 011c0d0f090e00
Login    check : 0xa8a17eee
Password check : 0xa8a17eee
Check success :)
Valid login for pass_magicnumber 0xa8a17eee: Va[JiIUpHBI]in, length = 14
Valid login for pass_magicnumber 0xa8a17eee: VaU[^OnyD^fin, length = 13
Valid login for pass_magicnumber 0xa8a17eee: Va|IkH`y`i2in, length = 13
Valid login for pass_magicnumber 0xa8a17eee: VaTziSl^oK>in, length = 13
Valid login for pass_magicnumber 0xa8a17eee: VawNzAOGWktin, length = 13
Valid login for pass_magicnumber 0xa8a17eee: Vaeh]bmzbwin, length = 12
Valid login for pass_magicnumber 0xa8a17eee: VaugjXcNEvBin, length = 13
Valid login for pass_magicnumber 0xa8a17eee: VaJoMwQ{p[8in, length = 13
Valid login for pass_magicnumber 0xa8a17eee: VatBZwR`R|Ein, length = 13
Valid login for pass_magicnumber 0xa8a17eee: VaIy[lkZQbKin, length = 13

所有列出的有效登录都适用于密码“011c0d0f090e00”。如果您稍微更改密码，请说：“011c0d0f090efe”，这就是您得到的：

Login: VaNpNa^Twin 
Password: 011c0d0f090efe
Login    check : 0xa8a17e10
Password check : 0xa8a17e10
Check success :)
Valid login for pass_magicnumber 0xa8a17e10: VaeOTUkOG8in, length = 12
Valid login for pass_magicnumber 0xa8a17e10: VaUDFEzBx>in, length = 12
Valid login for pass_magicnumber 0xa8a17e10: Va|gktoein, length = 10
Valid login for pass_magicnumber 0xa8a17e10: VaaPRTogiin, length = 11
Valid login for pass_magicnumber 0xa8a17e10: VaFEzBpktin, length = 11
Valid login for pass_magicnumber 0xa8a17e10: VafCCzmQrin, length = 11
Valid login for pass_magicnumber 0xa8a17e10: VaFDWMHSNC<in, length = 13
Valid login for pass_magicnumber 0xa8a17e10: VaSvoIgR\in, length = 11
Valid login for pass_magicnumber 0xa8a17e10: Va[{eLdl?in, length = 11
Valid login for pass_magicnumber 0xa8a17e10: VaPaoDPXFDin, length = 12

现在，让我们谈谈从登录幻数生成密码。你必须攻击这个函数：

log_magicnumber = b ^ ((log_magicnumber << 5) + 1) ^ pass_bias

如果仔细观察，您会发现当前的log_magicnumber是使用先前的log_magicnumber值转换并与未知字节值和已知偏差混合计算得出的。迭代，它看起来像这样：

log_magicnumber(i) = b ^ ((log_magicnumber(i - 1) << 5) + 1) ^ pass_bias

如果我们对pass_magicnumber和pass_bias 进行异或，我们就剩下：

b ^ ((log_magicnumber << 5) + 1)

在生成b 的所有可能值（0-9和af，总共 16 种可能性）并为b 的每个可能值导出log_magicnumber的相应值后，我们对这些幻数值应用相同的步骤以获得另一个值 & 我们继续8 次（密码字符串为 64 位值 = 8 个字节，最小长度为 6 个字节）。如果设置为零，我们丢弃最左边的两个字节并将所有字节打包成密码字符串；然后我们使用密码幻数算法验证密码的幻数是否与登录名匹配。

这种方法相当于创建一个 8 阶段树，其中每个节点有 16 个子节点。这意味着我们必须生成 16 的 8 个字符的幂：16^8 = (2^4)^8 = 2^32 = 4.294.967.296 个字符 (4GB) 并将它们组合成 6 到 8 个字符的字符串每个字符串都被检查以进行验证。编码很有趣:)

其它你可能感兴趣的问题
上一篇如何使用 DbgUiRemoteBreakin 修复反调试器 下一篇内核调试 - 内核模式下的 Internet Explorer？