Category Archives: Cryptography

使用pbkdf2来存储用户密码

使用了simple-pbkdf2的python库,借鉴了flask-pbkdf2,代码如下:

import binascii
import hashlib
import os
# http://pypi.python.org/pypi/simple-pbkdf2/1.0
from pbkdf2 import pbkdf2_hex

def safe_str_cmp(a, b):
    if len(a) != len(b):
        return False
    rv = 0
    for x, y in zip(a, b):
        rv |= ord(x) ^ ord(y)
    return rv == 0

class MyPbkdf2(object):
    """docstring for MyPbkdf2
    def set_password(self, password):
        if isinstance(password, UnicodeType):
            password = password.encode("UTF-8")
        pbkdf2 = MyPbkdf2()
        self.password = pbkdf2.make_password(password)

    def check_password(self, password):
        if isinstance(password, UnicodeType):
            password = password.encode("UTF-8")
        pbkdf2 = MyPbkdf2()
        return pbkdf2.check_password(password, self.password)
    """
    hashfunc = hashlib.sha256
    iterations = 1000
    saltlen = 16
    keylen = 24

    def __init__(self, iterations=1000, saltlen=16, keylen=24):
        self.iterations = iterations
        self.saltlen = saltlen
        self.keylen = keylen

    def check_password(self, password, encoded):
        algorithm, iterations, salt, hash_val = encoded.split('$', 3)
        assert algorithm == "pbkdf2_sha256"
        #expected = pbkdf2_hex(password, salt, int(iterations), hashfunc=self.hashfunc)
        expected = self.make_password(password, salt, int(iterations))
        return safe_str_cmp(encoded, expected)

    def make_password(self, password, salt=None, iterations=None):
        if not salt:
            salt = self.generate_salt()
        if not iterations:
            iterations = self.iterations
        hash_val = pbkdf2_hex(password, salt, iterations, hashfunc=self.hashfunc, keylen=self.keylen)
        return '%s$%s$%s$%s' % ('pbkdf2_sha256', iterations, salt, hash_val)

    def generate_salt(self):
        return binascii.b2a_hex(os.urandom(self.saltlen))

 

彩虹表的原理简介

彩虹表的原理简介

彩虹表(Rainbow Table)是一种破解哈希算法的技术,它的性能非常让人震惊,在一台普通PC上辅以NVidia CUDA技术,对于NTLM算法可以达到最高每秒103,820,000,000次明文尝试(超过一千亿次),对于广泛使用的MD5也接近一千亿次。更神奇的是,彩虹表技术并非针对某种哈希算法的漏洞进行攻击,而是类似暴力破解,对于任何哈希算法都有效。

这几乎是令人难以置信的,Roger迫不及待的去看了 http://www.project-rainbowcrack.com 所介绍的原理。这其实已经不是新的技术了,但是很遗憾的是,搜索“彩虹表原理”出来的文章对彩虹表原理的介绍都有不太正确,Roger就在这里简单的介绍一下,主要参考的是Wiki上的这篇http://en.wikipedia.org/wiki/Rainbow_tables,英文好的可以去看这篇论文http://lasecwww.epfl.ch/pub/lasec/doc/Oech03.pdf

我们先来做点科普,哈希(Hash)算法就是单向散列算法,它把某个较大的集合P映射到另一个较小的集合Q中,假如这个算法叫H,那么就有Q = H(P)。对于P中任何一个值p都有唯一确定的q与之对应,但是一个q可以对应多个p。作为一个有用的Hash算法,H还应该满足:H(p)速度比较快;给出一个q,很难算出一个p满足q = H(p);给出一个p1,很难算出一个不等于p1的p2使得 H(p1)=H(p2)。正因为有这样的特性,Hash算法经常被用来保存密码————这样不会泄露密码明文,又可以校验输入的密码是否正确。常用的Hash算法有MD5、SHA1等。

破解Hash的任务就是,对于给出的一个q,反算出一个p来满足q = H(p)。通常我们能想到的两种办法,一种就是暴力破解法,把P中的每一个p都算一下H(p),直到结果等于q;另一种办法是查表法,搞一个很大的数据库,把每个p和对应的q都记录下来,按q做一下索引,到时候查一下就知道了。这两种办法理论上都是可以的,但是前一种可能需要海量的时间,后一种需要海量的存储空间,以至于以目前的人类资源无法实现。

