区块链基础——密码学哈希函数基本概念

密码学哈希函数

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

密码学哈希函数: 满足以下两种情况在计算上不可行的哈希函数. 1) 对已知Hash值找到对应的数据M; 2) 找到两个不同的数据M对应相同的Hash值.

密码学Hash函数的安全性需求

输入长度可变

输出长度固定

效率: 对任意给定的 x, 计算 H(x) 比较容易, 用硬件软件均可实现.

抗原像攻击(单向性): 对给定的Hash值 h, 找到满足 H(x) = h 的 x 在计算上是不可行的.

抗第二原像攻击(抗弱碰撞性): 对任何给定的 x, 找到满足 y ≠ x 且 H(x) = H(y) 的 y 在计算上是不可行的.

抗碰撞攻击(抗强碰撞性): 找到任何满足 H(x) = H(y) 的偶对 (x, y) 在计算上是不可行的.

伪随机性: H 的输出满足伪随机性测试标准.

穷举攻击

相关问题:给定一个有 n 种可能的输出的哈希函数 H 以及一个特定的哈希值 H(x), 对于 H 的 k 个随机输入, k 的值为多少时才能保证至少存在一个 y 使得 H(y) = H(x) 的概率是 0.5.

对于一个单一的值 y, H(y) = H(x) 的概率是 1/n. 相反, H(y) != H(x) 的概率就是 1 - 1/n. 如果生成 k 个随机的 y 值, 这些值全都不满足 H(y) = H(x) 的概率就是. 那么至少有一个值满足的概率就是.

根据二项式定理:

a 很小时, 展开式可以近似为 1 - ka. 那么至少有一个值满足的概率就可以近似为

为了使概率为 0.5, 可以令 k = n / 2.

对于一个 m 比特的哈希码, 可能的编码数为, 那么对应 k 的值就是.

生日悖论

求最小的 k 值使得在一个 k 个人的群组中至少有两个人的生日相同的概率大于 0.5 (忽略2月29号并假设对于一个人的生日日期是等概率的).

任意两个人的生日不同的概率是 364/365. 第三个人和前两个人的生日都不同的概率是 363/365,第四个人与前三个人的生日都不同的概率是 362/365,以此类推, 直到第24个人与前面的人生日都不同的概率是 342/365.把这23个概率乘起来得到的值大约为 0.507, 稍稍大于 0.5.

为了更形式化地描述这个问题, 定义 P(n, k)为假设共有 n 天, 取 k 个人, 其中至少有两个人的生日相同的概率.

从而问题就可以表示为求解满足 P(365, k) ≥ 0.5 的 k 的值.

首先可以定义 Q(365, k) 为没有人生日相同的概率, 假设 k ≤ 365 (如果 k ≥ 365 不可能使所有值都不同). 用 N 表示对于 k 个人在没有两个人生日相同的情况下有多少种可能, 根据排列组合

从而得到:

利用生日悖论进行碰撞攻击

  该策略由Gideon Yuval在1979年提出[1]. 其基本的思想是攻击者通过构造多个已知合法消息(发送者已经签名的消息)的变式和伪造消息的变式, 进而找到这两组消息之间的一对碰撞,然后让发送者对合法消息的变式进行签名, 这样也就得到了伪造的非法消息的哈希值(因为和的哈希值相同). 然后攻击者发送伪造的消息以及发送者对的签名, 从而达到欺骗接收者的目的.

发送方A准备对文本消息 x 进行签名, 其使用的方法是: 用A的私钥对 m位的Hash码加密并讲加密后的Hash码附于消息之后.

攻击者产生该(合法)消息 x 的种变式, 且每一种变式表达相同的意义, 将这些消息以及对应的Hash值存储起来.

攻击者准备伪造一条消息 y, 并想获取A的签名.

攻击者再产生该伪造(非法)消息 y的消息变式, 每个变式与 y表达相同的意义. 对于每个, 攻击者计算, 并与任意的进行比对, 重复这一过程直到碰撞出现. 即这一过程直到找到一个与某个具有相同的Hash值.

攻击者将该合法消息变式提供给A签名, 将该签名附于伪造消息的有效变式后并发送给预期的接收方. 因为上述两个变式的Hash码相同, 所以它们产生的签名也相同, 因此攻击者即使不知道加密密钥也能攻击成功.

对长度为 m的Hash码, 对于穷举攻击所需的代价分别与下表中相应量成正比.

如果要求抗强碰撞能力, 那么值决定了该Hash码抗穷举攻击的强度.

References

Gideon Yuval. HOW TO SWINDLE RABIN[J]. Cryptologia, 1979, 3(3):187-191.

WilliamStalings. 密码编码学与网络安全:原理与实践[M]. 电子工业出版社, 2001.