密码学之哈希算法杂谈

很久没有再继续写密码学的文章了，我对密码学的兴趣源于两个，一是和 GFW 多年的斗智斗勇，二是满足我的好奇心和隐私需求。再次重申我不是密码学科的专业人士，如有错误或者补充观点，请务必联系我！之前密码学系列文章的逻辑思路不容易令人理解，这次换成提问的方式讲解哈希相关内容：

问题1：加密算法和哈希算法是否有区别，哈希算法有哪些？

问题2：什么是碰撞？

问题3：我们常说的加盐是什么？

问题4：基于哈希的单向性和雪崩性，那么入侵系统之后提取哈希值有什么意义？

问题5：系统是如何判断用户的密码是正确的? 哈希过程在浏览器还是服务器完成？

问题6：攻击者获取了数据库权限，直接替代哈希值是否能实现任意账号登录？

加密算法和哈希算法是否有区别，哈希算法有哪些？

为了保护一个人不易被辨识出是谁，那么可以通过戴墨镜、戴口罩、化妆等方式掩盖自己的特征。加密( Encryption ) 是将明文信息改变为难以读取的密文内容，使之不可读。只有知道解密方法的对象，经由解密过程后才能将密文还原为正常可读的内容。常说的 DES 、 AES 、RSA、SM2 等加密算法都是 “易容术” 的一种。

为了辨识一个人的身份，我们提取这个人的指纹，再经过特定的方式比对就可以知道 “他/她” 是谁。散列函数( Hash function )又称散列算法、哈希函数，是一种从任何一种数据中创建小的数字“指纹”的方法。散列函数把消息或数据压缩成摘要，使得数据量变小，将数据的格式固定下来。

MD4算法一般使用在32位的计算机处理器模块内，通过软件系统来实现其算法功能。然而，由于MD4算法本身存在的安全性漏洞，目前它已经被更为先进安全的算法所淘汰。但MD4算法为之后的MD5算法、SHA-1算法、ripemd 算法等提供了很好的理论基础。MD5算法是MD4算法的升级版，它在MD4算法的基础上增加了 safety-belts 功能，使整个算法变得更加可靠。MD5算法在MD4算法的基础上加入了第四轮的计算模式，每一个步骤都是一一对应的固定值，改进了MD4算法中在第二轮、第三轮计算中的漏洞，完善了访问输入分组的次序，从而减小其对称性和相同性。通过这些变化，使得MD5与MD4相比变得复杂很多，整个运转速度也要比MD4慢一些，但是从整体安全性、抗冲突和抗分析方面有了很大的提高。

SHA-1算法也叫做安全哈希算法，主要应用于digital signature standard dss里面定义的数字签名算法。SHA-1算法长度一般为160bit 的message digest，SHA-1算法在接收消息摘要的过程中，可以利用message digest 来检查数据的完整情况。它不会从message digest 中还原相关的内容，此外两个不同的message 不会产生相同的message digest，因此SHA-1算法具有很强的brute-force性能。SHA-1算法的计算方式是基于MD4的算法原理，它的填补和分组模式与MD5是一样的，但是在算法中，SHA-1的非线性函数、循环左移运算和加法常数与MD5算法的运算方式有一定的差异，SHA-1的安全性和稳定性比MD5算法更加可靠，且运算速度也有了一定的提高。

SM3算法适用于商用密码应用中的数字签名和验证，是在SHA-256基础上改进实现的一种算法。SM3算法采用Merkle-Damgard 结构，消息分组长度为 512 位，摘要值长度为 256 位。用上图来讲解SM3算法运算流程：首先判断是否要填充 ( Padding )，然后将数据按块切分，每块 ( Block ) 占 512 比特。将初始向量( Initial Vector ) 与第一个数据块 B₁ 丢进压缩函数( Compression function )执行运算，得出结果 V₁。将V₁与第二个数据块 B₂ 丢进压缩函数执行运算，得出结果V₂，直至运算到最后一个数据块B_n 得出结果V_n，结果V_n 就是我们固定长度的哈希值。哈希值也叫做预映射( pre-image )或散列值。

