Store and validate hashed password

Table of Contents

1 “用户名+密码”认证简介

采用“用户名+密码”这种登录方式的系统如何实现认证呢?

最原始的方法是用户注册后,系统把用户的密码保存到数据库(或文件)中;当用户登录时,把用户的输入密码和之前系统中保存的密码对比,两者相同就通过认证,不同就拒绝认证。这种办法的缺点在于,如果攻击者得到了保存用户密码的数据库,则用户密码就直接被攻击者获取了。显然,直接明文保存用户密码的作法是非常不安全的。

一种容易想到的改进思路是:不直接保存用户密码,而是保存用户密码的hash值(比如说密码对应的MD5值)。当用户登录时,把用户的输入密码进行相同的hash运算后得到hash值后与数据库中保存的hash值对比,两者相同就通过认证,不同就拒绝认证。这样,就算攻击者得到了保存用户密码hash值的数据库,他也无法通过hash值反推出用户的密码。但是,这种方法也是不安全的。一般来说,用户密码不会设置得太长,假设用户的密码是不超过8位的数字或字母,攻击者可以把不超过8位的数字或字母的所有可能组合提前计算出hash值保存到一个表中(称为Rainbow Table,即“彩虹表”),这样攻击者得到保存用户密码hash值的数据库后,就可以直接查询彩虹表,从而得到用户的真正密码。

2 防止“彩虹表攻击”:计算hash前加salt

为了防止使用“彩虹表”批量破解哈希值,我们可以采用对密码加盐salt(一个随机字符串)后再计算hash值的方式。具体过程如下所述(注:下面的介绍仅是原理性的,不要直接拿来用到生产系统中)。

假设系统采用的hash算法为MD5,用户user1在注册时指定密码为8位字符“Lq!bZ/05”,我们生成一个15位随机数“!x.%1Qp^3q,8hQz”作为盐值,则我们把密码和盐值的组合“!x.%1Qp^3q,8hQzLq!bZ/05”的MD5值d9ace71d953f73d3a37ba9d3ab1cd30d保存到数据库中。又假设用户user2在注册时指定密码为8位字符“64pXi.rW”,我们生成一个15位随机数“s2A1ksI*72fe#41”作为盐值,则可算出密码和盐值的组合“s2A1ksI*72fe#4164pXi.rW”对应MD5值为f4b0cc569f41f9330f200f3bcdfb30b5。为了能够正确地验证密码,我们必须需要把盐值也保存到数据库中。

系统用户数据库如下所示:

user salt hash
user1 !x.%1Qp^3q,8hQz d9ace71d953f73d3a37ba9d3ab1cd30d
user2 s2A1ksI*72fe#41 f4b0cc569f41f9330f200f3bcdfb30b5

攻击者通过非法手段获得了系统的数据库后,通过查询“彩虹表”,一般情况下找不到d9ace71d953f73d3a37ba9d3ab1cd30d和f4b0cc569f41f9330f200f3bcdfb30b5的对应记录。因为它们是15+8=23位字符的hash值,一般来说,MD5的“彩虹表”能覆盖任意1到10位字符的hash值就很不错了,目前还没有能覆盖任意23位字符的MD5“彩虹表”(因为这个数据量实在太大了)。如果我们把salt的长度变得更长,则通过查询“彩虹表”来破解MD5就更加不可行了。

这时,攻击者只能采用“暴力破解”方法了。比如,想要破解用户user1的密码,攻击者得计算字符串“!x.%1Qp^3q,8hQzXXXXXXXX”(其中XXXXXXXX是未知的任意组合)的MD5值,一旦发现其中某个字符串(就是“!x.%1Qp^3q,8hQzLq!bZ/05”)的MD5值为d9ace71d953f73d3a37ba9d3ab1cd30d时,则破解出了用户user1的密码(为“Lq!bZ/05”)。

