Random walk to my blog

my blog for sharing my knowledge,experience and viewpoint

0%

如何保存你的登录密码

发表于 更新于

开发登录功能的时候，需要保存用户的密码。用户的密码一般不是明文(plain text)，而是经过散列(hash)或者加密(encrypt)保存的。本文介绍几个常用的保存密码的算法。

考虑以下的User表。

1
2
3
4
5
6
7
CREATE TABLE `user`(
    `id` INT UNSIGNED NOT NULL AUTO_INCREMENT COMMENT '主键',
    `account` VARCHAR(128) NOT NULL DEFAULT '' COMMENT '账号',
    `password_hash` VARCHAR(1024) NOT NULL DEFAULT '' COMMENT '密码散列值',
    `salt` VARCHAR(128) NOT NULL DEFAULT '' COMMENT '盐',
    PRIMARY KEY(`id`),
)ENGINE=InnoDB AUTO_INCREMENT=1 DEFAULT CHARSET=utf8mb4 COMMENT='用户账号表';

MD5消息摘要算法

MD5信息摘要算法（MD5 Message-Digest Algorithm），一种被广泛使用的密码散列函数，可以产生出一个128比特（16字节）的散列值（hash value），用于确保信息传输完整一致。
需要注意的是, MD5不是一种加密算法，而是一种压缩信息的算法。当输入的值有很少的变化时，结果也会产生很大的不同。看下面的例子。

1
2
3
4
5
$ md5 -s "patrick"
MD5 ("patrick") = 6c84cbd30cf9350a990bad2bcc1bec5f

$ md5 -s "Patrick"
MD5 ("Patrick") = f87567f2159b425795ebb7ba9bc406ec

MySQL保存MD5的密码

MySQL保存使用md5保存密码，除了使用CHAR(32)来保存，也可以使用BINARY(16)来保存。

1
2
3
4
5
6
7
8
9
10
MySQL [(none)]> SET @str='patirck';
Query OK, 0 rows affected (0.00 sec)

MySQL [(none)]> SELECT MD5(@str),LENGTH(MD5(@str)) AS len_md5,LENGTH(UNHEX(MD5(@str))) as len_unhex;
+----------------------------------+---------+-----------+
| MD5(@str)                        | len_md5 | len_unhex |
+----------------------------------+---------+-----------+
| 91325f7a12f20fef31a48b5d691c279c |      32 |        16 |
+----------------------------------+---------+-----------+
1 row in set (0.01 sec)

示例说明

  1. MySQL中，BINARY类型是用来保存二进制字符串(byte string)，MySQL会给BINARY类型的变量添加\0.
  2. 从MySQL的文档中，UNHEX(str),将字符串的字符，以十六进制去解析，然后转化为二进制字符串。
    1
    2
    3
    4
    5
    6
    7
    8
    mysql> SELECT UNHEX('4D7953514C');
            -> 'MySQL'
    mysql> SELECT X'4D7953514C';
            -> 'MySQL'
    mysql> SELECT UNHEX(HEX('string'));
            -> 'string'
    mysql> SELECT HEX(UNHEX('1267'));
            -> '1267'
    并且，输入的字符必须是合法的十六进制数字(‘0’…’9’,’a’…’f’,’A’…’F’)
    1
    2
    3
    4
    5
    6
    mysql> SELECT UNHEX('Patick');
    +-----------------+
    | UNHEX('Patick') |
    +-----------------+
    | NULL            |
    +-----------------+
  3. 与UNHEX对应的HEX。从MySQL的文档中，HEX(str)返回一个字符串的十六进制表示，字符串的每个字符，都被转化成2个十六进制的数字。
    1
    2
    3
    4
    mysql> SELECT X'616263', HEX('abc'), UNHEX(HEX('abc'));
            -> 'abc', 616263, 'abc'
    mysql> SELECT HEX(255), CONV(HEX(255),16,10);
            -> 'FF', 255

MD5 + salt

MD5本质上是一个信息摘要算法，将长度不一的密码p映射成一个128比特的散列值(hash value)hash(p)。
那么能否从散列值hash(p)，反推出密码p了？如果可以的话，当黑客拿到数据库的结果散列的密码，尝试反推出密码，并且用相同的账号密码去登录用户在其他地方的账号，这回造成用户资料的泄露。

