关于hashcash

2017-01-06 本文已影响1910人 Pony小马

来源

这个概念最早来自Adam Back的一篇论文

Hashcash - A Denial of Service Counter-Measure

hashcash是一个基于hash算法的系统

用途

邮件过滤

邮件过滤是hashcash最广泛的应用。

比特币

比特币的上的应用是为了防止双重支付（double-spending），这个是比特币得以运行的根本，可以防止伪造交易。

这部分的细节会单独写一篇文章

技术原理

原理概述

下面就从技术角度分析下为什么hashcash可以用于以上领域。了解密码学算法的人都知道rsa算法，它是基于数学中的大数分解困难设计的。也就是说，给你一个很大的数字，你要得到它的乘数因子很困难，但是反过来给你你个数（因子），你可以很容易得到它们的积。

hashcash就是希望基于类似这样的数学难题，希望你做大量的工作，也就是付出CPU的计算代价(这个概念很重要，比特币中这个也是关键)，得到正确的结果，才能获取某些资源（比方说往你的邮箱发送垃圾邮件）。

在计算机的世界里相对还是公平很多的，多劳多得，少劳少得。而人类自己制定的规则里有太多的人可以不劳而获。

邮件过滤正是基于这样的原理，我们设定一个规则：所有想给我发送电子邮件的人，我都要求他满足一个计算结果才会接受。要满足这个计算结果必须付出CPU的计算代价。即使一次计算只需要几秒钟，对于垃圾邮件的系统来说都是致命的，因为这些系统每天要发送数以万计的垃圾邮件，多出的CPU时间对它们来说代价是非常大的。

原理详解

什么是sha1碰撞

先看一个概念，sha1碰撞。

hashcash使用的不是RSA，而是一种叫hash的散列过程。用到的算法叫SHA（Secure Hash Algorithm）。

简单来讲，一串输入数据无论多长，hash之后可以得到一个固定长度（hash版本不同，这个长度也不同，比如SHA1结果是160比特，SHA-256结果是256比特位）的数据，这个数据我们把它称为散列值。

SHA有个特点是，只有输入数据完全相同才能得到相同的散列值，否则即使输入数据只相差一个标点符号，都会导致戳记千差万别。

Data	SHA1
this is test data,	6b5a04fdbb8b98db76db1ffdec6936f8d7c46a6d
this is test data。	333e9667643afd2f5784cefd42a65cb3aa7c773d

上面的示例中，两个数据只差了一个标点，散列值却大不相同。

sha1无论如何只是随机生成的一个字符串而已，有没有可能连个不同的输入数据，得到相同的散列值呢？答案是肯定的。当出现这种情况时，我们说发生了一次SHA1碰撞。

不过根据查到的资料显示，sha1碰撞的几率是$2^{{60}$，也就是说每$2}{60}$个样本中能找到两个sha1相同的值。

如何在电子邮件中起作用

比如有个人要给我发送邮件，我要求它的邮件头部加上一个字符串（我们把这个字符串叫做戳记，hashcash stamp)。我要求用这个戳记生成的散列值必须满足前面20个比特位都是0。

同时戳记必须包括7个域：


1. 版本号（版本 0 更简单，但是有一些局限性）。
2. 声明的比特值。如果戳记没有真正地使用声明的前导零比特进行散列，那么它就是非法的。
3. 生成戳记的日期（和时间）。可以认为当前时间之后的戳记以及那些在很久以前的戳记是非法的。
4. 戳记为哪个资源而生成。可能是一个电子邮件地址，但是也可能是一个 URI 或者其他命名的资源。
5. 特定应用程序可能需要的扩展。任何附加的数据都可以放置在这里，但是，在到目前为止的使用中， 这个域通常是空的。
6. 将该戳记与其他所有人为相同的资源在同一日期生成的戳记区别开来的随机因子（salt）。例如，两个不同的人 可以合情合理地在同一天向我的同一个地址发送电子邮件。他们不应该由于我使用了 double spend 数据库而无法 发送成功。但是，如果他们每个人都使用一个随机因子，那么完整戳记将是不同的。
7. 后缀是算法真正起作用的部分。假定给出了前 6 个域，为了生成一个通过期望数目的前导零 进行散列的的戳记，minter 必须尝试很多连续的后缀值。