通过上面的分析可知,要实现较好的安全性,salt需要满足:

  1. salt不能太短。假设salt很短(比如为2个字符),则利用“彩虹表”很可能可以直接破解hash。
  2. salt要足够随机,不能重复使用(特别地,每个用户的salt要不同;同一个用户在修改密码后,salt也要更换)。假设系统中有1万个用户,且使用的salt都相同,尽管破解某一个指定用户密码的难度不变,但攻击者破解所有用户密码需要尝试的次数将大大减少,所以使用相同salt会大大降低了“暴力破解”的难度。

3 防止“哈希长度扩展攻击”:不要使用hash(salt || password)方式,请使用HMAC

hash(salt || password)这种方式(其中||表示字符串连接)可以防止“彩虹表”攻击,但它也不安全。利用一种称为“哈希长度扩展攻击(Length extension attack)”的手段可能非法进入系统。

Hash functions like MD5, SHA1, and SHA2 use the Merkle–Damgård construction, which makes them vulnerable to what are known as length extension attacks. This means that given a hash Hash(key + message), an attacker can compute Hash(pad(key + message) + extension), without knowing the key.

下面通过一个例子(摘自:哈希长度扩展攻击, 绿盟科技博客)来演示哈希长度扩展攻击。

假设web系统的密码验证逻辑为:

$auth = false;
if (isset($_COOKIE["auth"])) {
   $auth = unserialize($_COOKIE["auth"]);
   $hsh = $_COOKIE["hsh"];
   if ($hsh !== md5($SECRET . strrev($_COOKIE["auth"]))) {    //$SECRET is a 8-bit salt
     $auth = false;
   }
} else {
  $auth = false;
  $s = serialize($auth);
  setcookie("auth", $s);
  setcookie("hsh", md5($SECRET . strrev($s)));
}

为了方便,我们用下面类似的python (example.py)来测试:

import hashlib
import sys
from urllib import unquote

def login(password, hash_val):
    m = hashlib.md5()
    secret_key = "message"               # secret_key is a salt
    m.update(secret_key + password)
    if(m.hexdigest() == hash_val):
        print "Login Successful!"
    else:
        print "Login Failed"

if __name__ == "__main__":
    password = unquote(sys.argv[1])
    hash_val = unquote(sys.argv[2])
    login(password, hash_val)

已知系统中用户user1的密码为root(攻击者不知道),对应的salt为message(攻击者不知道),md5(salt || password)=md5(messageroot)=f3c36e01c874865bc081e4ae7af037ea(攻击者通过非法途径攻取了)。

$ python example.py root f3c36e01c874865bc081e4ae7af037ea
Login Successful!

利用“哈希长度扩展攻击”(不详细介绍原理和步骤),我们可以算出一个密码和相应hash值,它们可以通过上面的密码验证逻辑,测试如下:

$ python example.py %80%00%00%00%00%00%00%00%00%00%00%00%00%00%00%00%00%00%00%00%00%00%00%00%00%00%00%00%00%00%00%00%00%00%00%00%00%00%00%00%00%00%00%00%00%00%00%00%00%38%00%00%00%00%00%00%00admin e53a681a30ff99e3f6522270ca7db244
Login Successful!

通过上面的输出知,攻击者使用伪造的密码和hash值进入了系统。

需要说明的是,“哈希长度扩展攻击”需要应用具备下面条件:

  1. 使用hash(key || message)这种方式,且使用了MD5或SHA-1等基于Merkle–Damgård构造的哈希函数生成哈希值;
  2. 让攻击者可以提交数据以及哈希值,虽然攻击者不知道密文;
  3. 服务器把提交的数据跟密文构造成字符串,并经过哈希后判断是否等同于提交上来的哈希值。

在前面的攻击实例中,服务器接受用户输入的密码和hash值。不过,在用户登录过程中,可设计服务器仅接受一个密码,计算密码相应hash,再和数据库中的值对比,即可实现认证过程(这个过程并不会受到“哈希长度扩展攻击”)。

参考:
哈希长度扩展攻击的简介以及HashPump安装使用方法
哈希长度扩展攻击解析
科普:哈希长度扩展攻击

