Python 哈希算法详解：从 MD5 到密码学安全特性

哈希算法基础：保密性与完整性

哈希（Hash）是构建密码学安全性的核心基础，它引入了单向函数和指纹的概念。

• 无论输入内容如何，哈希算法都能生成相同且唯一的输出值。
• 生成的输出值中不包含任何关于原始输入内容的线索或信息。

一、保密性与完整性的区别

简单来说，信息的保密性确保只有授权人员能够读取消息，而信息的完整性则确保只有授权人员能够修改消息。在许多情况下，即使加密后的消息无法被他人读取（保密性），密文仍可能在传输过程中被截取或恶意篡改（完整性）。

信息摘要（Message Digest）或指纹技术正是用于验证信息完整性的关键手段。

一个可靠的信息摘要必须满足以下基本条件：

• 相同的文档始终生成相同的摘要，这使其能够作为文档的身份标识。
• 生成的摘要在统计上表现为随机分布，不包含原始文档的任何可预测信息，从而难以被逆向破解。

信息摘要也被称为指纹，它是一小段代表文档“身份”的数据，类似于人类指纹。虽然任何人都可以通过指纹验证身份，但指纹本身并不包含身体的所有信息。同理，文档的指纹可以快速生成且唯一标识文档，但仅凭指纹几乎不可能还原出原始文档内容。

通过比对两份文档的信息摘要（指纹）是否一致，即可确认内容是否相同以及传输过程中是否被恶意修改。同时，这种机制不会泄露原始文档的具体内容。

MD5 算法原理与局限性

二、MD5 算法概述

MD5 是一种历史悠久的哈希算法，其名称中的 MD 代表 Message Digest（消息摘要）。它能够将任意大小的输入文档转换为一个唯一的 16 字节长度的摘要数据。

注意：鉴于 MD5 历史久远且摘要长度较短，不建议在安全性要求极高的场景中使用该算法。

>>> from hashlib import md5
>>> md5(b'alice').hexdigest()
'6384e2b2184bcbf58eccf10ca7a6563c'
>>> md5(b'bob').hexdigest()
'9f9d51bc70ef21ca5c14f307980a29d8'
>>> md5(b'balice').hexdigest()
'6760742ebf884c998752b4e082b78224'
>>> md5(b'cob').hexdigest()
'386685f06beecb9f35db2e22da429ec9'
>>> md5(b'a').hexdigest()
'0cc175b9c0f1b6a831c399e269772661'
>>> md5(b'aa').hexdigest()
'4124bc0a9335c27f086f24ba207a4912'
>>> md5(b'aa' * 100000).hexdigest()
'561b1994f6baacd6e5eaf4baaa12849f'
>>> md5(b'alice').hexdigest()
'6384e2b2184bcbf58eccf10ca7a6563c'

从输出结果可以看出，即使输入内容非常相似（例如 'bob' 和 'cob'），摘要算法生成的输出也是发散的，彼此之间没有相似性，看起来像是随机生成的结果。然而，对于任意相同的输入，生成的摘要数据始终是确定且唯一的。

哈希函数的基本特性

三、哈希算法的基本规则

通常提到哈希算法时，人们会联想到密码学和安全性场景。但实际上，我们很早就接触过一种完全“非密码学”的哈希场景，例如判断一个数是奇数还是偶数。从本质上看，哈希函数的目的是将巨大（甚至无穷大）数量的输入映射到一个相对较小的数据集中。例如 MD5，无论输入文档多大，最终都会生成一个固定长度（16 字节）的十六进制数字作为指纹。这意味着 MD5 的输入集合实际上大于其输出集合。只要输入文档的集合足够大，就有可能出现重复的指纹信息（碰撞）。

这与判断数字奇偶性的逻辑相通。无论数字多大或多奇特，我们总可以将其“压缩”为奇数或偶数，用 1 bit 的 1 或 0 表示。但仅知道一个未知数字是奇数（或偶数），就无法推断出该数字的确切值。

上述逻辑验证了哈希函数共有的三个基本特性：

• 一致性（Consistency）：相同的输入只会生成相同的输出信息。
• 压缩性（Compression）：可以将体量很大的输入压缩成一个固定大小的输出。
• 有损性（Lossiness）：仅通过检查输出无法反向计算出输入值。