这些域不一定都要有，比如5域就可以不要。

前面6个域基本都要填固定的或者有意义的数据，不能随便写，所以要得到满足规则的散列值，邮件发送者只能不断的尝试7域的数据，这就是所谓的付出CPU的代价，这个时间是

$$1048576 = 2^{20}$$

百万次的计算代价，对一个CPU大概是几秒左右的执行时间。

下面是一个戳记的例子：

1:20:040927:mertz@gnosis.cx::odVZhQMP:7ca28

1表示sha1
20表示要求散列值前缀必须满足20个比特位是0
mertz@gnosis.cx 表示收件人地址

另外4域是时间，可以对戳记的有效期加上要求，当然这都是附加功能了。

输入数据的规则肯定是根据不同的邮箱有不同的要求，不然的话垃圾邮件的制造者就可以用一个满足规则的戳记到处使用，那hashcash的意义就没有了。

代码示例

搞清楚原理，代码实现不难。可以通过下面这个链接看下hashcash的一个实现版本：

David 的 hashcash.py 模块和脚本

代码分析

如何使用

>>> from hashcash import mint, _mint
>>> mint('foo', bits=16)
'1:16:040922:foo::+ArSrtKd:164b3'

只要调用mint函数就可以找到满足条件的戳记，第一个参数是前面讲到的4域，可以传入一个表示请求原因的标识。第二个参数16标识散列值的前缀要满足16个比特位。函数返回一个满足条件的戳记。

mint函数

def mint(resource, bits=20, now=None, ext='', saltchars=8, stamp_seconds=False):
    """看下mint函数的定义，前两个已经说过了。

now表示生成戳记的日期，对应第3域，如果不指定就按当前时间。

ext 对应的是第5域，可以加一些附加的数据，如果不指定，生产的戳记5域是空的。

saltchars表示一个随机因子，对应6域。它的缺省值是8,表示可以生成一个8位的随机字符串，可以是任意字母和“=/+”中的组合。_salt函数负责生成。

stamp_seconds为True就表示3域的时间精确到秒。否则精确到天。
    """
    ver = "1"
    now = now or time()
    if stamp_seconds: ts = strftime("%y%m%d%H%M%S", localtime(now))
    else:             ts = strftime("%y%m%d", localtime(now))
    challenge = "%s:"*6 % (ver, bits, ts, resource, ext, _salt(saltchars))
    return challenge + _mint(challenge, bits)

_salt函数

def _salt(l):
    """
    Return a random string of length 'l'
    生成一个8位的随机字符串，可以是任意字母和“=/+”中的组合
    ascii_letters表示的是26个字母大小写字符串。
    choice(alphabet)从alphabet范围的字符串里返回一个随机字符，而
    [choice(alphabet) for _ in [None]*l]

这是一个链表推导式的用法，具体可以网上查下。它最终生成一个有8个元素的列表，然后由join函数转成字符串。

"""
    alphabet = ascii_letters + "+/="
    return ''.join([choice(alphabet) for _ in [None]*l])

_minth函数

def _mint(challenge, bits):
    """Answer a 'generalized hashcash' challenge'

    这个函数是核心， 前面提到，7域所表示的后缀是算法真正起作用的部分。假定给出了前 6 个域，为了生成一个通过期望数目的前导零 进行散列的的戳记，minter 必须尝试很多连续的后缀值。

这个函数就是在不断的尝试，最终找到这个前缀。

    NOTE: Number of requested bits is rounded up to the nearest multiple of 4
    """
    counter = 0
    hex_digits = int(ceil(bits/4.))
    zeros = '0'*hex_digits
    while 1:
        digest = sha(challenge+hex(counter)[2:]).hexdigest()
        if digest[:hex_digits] == zeros:
            tries[0] = counter
            return hex(counter)[2:]
        counter += 1

