用 hashcash 打击垃圾邮件

hashcash 是一个基于可广泛应用的 SHA-1 算法的巧妙系统，它使得请求者要进行大量可参数化的工作，而求值程序仍可以“廉价”地进行检验。换句话说，发送者为了向您的收件箱中放入一些内容，不得不去做一些切实的工作。您当然可以使用 hashcash 来防止垃圾邮件，不过它还有其他方面的应用，其中包括为 Wiki 防止垃圾邮件以及加速分布式并行应用程序的运转。在本文中，您将接触到 David 自己的基于 Python 的 hashcash 实现。

hashcash.org Web 站点（请参阅参考资料）指出，hashcash 系统的主要功能是作为一个垃圾邮件过滤协议：

Hashcash 是一个拒绝服务（denial-of-service）计数器度量工具。当前它的主要作用是帮助 hashcash 用户避免因为使用了基于内容和基于黑名单的（blacklist-based）反垃圾邮件系统而丢失邮件。

可是，我认为，这项技术有着广泛的适用性，并不是只适用于电子邮件。本文还将介绍这项技术在邮件过滤方面的应用，并将提供它在其他一些方面的应用。文中将介绍我自己用 Python 完成的 hashcash 实现（它似乎是第一个当前 发布的 Python 版本），hashcash.org 站点上现在已经包含该实现。David McNab 创建了一个 Python 实现，该实现使用的协议与 hashcash 不是特别相似；其他一些开发人员也创建了部分实现 hashcash 的不完全的 Pytyhon 版本。

不过，在开始这些话题之前，让我们来回顾一下什么是 hashcash。

hashcash 基础知识
hashcash 的灵感来自于这样一个想法，即一些数学结果难于发现而易于校验。一个众所周知的例子是因数分解一个大的数字（尤其是因数较少的数字）。将一些数字相乘来获得它们的积的代价是低廉的（毕竟，CPU 周期就是金钱），但首先找到那些因数，而这项操作的代价却要高得多。

RSA 公钥密码系统就是基于这种因数分解特性的。如果应答者能够回答因数分解质询（Challenge），则说明他已经做了相当多的工作（或者偷偷地从生成那个组合的人那里得到了因数）。

对交互式质询来说，因数分解足以胜任。比如，我有一个在线资源，希望您能象征性地为其付出代价。我可以向您发送一个消息，说“只要您能因数分解这个数，我将让您得到这个资源”。没有诚意的人将无法得到我的资源，只有那些能够证明自己有足够的兴趣、付出一些 CPU 周期来回答这个质询的人才能得到这个资源。

非交互式质询
不过，有一些资源无法很方便地进行交互式协商。

我的电子邮件收件箱是我非常重视的一个资源。但不期而至的消息占用了我的一些磁盘空间和带宽，最糟糕的是，它们吸引了我的注意力。我并不介意陌生人给我写信，但是，我希望他们能以稍微认真的态度，亲自通过对我有价值的邮件与我取得联系。至少，我不希望他们是垃圾邮件制造者，那些人向我和上百万的其他人发送包含同样消息的邮件，期望我们中的某些人能购买某种产品或陷入一个骗局。

为了实现非交互式的“支付（payment）”，hashcash 让我向所有想给我发送电子邮件的人都分发一个标准质询。在您的消息头中，必须包括一个合法的 hashcash 戳记（hashcash stamp）；具体地说，该标志中包含我的收件人地址。

hashcash 提出质询的方式是，当通过安全散列算法（Secure Hash Algorithm）进行散列时，要求“minters”生成一个字符串（戳记，stamps），在它们的散列中有很多前导零。所找到的前导零的数目就是特定戳记的比特值。给定 SHA-1 的一致性与加密强度，找出给定比特值的 hashcash 戳记的惟一已知途径是平均 2^b 次运行 SHA-1。

然而，要确认一个戳记，只需要进行一次 SHA-1 计算即可。对于电子邮件中的应用来说，当前推荐使用的是 20-比特值：为了找到一个合法的戳记，发送者需要进行大约一百万次尝试，在最新的 CPU 和经过编译的应用程序上，这将需要不到一秒的时间。在相对旧一些的机器上它也只需要几秒钟的时间。

虽然我们已经开始讨论 bashcash 基础知识，但在继续讨论之前，让我们先领略一下 SHA 算法的强大功能。

