最近听到一个来公司面试的码农说他使用Base64加密数据（Base64是一种编码格式，在编码解码计算过程中不会丢失信息量。通俗点说就相当于把“你好”加密成了“hello”），这跟明文没什么区别，如果一个hacker有本事截获你的数据，你不可能指望他不会解码Base64。这篇文章希望能分享一些关于加密的常识。
一.散列函数(Hash function)
1.常见误区
关于加密算法，最常见的一个误区在于认为MD5,SHA1,SHA256就是加密算法，其实它们只是用来实现加密算法的一部分，更准确的说，它们只是散列函数，就像java中随处可见的hashCode方法一样，它们的共同点在于都要尽可能避免冲突（两个不同的输入却有相同的输出），而区别在于java中的hashCode方法用于提高散列表的性能，因此主要关注于计算速度而不是安全。
第二个常见误区在于，大家都觉得MD5,SHA1之所以安全，是因为它们计算过程不可逆，举个例子:1
MD5("hello") = 5D41402ABC4B2A76B9719D911017C592
对MD5散列函数输入字符串"hello"，总是可以得到5D41402ABC4B2A76B9719D911017C592，但现在没有以后也不可能有任何方法将5D41402ABC4B2A76B9719D911017C592解密为"hello"（目前所有所谓的解密都是基于猜测）。乍一看这很神奇，在解释它之前，先来看下维基百科上对散列函数的定义：
散列函数是一种输入任意大小的数据，返回固定大小的值的函数
继续以MD5为例，对它输入任意大小的数据，它的返回值都是128位(16字节)。假如这个过程可逆，那么无损压缩就不再有极限，也就意味着给你一张软盘，你就能存储全世界！换句话说，按照上面的定义，根本不存在可逆的散列函数。看到这里你可能依然很困惑，对于任意大小的数据散列不可逆也许比较好理解，但是"hello"明明只有5个字符，为什么也不可逆呢？专业一点解释就是，在计算过程中丢掉一部分信息量即可（对于信息的量化，可以参考我这篇文章香农信息论与回答老鼠喝药问题的正确姿势），草根一点的解释是，你只要让你的函数对于不同的输入，可以得到相同的输出即可。比如f(x)=x^2就是一个不可逆的函数，因为已知f(x)=1，没办法知道x到底是正1还是负1。
2.散列冲突(Hash collision)
对于任意输入数据，经过散列函数计算后得到的散列值，又称为数据指纹（fingerprint）或摘要(digest)，它就像人类的指纹一样，你不可能通过一个人的指纹而了解这个人的全部信息，但是你总是可以快速的取到一个人的指纹。并且很难重复，如果两个不同的输入数据有着同样的散列值，则称为散列冲突。正常情况下假设一个结果分布完全均匀的散列函数输出128位的散列值，那么发生冲突的概率大概在$1/2^{128}$这个数量级，这几乎等同于不可能。但人们可以根据散列函数的实现过程，设计算法来查找冲突值，也就是常说的碰撞攻击(collision attack)。加密用散列函数最大的设计难点，就在于要让别人即使知道了该函数的所有实现细节，也无法找到高效的碰撞攻击算法。
3.过时的散列函数(Deprecated hash function)
2004年山东大学的王小云教授宣布攻破MD4,MD5(Collisions for Hash Functions)，2017年（也就是最近）荷兰密码学研究小组与Google宣布攻破SHA-1(Announcing the first SHA1 collision，shattered)，下图解释了对这些函数查找散列冲突所需的计算量：
可以看到使用google最近研究的算法破解SHA-1需要110块GPU一年的计算量，虽然这个数字看起来非常大，不过依然比暴力算法快了十万倍，因此Google已将SHA-1算法标记为过时(deprecated)的（顺便提一句，linus(linux,git的开发者)最近也受到这条新闻的压力，发文宣布更新git中用到的SHA-1算法）。当然上图还有一点值得注意，前文提到的MD5算法，对它进行碰撞攻击只需要消耗一台智能手机30秒的计算量。
二.如何攻击加密算法
1.暴力算法(Brute force attacks)
已知密码的散列值（数据指纹），和它的加密算法，如何破解该密码?最简单的办法就是穷举该密码所有可能的字符组合，对每个结果调用加密算法，然后与已知的散列值比对。这种办法需要消耗巨大的计算量，但它的好处是总会找到该密码的散列冲突值。举例来说，假设某地警察局获取了罪犯留在犯罪现场的指纹，不可能仅根据该指纹就解析出罪犯的所有信息。于是警察想了一个办法，让当地所有人到警察局一一采集指纹进行比对。这就是暴力算法。
2.字典攻击(Dictionary attacks)
字典攻击指的是先使用一个文件，记录常用来作为密码的单词，这些单词可以从已经攻破的生产环境数据库提取，或者使用一些机器学习算法生成。然后使用这些词的散列值与已知密码的散列值进行比对来破解密码。继续用上面的例子，字典攻击就类似于警察局先在所有人中挑出一部分有犯罪记录的人，只采集这些人的指纹来查找罪犯。没有任何方法可以防御暴力攻击与字典攻击，换句话说如果一个加密算法是安全的，那么它只能被暴力算法和字典攻击来破解。
3.查找表(Lookup Tables)
1 | Searching: 5f4dcc3b5aa765d61d8327deb882cf99: FOUND: password5 |
查找表是一种非常有效的破解常用散列函数的方法，它的思路就是事先计算好常见密码的散列值并存在数据库中（牺牲空间复杂度来降低时间复杂度）。好的查找表实现即便预先存储了几十亿对散列值，依然能达到每秒查找上百个散列值的效率。查找表相当于警察将有犯罪记录的人的指纹保存在数据库中，之后拿到犯罪现场的指纹，直接先从数据库中搜索比对。目前很多在线提供密码破解的网站都是基于查找表实现的。
4.反向查找表(Reverse Lookup Tables)
1 | Searching for hash(apple) in users' hash list... : Matches [alice3, 0bob0, charles8] |
顾名思义，该方法根据要破解的用户表来建立查找表，比如说我现在拿到了一张用户表，其中每个用户的密码都是散列值。我可以先遍历这张表，将其存到一个HashMap结构中，使用密码散列值作为key，使用用户名数组作为value。之后我可以随便猜一些常用密码比如123456，在HashMap中查找键值Hash(123456)就能得到所有密码是123456的用户名。
5.彩虹表(Rainbow Tables)
假设有一个散列函数H，和一个有限的密码集合P，目标是构建一张表，使得对于任意散列值h，可以找到P中对应的元素p满足H(p)=h，或者可以判定该p在P集合中不存在。最简单的实现是计算P中所有元素的散列值并存储下来。这样就能得到一个查找表，这种方法的问题在于假如P集合非常大，则需要耗费巨大的存储空间。
另一种思路是引入一个归约函数R(reduction function)，这个归约函数输入一个散列值h，返回一个字符串（并不要求H(p)=h），通过交替应用散列函数H与归约函数R，可以形成一个由密码与散列值组成的散列链。举个栗子，如果P是所有小写字母与数字的集合，散列值为32位，那么一个散列链大概长这样：1
aaaaaa -> 281DAF40 -> shfnyd -> 920ECF10 -> kiebgt
我们可以选定P中的一个集合，计算多条这样的散列链，并且约定每条散列链的长度k。之后只保存散列链的起点与终点，如上例中的aaaaaa与kiebgt。现在假设我们要查找一个散列值h对应的p，可以先对h调用归约函数R，之后同样是交替调用H与R，直到中途得到一个值与我们存储的一个终点相匹配。再利用该终点与对应的起点重新生成散列链，该链中就很有可能包含散列值h，于是可以立即得到h散列前的值p。
举例来说，假设我们要查找散列值920ECF10对应的密码p，先对它调用归约函数得到kiebgt，之后发现该结果是已保存散列链的终点。于是利用该终点与对应的起点aaaaaa重新计算得到aaaaaa -> 281DAF40 -> shfnyd -> 920ECF10 -> kiebgt。于是得到了920ECF10散列前的值shfnyd。
上面演示的是散列链在理想情况下的工作方式，实际应用中还会碰到很多问题。其中有一个严重的缺陷在于如果两条链中的任何两个点碰撞（有同样的值），那它们后续的所有点都将重合，这将浪费很大的计算量。彩虹表就是用来解决该问题的，它采用一系列归约函数$R_1,R_2...R_k$来代替上面的归约函数R。最终实现如果两个散列链发生碰撞，那它们的终点一定相同。这样就可以依据终点来删除重复的散列链，从而大幅降低了碰撞的次数。
简而言之，暴力算法需要计算每一个可能的猜测，意味着消耗大量的时间。查找表需要保存每一个可能的猜测，意味着消耗大量的存储。彩虹表是处于它们之间的一个折中的解决方案。
三.关于加盐(salt)
1 | hash("hello") = 2cf24dba5fb0a30e26e83b2ac5b9e29e1b161e5c1fa7425e73043362938b9824 |
由于散列函数对同样的密码总是会得到同样的散列值，因此查找表与彩虹表才能够起效。如果每次在密码散列之前，对该密码添加一个随机字符串。就可以有效的防止这种攻击，而这个随机字符串就称为盐值(salt)。如上面的例子，在对hello进行散列之前添加一个随机的盐值，就可以保证每次加密hello都能得到不同的结果。但这样一来每次生成密码散列值后，还需要保存对应的盐值，否则之后当用户输入密码登陆时，就没办法验证该密码的正确性了。下面列一些关于盐值的常识：
- 盐值没必要保密
由于攻击者事先不知道盐值，就没办法事先计算查找表与彩虹表，又因为相同密码每次得到的散列值都不一样，因此反向查找表也没办法起效。这就是盐值存在的目的。使用任意足够长的随机字符串都可以达到该目的，而试图将该字符串保密则完全是多此一举。
一般来说可以把盐值保存在用户表中，或者直接与密码的散列值保存在一起就可以了。 - 不要重用盐值
一个常见的错误是只随机生成一次盐值，之后就所有密码散列都重用该盐值，或者干脆将盐值作为常量写死在程序中。这样一来攻击者可以根据该盐值来计算查找表与彩虹表。同时由于两个相同的密码还是会得到相同的散列值。反向查找表也依然有效，攻击者只要在每次猜测密码后，将该盐值加到猜测的密码上就可以了。
正确的做法是每次要生成密码散列值的时候，都为该密码生成一个新的随机的盐值。 - 不要使用太短的盐值
如果盐值太短，攻击者依然可以通过枚举所有可能盐值的方式来构建查找表，举例来说如果盐值只包含三个ASCII字符，那么一共只有95^3种可能的盐值。如果一个查找表包含1MB最常见的密码，那么一个包含所有盐值的查找表大概是837GB，考虑现在花300来块就能买个1TB的硬盘，这个数值真的不算大。
选择多长的盐值合适？一个简单的方法是跟散列值一样长就好，比如说SHA256的输出结果为256bits(32字节)，那么使用32字节的盐值就可以了。
四.算得慢一点！
前面提到使用暴力算法来查找SHA-1散列函数的冲突值，需要耗费数千万块GPU一年的运算量。这可能会让你产生一些错觉，因为它是不限定输入的。换句话说假如限定输入只由6位数字与小写字母组成，那么一块GPU每秒可以破解数十亿个这样的输入。对于实际场景中一些比较复杂的密码，其计算效率也不会低于每秒一个。这也解释了为什么说SHA-256,SHA-512是安全的散列函数，但不是安全的加密算法。因为使用暴力算法破解这些安全的散列函数一样是非常高效的。
解决的办法是使用一种称为key stretching的技术，它的用途就是让散列函数变慢。以bcrypt为例，该算法接受一个安全因子(security factor)为参数，使用该参数来决定密码散列过程有多慢。通过调整该参数，可以将散列函数计算时间控制在0.3到0.5秒之间。这样的时间消耗对用户来说几乎感受不到。但是对于那些试图通过暴力算法来攻击系统的人来说，是慢得无法忍受的。举例来说，假设密码只由6位数字与小写字母组成，一台现代PC使用MD5算法枚举完所有可能性所花的时间不超过30秒。但是如果你将一次散列函数的计算时间控制在0.5秒左右，那么将密码枚举完大概要30年。
五.Sample
bcrypt是目前比较成熟的一种加密算法，下面通过分析一个它的散列值，来看看它涉及到上文提到的哪些要点。1
$2a$10$N9qo8uLOickgx2ZMRZoMyeIjZAgcfl7p92ldGxad68LJZdL17lhWy
该散列值格式称为Modular Crypt Format，其中包括如下内容：
- id:2a
2a是一个标识符，用于指示用到的散列函数，如1表示MD5，5表示SHA-256 - param:10
这里的10，就是上面提到的安全因子。该值越大，表示用于生成该散列值的函数运行速度越慢。 - salt:N9qo8uLOickgx2ZMRZoMye
128位盐值，使用Base64编码为22个字符 - hash:IjZAgcfl7p92ldGxad68LJZdL17lhWy
实际密码与盐值共同散列后的结果，占184位，使用Base64编码为31个字符
最后，这些常识只能帮你鉴别哪些加密不安全，或者说不够安全。了解了这些内容并不意味着你可以在生产环境中使用你自己写的加密算法，本着对用户负责的态度，应该始终选择经过考验的成熟算法。
参考链接：