在O(n)的复杂度内反转SHA-256sigma0函数？

html5 • • 问答

介绍

作为 SHA-256 散列算法的一部分，有一个函数通常被称为?1，或者sigma0为了方便起见。基本上，它以 X 作为输入，其中 X 是 32 位无符号值。然后像这样转换它：

ROTATE_RIGHT(X, 7) ^ ROTATE_RIGHT(X, 18) ^ SHIFT_RIGHT(X, 3)


ROTATE_RIGHT(X, 7) ^ ROTATE_RIGHT(X, 18) ^ SHIFT_RIGHT(X, 3)

一点解释，如果你需要的话：

  • ROTATE_RIGHT(X, Y) - 将 X 的位向右旋转 Y
  • SHIFT_RIGHT(X, Y) - 将 X 的位右移 Y，因此结果的前 Y 位始终为 0

另外，如果您需要代码，这里是 Python 的完整版本：

反向功能

我开始怀疑那个东西是否可逆，令我惊讶的是，编写一个函数并没有花很长时间，该函数根据 givensigma0的输出返回该函数的输入，或者简单地说，反转sigma0函数。我不会把代码放在这里，因为它是用 Node.js 编写的，并且根据sigma0通过掩码搜索特定输入的更复杂的需求进行了大量修改，但我想给你一个我如何解决它的基本概念，所以也许你可以用一些关于如何实现我需要的新想法来启发我。

我的解决方案很简单，但它也是递归的。我们知道每个输出的位都是两个或三个输入位的异或运算的结果。所以我制作了一个依赖表，以便我可以看到输出位如何受到输入位的影响：

I:  00,01,02,03,04,05,06,07,08,09,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31

R7  25,26,27,28,29,30,31,00,01,02,03,04,05,06,07,08,09,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24
R18 14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,00,01,02,03,04,05,06,07,08,09,10,11,12,13
S3  zz,zz,zz,00,01,02,03,04,05,06,07,08,09,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28
---------------------------------------------------------------------------------------------------
O:  00,01,02,03,04,05,06,07,08,09,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31

这件事是关于什么的？假设，在输出的第 1 位中，我们有 1。为方便起见，我将其写为O[0], O[1], ... O[31]，输出的第O[x](x+1) 位也是如此。输入相同，标记为I。

所以，O[0] == 1。在上表中我们可以看到，O[0]是的XOR运算的结果I[25]和I[14]。这意味着这些输入的位中只有一个必须是 1。所以在这一点上，我们可以说我们可以为输入创建两个合适的掩码：

##############0#########1#######
##############1#########0#######

这些面具是解决方案的关键，至少对我来说是这样。#表示任何值（0 或 1）。当我们创建掩码时，我们为下一位调用递归函数，但保留掩码。如果我们没有适合以前的掩码的可能掩码，则先前的掩码没有解决方案，如果我们达到第 32 位，我们保证掩码中没有锐利，这将是答案。

首先，我需要告诉你这东西有效。但是在 Node.js 上，它计算每个值大约 100 毫秒，我不知道我的递归算法最糟糕的复杂性是什么，因为它很难衡量。它不满足我，我在试图解决这个 O(n) 的时候脑子坏掉了。

问题

我想知道是否有可能编写一个sigma0在 O(n) 复杂度内反转的函数，其中n输入/输出中的位数等于 32，没有递归、掩码或树，简单而快速。

我没有为我的陈述得出任何数学证明，但我测试了许多不同的值，我可以自信地声称输入值的数量等于这个函数的输出值的数量，并且两者都等于2^32 - 1。换句话说，对于每个输出，只有一个可能的sigma0函数输入。

这让我想到，sigma0原始函数产生复杂度为 O(n)的事实意味着反向函数必须有一个也适用于 O(n) 的解决方案。

如果您在数学上向我证明这是不可能的，我也会接受这个答案，但我没有发现任何表明此任务不可能的内容。

消耗资源的解决方法

如果我有 16gb 的空闲内存，我可以将所有可能的值预先计算到文件中，然后将它作为一个巨大的数组加载到内存中。但这不是解决方案，因为还有其他 3 个类似的功能，要为所有这些功能做到这一点，我需要 64gb 的内存，这对于这个简单的任务来说太昂贵和过多了。

UPD：高斯消元法