暴力攻击(brute force attack)

暴力攻击就是，对于给出的一个hash(p)，反算出一个p来满足q = hash(p)。
一般有两种方法，一种就是，把密码集合中的每一个p都算一下hash(p)，直到结果等于p；另一种办法是查表法，搞一个很大的数据库，把每个p和对应的hash(p)都记录下来，按q做一下索引。这两种办法理论上都是可以的，但是前一种可能需要海量的时间，后一种需要海量的存储空间。
因此暴力攻击并不可行。

彩虹表攻击(rainbow table attack)

既然存储所有的明文密码对需要的空间太大，密码学家们想出了一种以计算时间降低存储空间的办法：“预计算的哈希链集”（Precomputed hash chains）。下面是一条k=2哈希链：

1
2
aaaaaa -> 281DAF40 -> sgfnyd -> 920ECF10 -> kiebgt
       H           R          H           R

H函数就是要破解的哈希函数。
约简函数（reduction function）R函数是构建这条链的时候定义的一个函数：它的值域和定义域与H函数相反。通过该函数可以将哈希值约简为一个与原文相同格式的值。
这条链是这样生成的：

  • 随机选择一个明文aaaaaa
  • 对其求哈希得到281DAF40
  • R(281DAF40) 得到另外一个明文sgfnyd。
  • 继续重复2,3步骤
    存储的时候，不需要存储所有的节点，只需要存储每条链的头尾节点（这里是aaaaaa和kiebgt）
    以大量的随机明文作为起节点，通过上述步骤计算出哈希链并将终节点进行储存，可得到一张哈希链集。

预计算的哈希链集的使用：破解一个hash值

  • 假设其刚好是920ECF10：首先对其进行一次R运算，得到kiebgt，然后发现刚好命中了哈希链集中的（aaaaaa,kiebgt）链条。可以确定其极大概率在这个链条中。于是从aaaaaa开始重复哈希链的计算过程，发现sgfnyd的哈希结果刚好是920ECF10,于是破解成功。
  • 密文不是920ECF10而是281DAF40：第一次R运算后的结果并未在末节点中找到，则再重复一次H运算+R运算，这时又得到了末节点中的值“kiebgt”。于是再从头开始运算，可知aaaaaa刚好哈希值为281DAF40。
  • 如是重复了k（=2）次之后，仍然没有在末节点中找到对应的值，则破解失败。
    预计算的哈希链集的意义

对于一个长度为k的预计算的哈希链集，每次破解计算次数不超过k，因此比暴力破解大大节约时间。
每条链只保存起节点和末节点，储存空间只需约1/k，因而大大节约了空间。

防御彩虹表的攻击：加盐(salt)

盐（Salt），在密码学中，是指在散列之前将散列内容（例如：密码）的任意固定位置插入特定的字符串。这个在散列中加入字符串的方式称为“加盐”。其作用是让加盐后的散列结果和没有加盐的结果不相同，在不同的应用情景中，这个处理可以增加额外的安全性。

比如说，用户的密码是passwd,盐是my,组成后的值是mypasswd, md5的值是3102125cae72c19f215480ddf2d0d5c3。这样，就算md5的散列值被破解，获得mypasswd，也难以获得用户的原始密码。
我们甚至可以进行两次的md5散列操作.

1
md5(md5(password)+salt)

这样使得保存的密码更为安全。

SHA(Secure Hash Algorithms):安全散列算法

关于SHA的维基百科是这样解释SHA算法的

安全散列算法（Secure Hash Algorithm，SHA）是一个密码散列函数家族，是FIPS所认证的安全散列算法。能计算出一个数字消息所对应到的，长度固定的字符串（又称消息摘要）的算法。且若输入的消息不同，它们对应到不同字符串的几率很高。
SHA-0：1993年发布，当时称做安全散列标准（Secure Hash Standard），发布之后很快就被NSA撤回，是SHA-1的前身。
SHA-1：1995年发布，SHA-1在许多安全协议中广为使用，包括TLS、GnuPG、SSH、S/MIME和IPsec，是MD5的后继者。但SHA-1的安全性在2010年以后已经不被大多数的加密场景所接受。2017年荷兰密码学研究小组CWI和Google正式宣布攻破了SHA-1[1]。
SHA-2：2001年发布，包括SHA-224、SHA-256、SHA-384、SHA-512、SHA-512/224、SHA-512/256。SHA-2目前没有出现明显的弱点。虽然至今尚未出现对SHA-2有效的攻击，但它的算法跟SHA-1基本上仍然相似。
SHA-3：2015年正式发布，由于对MD5出现成功的破解，以及对SHA-0和SHA-1出现理论上破解的方法，NIST感觉需要一个与之前算法不同的，可替换的加密散列算法，也就是现在的SHA-3。