我们可以简单的算一下,对于14位的大小写加数字(先不算特殊字符了)组成的密码的集合有多大?自然就是(26*2+10)^14 = 62^14 = 1.24 * 10^25,这个就约等于12亿亿亿,即使我们每纳秒可以校验一个p(一秒钟10亿次,目前PC做不到),暴力破解法也大概需要4亿年;如果我们采用查表法,假定Hash的结果是128Bit即16字节的,光存放Hash(不存放明文P)就需要10^26字节的存储空间。什么?现在硬盘很便宜?没错现在1GB硬盘大概是五毛钱,那么按这个来算光存储这个Hash大概需要5亿亿人民币来买硬盘。所以有些文章说彩虹表就是依赖查一个巨大的表来破解Hash,简直是个无知的玩笑。

也正因为如此,我们一直都认为Hash是足够安全的,十几位的密码也是强度足够的,直到彩虹表的出现。现在我们来看看彩虹表是怎么干的。

彩虹表的根本原理就是组合了暴力法和查表法,并在这两者之中取得一个折中,用我们可以承受的时间和存储空间进行破解。它的做法是,对于一个Q = H(P),建立另一个算法R使得 P = R(Q),然后对于一个p,这样进行计算:

p0 -H-> q1 -R->p1 -H-> q2 -R->p2 -H-> q3 -R->p3  … -H-> q(n-1) -R->p(n-1) -H-> qn -R->pn

简单的说,就是把q用H、R依次迭代运算,最后得到pn,n可能比较大。最后我们把p0和pn都存储下来,把其他的结果都丢弃。然后用不同的p0代入计算,得到多个这样的p的对子。

我们在做破解的时候,给出了一个q,我们来寻找p。我们先把q做一次R运算得到一个值例如叫c1,然后把c1和每一个p对的最后一个做比较,假如和某一个pn相等,那么有可能这个pn所对应的p(n-1)就是我们在追寻的q,为了验证我们把pn对应的p0再做一次链式计算,比对qn是否就是给出的q,如果是,很明显p(n-1)就是我们在追寻的p,因为 p(n-1) -H-> qn。如果不是就继续寻找直到遍历所有的q0qn对。

事情还刚刚开始,我们再算q -R-> c1 -H-> -R-> c2,再比对c2是否是qn,如果是,那么p(n-2)就可能是p;再算c3、c4直到c(n-1),不知道这样说你明白了吗?

总的来说,就是用一个p0pn对来存储了一个链子的数据,如果n很大,就可以大大减小了存储的空间。这样带来的问题是必须做n次比对,时间更长,但是我们不需要瞬间破解,等待几秒乃至几天破解一个密码都是可以接受的。

当然这里只是讲述了最粗浅的原理,仔细想一下还有很多的问题,例如R的选择,Hash冲突的处理,如何选择p0来实现足够的覆盖,如何在有限资源下生成彩虹表等等。对这些感兴趣的可以去看看RainbowCrack的源码 http://www.project-rainbowcrack.com

说到彩虹表不得不说ophcrack和LM Hash了。本来即使是彩虹表的千亿次速度,破解14位数字字母的密码也需要百万年的时间,无奈微软为自己的Windows密码设计了一个极其傻逼的算法LM Hash:它把超过7位的密码拆成两个7位的密码分别做hash。。。然后还大小写不分,这使得它的取值范围只有 36^7 约 784亿,这么小的集合加上彩虹表的威力,很快就可以破解出来。于是有了ophcrack,它可以dump SAM,然后Load指定的彩虹表进行破解。SAM是Windows存放密码散列的地方(system32\config\sam),一般情况下是受到操作系统保护的,即使是管理员也没办法读取,但是还是有很多工具能把它读出来,例如ophcrack自带的pwdump。下面是Roger在笔记本上用ophcrack破解一个11位大小写+数字密码的截图,仅仅4秒!如果table已经在内存中,速度还会更快,几乎是瞬间。当然这个程序要求内存比较大,否则Load Table会比较慢。