感谢 Artjom B. 的评论，我找到了一种通过高斯消元法求解 XOR 方程的好方法。目前我正在尝试解决这样的矩阵：

Input:  00000000100110101000111011101001
Output: 01110001101010000010010011100110

0:  0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 | 0
1:  0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 | 1
2:  0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 | 1
3:  1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 | 1
4:  0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1 0 0 | 0
5:  0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1 0 | 0
6:  0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1 | 0
7:  1 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 | 1
8:  0 1 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 | 1
9:  0 0 1 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 | 0
10: 0 0 0 1 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 | 1
11: 0 0 0 0 1 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 | 0
12: 0 0 0 0 0 1 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 | 1
13: 0 0 0 0 0 0 1 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 | 0
14: 0 0 0 0 0 0 0 1 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 | 0
15: 0 0 0 0 0 0 0 0 1 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 | 0
16: 0 0 0 0 0 0 0 0 0 1 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 | 0
17: 0 0 0 0 0 0 0 0 0 0 1 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 | 0
18: 1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 | 1
19: 0 1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 | 0
20: 0 0 1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 | 0
21: 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 | 1
22: 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 | 0
23: 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 | 0
24: 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 1 0 0 0 0 0 0 0 0 0 0 | 1
25: 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 1 0 0 0 0 0 0 0 0 0 | 1
26: 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 1 0 0 0 0 0 0 0 0 | 1
27: 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 1 0 0 0 0 0 0 0 | 0
28: 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 1 0 0 0 0 0 0 | 0
29: 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 1 0 0 0 0 0 | 1
30: 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 1 0 0 0 0 | 1
31: 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 1 0 0 0 | 0

发布矩阵，这样您就可以看到它的外观，而不必浪费时间自己创建它。一旦我解决了它，我会更新我的问题。

回答

如果我们将其sigma0视为 GF(2) 32向量上的函数，您会注意到它是线性的。GF(2) 32 中的加法只是二进制 XOR：

>>> sigma0(235 ^ 352124)
2045075788

>>> sigma0(235) ^ sigma0(352124)
2045075788

这意味着，如果我们能找到sigma0(x0) = 0b1、sigma0(x1) = 0b10等，我们就可以轻松地逐位反转任何内容。我们可以很容易地找到这些逆z3：

import z3

def z3_sigma0(x):
    return z3.RotateRight(x, 7) ^ z3.RotateRight(x, 18) ^ z3.LShR(x, 3)

s = z3.Solver()
xs = [z3.BitVec(f"x{i}", 32) for i in range(32)]
for i in range(32):
    s.add(z3_sigma0(xs[i]) == (1 << i))
print(s.check())
m = s.model()
for i in range(32):
    print("x{:02} = 0x{:08x}".format(i, m[xs[i]].as_long()))

这立即输出：

sat
x00 = 0x185744e9
x01 = 0x30ae89d2
x02 = 0x615d13a4
x03 = 0xdaed63a1
x04 = 0x9cd03a8e
x05 = 0x08fdcc39
x06 = 0x11fb9872
x07 = 0x23f730e4
x08 = 0x5fb92521
x09 = 0xbf724a42
x10 = 0x57ee6948
x11 = 0xafdcd290
x12 = 0x76b358ec
x13 = 0xf531f531
x14 = 0xc36917ae
x15 = 0xb78f9679
x16 = 0x4615d13e
x17 = 0x947ce695
x18 = 0x19a4740f
x19 = 0x2b1facf7
x20 = 0x4e681d07
x21 = 0x84877ee7
x22 = 0x385344eb
x23 = 0x70a689d6
x24 = 0xf91a5745
x25 = 0xc36917af
x26 = 0xb78f967b
x27 = 0x4615d13a
x28 = 0x8c2ba274
x29 = 0x290afdcd
x30 = 0x4a42bf73
x31 = 0x94857ee6

因此我们可以使用它来制作我们的反演函数：

sigma0_singleton_inverses = [
    0x185744e9, 0x30ae89d2, 0x615d13a4, 0xdaed63a1, 0x9cd03a8e, 0x08fdcc39,
    0x11fb9872, 0x23f730e4, 0x5fb92521, 0xbf724a42, 0x57ee6948, 0xafdcd290,
    0x76b358ec, 0xf531f531, 0xc36917ae, 0xb78f9679, 0x4615d13e, 0x947ce695,
    0x19a4740f, 0x2b1facf7, 0x4e681d07, 0x84877ee7, 0x385344eb, 0x70a689d6,
    0xf91a5745, 0xc36917af, 0xb78f967b, 0x4615d13a, 0x8c2ba274, 0x290afdcd,
    0x4a42bf73, 0x94857ee6
]