SHA 有多么强大？
在一次被证明是密码界中具有重大意义的事件中，披露出一个对 SHA-0 的碰撞（collision）（请参阅参考资料中指向 Pascal Junod 的电子邮件的链接，它给出了实际碰撞的细节）。所使用的攻击需要大约 2^51 步，远远少于我们所期望的暴力构造碰撞所需要的大约 2^80 步（以及存储空间）（遵循“生日悖论（birthday paradox）；关于生日悖论以及如何将它应用于散列函数的更多信息的链接，请参阅参考资料）。

在过于担心这种与 bashcash 相关的攻击之前，要紧记两点：一是这种方法攻击的是 SHA-0，不是 SHA-1（目前还不是）。另一相关的保证是，在当前最快的 CPU 上，2^51 步需要的时间仍会超过 9 CPU 年。即便有类似的方法可以应用于 SHA-1，构造虚假碰撞的代价也不可能低于构造更大数量的 20-位戳记（或者甚至是 40-位 hashcash 戳记）。

回到我们先前的讨论。

hashcash（版本 1）格式
只有一个特定的 SHA-1 散列值是不够的。我们还希望戳记特定于被请求的资源 —— 也就是说，用于 mertz@gnosis.cx 的戳记应该与用于 someuser@yahoo.com 的戳记具有不同的适用性。如果不是这样，垃圾邮件制造者就可以只生成一个高比特值的戳记并到处去使用它。

另外，一旦生成戳记，我不希望每一个想给我发送邮件的垃圾邮件制造者都能共享它。所以，hashcash 采用了以下两个额外步骤（或者至少建议它们应该作为协议的一部分）：

• 首先，戳记携带一个日期。用户可能会决定认为比特定期限更早的戳记是非法的。
• 其次，hashcash 客户机可能（并且多半应该）实现一个 double spend 数据库。

在 double spend 数据库中，每一个戳记都只能使用一次；如果第二次收到它，那么就认为它是非法的（非常类似于邮票在使用后会被做标记）。具体地说，hashcash（版本 1）戳记类似于下面的代码：

1:bits:date:resource:ext:salt:suffix

戳记包括 7 个域。

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

现在让我们来看 bashcash 如何在电子邮件中起作用。

bashcash 如何在电子邮件中起作用
在理想的世界中，所有发送者都应该在他们的消息中包含 bashcash 标记；接收者在接收时都将检查它们的合法性。不过，在实际生活中，hashcash 还没有得到那么广泛的应用。虽然如此，开始使用 bashcash（不管是作为发送者还是作为接收者）并不会对现有电子邮件工具产生任何影响。换句话说，在电子邮件中使用 bashcash，您不会有任何损失。

为了给发出的消息加上戳记，只需要向电子邮件添加头文件即可：用于电子邮件的每一个 To: 或 Cc: 接收者的 X-Hashcash 头。例如，某个想给我发送消息的人可能会在消息中包含一个与示例 rfc2822 头文件类似的头文件：

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

显然，应该由 MUA（邮件用户代理，mail user agents）、过滤器或者 MTA（邮件传输代理，mail transport agents）来做这件事情，而不是要求用户手工完成。不过，手工完成也不太难，至少实验时如此。首先，通过查看戳记的散列来校验它，如下所示：

$ echo -n 1:20:040927:mertz@gnosis.cx::odVZhQMP:7ca28 | sha
00000b50b85a61e7ba8ac4d5fed317c737706ae5

注意前导零（每一个十六进制数是 4 个比特）。当然，还需要校验哪个资源是您识别出来的那个资源（比如您的收件人地址之一），那个戳记还没有被使用过，日期是当前日期。另外，一个合法的戳记拥有的前导零的数目应该与其声明要拥有的数目相同（不过您可以决定强制实行您自己的允许邮件通过的最小代价：20 比特是一个不完全标准（semi-standard），它最终可能会随着 Moore 定律而发生改变）。

为什么这会起作用？
生成一个 20-比特的戳记只需要几秒钟的时间。当您一天中只发送几十封电子邮件时，这个代价并不大。但是，对那些想要发送数百万消息的垃圾邮件制造者来说，不能容忍每条消息使用额外几秒的 CPU 时间。一天之中只有 86,400 秒。即使垃圾邮件制造者利用植入木马（trojans）的僵尸（zombies）的技术，需要使用具体的 hashcash 戳记至少也会减少那些僵尸进程的发出量。当然，校验一个戳记所需的时间只是一秒的一小部分。