密码学安全哈希的关键属性

然而，对于一个满足密码学安全的哈希函数而言，除了以上三点外，还需要具备以下属性：

• 抗原像攻击（Preimage resistance）
• 抗第二原像攻击（Second-preimage resistance）
• 抗碰撞攻击（Collision resistance）

抗原像攻击（Preimage Resistance）

抗原像攻击（Preimage Resistance）详解

哈希函数的“原像”（preimage）是指能够生成同一个特定指纹的所有输入的集合。即对于某个哈希函数 H 与摘要 k，所有满足 H(x) = k 的输入值 x 共同组成了 H 与 k 的原像。

抗原像攻击的意义在于，仅知晓某个摘要的前提下，通过有限的计算无法获取其原像中的任何一个元素。也就是说，只通过结果无法知晓输入。由于摘要中不包含原始文档的任何信息（有损性），无法通过逆向运算由摘要反推出原始输入。攻击者只能随机尝试任意输入，以期碰巧得到同样的摘要信息（即暴力破解）。

因此，前文提到的奇偶函数不能作为安全的哈希函数使用。假设使用奇偶作为哈希函数（奇数输出 1，偶数输出 0），则对于摘要 1，总可以很轻易地在原像（此处是全体奇数）中找到任意多个摘要同为 1 的元素。这意味着原始输入可以轻易被修改而不影响指纹数据，则该指纹作为信息完整性的验证条件就失去了意义。

但是对于较安全的哈希算法如 MD5，由 MD5(x) = ca8a0fb205782051bd49f02eae17c9ee 就无法在有限的计算内找到确定的 x 的值。MD5 生成 16 字节（16 * 8 = 128bit）长度的摘要，其中可以包含 2^128 种不同的数字组合。因此使用暴力破解的话，最多需要尝试 2^128 = 340282366920938463463374607431768211456 次！假设每秒钟可以尝试一百万条输入，仍需要 10^26 年完成所有验证操作！

抗第二原像与抗碰撞攻击

抗第二原像攻击与抗碰撞攻击

抗第二原像攻击（Second-Preimage Resistance）是指，即便知晓某个原始文档以及由该文档生成的摘要数据，仍很难计算出可以生成同样摘要的另一个不同的文档。即在已知 MD5(alice) = 384e2b2184bcbf58eccf10ca7a6563 的情况下，仍无法找出除 'alice' 以外的另一个输入生成同样的摘要。为了寻求可以替换掉 'alice' 的另一个值，同时不影响摘要认证，达到混淆的目的，最终仍需使用暴力破解的方式。

抗碰撞攻击（Collision Resistance）是指很难找出任意两个生成相同摘要（相同而非特定）的输入值。可以参考“生日问题”，即在一个班级中，存在两个生日为同一天的学生的概率远比存在一个生日为特定日期的学生的概率大得多。

抗碰撞攻击的意义在于，无法故意找出两套符合同一指纹的输入以达到混淆的目的。比如 MD5 算法：

>>> from hashlib import md5
>>> md5('bob').hexdigest()
'9f9d51bc70ef21ca5c14f307980a29d8'
>>> md5('cob').hexdigest()
'386685f06beecb9f35db2e22da429ec9'

对于很相似的输入 'bob' 和 'cob'，其指纹信息的差异却非常大，没有任何可供预测的规律。这得益于一种称为雪崩效应（avalanche property）的特性：输入的微小变化总可以在输出中产生巨大的无法预测的差异。

由前文提到的生日问题可知，找出两个生成相同指纹的元素远比找出某个可以生成特定指纹的元素要容易得多。以 MD5 算法的暴力破解为例，后者往往需要做 2^128 次尝试，而前者只需要 2^64 次尝试。现实中 MD5 的抗碰撞能力远非想象中那么优异，甚至存在一种非暴力破解的方式能够在一小时以内攻破 MD5 的抗碰撞能力。所以尽量不要使用 MD5 这个已经不再维护超过 10 年、安全漏洞存在 20 年的古老算法。

参考资料

Practical Cryptography in Python: Learning Correct Cryptography by Example

以上就是 Python 密码学示例——理解哈希（Hash）算法的详细内容，更多关于 Python 哈希（Hash）算法的资料请关注本站其它相关文章！