python 密码学示例——理解哈希（Hash）算法

Hash 是密码学安全性的基石，它引入了单向函数（one-way function）和指纹（fingerprint）的概念。即：

• 对于任意输入，都可以产生相同的、唯一的输出值
• 输出值中不包含输入值的任何线索
  

一、保密性（confidentiality）与完整性（integrity）

简单来说，信息的保密性确保除授权人员以外的任何人都无法读取该消息，信息的完整性则确保除授权人员以外的任何人都无法修改该消息。
很多时候一段加密的消息无法被他人读取和理解（保密性），并不意味着该密文不会在传播过程中被截取和恶意修改（完整性）。

信息摘要（message digest）或指纹（fingerprint）技术即用于验证信息的完整性。

信息摘要需满足的基本条件为：

• 相同的文档永远会生成相同的摘要（能够作为身份线索）
• 生成的摘要“感觉”是随机的，即摘要中不包含原始文档的任何信息（无法被破解）
  

信息摘要也被称作指纹，即可以代表某份文档“身份”的一小段数据，类似于人类的指纹。
每个人都可以通过指纹验证其身份，但该指纹并不包含其身体的所有信息。文档的指纹也是如此，可以很方便快速的通过文档内容计算得出一小段唯一的指纹数据作为其SFZ明，但是只有指纹数据就几乎不可能得出原始文档的内容。

对于两份文档，只需要比对其信息摘要（指纹）是否一致，就可以确保其内容是否相同，在传播过程中是否被人恶意修改。同时该指纹信息也不会造成原始文档本内容的泄露。

二、MD5

MD5 是一种比较古老的哈希算法，其名字中的 MD 即代表 message digest。它可以从任意大小的文档计算出一个唯一的 16 字节长度的摘要数据。

PS：鉴于 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 表示就可以。但是只说明某个未知数字是奇数（或偶数），我们就无法猜出该数字的准确值。

上面的逻辑验证了哈希函数共有的 3 个特性：

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

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

• Preimage resistance
• Second-preimage resistance
• Collision resistance
  

Preimage Resistance

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

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

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

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

Second-Preimage Resistance 与 Collision Resistance

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

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

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 的 collision resistance 远非想象中那么优异，甚至存在一种非暴力破解的方式 能够在一小时以内攻破 MD5 的 collision resistance。
所以尽量不要使用 MD5 这个已经不再维护超过 10 年、安全漏洞存在 20 年的古老算法。

参考资料

Practical Cryptography in Python: Learning Correct Cryptography by Example