区块链基础-哈希函数

2018年07月10日

概念

Hash（哈希或散列）算法是非常基础也非常重要的计算机算法。它能将任意长度的二进制明文串映射为较短的（通常是固定长度的）二进制串（Hash 值），并且不同的明文很难映射为相同的 Hash 值。

例如,计算一段话 “Hi, this is alphajon” 的 SHA-256 hash 值。

$ echo "Hi, this is alphajon"|shasum -a 256
f91a7a52d470212be48285f6c8f6a656e71b32e063869db48062ff54121c8404

这意味着对于某文件，只要其 SHA-256 Hash 计算后同样为 f91a7a52d470212be48285f6c8f6a656e71b32e063869db48062ff54121c8404，则文件内容极大概率上就是 “Hi, this is alphajon”。

Hash 值在应用中又常被称为指纹（fingerprint）或摘要（digest）。Hash 的核心思想也经常被应用到基于内容的编址或命名算法中。

数学定义

哈希函数: 以不定长数据为输入, 产生固定长度的Hash值 h = H(M).

密码学哈希函数: 满足以下两种情况在计算上不可行的哈希函数.

1) 对已知Hash值找到对应的数据M;

2) 找到两个不同的数据M对应相同的Hash值.

特点

一个优秀的 Hash 算法，具有如下特点：

  • 正向快速：给定明文和 Hash 算法，在有限时间和有限资源内能计算得到 Hash 值；
  • 逆向困难：给定（若干）Hash 值，在有限时间内很难（基本不可能）逆推出明文；
  • 输入敏感：原始输入信息发生任何改变，新产生的 Hash 值都应该出现很大不同；
  • 冲突避免：很难找到两段内容不同的明文，使得它们的 Hash 值一致（发生碰撞）。

冲突避免有时候又被称为“抗碰撞性”，分为“弱抗碰撞性”和“强抗碰撞性”。如果给定明文前提下，无法找到与之碰撞的其它明文，则算法具有“弱抗碰撞性”；如果无法找到任意两个发生 Hash 碰撞的明文，则称算法具有“强抗碰撞性”。

哈希算法举例

目前常见的 Hash 算法包括 MD5 和 SHA 系列算法。

MD4（RFC 1320）是 MIT 的 Ronald L. Rivest 在 1990 年设计的，MD 是 Message Digest 的缩写。其输出为 128 位。MD4 已证明不够安全。

MD5（RFC 1321）是 Rivest 于 1991 年对 MD4 的改进版本。它对输入仍以 512 位进行分组，其输出是 128 位。MD5 比 MD4 更加安全，但过程更加复杂，计算速度要慢一点。MD5 已被证明不具备“强抗碰撞性”。

SHA（Secure Hash Algorithm）并非一个算法，而是一个 Hash 函数族。NIST（National Institute of Standards and Technology）于 1993 年发布首个实现。目前知名的 SHA-1 算法在 1995 年面世，它的输出为长度 160 位的 Hash 值，抗穷举性更好。SHA-1 设计时模仿了 MD4 算法，采用了类似原理。SHA-1 已被证明不具备“强抗碰撞性”。

为了提高安全性，NIST 还设计出了 SHA-224、SHA-256、SHA-384，和 SHA-512 算法（统称为 SHA-2），跟 SHA-1 算法原理类似。SHA-3 相关算法也已被提出。

目前，MD5 和 SHA1 已经被破解，一般推荐至少使用 SHA2-256 或更安全的算法。

注：MD5 是一个经典的 Hash 算法，其和 SHA-1 算法都被认为安全性已不足应用于商业场景。

一般情况下，Hash 算法多是计算敏感型。意味着计算资源是瓶颈，主频越高的 CPU 进行 Hash 的速度也越快。因此可以通过硬件加速来提升 Hash 计算的吞吐量。例如采用 FPGA 来计算 MD5 值，可以轻易达到数十 Gbps 的吞吐量。

也有一些 Hash 算法不是计算敏感型的。例如 scrypt算法，计算过程需要大量的内存资源，节点不能通过简单地增加更多 CPU 来获得 Hash 性能的提升。这样的 Hash 算法经常被应用到避免算力攻击的场景下。

哈希算法应用

Hash 算法并不是一种加密算法，不能用于对信息的保护。

但 Hash 算法常被应用到对口令的保存上。例如用户登录网站需要通过用户名和密码来进行验证。如果网站后台直接保存用户的口令明文，一旦数据库发生泄露后果不堪设想。大量用户倾向于在多个网站选用相同或关联的口令。

利用 Hash 的特性，后台可以仅保存口令的 Hash 值，这样每次比对 Hash 值一致，则说明输入的口令正确。即便数据库泄露了，也无法从 Hash 值还原回口令，只有进行穷举测试。

然而，由于有时用户设置口令的强度不够，只是一些常见的简单字符串，如 password、123456 等。有人专门搜集了这些常见口令，计算对应的 Hash 值，制作成字典。这样通过 Hash 值可以快速反查到原始口令。这一类型以空间换时间的攻击方法包括字典攻击和彩虹表攻击（只保存一条 Hash 链的首尾值，相对字典攻击可以节省存储空间） 等。

为了防范这一类攻击，一般采用加盐（Salt）的方法。保存的不是口令明文的 Hash 值，而是口令明文再加上一段随机字符串（即“盐”）之后的 Hash 值。Hash 结果和“盐”分别存放在不同的地方，这样只要不是两者同时泄露，攻击者就很难破解了。