另一方面，向您自己的 MUA 添加 hashcash 生成和校验对其他所有人没有任何负面影响（不像其他一些反垃圾邮件方法）。对那些不使用该协议的接收者而言，这些只是一个他们很容易忽略的附加头文件。对那些没有添加 hashcash 戳记的发送者而言，检验 X-Hashcash: 的接收者不用校验任何内容。如果发送者没有添加戳记，那么您的境况不会因为进行检验而变得更糟；也不会因此变得更好。

一个好的 MUA 或者垃圾邮件过滤系统可以将拥有合法 hashcash 戳记的电子邮件列入白名单（whitelist）。SpamAssassin 甚至更巧妙地为更多合法 hashcash 比特提供了更高的 +ve 分数。我认为，将基于 bashcash 的方法应用于白名单是对 TMDA 等交互式质询系统的改进 —— 质询消息在返回时不会丢失，发送者不会忘记响应质询。质询响应就在原始消息之中（作为一个 hashcash 戳记）。

hashcash 的其他应用
hashcash 对非交互式质询最为实用。不过，没有理由使得它不能同样用于交互式上下文中。随着更多工具增加了对 hashcash 的支持，尤其是 Mozilla 套件等多用途应用程序，在交互式和非交互式条件下使用 bashcash 都同样变得更加简单。

例如，如果 Thunderbird 邮件工具得到了进行 hashcash 计算的 API 调用，那么它应该直接让它的同属工具 Firefox Web 浏览器用与生成 hashcash 戳记的 API 去响应交互式质询。

什么是 Wiki? Wiki 是“可以运转的最简单的在线数据库”。它支持设计用于动态创建新页面和页面之间交叉链接的超链接和简单文本语法处理。 Wiki 是服务器软件，允许用户使用浏览器自由地构建和 编辑 Web 页面的内容，提供了一种“开放编辑”服务，从而促生了一种不同寻常的群组通信机制。它不仅允许所有用户编辑页面的内容，还允许用户编辑对页面或者站点做出贡献的组织。 要深入了解 Wiki，请参阅参考资料中关于“什么是 Wiki”的链接。

保护 Wiki
Wiki 有时会遭遇到与垃圾邮件十分类似的破坏，bashcash 在非电子邮件上下文中似乎是一个不错的解决方案。由于 Wiki 通常开放给任何人进行编辑，所以 Wiki 社区的灾难之一是 Wiki-crawling 破坏程序，它们向 Wiki 站点添加一些无关的商业链接。

我帮助维护的一个 Wiki 最近不断遭到恶意破坏，迫使我们做出了有些不受欢迎的回应，要求所有张贴者拥有一个用户帐号。这些帐号都是在一视同仁的基础上给出的，并根据自动使用电子邮件发送的质询来返回一个证明已经收到随机密钥的消息。不过，要求使用这样的帐号从根本上说与 Wiki 精神是相违背的。

添加 hashcash 质询并不能防止对 Wiki 站点的自动破坏，但是它可以使破坏行为变得更慢。如果破坏一个站点需要的时间是很多秒，而不是一秒的一小部分，那么检索 Wiki 找出无用信息就不那么引人注目了。实际上，我认为在这种应用中，使用大于 20-比特的传输率是一个好主意。也许 24 比特或 28 比特是合理的负荷（已经登录的用户仍然可以避开它）。

您可能会认为，在接受 Wiki 编辑时，普通的时间延迟会有类似效果，不过这种思维方式中有一个漏洞。破坏者可以并行化其破坏行为 —— 例如，如果每个站点添加了 5 秒的延迟，那个破坏者可以利用这 5 秒钟的时间来开始对其列表上的其他 Wiki 进行修改。通过要求保证有效 CPU 的利用率，比如使用 bashcash，破坏者再也不能并行地进行破坏。

Wiki 质询可以是交互式的，也可以是非交互式的。站点在将用户引导到实际的编辑屏幕之前，可以直接将用户引导到一个质询屏幕。可以生成一个随机资源来作为这个保护屏幕的质询。

不过，更好的方法是使这项要求具有非交互性。例如，在一个已有的 Wiki 系统中，可以使用与下方所示类似的 URL 来编辑某个资源：

http://somewhere.net/wiki?action=edit&id=SomeTopic

在一个假定使用 bashcash 进行保护的 Wiki 中，可能需要使用不同的 URL，比如：

http://somewhere.net/wiki?stamp=1:24:040928:SomeTopic:edit:KG4E9PaK2VLjKM2Z:0000Zbrc

在允许编辑之前，Wiki 服务器可以校验该戳记。不过，进行编辑不需要创建一个帐号和透露任何个人信息。double spending 和（可能持续时间较短）过期校验进一步为真正要进行编辑的行为提供了保证。对我而言，生成上面的 URL 并不难，使用下面的命令即可：