3.1 Keyed-Hash Message Authentication Code (HMAC)

前面介绍过,利用md5(key || message)方式(其中||表示字符串连接)生成的hash可能会受到“哈希长度扩展攻击”。

那么,我们可以使用md5(message || key)或者md5(md5(key) || message)等方式生成hash来避免“哈希长度扩展攻击”吗?答案是:不要这么做,请使用密码专家设计的方案——Keyed-Hash Message Authentication Code (HMAC),其RFC文档为:https://tools.ietf.org/html/rfc2104

HMAC仅是一种混合key和message的方法,可以使用任意hash函数,如使用md5/sha1/sha256等hash算法时,相应hamc算法可称为HmacMD5/HmacSHA1/HmacSHA256。

HMAC的伪代码实现为:

function hmac (key, message) {
    if (length(key) > blocksize) {
        key = hash(key) // keys longer than blocksize are shortened
    }
    if (length(key) < blocksize) {
        // keys shorter than blocksize are zero-padded (where ‖ is concatenation)
        key = key ‖ [0x00 * (blocksize - length(key))] // Where * is repetition.
    }

    o_key_pad = [0x5c * blocksize] ^ key // Where blocksize is that of the underlying hash function
    i_key_pad = [0x36 * blocksize] ^ key // Where ^ is exclusive or (XOR)

    return hash(o_key_pad ‖ hash(i_key_pad ‖ message)) // Where ‖ is concatenation
}

3.1.1 HMAC实例(openssl, Java)

可以直接使用工具openssl来测试hmac,如下:

$ echo -n "password" | openssl dgst -sha1 -hmac "salt"
c1d0e06998305903ac76f589bbd6d4b61a670ba6
$ echo -n "data" | openssl dgst -sha1 -hmac "key"
104152c5bfdca07bc633eebd46199f0255c9f49d

Java中测试如下:

// from https://gist.github.com/ishikawa/88599/3195bdeecabeb38aa62872ab61877aefa6aef89e
import java.security.InvalidKeyException;
import java.security.NoSuchAlgorithmException;
import java.security.SignatureException;
import java.util.Formatter;

import javax.crypto.Mac;
import javax.crypto.spec.SecretKeySpec;


public class HmacSha1Signature {
	private static final String HMAC_SHA1_ALGORITHM = "HmacSHA1";

	private static String toHexString(byte[] bytes) {
		Formatter formatter = new Formatter();

		for (byte b : bytes) {
			formatter.format("%02x", b);
		}

		return formatter.toString();
	}

	public static String calculateRFC2104HMAC(String data, String key)
		throws SignatureException, NoSuchAlgorithmException, InvalidKeyException
	{
		SecretKeySpec signingKey = new SecretKeySpec(key.getBytes(), HMAC_SHA1_ALGORITHM);
		Mac mac = Mac.getInstance(HMAC_SHA1_ALGORITHM);
		mac.init(signingKey);
		return toHexString(mac.doFinal(data.getBytes()));
	}

	public static void main(String[] args) throws Exception {
		String hmac = calculateRFC2104HMAC("data", "key");

		System.out.println(hmac);
		assert hmac.equals("104152c5bfdca07bc633eebd46199f0255c9f49d");
	}
}

4 让暴力破解更慢:使用"Slow Hash Function"

现代计算机的计算能力越来越强大,还可以利用GPU加速,使得计算字符串的MD5,SHA1等hash值非常快,这使得暴力破解需要的时间越来越短。

为了更好地抵抗暴力破解,我们可以设计hash算法,使得计算一次hash值需要的时间比较长,从而使暴力破解的时间变长。这类慢hash算法有:PBKDF2, bcrypt, scrypt, Argon2, crypt ($2y$, $5$, $6$ 版本) 等等。

说明:不要使用MD5, SHA1, crypt ($1$, $2$, $2x$, $3$ 版本) 等对密码进行hash运算,它们抵抗暴力破解的能力很差。

5 总结:如何保存和验证密码