ophcrack还有Live CD的ISO供下载,这意味着,只要可以物理接触一个XP的系统,就可以轻松的获取所有用户的密码明文!那我们将如何应对?像Windows这样的是无法有力的保护散列的存放的,唯一的办法是禁用很弱智的LM Hash算法,仅使用比较强的NT Hash,破解的难度会增大很多。Vista以后默认禁用了LM Hash。对于XP,可以修改本地安全策略的安全选项,“网络安全:不要再下次更改密码时存储Lan Manager的 Hash值” 设为启用,再修改一次密码就可以了。

最后再提一下王小云的MD5的破解问题。这个准确来说不叫破解,而是她找到一种方法能快速找到碰撞。就是给出一个p1,可以很快算出一个不等于p1的p2使得 MD5(p1)=MD5(p2),这一点足够把MD5枪毙掉了。但是这并不意味着能根据MD5的Hash反算出明文来,也无助于对密码的破解。

用户原始密码破解的方法和对策

用户原始密码破解的方法

这里说的用户原始密码破解有两个前提:

1. 黑客拿到了用户加密后的密文。举个例子,系统的/etc/passwd文件被盗走了。如果不知道密文,直接用不同的原始密码去尝试登陆系统来破解,可以很容易在登录尝试的地方做限制,比如错误3次30分钟内禁止再尝试等。
2. 黑客知道系统由原始密码产生密文的算法。这个算法有很多种,比如:

using a hash (MD5, SHA, SHA256)
using unique salt per entry and a hash (MD5, SHA, SHA256)
using bit/key stretching mechanisms or being overall time expensive (PBKDF2, bcrypt, scrypt, phpass)

一般破解的方法有这么几个:
1. 穷举法
2. 字典法
3. 彩虹表法

穷举法是用从一个猜测的原始密码出发,通过已知的算法来计算密文,然后将计算得到的结果和密文做比较,如果一致就认为找到了原始的密码。由于加密算法的值域空间有限,可能存在两个不同的原始密码对应同样的密文,找到原始密码中的任何一个,都可以认为破解成功了。
理论上讲,穷举法是肯定可以破解出原始密码的,唯一的问题就是消耗时间的长短。如果花了100年才找到原始密码,我们就可以认为这个破解方法失效了。

字典法是在穷举法的基础上做了一些优化。人们选择密码不是完全随机的,往往是一些单词和数字的组合,这些常见的组合形成一个字典。我们可以基于这个字典里的密码,来穷举破解。这样一般可以大大加快破解速度。但是也存在根本找不到原始密码的可能。

对于这两种方法,抵御的手段就是减缓由原始密码计算得到密文的速度,比如由原始密码得到密文需要1秒钟。这对于正常的系统运行来讲,不是一个不能接受的时间,但是如果穷举法每尝试一个密码都要消耗1秒钟,那基本上穷举法就废掉了。
这里通常的做法就是迭代,迭代1000或者更多的次数。随着计算机计算能力的提高,这个迭代次数也需要相应的增加。

彩虹表法的思路和穷举法不一样,先构造一个比较大的原始密码–>密文的表,然后直接从这个表里查密文,直接找到对应的原始密码(这个描述是不准确的,实际上彩虹表是根据hash冲突的方法,极大的压缩了这个反向的表,里面存储的实际上是很多链条)。彩虹表的规模越大,找到原始密码的可能性就越大。彩虹表可以自己生成,或者从网上下载构建好的彩虹表。但是要注意选择对应加密算法生成的彩虹表。

因为彩虹表在破解的时候,不需要大规模的计算密文,所以通过减缓计算加密密码的速度的方法不能很好的防御这种破解。比如经典的MD5加密法,有很多网站可以直接从md5值查询原始密码:
http://www.xmd5.org/index_cn.htm、http://md5.rednoize.com/。

怎么抵御这种破解呢?方法是给每个原始密码增加一个salt. 计算加密密码的时候,不直接从原始密码出发,而是从(原始密码+salt)出发来计算密文。这样提前准备的彩虹表就不能很好的工作了。
如果一个系统里有多个密文,每个密文都应该使用不同的salt。

PBKDF2标准就是从上面2个角度,来加密用户的原始密码的:

The PBKDF2 key derivation function has five input parameters:

DK = PBKDF2(PRF, Password, Salt, c, dkLen)