hashcash -mCb 24 -x edit SomeTopic

不过，通常，为了确保更少的延迟，Web 浏览器可能会选择在后台生成类似的戳记。例如，当我正在读取资源时，上述 URL 可能已经创建在高速缓存中：

http://somewhere.net/wiki?SomeTopic

或许还将缓存其他一些编辑戳记，将它们用于当前 Wiki 页所链接的页面。

检验 CPU 资源
hashcash 的一个交互式应用可能是用于分布式处理任务中。一些项目（比如 Great Internet Mersenne Prime Search（GIMPS））和 SETI@home 及其任务（比如蛋白质折叠和密码方面的难题）有时会借用大量的志愿者机器，这里只列出了其中少数项目和任务的名称。每个志愿者都只需要下载一些代码，并将其作为一项大任务的一部分来运行，然后将中间计算发回中央服务器即可。这些工作是对空闲 CPU 周期的极好利用。

我所知道的所有分布式任务几乎都允许任何人加入。不过，不难想像，对于有协同要求的任务而言，如果一个节点不能在期望的时间段内完成其任务，那么这个行动迟缓的节点对整体计算造成的损害要比它所做贡献多一些。

在这种情况下，应该要求每一个参与节点都有最小限度的 CPU 速度。虽然使用具体类型的计算来检验速度更为精确，不过，hashcash 还提供了一个相对通用的 CPU 基准。SHA-1 是一种非常典型的数学计算。如果参与节点已经安装了 hashcash（而不是一些定制的软件工具），那么，对 hashcash 质询的回答就可以作为一种“必须达到某种高度才能登堂入室（you must be this tall to enter this ride）”风格的校验。

校验 CPU 能力的方法是，要求在短期间内得到高比特值。只有足够快的 CPU 才能回答这个质询。为此，必须半交互式地提供资源名。否则，参与者完全可以迟签他们的日期戳的日期，制造出创建速度很快的假象。

例如，一个快速的 Pentium III 或者 G4 可以在不到一秒钟之内生成一个 20-比特的戳记，但是 Pentium-II 或者 G3 做不到。我们可以假定一个 32-比特的质询，试运行的候选机器必须在一个小时之内回答它。请求者可能会发一封电子邮件，说：“向我发送一个质询”；协同服务器作出响应：“时间是 040927124732；质询资源是 a37tQk。”如果服务器在当天下午的 1:47 之前得到了一个正确的散列，那么该请求者将获得访问该资源的资格。

显然，我所建议的协议不能确保在每个节点上都能真正地完成工作。即使是最快的机器，也可能会出现断电的意外情况。用户可能会改变他们运行分布式软件的想法。不过，至少可以证明其具备似乎可信的资格。

通用的 hashcash 以及我的贡献
从 hashcash 概念整体来看，具体域和分隔符的使用从某种程度上说是任意的。实际上，hashcash 版本 0 使用了与版本 1 不同的域。这些选择都很好，不过，我认为“实际的 hashcash”只是某个家族的一名成员，我们可能会称这个家族为“通用 hashcash”。也就是说，只要给定任何质询字符串，都可以合理地提出以下要求：“给我一个后缀，一旦 challenge+suffix 被散列，它将生成 b 比特的碰撞”。真正的 hashcash 只不过是这种通用质询的一个实例。

现在，确实存在过于通用的问题。创建很多不兼容的、近似 bashcash 的协议实际上对谁都没有好处。例如，有一个“hashcash”的 Python 实现，使用了一个与 bashcash 有一点类似的质询协议（可能对加密价值而言也是如此），但是几乎不能使用它生成 hashcash 戳记。

所以，我决定编写一个真正适应的 bashcash 的 Python 实现，它甚至可以接受与用 C 编写的 hashcash 工具大致相同的命令行开关（不过，可能最为实用的是作为一个导入模块用于其他应用程序）。即使是在得到了 Psyco-ization 的帮助（只是一点点）的平台上，Python 版本最快运行也要比优化的 C 版本慢 10 倍。不过与 C 相比，它在灵活性方面依然可以胜出。

除了正确无误，我的 hashcash.py 模块还提供了一个内部函数 _mint() 以及一个公共函数 mint()。后者生成真正的 hashcash 版本 1 戳记。那是您应该使用的。

不过，前者，即 _mint()，完成了寻找 generalized hashcash 后缀的底层工作。您可能不应该使用它，但是，如果您想要使用它（并且保证您会小心使用它），它就在那里，您可以使用。

