简单密码：写给程序员的密码学入门（二：从hash到Challenge-Response）

书接上文，那么Hash是什么？有什么用? 很多人都讲了hash算法。我这里就讲的尽可能简单容易理解，不用什么原像抗性之类的词。

但是你相信我，hash是非常，非常有用的工具。

看完你有可能会发现一些hash意想不到的应用。

一：所以什么是hash？

呃，今天说的hash不同于你学数据结构和算法的那个hash。这里指的是密码学上的，有时称为哈希算法，有时称为摘要算法。计算出来的结果也根据场合也有不同的名称。

如果你是做web后端的同学，你大概经常看到老师傅在登录业务逻辑里用一个md5()，md5一种常见的hash算法，而后在数据库里密码字段中就出现了那些奇怪的东西，就是md5哈希算法计算出的散列值。
比如admin经过md5计算就是21232f297a57a5a743894a0e4a801fc3
啊，比如：

但是如果我们输入是admi 去掉最后一个n，就完全不一样了。

如果你的确没听说过hash是什么东西，非常推荐你去下面网站玩玩，看看什么是md5 hash。

MD5在线加密- 站长工具
 cmd5 （用完这个网站你还敢继续用md5吗？）

所以hash是什么？

简单的说它可以把任意长度的数据都计算出一个长度固定的值。而任何微小的改变都会造成完全不同的结果。

不理解的话再去玩玩上面发的网站。

这个算出来的值的特点：

不管你输入是多长多短，结果是定长的。比如md5结果一定是128位(32个十六进制字符)。
你不能通过计算出来的hash再推算回原来的消息。这个过程是单向的。
相同的输入，结果必定相同。
输入若有改动，哪怕只是一bit，结果几乎一定不同。

二：它可以用来做什么？

看起来，hash似乎就是给每个输入数据找一个难以伪造的字符串。而且这个字符串很难逆推出原消息。

数据库保存密码

在上文中我们提到了数据库存密码的hash会更安全，怎么个安全法？根据上面的特性，你没有存真正的密码，但又可以利用密码的hash来验证用户密码正确性。就算数据库被黑客下载，黑客也不能(或者说有难度)得到用户真正的密码。但是别用不加盐的md5了。下文会说。

消息/文件校验

另一个应用是可以用来做文件校验。你可以在下载某些软件，或者是操作系统镜像时看到有一个叫做checksum的东西，里面就是那个文件的hash。如果文件在传输过程被损坏或者被恶意替换，我们可以通过计算文件hash和官方提供的hash对比，检查完整性。如果文件发生了改变那么校验和极大概率会不同。说明这个文件和官方的不一样。

如果反着用这种东西呢？那就是比较古早的杀毒软件。比较老的杀毒软件的原理就是计算文件的hash，这个hash就是特征，接下来就是拿hash和病毒的hash对比，如果一样就是病毒了。当然这也有可能误杀就是。

同样的，你可能还听说过HMAC。你可以简单理解为让消息和密码放在一起hash，得到的一个东西。有这东西，我们能检查传输的消息有没有人篡改过。这个经常在各种webAPI里见到。

能不能用同名wifi钓鱼骗密码：Challenge-Response Protocol

这个问题很有趣，见过很多遍了。
这种场景下和hash有关系？有。
但是我们直接用hash的话行吗？
思考一下
你是黑客
3,2,1

不行，可以截取这个hash，直接发过去不就行了？密码完全都可以不知道。
这个叫做重放攻击。
啊，对，重放就像那个阿里巴巴和四十大盗，你喊芝麻开门，门就开了。你不需要知道这背后有什么原理。但是随机是重放的克星。

我们讲一个这个协议的极端简化版本

AP（你就当无线路由器）给你发一个随机数
你收到随机数，把密码加随机数放一起计算hash，像这样hash(密码+随机数)
发给AP验证。AP知道密码和随机数。

这样你还能骗到密码吗？骗不到了吧。随机数是重放的克星，你也不能重放攻击了。
这个就叫Challenge-Response Protocol。AP给你发的就是Challenge，然后你要响应(response)。

思考题：这个简化版本有漏洞吗？

这已经很接近零知识证明了，说到这个…

比特币

你猜比特币挖矿是在干啥？
就是在算sha-256。
区块就是一个公共的账本，但是这个账本怎么被承认有效呢？那就计算hash+一串未知值，加上这个未知值后的hash开头前几个bit必须是0. 多少个0取决于难度。这串未知值怎么来的？那只能暴力穷举。
然后我们认可的账本（区块）必须是那个消耗算力最多的。如果有人想伪造账本，那么他必须算力巨大，超过很多人才行。

重点！！！注意安全！！！

用加盐(salt)对抗破解：你可能注意到我之前给的比如cmd5的网站提供破解服务，因为cmd5提前计算了大量消息的md5，所以你只需要输入某弱密码的md5值，就能查询到它对应的密码。怎么应对呢？在计算用户密码的hash前可以给他密码加一个字符串再计算hash。这个叫做加盐(salt)，强行让密码变得复杂。这个就不好查到了。当然，md5已经过时，不要再用了。
多次迭代对抗暴力破解：hash算太快也不是好事。这样暴力破解太快了。现在一台普通的电脑计算md5的速度可能是10亿每秒级别的。为了对抗暴力，我们可以套娃。md5(md5(md5(…)))这样迭代个1000次来储存用户密码，能让别人暴力破解增加1000倍的工作量。当然咯，干脆别用md5了. 看下一条
像php中对于用户密码完全可以用bcrypt而不是md5，它自带salt功能。bcrypt自己就有多次迭代增加算力消耗拖延计算时间对抗暴力破解的能力。
不要再使用md5和SHA-1: 你可能注意到为什么我用了“几乎”一定不同和“大概率”不同。因为输入的信息长度不限，有无穷的可能。但是输出的长度是固定的，意味着输出的可能是有限的。所以必定会存在hash值相同的输入。但是非常难以遇到。比如对于sha-512进行穷举尝试碰撞，目前看需要百亿年。但是md5用现代的计算能力，可以比较省力地构造出相同的值。

严肃的说法

当然这是比较严谨且学术（枯燥）的说法

pre-image resistance: 有$h(x)$ 但是无法推算$x$
collision Resistance: 构造不出$x_1, x_2$使得$h(x_1)=h(h_2)$
second preimage resistance: 已知$x_1, h(x_1)$但是无法构造$x_2$使得$h(x_1)=h(h_2)$

而且md5, sha-1,256,512 这些都有被扩展攻击的问题。你不知道x，只知道h(x)但是你可以伪造任意的h(x+k)。使用时你可能需要考虑到这个问题。

在下一章节我们会谈论对称加密的古典加密方案