where:

  • PRF is a pseudorandom function of two parameters with output length hLen (e.g. a keyed HMAC)
  • Password is the master password from which a derived key is generated
  • Salt is a cryptographic salt
  • c is the number of iterations desired
  • dkLen is the desired length of the derived key
  • DK is the generated derived key

 

Storing password securely – hashses, salts and bit stretching

Original Post

        Details

Putting things into perspective, below are the most common forms of storing passwords (order from worse to best) :
  • Storing credentials in clear text
  • Storing credentials using a hash (MD5, SHA, SHA256)
  • Storing credentials using unique salt per entry and a hash (MD5, SHA, SHA256)
  • Storing credentials using bit/key stretching mechanisms or being overall time expensive (PBKDF2, bcrypt, scrypt, phpass)
It is a common occurrence that even high profile sites (linked-in.com) stored the credentials with a simple hash, there is no reason to do so today and in my view it’s borderline to negligence. There are different way to strengthen the resistance against brute-force attacks or precomputed rainbow table , adding a unique salt per entry is one, however looking at the big picture it is clear that using a unique SALT is not good enough for most password stores.
Let’s start by realising how old the different techniques are: [1]
  • Storing credentials in clear text : Ever since
  • Storing credentials using a hash : early 70s
  • Storing credentials using unique salt per entry and a hash : late 70s (DES crypt)
  • Storing credentials using bit/key stretching : bcrypt (1999) / scrypt (2009) /  PBKDF2 (2009)

Suitable Resistance per KDF

Technique / KDF Year Bruteforce Dictionnary RT GPU FPGA ASIC
Hash 1970 No No No No No No
Salted Hash 1976 No No Yes No No No
PBKDF2 * 2000 Yes Yes Yes Partial No No
Bcrypt 1999 Yes Yes Yes Yes** ?? No
Scrypt * 2009 Yes Yes Yes Yes** Yes Yes
* High iteration counts assumed
** Due to Memory Access

Estimated (ASIC) costs to crack one password in a year

Technique / KDF 6LL 8 LL 8 chars 10 chars
DES CRYPT < 1$ < 1$ < 1$ < 1$
MD5 < 1$ < 1$ < 1$ 1.1K$
MD5 CRYPT < 1$ < 1$ 130$ 1.1M$
PBKDF2 (100ms) < 1$ < 1$ 18k$ 160M$
bcrypt (95ms) < 1$ 4$ 130K$ 1.2B$
scrypt (64ms) < 1$ 150$ 4.8M$ 43B$
PBKDF2 (5.0s) < 1$ 29$ 920K$ 8.3B$
bcrypt (3.0s) < 1$ 130$ 4.3M$ 39B$
scrypt (3.8s) 900$ 610K$ 19B$ 175T$
 Source: Colin Percival [7]

Explanations :

  • “DES CRYPT” and “MD5 Crypt” are salted
  • “LL” : Lower case letter – example “aeterws”
  • “chars” : 95 printable 7-bit ASCII characters – example “6,uh3y[a”
  • The numbers in the parenthesis are the time it took to go through the setup/iterations, this depends on the CPU power and settings/iteration counts. It is notable how bcrypt offers a higher recovery costs at a lesser setup time thean PBKDF2, the same holds true for scrypt vs. bcrypt.

To Consider

All key derivation functions that are expensive to setup rely on the fact that (in case of a website) the authentication step requires the the setup to be done once while an attacker that has the pasword store dumped has to do the setup hundreds of thousands or millions of times. On the downside as the setup is expensive this might put load on the web-server and depending on the website you operate the number of iterations you configure (PBKDF2, bcrypt, scrypt) are a trade off to make between speed and “security”. As 98% of the website don’t deal with massive amount of new logins per second this is usually acceptable.
Another case to consider is that due to the expensive setup time that you could open the door to denial of service attacks with somebody trying to authenticate over and over again. This can however be relatively easily determined and blocked in most cases.

More information :

对用户的密码进行加密

目前常见的不可逆加密算法有以下几种:

  • 一次MD5(使用率很高)
  • 将密码与一个随机串进行一次MD5
  • 两次MD5,使用一个随机字符串与密码的md5值再进行一次md5,使用很广泛
  • PBKDF2算法
  • bcrypt
  • 其它加密算法

PBKDF2,也就是PKCS#5 v2.0的方法貌似较受人推崇。