在不同寻常的上下文中，bashcash 的变种可能很实用。无论如何，我希望 C 工具有类似的开关，即使是在 man 页中有关于您为什么不应该那样做的危险警告，它们也能够找到通用的 hashcash 后缀。我们电脑黑客喜欢深入到事物内部。

结束语
我希望本文已经使您大致了解可能的 bashcash 应用程序。我觉得前面介绍的质询协议是一个极为巧妙的构思。现在面临的挑战是如何获得更多可以更无缝地处理 bashcash 戳记的工具。

有很多 MUA、MTA 以及垃圾邮件过滤工具在使用 bashcash 方面已经做得很好，不过它们之间仍然存在明显的鸿沟。几乎没有任何非电子邮件应用程序使用 bashcash。不过，我相信这个概念是具有吸引力的。

如果这个概念的重要性与日俱增，那么它将会提供一个与自由软件和开放标准完全相容的调节访问电子资源的方法，该方法不会让我们陷入数码限制管理（digital restrictions management，DRM）、信息商业化以及常见的隐私泄漏的麻烦之中。

参考资料

• 您可以参阅本文在 developerWorks 全球站点上的 英文原文。
  
  
• 请访问 hashcash.org Web 站点。
  
  
• David 永远喜爱的参考资料是 Wikipedia，它有一个 hashcash 栏目。要了解 Wiki，首先要了解 什么是 Wiki。
  
  
• 生日悖论 是惟一一个理解起来与通常直觉相反的悖论。请阅读更多关于 Wikipedia 资料。
  
  
• 关于 SHA-0 碰撞的细节，请参阅密码学邮件存档（Mail Archive）中 Pascal Junod 的电子邮件。
  
  
• 指南 密码学简介：第 1 部分 （developerWorks，2001 年 1 月）向您介绍了密码学以及它的技术、数学和概念基础、术语。 密码学简介：第 2 部分 （developerWorks，2001 年 2 月）和 密码学简介：第 3 部分 （developerWorks，2001 年 3 月）是课程的继续。
  
  
• 要全面了解用于过滤垃圾邮件的实用工具，请阅读 用 SpamAssassin 消灭垃圾邮件 （developerWorks，2002 年 10 月）。
  
  
• Tagged Message Delivery Agent (TMDA) 是一个基于白名单而不是黑名单的垃圾邮件过滤工具；hashcash 可以与 TMDA 集成在一起。
  
  
• 下载 David 的 hashcash.py 模块和脚本， Hashcash 版本 1 的 Python 实现。
  
  
• 要深入了解 Python，请阅读 developerWorks 上 David 撰写的其他 developerWorks 上所有可爱的 Python 专栏文章。
  
  
• 在 Roaming charges: Trouble everyday （developerWorks，2004 年 10 月）中，Larry Loeb 描述了散列碰撞并研究了安全散列算法。
  
  
• Enhancing e-mail security with S/MIME 详细描述了作为 S/MIME 电子邮件安全协议（e-mail-security protocol）中散列算法的 SHA-1 算法的作用。
  
  
• Lessons in secure messaging using Domino 6 （developerWorks，2004 年 7 月）给出了 SHA-1 作为散列算法关键角色的另一个观点。
  
  
• 在 Developer Bookstore Linux 专栏中定购 打折出售的 Linux 书籍。
  
  
• 可以从 developerWorks 的 Speed-start your Linux app 专区下载运行于 Linux 之上的 IBM 中间件产品的免费测试版本，其中包括 WebSphere® Studio Site Developer、WebSphere SDK for Web services、WebSphere Application Server、 DB2® Universal Database Personal Developers Edition、Tivoli® Access Manager 和 Lotus® Domino Server。要更迅速地上手，请参阅针对各产品的 how-to 文章和技术支持。
  
  
• 通过参与 developerWorks blogs 加入 developerWorks 社区。
  
  
• 在 developerWorks Linux 专区中，可以找到更多为 Linux 开发人员准备的参考资料。
  

关于作者 David Mertz 是完全图灵的（Turing complete），但可能却通不过图灵测试（Turing Test）。要深入了解他的生活，请访问其个人主页。从 2000 年起，他一直负责撰写 developerWorks 专栏 Charming Python 和 XML Matters。请参阅他撰写的 Text Processing in Python 一书

本文原地址：

http://www-900.ibm.com/developerworks/cn/linux/l-hashcash.shtml?ca=dwcn-newsletter-linux
http://www.ibm.com/developerworks/linux/library/l-hashcash.html

,