科普 | 哈希函数的过去、现在与未来

科普 | 哈希函数的过去、现在与未来
哈希值和哈希函数的概念是初次入门区块链的人常听到的两个关键词,而且似乎对安全性来说特别关键 。(实际上也确实是 。)对于像比特币和以太坊这样由成千上万的节点通过 P2P 方法组成的去中心化网络来说,“免信任性” 和验证效率无疑是关键 。也就是说,这些系统需要找到方法把信息编码成紧凑的形式,同时让参与者能够安全快速地进行验证 。
比特币和以太坊网络所处理的主要内容叫做 “区块”,指的是由交易、时间戳和其他重要元数据所组成的数据结构 。比特币和以太坊网络的安全性的关键一环是:它能将表达网络全局状态的大块信息压缩成一个简短的消息 。在有需要之时,我们可以高效地验证这个消息的真实性 。这个过程就是用哈希函数来完成的,而得到的结果(消息)就是哈希值 。

科普 | 哈希函数的过去、现在与未来

文章插图
- 即使只更改输入中的一个字符,最后得出的哈希值也会完全不同 -
密码学哈希广泛应用于口令存储和文件验证系统 。简单来说,密码学哈希函数是一种确定性的算法,不论输入什么值,都能得到一个固定长度的字符串 。也就是说,同一个输入值始终对应同一个输出值 。
对哈希函数来说,重要的不仅是确定性(还有结果的随机性):即使只更改输入中的一个比特位,也会导致最终得到的哈希值截然不同 。
哈希算法有一个无可回避的问题叫碰撞可能性 。因为哈希值是固定长度的字符串,同一个输出哈希值有可能对应多个输入 。碰撞会造成很严重的后果 。如果有人能够按需要发起碰撞攻击,他就可以用恰当的哈希值将恶意文件或数据伪装成合法的、能够通过验证的文件 。好的哈希函数的设计目标是让攻击者极难找到方法来找出对应同一个哈希的不同输入 。
哈希计算的效率不应过高,以免让攻击者可以更简单地人为计算出碰撞 。哈希算法必须能够抵御“原像攻击(pre-image )” 。也就是说,对于特定哈希值,攻击者很难通过确定性计算步骤倒推出输入值(即,原像) 。
假设 s = hash(x),倒推 x 应该是近乎不可能的 。
总的来说,“好的” 哈希算法需要具备以下 3 个特性:
破解哈希算法
哈希算法的初始标准之一是 MD5 哈希 。MD5 哈希广泛应用于文件完整性验证(校验和),以及在网络应用数据库中存储经过哈希计算的账号口令 。MD5 的功能非常简单,因为它会将每个输入转换成一个固定的 128 位字符串输出,并通过多轮简单的单向操作来计算确定性输出 。由于输出值长度较短,操作又较为简单,MD5 很容易被破解,一种常见的攻击方法叫生日攻击 。
“生日攻击” 是啥玩意?
你有没有听说过这样一个事实?如果你将 23 个人放到一个房间里,其中两个人生日相同的概率为 50%。如果将 70 个人放到一个房间里,其中两个人生日相同的概率高达 99.9%。这就是我们所说的鸽笼原理( ),即,将 100 只鸽子装进 99 个鸽笼,必然有两只鸽子分享同一个鸽笼 。也就是说,固定长度的输出意味着所有输入输出组合中一定存在碰撞 。
科普 | 哈希函数的过去、现在与未来

文章插图
- 笼子不够时,鸽子就会凑对 -
事实上,MD5 的抗碰撞性太差,以至于一台家用 2.4 GHz 奔腾处理器都能在几秒内计算出哈希碰撞 。此外,由于 MD5 在互联网早期阶段得到了广泛应用,网络上有大量 MD5 原像遭到泄漏,通过谷歌搜索它们的哈希值就能找到 。
哈希算法的多样性发展 源起:SHA1 和 SHA2