check 函数

def check(stamp, resource=None, bits=None,
                 check_expiration=None, ds_callback=None):
    """Check 函数校验一个stamp是否满足条件,先来看看如何调用:
    
    比如我用mint生产了一个戳记:
    
    >>> mint('foo', bits=16)
    >>> 1:16:161205:foo::pMceorKP:1a804
    
    校验:
    >>> check('1:16:161205:foo::pMceorKP:1a804', 'foo',bits=16)
    >>> True
    
    第一个参数传入戳记，这个没什么可说的。
    第二个参数对应戳记的4域，可以不传，但是如果传入一定是和第一个参数的4域相同的。否则check失败
    第三个参数是要求的前缀0的比特位数目，可以传一个指定的值，但是这个值只能小于等于第一个参数的2域(可以思考下为什么)
    
    第四个参数是有效期范围，它对比的是3域的时间，比如如果这样调用:
    >>> check('1:16:161205:foo::ifnkkghf:21c97','foo', 16, 2*DAYS);
    说明你的有效期是两天, 16年12月08日，这个戳记就失效。如果改参数为空，则戳记永远有效。
    
    第五个参数暂时不讲。
    
    """
    if stamp.startswith('0:'):          # Version 0
        try:
            date, res, suffix = stamp[2:].split(':')
        except ValueError:
            ERR.write("Malformed version 0 hashcash stamp!\n")
            return False
        if resource is not None and resource != res:
            return False
        elif check_expiration is not None:
            good_until = strftime("%y%m%d%H%M%S", localtime(time()-check_expiration))
            if date < good_until:
                return False
        elif callable(ds_callback) and ds_callback(stamp):
            return False
        elif type(bits) is not int:
            return True
        else:
            hex_digits = int(floor(bits/4))
            return sha(stamp).hexdigest().startswith('0'*hex_digits)
    elif stamp.startswith('1:'):        # Version 1
        try:
            claim, date, res, ext, rand, counter = stamp[2:].split(':')
        except ValueError:
            ERR.write("Malformed version 1 hashcash stamp!\n")
            return False
        if resource is not None and resource != res:
            return False
        elif type(bits) is int and bits > int(claim):
            return False
        elif check_expiration is not None:
            good_until = strftime("%y%m%d%H%M%S", localtime(time()-check_expiration))
            if date < good_until:
                return False
        elif callable(ds_callback) and ds_callback(stamp):
            return False
        #这里的流程我做了一些修改，原来的代码逻辑有点问题
#         else:
        hex_digits = int(floor(int(claim)/4))![](./vars.py)
        return sha(stamp).hexdigest().startswith('0'*hex_digits)
    else:                               # Unknown ver or generalized hashcash
        ERR.write("Unknown hashcash version: Minimal authentication!\n")
        if type(bits) is not int:
            return True
        elif resource is not None and stamp.find(resource) < 0:
            return False
        else:
            hex_digits = int(floor(bits/4))
            return sha(stamp).hexdigest().startswith('0'*hex_digits)

问题

1. 找到满足条件的戳记后，后面不就可以一直用这个戳记了吗？

戳记有时间域，这个时间可以精确到天，也可以精确到秒。校验者一般都会用这个作为有效期的判断，所以满足条件的戳记只能在有效期范围内使用。

2. hashcash有缺点吗？

这种方法有效的前提是所用的算法会给CPU带来客观的计算代价。如果某一天算法所依赖的数学难题被攻破，抑或计算机的运算能力有了质的提升，以前秒级的运算变成了毫秒甚至微秒，那所有的这一切都将变得没有意义。

3. 要求的前缀越长，计算的时间就越长吗？

这个是肯定的。

参考