背景
在我们设计一个Web程序时，往往需要包含用户登录注册系统，如何安全地保存用户密码是一个不可忽视的大问题。如果直接保存密码明文，或者使用一些不安全的加密算法加密后保存密文，那么一旦数据库泄露，可能会造成非常大的危害。密码在数据库中往往并不需要还原，因此，最好的方式就是使用加盐的密码hash（salted password hashing）。
什么是hash
Hash算法是一种单向的函数，可以把任意数量的数据转换成固定长度的指纹，这个过程是不可逆的，而且，只要输入发生改变，哪怕只改变1bit，输出的指纹也会有很大的不同。这种特性非常适合用来保存密码。在一个使用Hash的账号系统中，用户注册和认证的大致流程如下：
但使用hash之后，密码就一定安全了吗？答案是错误的。最常听到的Hash算法有MD5、SHA256、SHA512等，如果在网上搜索MD5，能找到一大堆可以破解的网站，而且很多常见的字符串都可以逆向出来。显然，单纯对密码进行hash还是不够的。要知道如何正确使用Hash保存密码，我们首先需要了解黑客是如何破解hash的。
如何破解hash
字典和暴力破解攻击
字典攻击就是自己构造一个包含常见密码、短语、字符串的文件集合，然后对每一条数据进行hash，并和要破解的hash值比较，如果一致，就说明破解成功了。字典攻击的有效性和字典的质量成正比，和密码的复杂度成反比。
暴力破解就是不构造字典，直接尝试所有可能字符的所有组合。显然，当长度确定且较短时，它是可行有效的；但如果密码长度不确定，或者长度很长时，这种方式会消耗很大的资源。
理论上没有任何一种Hash算法能够抵抗字典和暴力破解攻击，我们能做的只是尽可能让这种方式变得低效。比如，强制用户使用复杂密码，采用未知长度的密码，采用密码工具提供的随机密码等。
查表破解
查表破解和上述方法类似。对于特定的hash类型，可以预先计算出密码字典中每一个密码的hash，然后将hash值和密码保存在一个表里，需要破解时只需要查表即可。一个设计良好的查询表结构，即使存储了数十亿个hash，每秒钟仍然可以查询成百上千个hash。
反向查表破解
反向查表破解的前提是攻击者已经拿到了数据库，然后构造常见密码字典，对字典中的值进行hash后与数据库比较，如果有匹配的，就可以破解相对应的用户密码了。这种攻击方式很有效果，因为通常情况下很多用户都会有使用相同的密码。
彩虹表
彩虹表和查表破解类似，只是牺牲了一些破解时间，来换取更小的存储空间，单位存储空间能够存储更多的hash。但哈希表并不是简单的明文到密文的映射。
彩虹表的前身
彩虹表的前身是“预计算的哈希链集”。当面对需要破解的哈希函数H，首先定义一个约减函数R，该函数的定义域与值域需要和H相反。通过R函数可以将哈希值约减为一个与原文相同格式的值，由于H不可逆，所以不可能通过R函数直接获取到明文，R函数只是将其转换成了一个相同格式的值，这个值落在H的定义域里面。然后再对这个值进行H运算，得到一个密文；再进行R运算，又得到一个相同格式的明文……这样重复k次后，我们就得到了一条哈希链（假设k=2）：
这条链并不需要完整记录下来，我们只需要在数据库中保存起始点和结束点即可，对于上图的这条哈希链，我们需要保存的是aaaaaa和kiebgt。之后，我们以大量随机明文作为起点，通过上述步骤计算出哈希链并将结束点存储，得到一张哈希链表。那么，如果使用这张哈希链表对密码进行破解呢？
假设我们知道密码哈希运算后的密文为920ECF10，则先对其进行一次R运算，得到kiebgt，查询哈希链表，发现存在这么一个结束点，那么我们就有足够的把握（并不是100%）认为，明文就存在于这条链上。之后，从起始点aaaaaa开始，重复哈希链的计算过程，发现sgfnyd进行H运算后得到的密文和要破解的密文一样，那么说明密码明文就是sgfnyd。
如果得到的密文不是920ECF10，而是281DAF40，那么一次R运算可能得不到存在的结束点，只需要再重复H和R运算即可，在上图的哈希链中，进行R->H->R运算后，得到了kiebgt，它是一个结束点，那么我们就可以找到起始点aaaaaa，重复哈希链表的计算过程，发现aaaaaa进行H运算后得到该密文，说明密码明文是aaaaaa。
如果进行了k次R->H运算后仍然没有找到结束点，那么我们就认为明文并不存在于这张表中，再计算也没有意义了。
每一条哈希链都代表了属性相同的一组明文，每一个明文都可以通过起始点快速地计算得出，计算次数不大于k。对于每一组明文，只需要保存起始点和结束点，储存空间只需约1/k，因此大大节约了空间。
R的问题
一个优秀的R函数应该做到以下两点：
- 能够将值域固定在特定的范围，如长度范围、字符取值范围等
- R必须同Hash函数一样，尽可能保证输出值在值域中均匀分布，减少碰撞的概率
什么是碰撞？发生了碰撞会出现什么结果呢？
碰撞就是R函数将不同的哈希值计算得出了相同的明文，这时就可能出现下图的情况，加粗部分是完全相同的哈希链。如果碰撞概率较大，那么可能会出现很多很多的重复部分，造成严重的冗余和浪费。
彩虹表的改进
彩虹表对碰撞问题进行了改进。在彩虹表中，R函数并不是一个函数，而是k个函数的集合。在生成哈希链的计算过程中，每一步都使用不同的R函数，如下图所示。这样，即使发生碰撞，只要他们不是在同一个位置，也不会造成太多的浪费，因为下一次R运算使用的函数并不相同。
如果碰撞发生的位置相同会怎样呢？假设都是在第i个位置发生的碰撞，那么总共要进行k此运算，剩下的计算次数是k-i次，每一次计算使用的R也是相同的，最终得到的结束点也一定是相同的，这样就会直接舍弃其中的一条链，自然不会浪费存储空间。
不过彩虹表的使用比较麻烦。首先，假设要破解的密文位于任一链条的k-1位置处，对其进行Rk运算，得到结束点，然后就可以用起始点验证其正确性。但如果并没有找到结束点，就需要假设它在k-2位置，进行两次运算……重复这个过程，直到找到包含在表中的结束点。最不利的情况下，需要将密文进行完整的R1->H->...->Rk运算后，才能得知明文是否存在于彩虹表中。
对于相同个数的明文，当k越大时，破解的期望时间就越长，但彩虹表所占用的空间就越小；相反，k越小时，彩虹表本身就越大，相应的破解时间就越短。这正是保持空间、时间二者平衡的精髓所在。极端的，令k=1，简化函数R(x)=x，这样的彩虹表就变成了通常的错误理解，即将明文、密文对应关系全部保存的表。此时由于k极小，因而得到的表的体积极大，甚至可能超出储存能力。
如果将哈希后的密文比作一把锁，暴力破解的方法就是现场制作各种各样不同齿形的钥匙，再来尝试能否开锁，这样耗时无疑很长；查表破解，是事先制作好所有齿形的钥匙，全部拿过来尝试开锁，这样虽然省去了制作钥匙的时间，但是这些钥匙实在是太多了，没法全部带在身上；彩虹表，是将钥匙按照某种规律进行分组，每组钥匙中只需要带最有特点的一个，当发现某个“特征钥匙”差一点就能开锁了，则当场对该钥匙进行简单的打磨，直到能开锁为止。这种方法是既省力又省时的。
彩虹表的防御
从上述过程可知，彩虹表是针对特定的哈希函数H制作的，如果H变了，那么哈希表也需要改变。因此防御哈希表，可以从改变H下手，这就是后面要提到的加盐。
加盐
如果两个用户使用了同样的密码，那么一定他们的密码hash也一定相同。我们可以让每一个hash随机化，同一个密码每次hash后得到不同的密码，这样就可以避免彩虹表攻击了。
具体操作就是，给每个密码加一个随机的前缀或者后缀，然后再进行哈希，这个随机的后缀或前缀就称为“盐”。检查用户输入的密码时，我们也还需要这个盐值，因此需要把它也保存在数据库中，可以单独新建一个salt列来保存，或者也可以同hash保存在一列中，中间通过特殊符号分隔。
盐不需要保密，只要盐是随机的话，查表，彩虹表都会失效。因为攻击者无法事先知道盐是什么，也就没有办法预先计算出查询表和彩虹表。如果每个用户都是使用了不同的盐，那么反向查表攻击也没法成功。
盐值的长度一定要足够长，如果太短，假设只有3位，那么可能只需要1TB的存储空间就足够破解了。一个经验规则就是盐的至少要跟hash函数输出的长度一致。
盐值不可以复用，否则可能会被逆向出来，构造出特定的彩虹表进行快速破解。正确的做法是，使用可靠安全的随机数生成器来得到，在Java中可以用java.security.SecureRandom，在Python中可以用os.urandom，在PHP中可以用mcrypt_create_iv或者openssl_random_pseudo_bytes。每一个用户、每一个密码都需要使用不同的盐，每次修改密码都要生成一个新的随机盐，永远不要重复使用盐。
要验证用户输入的密码，需要从数据库中取出盐和哈希，然后将用户输入与盐值拼接，以相同的哈希函数进行哈希，与数据库中的值进行比较，如果相同，说明密码正确。
加盐可以让攻击者无法使用查表和彩虹表的方式对大量hash进行破解，但是依然无法避免对单个hash的字典和暴力攻击。高端的显卡(GPUs)和一些定制的硬件每秒可以计算数十亿的hash，所以针对单个hash的攻击依然有效。
如何恰当地进行hash
为了避免字典和暴力攻击，我们可以采用一种称为key扩展(key stretching)的技术。这种技术的思路就是让hash变得非常缓慢，即使使用告诉GPU和特定的硬件，字典和暴力破解的速度也慢到没有实用价值。通过减慢hash的过程来防御攻击，但是hash速度依然可以保证用户使用的时候没有明显的延迟。
常见的此类算法有PBKDF2和bcrypt。这些算法采用了一个安全变量或者迭代次数作为参数。比如PBKDF2，采用对密码和盐值实用哈希函数进行特定次数的迭代，最终得到一个密文。
常见的PBKDF2算法代码实现
PHP
<?php
/*
* Password Hashing With PBKDF2 (http://crackstation.net/hashing-security.htm)
* Copyright (c) 2013, Taylor Hornby
* All rights reserved.
*
* Redistribution and use in source and binary forms, with or without
* modification, are permitted provided that the following conditions are met:
*
* 1. Redistributions of source code must retain the above copyright notice,
* this list of conditions and the following disclaimer.
*
* 2. Redistributions in binary form must reproduce the above copyright notice,
* this list of conditions and the following disclaimer in the documentation
* and/or other materials provided with the distribution.
*
* THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
* AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
* IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
* ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE
* LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
* CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
* SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
* INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
* CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
* ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
* POSSIBILITY OF SUCH DAMAGE.
*/
// These constants may be changed without breaking existing hashes.
define("PBKDF2_HASH_ALGORITHM", "sha256");
define("PBKDF2_ITERATIONS", 1000);
define("PBKDF2_SALT_BYTE_SIZE", 24);
define("PBKDF2_HASH_BYTE_SIZE", 24);
define("HASH_SECTIONS", 4);
define("HASH_ALGORITHM_INDEX", 0);
define("HASH_ITERATION_INDEX", 1);
define("HASH_SALT_INDEX", 2);
define("HASH_PBKDF2_INDEX", 3);
function create_hash($password)
{
// format: algorithm:iterations:salt:hash
$salt = base64_encode(mcrypt_create_iv(PBKDF2_SALT_BYTE_SIZE, MCRYPT_DEV_URANDOM));
return PBKDF2_HASH_ALGORITHM . ":" . PBKDF2_ITERATIONS . ":" . $salt . ":" .
base64_encode(pbkdf2(
PBKDF2_HASH_ALGORITHM,
$password,
$salt,
PBKDF2_ITERATIONS,
PBKDF2_HASH_BYTE_SIZE,
true
));
}
function validate_password($password, $correct_hash)
{
$params = explode(":", $correct_hash);
if(count($params) < HASH_SECTIONS)
return false;
$pbkdf2 = base64_decode($params[HASH_PBKDF2_INDEX]);
return slow_equals(
$pbkdf2,
pbkdf2(
$params[HASH_ALGORITHM_INDEX],
$password,
$params[HASH_SALT_INDEX],
(int)$params[HASH_ITERATION_INDEX],
strlen($pbkdf2),
true
)
);
}
// Compares two strings $a and $b in length-constant time.
function slow_equals($a, $b)
{
$diff = strlen($a) ^ strlen($b);
for($i = 0; $i < strlen($a) && $i < strlen($b); $i++)
{
$diff |= ord($a[$i]) ^ ord($b[$i]);
}
return $diff === 0;
}
/*
* PBKDF2 key derivation function as defined by RSA's PKCS #5: https://www.ietf.org/rfc/rfc2898.txt
* $algorithm - The hash algorithm to use. Recommended: SHA256
* $password - The password.
* $salt - A salt that is unique to the password.
* $count - Iteration count. Higher is better, but slower. Recommended: At least 1000.
* $key_length - The length of the derived key in bytes.
* $raw_output - If true, the key is returned in raw binary format. Hex encoded otherwise.
* Returns: A $key_length-byte key derived from the password and salt.
*
* Test vectors can be found here: https://www.ietf.org/rfc/rfc6070.txt
*
* This implementation of PBKDF2 was originally created by https://defuse.ca
* With improvements by http://www.variations-of-shadow.com
*/
function pbkdf2($algorithm, $password, $salt, $count, $key_length, $raw_output = false)
{
$algorithm = strtolower($algorithm);
if(!in_array($algorithm, hash_algos(), true))
trigger_error('PBKDF2 ERROR: Invalid hash algorithm.', E_USER_ERROR);
if($count <= 0 || $key_length <= 0)
trigger_error('PBKDF2 ERROR: Invalid parameters.', E_USER_ERROR);
if (function_exists("hash_pbkdf2")) {
// The output length is in NIBBLES (4-bits) if $raw_output is false!
if (!$raw_output) {
$key_length = $key_length * 2;
}
return hash_pbkdf2($algorithm, $password, $salt, $count, $key_length, $raw_output);
}
$hash_length = strlen(hash($algorithm, "", true));
$block_count = ceil($key_length / $hash_length);
$output = "";
for($i = 1; $i <= $block_count; $i++) {
// $i encoded as 4 bytes, big endian.
$last = $salt . pack("N", $i);
// first iteration
$last = $xorsum = hash_hmac($algorithm, $last, $password, true);
// perform the other $count - 1 iterations
for ($j = 1; $j < $count; $j++) {
$xorsum ^= ($last = hash_hmac($algorithm, $last, $password, true));
}
$output .= $xorsum;
}
if($raw_output)
return substr($output, 0, $key_length);
else
return bin2hex(substr($output, 0, $key_length));
}
?>
JAVA
/*
* Password Hashing With PBKDF2 (http://crackstation.net/hashing-security.htm).
* Copyright (c) 2013, Taylor Hornby
* All rights reserved.
*
* Redistribution and use in source and binary forms, with or without
* modification, are permitted provided that the following conditions are met:
*
* 1. Redistributions of source code must retain the above copyright notice,
* this list of conditions and the following disclaimer.
*
* 2. Redistributions in binary form must reproduce the above copyright notice,
* this list of conditions and the following disclaimer in the documentation
* and/or other materials provided with the distribution.
*
* THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
* AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
* IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
* ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE
* LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
* CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
* SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
* INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
* CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
* ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
* POSSIBILITY OF SUCH DAMAGE.
*/
import java.security.SecureRandom;
import javax.crypto.spec.PBEKeySpec;
import javax.crypto.SecretKeyFactory;
import java.math.BigInteger;
import java.security.NoSuchAlgorithmException;
import java.security.spec.InvalidKeySpecException;
/*
* PBKDF2 salted password hashing.
* Author: havoc AT defuse.ca
* www: http://crackstation.net/hashing-security.htm
*/
public class PasswordHash
{
public static final String PBKDF2_ALGORITHM = "PBKDF2WithHmacSHA1";
// The following constants may be changed without breaking existing hashes.
public static final int SALT_BYTE_SIZE = 24;
public static final int HASH_BYTE_SIZE = 24;
public static final int PBKDF2_ITERATIONS = 1000;
public static final int ITERATION_INDEX = 0;
public static final int SALT_INDEX = 1;
public static final int PBKDF2_INDEX = 2;
/**
* Returns a salted PBKDF2 hash of the password.
*
* @param password the password to hash
* @return a salted PBKDF2 hash of the password
*/
public static String createHash(String password)
throws NoSuchAlgorithmException, InvalidKeySpecException
{
return createHash(password.toCharArray());
}
/**
* Returns a salted PBKDF2 hash of the password.
*
* @param password the password to hash
* @return a salted PBKDF2 hash of the password
*/
public static String createHash(char[] password)
throws NoSuchAlgorithmException, InvalidKeySpecException
{
// Generate a random salt
SecureRandom random = new SecureRandom();
byte[] salt = new byte[SALT_BYTE_SIZE];
random.nextBytes(salt);
// Hash the password
byte[] hash = pbkdf2(password, salt, PBKDF2_ITERATIONS, HASH_BYTE_SIZE);
// format iterations:salt:hash
return PBKDF2_ITERATIONS + ":" + toHex(salt) + ":" + toHex(hash);
}
/**
* Validates a password using a hash.
*
* @param password the password to check
* @param correctHash the hash of the valid password
* @return true if the password is correct, false if not
*/
public static boolean validatePassword(String password, String correctHash)
throws NoSuchAlgorithmException, InvalidKeySpecException
{
return validatePassword(password.toCharArray(), correctHash);
}
/**
* Validates a password using a hash.
*
* @param password the password to check
* @param correctHash the hash of the valid password
* @return true if the password is correct, false if not
*/
public static boolean validatePassword(char[] password, String correctHash)
throws NoSuchAlgorithmException, InvalidKeySpecException
{
// Decode the hash into its parameters
String[] params = correctHash.split(":");
int iterations = Integer.parseInt(params[ITERATION_INDEX]);
byte[] salt = fromHex(params[SALT_INDEX]);
byte[] hash = fromHex(params[PBKDF2_INDEX]);
// Compute the hash of the provided password, using the same salt,
// iteration count, and hash length
byte[] testHash = pbkdf2(password, salt, iterations, hash.length);
// Compare the hashes in constant time. The password is correct if
// both hashes match.
return slowEquals(hash, testHash);
}
/**
* Compares two byte arrays in length-constant time. This comparison method
* is used so that password hashes cannot be extracted from an on-line
* system using a timing attack and then attacked off-line.
*
* @param a the first byte array
* @param b the second byte array
* @return true if both byte arrays are the same, false if not
*/
private static boolean slowEquals(byte[] a, byte[] b)
{
int diff = a.length ^ b.length;
for(int i = 0; i < a.length && i < b.length; i++)
diff |= a[i] ^ b[i];
return diff == 0;
}
/**
* Computes the PBKDF2 hash of a password.
*
* @param password the password to hash.
* @param salt the salt
* @param iterations the iteration count (slowness factor)
* @param bytes the length of the hash to compute in bytes
* @return the PBDKF2 hash of the password
*/
private static byte[] pbkdf2(char[] password, byte[] salt, int iterations, int bytes)
throws NoSuchAlgorithmException, InvalidKeySpecException
{
PBEKeySpec spec = new PBEKeySpec(password, salt, iterations, bytes * 8);
SecretKeyFactory skf = SecretKeyFactory.getInstance(PBKDF2_ALGORITHM);
return skf.generateSecret(spec).getEncoded();
}
/**
* Converts a string of hexadecimal characters into a byte array.
*
* @param hex the hex string
* @return the hex string decoded into a byte array
*/
private static byte[] fromHex(String hex)
{
byte[] binary = new byte[hex.length() / 2];
for(int i = 0; i < binary.length; i++)
{
binary[i] = (byte)Integer.parseInt(hex.substring(2*i, 2*i+2), 16);
}
return binary;
}
/**
* Converts a byte array into a hexadecimal string.
*
* @param array the byte array to convert
* @return a length*2 character string encoding the byte array
*/
private static String toHex(byte[] array)
{
BigInteger bi = new BigInteger(1, array);
String hex = bi.toString(16);
int paddingLength = (array.length * 2) - hex.length();
if(paddingLength > 0)
return String.format("%0" + paddingLength + "d", 0) + hex;
else
return hex;
}
/**
* Tests the basic functionality of the PasswordHash class
*
* @param args ignored
*/
public static void main(String[] args)
{
try
{
// Print out 10 hashes
for(int i = 0; i < 10; i++)
System.out.println(PasswordHash.createHash("p\r\nassw0Rd!"));
// Test password validation
boolean failure = false;
System.out.println("Running tests...");
for(int i = 0; i < 100; i++)
{
String password = ""+i;
String hash = createHash(password);
String secondHash = createHash(password);
if(hash.equals(secondHash)) {
System.out.println("FAILURE: TWO HASHES ARE EQUAL!");
failure = true;
}
String wrongPassword = ""+(i+1);
if(validatePassword(wrongPassword, hash)) {
System.out.println("FAILURE: WRONG PASSWORD ACCEPTED!");
failure = true;
}
if(!validatePassword(password, hash)) {
System.out.println("FAILURE: GOOD PASSWORD NOT ACCEPTED!");
failure = true;
}
}
if(failure)
System.out.println("TESTS FAILED!");
else
System.out.println("TESTS PASSED!");
}
catch(Exception ex)
{
System.out.println("ERROR: " + ex);
}
}
}
参考链接
文章评论
欢迎互访。