名称	类型	常见用途
SM1	对称加密算法	IC卡、智能钥匙等硬件加密	密钥长度128比特，分组长度128比特
SM2	基于椭圆曲线数字签名算法、交换协议和公钥加密	数字签名、协商密钥、非对称加密	密钥长度128比特，分组长度128比特
SM3	杂凑演算法	消息认证码、随机数、数字签名	输出固定256比特的结果
SM4	对称加密算法	无线局域网， WAPI标准	密钥长度128比特，分组长度128比特， 32轮非线性迭代结构，由国家密码管理局负责计划
SM7	分组密码算法	非接触式IC卡	密钥长度128比特，分组长度128比特
SM9	双线性对的标识密码算法	无需申请的数字证书的身份认证	密钥长度256比特
ZUC	流加密算法	加密算法 128-EEA3 和完整性算法128-EIA3 可用于移动通信，4G网络	128比特的初始向量和128比特的密钥长度
DES	对称加密算法	加密数据	密钥长度48(56减8)比特，分组长度64比特，执行16轮Feistel Cipher迭代，由原NAS负责计划
3DES	对称加密算法	加密数据	密钥长度112比特，分组长度64比特，执行16轮Feistel Cipher迭代，由NAS负责计划
AES	对称加密算法	加密数据	密钥长度可选128/192/256比特，分组长度128比特，取决于密钥长度执行10至14轮次迭代，由NIST负责计划
RSA	基于特殊的可逆模幂运算的公钥加密算法	非对称加密	密钥长度可选1024比特、2048比特、3072比特或4096比特。
MD5	杂凑演算法	完整性检验	输出固定128比特的结果
SHA1	杂凑演算法	完整性检验	输出固定160比特的结果
SHA2	杂凑演算法	完整性检验	输出可选224比特、256比特、384比特或512比特的结果

SM2 算法是国家密码管理局编制的一种商用密码非对称算法，基于 ECC 算法，安全性与NIST Prime256 相当。ECC和RSA对比的情况下，具有抗攻击性强、CPU 占用少、内容使用少、网络消耗低和加密速度快的特点，3072 位长度的RSA 密钥加密效果等同于 256 位长度的 ECC 密钥加密。 2010年，国密局公开 SM2 算法。
SM3 算法是国家密码管理局编制的一种商用密码摘要算法，安全性与效率与 SHA256 相当。2010年，国密局公开SM3 算法。
SM4 分组密码算法，原名SMS4，国家密码管理局于2012年3月21日发布。
ZUC 算法，国家密码管理局于2012年3月21日发布。
SM9是中华人民共和国政府采用的一种标识密码( ID-based_cryptography )标准，由国家密码管理局于2016年3月28日发布。SM9的加密强度等同于3072位密钥的 RSA 加密算法。
RSA 规定待加密的字节数不能超过密钥的长度值除以 8 再减去 11，密文长度等于密钥的长度值除以 8 ，对超长问题可使用拆分数据或对称加密处理。

RSA密钥长度	SM2密钥长度	破解时间
521比特	106比特	104年（已破解）
768比特	132比特	108年（已破解）
1024比特	160比特	1011年
2048比特	210比特	1020年

算法名称	签名速度	验签速度
1024 RSA	2792次/秒	51224次/秒
2048 RSA	455次/秒	15122次/秒
256 SM2	4095次/秒	871次/秒

什么是碰撞？

碰撞指的是用不同的原始数据运算后得出相同的值，数学语言表示为：有一个函数 f(x) ，找到了x₁和x₂，并且x₁ ≠ x₂ ，如果满足 f(x₁) = f(x₂)，则认为发生一次碰撞( Collision ) ，函数 f(x) 不局限于是哈希函数。碰撞攻击和算法破解是两种不同的概念，当攻击者需要花费巨大的成本 ( 比如时间和算力 ) 破译我们的密码，其中产生的收益远小于实际付出的成本，那么我们就认为我们的密码是安全的，下面提供两个不同 PDF 文件，但它们的 SHA-1 哈希值却是一样的，因此 SHA-1 会逐渐被其他安全算法替换。