SHA1和SHA2的一个主要区别是，SHA1是160 bit的散列值，而SHA2可以产生几种不同长度的散列值，例如SHA-256产生256 bit的散列值。下面是在linux上计算patrick的SHA256值的命令。

1
2
$ echo -n patrick | sha256sum
23ddda4810068cc44360dffd31b6c5a9ad13fb9e6a69c9354a5d1b07f1b9843f

目前，SHA1算法已经不再使用，广泛使用的是SHA2算法

Linux用户登录的密码保存方式

Linux的密码是保存在/etc/shadow文件中。看下面示例。

1
2
sudo cat /etc/shadow
patrick:$6$C/vGzhVe$aKKGdhzTmYyxp8.E68gCBkPhlWQ4W7/OpCFQYV.qsCtKaV00bToWh286yzy73jedg6i0qSlZkZqQy.wmiUdje:18447:0:99999:7:::
  • patrick
  • 加密后的密码：$6$C/vGzhVe$aKKGdhzTmYyxp8.E68gCBkPhlWQ4W7/OpCFQYV.qsCtKaV00bToWh286yzy73jedg6i0qSlZkZqQy.wmiUdje
  • 上次修改密码的时间:18447天(从1970.1.1开始算起)
  • 两次修改密码间隔：没有限制
  • 两次修改密码间隔最多的天数：没有限制
  • 提前7天警告用户密码将过期
  • 该用户永久可用
    加密的格式是
    1
    $id$salt$encrypted
    id表示加密算法，1代表MD5，5代表SHA-256，6代表SHA-512。salt表示盐,系统随机生成。encrypted表示密码的散列值(hash)

SHA足够安全了吗？

MD5,SHA都是信息摘要算法，他们不是被设计用来做密钥导出函数（Key derivation function）的。
即使是SHA3散列函数，在计算能力越来越强的时候，被破解的时间也大幅减少。

密钥派生函数:在密码学中，密钥派生函数（英语：Key derivation function，简称：KDF）使用伪随机函数从诸如主密钥或密码的秘密值中派生出一个或多个密钥。KDF可用于将密钥扩展为更长的密钥或获取所需格式的密钥，例如将作为迪菲-赫尔曼密钥交换结果的组元素转换为用于高级加密标准（AES）的对称密钥。用于密钥派生的伪随机函数最常见的示例是密码散列函数。
这种使用可以表示为DK = KDF（Key，Salt，Iterations），其中DK是派生密钥，KDF是密钥导出函数，Key是原始密钥或密码，Salt是作为密码盐的随机数，Iterations是指子功能的迭代次数。使用派生密钥代替原始密钥或密码作为系统的密钥。盐的值和迭代次数（如果不固定）与散列密码一起存储或以加密消息的明文形式发送。

这里介绍一种bcrypt的密码散列算法。

bcrypt

bcrypt是设计用于密码散列的，所以它是一个运行速度比较慢的算法。运行速度比较慢，对于密码散列来说，算是一个比较好的特性，因为攻击者也需要更长的时间去生成字典攻击。
bcrypt算法主要分为2个步骤.

  1. EksBlowfishSetup使用cost,salt,password去初始化状态eksblowfish。然后bcrypt使用大量的时间去运行密钥派生，从一个主key中得到一系列的子key。这里的主key就是输入的password。
  2. 然后使用OrpheanBeholderScryDoubt的字符串，进行64次加密。
    1
    2
    3
    4
    5
    6
    bcrypt(cost,salt,pwd)
      state <- EksBlowfishSetup(cost,salt,key)
      ctext <- "OrpheanBeholderScryDoubt"
      repeat(64)
         ctext <- EncryptECB(sate,ctext)
      return Concatenate(cost,salt,ctext)