如何进行算法逆向工程？

Question

我想知道如何反向算法，例如存储登录信息或PIN码的算法。

假设我有一些数据，其中：

7262627 -> ? -> 8172

5353773 -> ? -> 1132

等等，这只是一个例子。或者说一个十六进制字符串被转换成另一个字符串。

&h8712 -> &h1283 或者类似的东西。

我该如何开始研究算法呢？从哪里开始呢？

你会尝试不同的移位、异或操作，希望能发现一些规律吗？我相信这样做就像在黑暗中寻找，还有更好的方法。

甚至有可能逆向工程这种类型的算法吗？

如果这个问题很愚蠢，请原谅我。感谢您的帮助和指导。

- Evelyn

---

为什么这个问题被标记为“不是一个真正的问题”？很容易看出这个问题在询问什么。问题并不模棱两可、含糊不清、不完整或修辞性，尽管它可能过于宽泛。在当前形式下，这个问题可以得到合理的回答：特别是因为它只是在问如何开始对哈希函数进行密码分析。回答这个问题并不需要一本教科书。 - Steve Jessop

请参见 https://dev59.com/XknSa4cB1Zd3GeqPQbYM。 - sdcvvc

Answer 1

有几种尝试方法：

- 获取源代码或反汇编可执行文件。 - 根据其他人使用的哈希函数进行猜测。例如，由32个十六进制数字组成的哈希值可能是MD5的一个或多个重复，如果您可以获得单个输入/输出对，则很容易确认或否认此（但请参见下面的“盐”）。 - 统计分析大量输入和输出对，寻找任何类型的模式或相关性，并将这些相关性与已知哈希函数的属性和/或系统设计者可能使用的可能操作相关联。这超出了单个技术的范围，进入了一般密码分析的领域。 - 询问作者。安全系统通常不依赖于使用的哈希算法的保密性（如果确实依赖于保密性，则通常不会长时间保持安全）。您提供的示例非常小，但是密码的安全哈希始终涉及盐，而您的密码明显没有。因此，我们可能不谈论作者有信心这样做的那种系统。

对于输出仅为4位小数的哈希，您可以通过构建每个可能的7位数字输入及其散列值的表来攻击它。然后，您可以反转表格并获得您的（一对多）去哈希操作。您永远不需要知道哈希实际上是如何计算的。如何获取输入/输出对？嗯，如果外部人员可以以某种方式指定要散列的值并查看结果，则拥有所谓的“选择明文”，并且依赖于此的攻击称为“选择明文攻击”。因此，如果7位数-> 4位数哈希用于允许选择明文攻击生成大量输入/输出对的方式，则非常脆弱。我意识到这只是一个例子，但这也是反转它的一种技术示例。

请注意，逆向工程哈希和实际反转哈希是两个不同的事情。您可以弄清楚我正在使用SHA-256，但这并不能帮助您反转它（即，给定输出，计算出输入值）。没有人知道如何完全反转SHA-256，尽管当然总有彩虹表（请参见上面的“盐”）至少没有人承认他们这样做，所以对您或我没有用。

- Steve Jessop

Answer 2

也许你不能。假设转换函数已知，类似于：

function hash(text):
    return sha1("secret salt"+text)

但是"秘密盐"并不为人所知，而且具有加密强度（一个非常大的随机整数）。即使有很多明文和密文对，你也无法从中暴力破解出秘密盐。

事实上，如果使用的哈希函数被认为是两个同样强大的函数之一，你甚至无法猜测到底使用了哪一个。

- SingleNegationElimination

---

+1，但是你最后的说法有点不准确。对于两个完全强大的哈希函数来说是正确的，但是一个哈希函数可能离实际可逆还有很长的路要走，但在给定足够的数据时仍然可以通过统计偏差进行识别。特别是对于SHA-1，目前的得分不确定。它在各种方面都趋向于稍微弱一些。 - Steve Jessop

@Steve Jessop：我完全同意这一点；据我所知，没有可推广的证明表明哈希函数没有数学上的弱点，但同时也没有可推广的方法来检测和利用它们。至少与SHA-1一样强大的哈希函数的漏洞可能总是需要特定的弱点知识来利用。 - SingleNegationElimination

是的，你（或者说加密社区）会运行在你所知道的每个哈希上的所有统计测试。如果某个哈希显示出偏差，那么这种偏差可以用来从输出中暂时地识别它。因此，你肯定会使用关于该哈希的特定知识，或者至少是包括该哈希在内的一类哈希的知识。要区分你的“两个同样强大的函数”，你需要知道其中一个函数中的特定偏差，而另一个函数则可以假定不具有该偏差。 - Steve Jessop

Answer 3

在黑暗中乱猜会让你发疯。有一些算法，根据当前的理解，你无法在预测的宇宙末日之前推断出其内部运作方式，除非知道确切的细节（可能包括私钥或内部状态）。当然，其中一些算法是现代密码学的基础。

如果您事先知道存在要发现的模式，则有时可以采用某些方法来接近这一目标。例如，如果数据集包含几个输入值，这些值相差1，请比较相应的输出值：

7262627 -> 8172
7262628 -> 819
7262629 -> 1732
...
7262631 -> 3558

在这里，很明显（只需几分钟和计算器），当输入增加1时，输出按913模8266递增（即简单的线性同余生成器）。

“差分密码分析”是一种相对较新的技术，用于分析加密块密码的强度。该技术依赖于一种类似但更复杂的思想，其中密码算法已知，但假定私钥未知。考虑彼此仅相差一个比特的输入块，并跟踪该比特在密码中的影响，以推断每个输出比特翻转的可能性有多大。

其他解决此类问题的方法包括考虑极端值（最大值、最小值）、分布（导致“频率分析”）、方向（数字是否总是增加？减少？），以及（如果允许）考虑找到数据集的上下文。例如，某些类型的 PIN 码始终包含重复的数字，以使它们更易记住（我并不是说可以从其他任何东西推断出 PIN 码，只是重复的数字是要考虑的“少”一个数字！）。

- SimonJ

---

"很明显，当输入增加1时，输出会增加913模8266" - 这正是我刚想说的。老实说;-) - Steve Jessop

Answer 4

这种算法是否实际上可以被逆向工程化呢？

如果是一个有缺陷的算法，并且有足够的加密/未加密对，那么是可能的。但是，一个设计良好的算法可以消除这种可能性。

- John