Hash 算法与数字摘要

定义

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

例如计算一段话 “hello blockchain world, this is yeasy@github” 的 SHA-256 hash 值。

$ echo "hello blockchain world, this is yeasy@github"|shasum -a 256
db8305d71a9f2f90a3e118a9b49a4c381d2b80cf7bcef81930f30ab1832a3c90

这意味着对于某个文件，无需查看其内容，只要其 SHA-256 Hash 计算后结果同样为 db8305d71a9f2f90a3e118a9b49a4c381d2b80cf7bcef81930f30ab1832a3c90，则说明文件内容极大概率上就是 “hello blockchain world, this is yeasy@github”。

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

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

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

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

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

results matching ""

    No results matching ""