To Store a Password

  1. Generate a long random salt using a Cryptographically Secure Pseudo-Random Number Generator.
  2. Prepend the salt to the password and hash it with a standard password hashing function like Argon2, bcrypt, scrypt, or PBKDF2, etc.
  3. Save both the salt and the hash in the user's database record.

To Validate a Password

  1. Retrieve the user's salt and hash from the database.
  2. Prepend the salt to the given password and hash it using the same hash function.
  3. Compare the hash of the given password with the hash from the database. If they match, the password is correct. Otherwise, the password is incorrect.

参考:Salted Password Hashing - Doing it Right

6 Unix crypt function

Unix-like 系统中的 crypt 函数,是一个可以加salt(只能是两位字符)的hash函数。以前用它来加密系统用户的密码。

下面是函数 crypt 的简单测试实例:

$ cat test.c
#define _XOPEN_SOURCE
#include <unistd.h>
#include <stdio.h>
#include <stdlib.h>

int main() {
    printf("%s\n", crypt("password", "sa"));
    exit(0);
}
$ gcc test.c -lcrypt -o test
$ ./test
sa3tHJ3/KuYvI

很多其它语言也实现了crypt,测试如下:

$ python -c 'import crypt; print crypt.crypt("password","sa")'
sa3tHJ3/KuYvI
$ ruby -e 'print "password".crypt("sa"); print("\n");'
sa3tHJ3/KuYvI
$ perl -le "print crypt('password','sa');"
sa3tHJ3/KuYvI

参考:
https://en.wikipedia.org/wiki/Crypt_(C)
man 3 crypt

6.1 Modular Crypt Format

原始的crypt函数早已不再安全,现代Unix-like系统不使用原始的crypt来加密用户密码。

现代系统中,一般通过扩展salt的格式来支持其他hash算法,扩展后的salt格式称为 Modular Crypt Format

Modular Crypt Format 的基本格式(使用 $ 作为分隔符)为:

$id$salt$encrypted

下面是 Modular Crypt Format 的一些例子:

Table 1: Modular Crypt Format
Schema Id Schema Example
  DES sa3tHJ3/KuYvI
1 MD5 $1$etNnh7FA$OlM7eljE/B7F1J4XYNnk81
2,2a,2x,2y bcrypt $2a$10$VIhIOofSMqgdGlL4wzE//e.77dAQGqntF/1dT7bqCrVtquInWy2qi
3 NTHASH $3$$8846f7eaee8fb117ad06bdd830b7586c
5 SHA-256 $5$9ks3nNEqv31FX.F$gdEoLFsCRsn/WRN3wxUnzfeZLoooVlzeF4WjLomTRFD
6 SHA-512 $6$qoE2letU$wWPRl.PVczjzeMVgjiA8LLy2nOyZbf7Amj3qLIL978o18gbMySdKZ7uepq9tmMQXxyTIrS12Pln.2Q/6Xscao0

例如,我的Linux中,保存用户密码使用的是 crypt $6$

$ sudo cat /etc/shadow
......
cig01:$6$gL5SlRI4$eez954NDwizilXE6jIQ9VfzeYmL3UigUIcDLLlPm.eAXVv/i3XdNdhSlO97cOTgzSRkXL93kP1JZxQ6/0XLbQ1:16620:0:99999:7:::
......

用户cig01的密码为12345(不要使用这样的简单密码),使用python验证如下:

$ python -c 'import crypt; print crypt.crypt("12345", "$6$gL5SlRI4$")'
$6$gL5SlRI4$eez954NDwizilXE6jIQ9VfzeYmL3UigUIcDLLlPm.eAXVv/i3XdNdhSlO97cOTgzSRkXL93kP1JZxQ6/0XLbQ1

上面输出和/etc/shadow中保存的信息一致,从而验证了cig01的密码确实为12345。


Author: cig01

Created: <2016-04-16 Sat 00:00>

Last updated: <2018-01-02 Tue 15:38>

Creator: Emacs 25.3.1 (Org mode 9.1.4)