def inv_sigma0(x):
    r = 0
    for i in range(32):
        if x & (1 << i):
            r ^= sigma0_singleton_inverses[i]
    return r

确实：

>>> def test_inv_once():
...     r = random.randrange(2**32)
...     return inv_sigma0(sigma0(r)) == r
>>> all(test_inv_once() for _ in range(10**6))
True

上面可以写成完全无环和无分支的：

def inv_sigma0(x):
    xn = ~x
    r  = (((xn >>  0) & 1) - 1) & 0x185744e9
    r ^= (((xn >>  1) & 1) - 1) & 0x30ae89d2
    r ^= (((xn >>  2) & 1) - 1) & 0x615d13a4
    r ^= (((xn >>  3) & 1) - 1) & 0xdaed63a1
    r ^= (((xn >>  4) & 1) - 1) & 0x9cd03a8e
    r ^= (((xn >>  5) & 1) - 1) & 0x08fdcc39
    r ^= (((xn >>  6) & 1) - 1) & 0x11fb9872
    r ^= (((xn >>  7) & 1) - 1) & 0x23f730e4
    r ^= (((xn >>  8) & 1) - 1) & 0x5fb92521
    r ^= (((xn >>  9) & 1) - 1) & 0xbf724a42
    r ^= (((xn >> 10) & 1) - 1) & 0x57ee6948
    r ^= (((xn >> 11) & 1) - 1) & 0xafdcd290
    r ^= (((xn >> 12) & 1) - 1) & 0x76b358ec
    r ^= (((xn >> 13) & 1) - 1) & 0xf531f531
    r ^= (((xn >> 14) & 1) - 1) & 0xc36917ae
    r ^= (((xn >> 15) & 1) - 1) & 0xb78f9679
    r ^= (((xn >> 16) & 1) - 1) & 0x4615d13e
    r ^= (((xn >> 17) & 1) - 1) & 0x947ce695
    r ^= (((xn >> 18) & 1) - 1) & 0x19a4740f
    r ^= (((xn >> 19) & 1) - 1) & 0x2b1facf7
    r ^= (((xn >> 20) & 1) - 1) & 0x4e681d07
    r ^= (((xn >> 21) & 1) - 1) & 0x84877ee7
    r ^= (((xn >> 22) & 1) - 1) & 0x385344eb
    r ^= (((xn >> 23) & 1) - 1) & 0x70a689d6
    r ^= (((xn >> 24) & 1) - 1) & 0xf91a5745
    r ^= (((xn >> 25) & 1) - 1) & 0xc36917af
    r ^= (((xn >> 26) & 1) - 1) & 0xb78f967b
    r ^= (((xn >> 27) & 1) - 1) & 0x4615d13a
    r ^= (((xn >> 28) & 1) - 1) & 0x8c2ba274
    r ^= (((xn >> 29) & 1) - 1) & 0x290afdcd
    r ^= (((xn >> 30) & 1) - 1) & 0x4a42bf73
    r ^= (((xn >> 31) & 1) - 1) & 0x94857ee6
    return r

最快的版本可能是这个，使用 2 × 2 16大小的查找表（或类似地对 4 × 2 8大小的表进行四次查找）一次按 16 位分组。

sigma0_16bit_inverse_lo = [inv_sigma0(x)       for x in range(2**16)]
sigma0_16bit_inverse_hi = [inv_sigma0(x << 16) for x in range(2**16)]
def fast_inv_sigma0(x):
    return (sigma0_16bit_inverse_lo[x & 0xffff] ^
            sigma0_16bit_inverse_hi[(x >> 16) & 0xffff])

  • @MaxSeid And yes, `z3` is an immensely powerful tool, magic at times, but it can very quickly go from 'solve my problem with z3' to 'z3 is useless for my problem', and sometimes you don't know which it is before simply trying out the solver. If you had use Gaussian elimination on your matrix and read them out as binary integers row-by-row, you would've found the same integers I found using `z3`.
以上是在O(n)的复杂度内反转SHA-256sigma0函数？的全部内容。
THE END
分享
二维码
< <上一篇
下一篇>>