如何进行逆向工程算法？

Question

我想知道如何去颠倒一个算法，如用于存储登录名或密码的算法。

可以说我有数据量，其中：

7262627 -> ? -> 8172 

5353773 -> ? -> 1132 

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

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

我该如何着手弄清楚算法是什么？一个人从哪里开始？

你会开始尝试不同的班次，xors和希望有什么突出的东西吗？我确信有更好的方法，因为这看起来像在黑暗中刺伤。

反向工程这种算法是否可行？

对不起，如果这是一个愚蠢的问题。感谢您的帮助/指示。

Answer 1

反向工程这种算法是否可行？

有可能与一个有缺陷的算法和足够的加密/未加密的对，但一个精心设计的算法可以消除这样它在所有的这种可能性。

Answer 2

也许，你不能。假设转换功能是已知的，像

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

但“秘密盐”不知道，是保密性强的（一个非常大的，随机整数）。即使是非常大量的纯文本crypttext对，也绝不能强制使用秘密盐。实际上，如果使用的精确哈希函数是已知的两个同样强大的函数之一，那么您甚至不可能在使用哪一个哈希函数之间得到一个好的猜测。

Answer 3

有一些东西的人尝试：

• 获取源代码，或拆解的可执行文件。
• 猜测，基于其他人使用的散列函数。例如，由32个十六进制数字组成的哈希可能是MD5的一个或多个重复，并且如果您可以获得单个输入/输出对，则很容易确认或反驳（尽管参见下面的“盐”）， 。
• 统计分析大量输入和输出对，查找任何类型的模式或相关性，并将这些相关性与系统设计者可能使用的已知散列函数和/或可能操作的属性相关联。这超出了单一技术的范围，并进入了通用密码分析领域。
• 问问作者。安全系统通常不依赖于他们使用的哈希算法的保密性（如果他们使用哈希算法，通常不会保密）。然而，你给出的例子很小，密码的安全散列总是涉及盐，而你显然不会。所以我们可能不会谈论作者有信心这样做的系统。

对于输出仅为4位十进制数字的散列，只需构建一个包含每个可能的7位输入的表格及其散列值，即可对其进行攻击。然后，您可以反转该表，并进行（一对多）去散列操作。你永远不需要知道散列是如何计算的。你如何获得输入/输出对？那么，如果外人可以以某种方式指定要散列的值，并查看结果，那么就有了所谓的“选定明文”，并且依赖于此的攻击是“选定的明文攻击”。因此，如果以允许选择明文攻击生成大量输入/输出对的方式使用7位数字 - > 4位数字散列，则其实非常微弱。我意识到这只是一个例子，但它也只是扭转它的一种技术的一个例子。

请注意，对散列进行逆向工程并实际反转散列是两件不同的事情。你可能会发现我使用的是SHA-256，但是这并不能帮助你将其反转（即给出一个输出，计算出输入值）。没有人知道如何完全反转SHA-256，尽管当然总是有彩虹表（见上面的“盐”）<conspiracy>至少没有人承认他们这样做，所以对你我都没有用处。 </conspiracy>

Answer 4

在黑暗中刺伤会使你精神错乱。有一些算法，根据目前的了解，你不可能希望推断现在和宇宙[预测]结束之间的内部工作，而不知道确切的细节（可能包括私人密钥或内部状态）。当然，其中一些算法是现代密码学的基础。

如果你事先知道有一个要发现的模式，有时候有办法解决这个问题。例如，如果数据集包含相差1多个输入值，比较对应的输出值：

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

这是相当清楚的（给定了几分钟，一个计算器），当加1，输入增大输出增加913模8266（即简单的linear congruential generator）。

Differential cryptanalysis是用来分析密码分组密码的强度，依靠对于其中密码算法是已知的类似但更复杂的想法比较现代的技术，但它承担的私钥不。考虑一个位彼此不同的输入块，并通过密码来追踪该位的影响，以推断每个输出位可能“翻转”的可能性。

解决这类问题的其他方法是查看极值（最大值，最小值），分布（导致frequency analysis），方向（数字总是增加？减少？）和（如果允许的话） ）考虑数据集被发现的上下文。例如，某些类型的PIN码的总是包含重复的数字，使他们更容易记住（我不是说PIN码可以一定是推断从别的 - 只是一个重复的数字是一个少一位数字担心！）。