点击下载 PDF1：

点击下载 PDF2：

[[https://i.ooxx.ooo/2018/07/26/1e102db9bdfa7f8ab7136313bba257e6.jpg])

同样不安全的还有 MD5 算法，目前坊间流传字母和数字组合的八位数密码 ( 合计有 (26*2+10)⁸ 种组合方式 ) 生成的 MD5 值已经可以通过彩虹表的方式秒破。彩虹表是一种使用空间换取时间的技术，跟查表破解很相似，用下面介绍的加盐处理方式可以很好的抵御彩虹表攻击。

RainbowCrack is a general propose implementation of Philippe Oechslin’s faster time-memory trade-off technique. It crack hashes with rainbow tables.

1999年1月，distributed.net与电子前哨基金会合作，在22小时15分钟内即公开破解了一个DES密钥。
2004年，王小云在美国加州圣巴巴拉的 Crypto’2004 会议上证明MD5算法可以产生碰撞。
2008年，荷兰埃因霍芬技术大学科学家成功把2个可执行文件进行了MD5碰撞，使得这两个运行结果不同的程序被计算出同一个MD5。
2008年12月一组科研人员通过 MD5 碰撞成功生成了伪造的SSL证书，这使得在https协议中服务器可以伪造一些根CA的签名。
2010年成功分解了RSA-768私钥。
2017年2月24日，谷歌通过9兆亿次运算攻破 SHA-1 算法。

我们常说的加盐是什么？

讲加盐之前，先解释清楚认证 (Authenticate) 和授权 (Authorization) 的区别，认证是系统比对记录后，识别出你所拥有身份的过程，授权是系统查看记录，根据记录授予你权限的过程。两者对应不用的技术功能，比如指纹识别、single sign on、Two-Factor-Authentication、HMAC、JSON Web Token 属于认证管理。策略组、用户组、权限组等属于授权管理。因为哈希不可逆的特点，数据库存储用户的密码都是以哈希值的形式存在，用户请求登录时，我们只是比对用户密码加密后的哈希值和存储记录的哈希值是否一致，相同则认为该用户是他所声称的用户身份。理论上用户的密码只能由用户自己知道，但是即便如此，还会出现这样的情况：

为了方便记忆，用户可能会在不同的网站上使用相同的密码，黑客猥琐一笑，开始撞库。
为了方便输入，用户可能会设置一个非常简单的密码，比如123456，黑客猥琐一笑，开始导入字典。
为了方便运维，开发者可能会直接将用户密码直接写入数据库，黑客猥琐一笑，开始脱裤。
为了方便管理，开发者可能会把敏感信息暴露在不安全的地方，如审计日志、源码托管等，黑客猥琐一笑，开始爬虫。

当我看到某单位的系统管理员把所有的密码都记录在Excel和便利贴上的时候，我差点忍不住骂人。

所以数据库的加密存储很有必要，用正确且合适的加密算法很有必要，相关人员的意识培也很有必要。常见的数据库比如 mysql 就提供非常方便的 MD5 加密存储功能，但是上文已经讲到了 MD5 的不安全性问题，所以开发者们想到了加盐的办法。关于加盐如何在实际在应用的使用，知乎答主 CoderZh 和乌云知识库的第1066篇文章已经写的很好了，我就不重复造轮子了。

md5(md5(password)+Salt)

总结有那么几种耍流氓的方式：

所有使用性能借口做明文存储密码的运维人员都是耍流氓，包括单纯的 md5(text)=password
所有使用固定字符串作为盐值的运维人员都是耍流氓，无论你的字符串多复杂多长。
所有使用过短长度的随机盐作为密码加密存储的运维人员都是耍流氓。
所有使用非权威算法做密码加密存储的运维人员都是耍流氓。

基于哈希的单向性和雪崩性，那么入侵系统之后提取哈希值有什么意义？

意义在于需要破解哈希，使得哈希值变成明文密码进而持续内网渗透，漏洞编号MS08-067则利用哈希值直接登录。先要介绍 windwos 系统下 NTLM 和 Net-NTLM。我在刚刚接触这方面的内容的时候，也常常搞混 NTLM，NTLMv1/v2，Net-NTLMv1/v2 这几个概念，下面推荐几篇不错的文章：

利用NTLM中继攻击

MS08-067漏洞原理剖析

MS08-068漏洞利用工具

Windows下的密码hash——NTLM hash和Net-NTLM hash介绍

Windows下的密码hash——Net-NTLMv1介绍

Practical guide to NTLM Relaying in 2017 (A.K.A getting a foothold in under 5 minutes)

Windows系统下的 Hash 密码格式为：用户名称:RID:NTLM-Hash值:Net-Hash值，例如：

Administrator:500:C8825DB10F2590EAAAD3B435B51404EE:683020925C5D8569C23AA724774CE6CC:::表示

用户名称为：Administrator

RID为：500

LM-Hash值为：C8825DB10F2590EAAAD3B435B51404EE

NT-Hash值为：683020925C5D8569C23AA724774CE6CC

NTLM的 Hash 存放在 windows 的安全账户管理 (SAM) 数据库以及域控的NTDS.dit 数据库中，且自 Windows Vista 和 Windows Server 2008 开始，Windows 取消 NTLM hash 使用。Net-NTLM Hash 是指网络环境下NTLM认证中的hash 。这样说明了NTLM是可以进行哈希传递攻击，而Net-NTLM是无法利用进行哈希传递攻击的。除此以外，还可以利用让受害者访问不存在的主机的共享进行 LLMNR Poison 攻击，这样可以获得受害者主机的 Hash ，拿到 Hash 就可以进行暴力破解了，如果是弱口令的话，就可以爆破出密码。同样也可以利用让受害者访问不存在的 HTTP 服务器进行 401 认证拿到客户端的 Hash。

系统是如何判断用户的密码是正确的? 哈希过程在浏览器还是服务器完成？

Windows系统中有一种是基于Kerberos的认证，关于Kerberos认证我再单独写一篇。另一种是基于 NTLM 挑战模式的身份认证，后者就是以用户密码哈希值作为密钥，这一把密码用户通过哈希运算得出，服务器通过查找记录得出，因此可以理解成是是对称加密的模式，流程如下：

客户端首先在本地加密当前用户的密码成为密码散列
客户端向服务器发送自己的帐号，这个帐号是没有经过加密的，明文直接传输
服务器产生一个16位的随机数字发送给客户端，作为一个 challenge（挑战）
客户端再用加密后的密码散列来加密这个 challenge ，然后把这个返回给服务器。作为 response（响应）
服务器把用户名、给客户端的challenge 、客户端返回的 response 这三个东西，发送域控制器
域控制器用这个用户名在 SAM 密码管理库中找到这个用户的密码散列，然后使用这个密码散列来加密 challenge。
域控制器比较两次加密的 challenge ，如果一样，那么认证成功。

哈希过程应该浏览器和服务器端都运行一次。

浏览器端必然不能以明文的形式传输密码到服务器端，因此我们可以采用 javascript 在浏览器内实现对用户密码的哈希运算，再将结果发送到服务器端，服务器对接受的哈希值执行比对就可以判断密码是否正确。但是这样做的问题在于，如果传输通道上存在中间人，那么中间人拦截了用户密码的哈希值之后，直接重放即可登录用户账号，甚至不需要解密，所以仅仅在浏览器执行一次哈希是不安全的，我们还需要在服务器端执行第二次哈希后判断用户密码是否正确。在浏览器端做加密需要注意下面几点：