为什么不能对密码哈希进行逆向工程？
我很久以前就研究过这个并且已经阅读了很多，但我找不到为什么它不能完成的解释。一个示例将使我的问题更容易理解并保持简单，我们将其基于不使用盐的散列算法（LanMan）。
说我的密码是“密码”。LanMan 将对其进行哈希处理并将其存储在数据库中。破解程序可以通过散列您提供的密码猜测来暴力破解这些密码。然后它将生成的哈希与数据库中的哈希进行比较。如果匹配，它会计算出密码。
为什么，如果密码破解者知道将纯文本密码转换为散列的算法，它就不能逆转从散列计算密码的过程吗？
这个问题是本周的 IT 安全问题。
阅读 2012 年 2 月 24 日的博客文章了解更多详情或提交您自己的本周问题。
让我发明一个简单的“密码散列算法”来向您展示它是如何工作的。与此线程中的其他示例不同，如果您可以忍受一些奇怪的密码限制，那么这个示例实际上是可行的。您的密码是两个大质数，x和y。 例如：
x = 48112959837082048697
y = 54673257461630679457
你可以很容易地编写一个计算机程序在 O( N ^2) 时间内计算xy ，其中N是x和y的位数。 （基本上这意味着如果数字是两倍长，则需要四倍的时间。有更快的算法，但这无关紧要。）将xy存储在密码数据库中。
x*y = 2630492240413883318777134293253671517529
一个五年级的孩子，只要有足够的草稿纸，就能找出答案。但是你如何扭转它呢？人们设计了许多算法来分解大数，但与x乘y 的速度相比，即使是最好的算法也很慢。 并且这些算法都不能由五年级学生执行，除非数字非常小（例如，x=3，y=5）。
这是关键属性：向前计算比向后计算要简单得多。对于许多问题，您必须发明一种全新的算法来反转计算。
这与单射或双射函数无关。 当您破解密码时，您是否获得相同的密码或获得具有相同哈希值的不同密码通常并不重要。散列函数的设计使得它很难反转并得到任何答案，即使是具有相同散列的不同密码。用加密语言来说：易受原像攻击的哈希函数是完全没有价值的。（如果你有一个x < y 的规则，上面的密码散列算法是单射的。）
密码学专家做什么的？有时，他们试图找出新的算法来反转散列函数（原像）。他们完全按照你说的做：分析算法并尝试反转它。有些算法之前已经被反转，有些则没有。
读者练习：假设密码数据库包含以下条目：
3521851118865011044136429217528930691441965435121409905222808922963363310303627
密码是什么？（这对于计算机来说其实并不太难。）
脚注：由于人们在实践中选择的密码数量很少，一个好的密码哈希不仅难以向后计算，而且向前计算也很耗时，以减缓字典攻击。作为另一层保护，随机盐防止使用预先计算的攻击表（例如“彩虹表”）。
脚注 2：我们怎么知道哈希函数很难反转？不幸的是，我们没有。我们只是不知道任何简单的方法来反转散列函数。制作一个可证明难以逆转的散列函数是散列函数设计的圣杯，目前还没有实现（也许永远不会发生）。
这是一个很好的问题。
我们必须首先给出一个精确度：许多单向函数，特别是密码学中常用的散列函数，接受来自比输出值空间大得多的空间的输入。例如，为最多 18446744073709551615 位的字符串的输入定义了 SHA-256；有2 18446744073709551616 -1个可能的输入，但由于输出始终是 256 位的序列，因此 SHA-256 只有2 256个可能的输出。必然地，一些不同的输入产生相同的输出。因此，对于给定的 SHA-256 输出，不可能明确地恢复所使用的输入，但可能有可能计算出产生给定输出值的输入。原像阻力是关于：为输出找到匹配输入的难度（不管该输出最初是如何获得的）。
所以我们谈论一个每个人都可以根据任何输入计算的函数（使用一个公开的程序，不涉及秘密值——我们不是在谈论加密）。
学者怎么说
目前尚不清楚单向函数是否真的存在。现在，我们有许多没有人知道如何反转的函数；但这并不意味着它们在数学意义上是不可能反转的。但是请注意，没有证明单向函数不存在，所以希望仍然存在。有些人怀疑单向函数是否存在可能是这些令人讨厌的数学断言之一，既无法证明也无法证伪（哥德尔定理证明了这样的事情一定存在）。但也没有证据证明这一点。
因此，没有证据表明任何给定的散列函数真的能抵抗原像。
有一些功能可以与众所周知的难题相关联。例如，如果n是两个大素数的乘积，那么函数x ⟼ x 2 mod n很难求逆：能够以非素数n为模计算平方根（在一般基础上）等价于能够分解 n，并且已知该问题很难。未证实请注意，要努力；只是数学家在（至少）过去的 2500 年里一直试图有效地分解大整数，尽管已经取得了一些进展，但这些聪明人都没有找到真正的杀手级算法。“RSA 模数”（两个随机选择的相似长度的大素数的乘积）因式分解的世界纪录是一个 768 位整数。
已经提出了一些基于此类“难题”的哈希函数；参见例如MASH-1 和 MASH-2（关于RSA 问题）和ECOH（带有椭圆曲线）。只有少数这样的功能存在，因为：
将“难题”转化为安全的散列函数并不容易；有很多棘手的问题。例如，虽然以非素数n为模提取平方根通常很困难，但有些值的平方根提取很容易。
比如说，这种散列函数的性能往往不是最理想的。就像比更常用的 SHA-1 慢 100 倍一样。
构建散列函数的更“标准”方式是将密码学家聚集在一起，让他们研究一些提议的设计。在密码分析尝试中存活了几年的功能被认为是“可能是强大的”。SHA-3 竞赛就是这样的努力；获胜者应在今年晚些时候公布。在 51 名候选人（成功通过行政步骤的候选人）中，有 14 人被保留用于“第 2 轮”，这 14 人已被许多密码学家相对仔细地研究过，没有人发现任何真正值得一提的功能。该列表已减少到 5 个，并将“很快”进一步减少到 1 个，但不是出于安全原因（大多数实际数据是关于性能，而不是阻力）。
是什么让 MD5 难以反转
既然我们不知道如何证明一个函数是难求逆的，那么我们最好的办法就是在一个特定的函数上试一试，以便对函数如何实现其表观阻力有一个“直觉”。
我选择MD5，这是众所周知的。是的，MD5 是“损坏的”，但那是为了碰撞，而不是原像。有一种已知的原像攻击，至少在理论上，比通用方式更快（“通用方式”是“运气”，即尝试输入直到找到匹配项，因为 MD5 具有2 128次评估的平均成本） 128 位输出；Sasaki-Aoki 攻击的成本为2 123.4，较低，但仍然太高而无法实际尝试，因此结果仍然是理论上的）。但是 MD5 相对简单，并且已经经受了相当长的一段时间的攻击，所以这是一个有趣的例子。
MD5 包含对数据块的“压缩函数”的多次评估。首先填充输入消息，使其长度变为 512 位的倍数。然后将其拆分为 512 位块。一个 128 位运行状态（保存在称为A、B、C和D的四个 32 位变量中）被初始化为一个常规值，然后使用压缩函数进行处理。压缩函数获取运行状态和一个 512 位消息块，并将它们混合为运行状态的新值。当所有消息块都这样处理完后，运行状态的最终值就是哈希输出。
因此，让我们专注于压缩功能。它是这样工作的：
重要的一点是有 64 轮，但只有 16 个消息词。这意味着每个消息词进入处理四次。我用粗体写，因为它是中心点；对原像的抵抗来自该特性。在 MD5 规范（RFC 1321）中描述了每一轮使用哪个消息字；该规范还描述了函数f i、循环计数s i和 32 位常数X i。
现在假设您正在尝试“反转” MD5；你从输出开始，慢慢地使用压缩功能。首先，您必须确定第 64 轮的输出。确实，压缩函数的输出是第 64 轮的输出与保存状态（A' B' C' D'值）之和。你两者都没有，所以你必须选择。您希望您能够找到消息词的值，这将允许您为第 1 轮的输入获得一些与您对A'及其兄弟的任意决定相一致的值。
让我们看看当您向后执行压缩函数时情况如何。您有一轮的输出（一轮后的变量A、B、C和D），并且您想重新计算该轮的输入。您已经知道B、C和D的先前值，但是对于A和M k，您有很多选择：每个 32 位值对于A都是可能的，并且每个都有对应的M k。起初，您对此感到高兴；谁会拒绝这样的自由？随便选一个M k，这只需几个操作就产生了相应的 A （试试吧！）。
但是在你以这种方式倒转 16 轮之后（第 49 到 64 轮，因为你是在向后工作），自由就消失了。您已经“选择”了所有消息词的值。当尝试反转第 48 轮时，您希望在该轮之前重新计算A的值；根据 MD5 规范，消息字M 2在第 48 轮中使用，并且您已经选择了M 2的值（当反转第 63 轮时）。所以A只有一种选择。那你说呢。一个选择就足以继续向后走。所以你继续。
现在，您正处于压缩功能的开始阶段。请记住，最初，您对A' B' C' D'的值进行了任意选择：这允许您计算第 64 轮的输出，并开始向后走。现在你已经获得了第 1 轮的输入，它应该与A' B' C' D'相同......并且它不匹配。这很正常：你随意选择了A' B' C' D'，而且你还随意选择了消息词M k，所以可以预料大部分时间它不会起作用。因此，您尝试通过追溯更改您对A' B' C' D'的初始选择来修复计算，ķ。但是对任何M k的每次修改都意味着在其他地方进行修改，因为每个M k被使用了四次。因此，您需要进行其他修改以取消其他修改，依此类推...
到那时你开始理解反转 MD5 的问题：每次你触摸一个位，它都会触发整个算法的大量修改，你需要通过触摸其他位来抵消，而且交互太多了. 基本上，您同时处理2 128个球，这对于跟踪所有这些球来说太过分了。
如果每个消息块是 2048 位长，分成 64 个字，并且每个消息字在 MD5 中只使用一次，那么您可以轻松地将其反转。你按上面做：任意选择A' B' C' D'，任意选择第 64 到第 5 轮的消息词；对于前四轮，您只需考虑您希望为该轮输入获得的值（与您对A'、B'、C'或D'的任意选择相匹配的值）并计算出相应的消息词。易如反掌。但是 MD5 不是按 2048 位块处理数据，而是按 512 位块处理数据，每个消息字使用四次。
一些额外的曲折
MD5的压缩函数结构实际上是Feistel密码的一种推广。在 Feistel 密码中，数据被分成两半，并且，对于每一轮，我们通过将另一半与从另一半和密钥计算的中间值相加/异或来改变一半；然后我们交换两半。将此方案扩展到四部分拆分，您将获得与 MD5 轮次相同的结构——旋转 90º：MD5 看起来像是使用消息块作为密钥对当前状态的加密（并且额外添加了带有已保存状态的第 64 轮的输出，它使 MD5 与旋转密码不同）。
所以也许我们可以用分组密码构建散列函数？事实上，我们可以：这就是惠而浦的意义所在。建立在旋转块密码之上的散列函数（消息块是密钥）；Whirlpool 的分组密码是“W”，它是 Rijndael 的衍生物，也就是众所周知的AES。但是 W 具有更大的块（512 位而不是 128 位）和重新生成的密钥调度。
当你从一个旋转的分组密码中创建一个哈希函数时，对哈希函数的原像攻击在某种程度上等同于对分组密码的密钥重构攻击；所以有一些希望，如果块密码是安全的，那么散列函数也是安全的。再次，有一些刻薄的细节。此外，对于这样的结构，哈希函数上的冲突就像对分组密码的相关密钥攻击一样；相关密钥攻击通常被认为是非致命的，并且经常被忽略（例如，它们不是 AES 竞争评估标准的一部分，而 Rijndael 在这方面被认为有点不稳定，这就是 W 拥有全新密钥的原因日程）。
一些较新的设计建立在不旋转的分组密码之上，因此哈希函数的安全性可以更直接地从分组密码的安全性中推导出来；参见例如 SHA-3 候选Skein，它定义在名为 Threefish 的分组密码上。
相反，可以尝试用散列函数制作分组密码。参见例如SHACAL，它是 SHA-1“直立”。而且，在提示上，SHACAL 有一些相关的关键弱点，这些弱点与 SHA-1 在碰撞方面的已知弱点非常相似（没有计算实际的碰撞，但我们有一个方法应该比通用碰撞查找算法）。
因此，与我在这篇文章的介绍中所说的相反，我们一直在谈论加密。关于散列函数和对称加密之间的联系还有很多有待发现和研究。
TL;DR：此消息没有 TL;DR。完整阅读，否则就离开。
此处答案的第一步是查看示例，例如来自@Dietrich 的不错的示例，这些示例在一个方向上比逆向运行更难，并且抵制了许多寻求速度突破的尝试。但是这个问题很复杂，所以我会尝试更多地充实它。
很多人似乎掉进了陷阱（呵呵），认为散列函数实际上是某种神奇的——它们确实是绝对的“单向函数”，在数学上根本不能倒退，只是因为它们被称为散列. 在安全论坛中，这不是一种健康的思考方式。在实践中往往是错误的。考虑到函数的基本数学定义是从域到图像的映射，这在理论上总是错误的。
原则上，所有哈希值都可以反转。它可能是混乱和野蛮的（如蛮力），使用今天的硬件可能需要不切实际的长时间，甚至可能长期坚持下去，但从数学上讲，这只是时间问题。正如@mucker 指出的那样，所有信息都可以找到原始密码（或者至少是一个有效的密码）。如果我们忘记了这一点，我们就会忘记聪明的启发式方法来挑选可能的密码的危险，这些密码经常成为新闻。散列是一个工程问题，主要挑战是效率问题 - 如何使在给定散列的情况下找到密码变得昂贵。这种想法的主要结果之一是使密码哈希变慢的重要性
哈希的科学和数学只会慢慢变得更好。真的没有任何证据表明任何哈希真的很难。@Dietrich 的回答是一个很好的方式来说明理想的散列函数是如何可能的。但只要看看真正的专家描述我们如何没有任何最好的加密算法的证据：对称密码和摘要算法的安全声明背后的数学模型是什么？
问题中引用了 LanMan 的事实进一步证明了我们需要避免理想化散列。LanMan 绝不是一个理想的散列函数，很容易被一些分析和一些暴力破解的组合打败。有关可怕哈希函数的另一个流行示例，请参阅MySQL OLD_PASSWORD 密码分析？.
因此，让自己摆脱陷阱——掉入陷阱不一定是单程旅行。认识到哈希是可逆的，并在寻找最佳方法来扭转它们时保持这种可信赖的安全思维活跃。这通常是找到真正难以逆转的最佳方式。我并不是要对那里的最佳实践进行诽谤，例如 bcrypt 或 PBKDF2 或 scrypt。但有证据表明，即使是优秀的程序员也经常犯这些错误。所以要小心你如何使用它们，不要试图发明你自己的。
因为这就是密码散列函数的工作方式，所以它们是单向（从普通到散列）数学函数。专门制定和测试算法以避免这种情况，并避免冲突（2个不同的纯文本生成相同的哈希）。
您可以在 wikipedia 上阅读更多内容，但本文的要点是：
理想的密码散列函数具有四个主要或重要的属性：
- 计算任何给定消息的哈希值很容易（但不一定很快）
- 生成具有给定哈希的消息是不可行的
- 在不更改哈希的情况下修改消息是不可行的
- 找到具有相同哈希的两条不同消息是不可行的
大多数对散列函数的攻击都是基于发现冲突（因此 2 个不同的纯文本将匹配相同的散列）或预先生成数百万个散列并比较它们，直到找到生成它的纯文本。
历史悠久：如果哈希算法是可逆向工程的 或者可以通过这种方式受到攻击，那么它就不是一个好的哈希算法。
对于密码，使用 BCrypt 进行调查，这篇文章有很多关于它的信息。