区块链基础 安全散列算法
背景介绍
安全散列算法(Secure Hash Algorithm, SHA)是目前使用最为广泛的Hash函数.SHA由美国国家标准与技术研究院(NIST)设计, 并在1993年作为联邦信息处理标准(FIPS 180)发布第一个版本(SHA-0). 随后SHA-0被发现存在缺陷, 1995年发布了关于SHA-0的修订版(SHA-1)(FIPS 180-1). SHA-1产生160位的Hash值. 2002年, NIST发布了修订版(FIPS 180-2), 给出了三种新的SHA版本, Hash值长度依次为256位, 384位和512位(SHA-256, SHA-384, SHA-512), 这些算法被统称为SHA-2.
王小云教授在2005年分别在Eurocrypt和Crypto学术会议上提出了对MD5[1]以及SHA-1[2]的攻击方式. 由于SHA-2, SHA-1, MD5, MD4这些算法有着类似的结构框架和基本数学运算, 随着SHA-1, MD5等算法的缺陷被发现, SHA-2的安全性也受到了怀疑. 因此在2007年, NIST宣布公开征集新一代Hash函数标准(SHA-3). 2012年10月, NIST公布了SHA-3设计作品中的优胜者(Keccak算法), 并将SHA-3作为新一代密码学Hash函数的标准, 目前SHA-3已经在逐步取代其他的Hash算法, SHA-3也是目前区块链中应用最广泛的Hash算法.
2017年2月23日Google宣布提出了第一个实用的能够产生SHA-1碰撞的方法(https://security.googleblog.com/2017/02/announcing-first-sha1-collision.html)
海绵结构
SHA-3的设计者将SHA-3使用的基本迭代结构成为海绵结构[3, 4]. 在海绵函数中, 输入消息被分块为固定长度的分组. 每个分组逐次作为每轮迭代的输入, 同时上轮迭代的输出也反馈至下轮的迭代中, 最终产生一组输出块. 海绵函数结构灵活, 允许可变的输入输出长度, 因此可以被用来设计Hash函数、伪随机数发生器以及其他密码函数.
海绵函数由三组参数定义:
f 为内部函数, 用于处理每轮的输入分组.
r 为输入分组的位长度, 称其为位速率(bitrate).
pad 为填充算法
如下图所示, 长度为 n 位的输入消息, 被分为 k 个固定长度的分组, 每个分组长度为r位. 如果需要, 消息将被填充以满足填充后的长度是r位的整数倍. 分组后的结果是, 其中 n = k × r. 为了格式统一, 任意消息都需要进行填充. 因此如果 n = 0 (mod r), 那么将填充一个 r 位的完整块. 填充算法实质上是作为海绵函数的一个参数.
在海绵结构的实现建议中, 给出了两个填充方案:
简单填充: 用pad10*表示, 用一个 1 后面跟若干个 0 进行填充, 0 的个数是使得总长度为分组长度整数倍的最小值.
多重位速率填充: 用pad10*1表示, 用一个 1 后面跟若干个 0, 再跟一个 1 进行填充, 0 的个数是使得总长度为分组长度整数倍的最小值. 这是在安全地采用不同位速率r使用相同的f时, 最简单的填充方法.
如下图所示, 在对所有的分组操作完后, 海绵函数产生一组输入块. 产生的输出数据块的个数由需要的输出位数所决定. 如果需要 l 位输出, 则产生 j 个输出块, 其中 (j - 1) × r ＜ l ＜ j × r.
下图给出了海绵函数的迭代结构. 海绵结构对于长度为 b = r + c 位的状态变量 s 进行操作, 状态变量的初值全部置为 0, 其取值在每轮迭代中更新. 数值 r 称为位速率, 该值是输入消息的分组长度. 位速率反映了每轮迭代中处理的位数: r 越大, 海绵结构处理消息的速度就越快. 数值 c 称为容量. 本质上容量是度量海绵结构能够达到的复杂程度以及安全度. 在实际应用中可以通过降低速度来提高安全性, 增大容量 c 的取值, 减小位速率 r 的取值, 反之亦然. Keccak的默认选择是 c = 1024, r = 576, 于是 b = 1600.
海绵结构包括两个阶段。吸水阶段过程如下: 对于每轮迭代, 通过填充若干个 0, 将输入数据块的长度从 r 位扩展为 b 位; 然后将扩展后的消息分组和 s 进行 XOR 异或运算得到 b 位的结果, 并作为迭代函数 f 的输入; f 函数的输出作为下一轮迭代中 s 的取值.
如果需要的输出长度满足 l ≤ b , 那么在吸水阶段完成后, 则返回 s 的前 l 位, 海绵结构的运行结束. 否则, 海绵结构进入挤压阶段. 首先, s 的前 l 位被保留作为输出分组, 然后在每轮迭代中通过重复执行 f 函数来更新 s 的值, s 的前 l 位被依次保留作为输出分组, 并与前面已生成的分组连接起来. 该处理过程共需要 j - 1次迭代, 直到满足 (j - 1) × r ＜ l ＜ j × r. 这时候将各输出分组连接 Y 的前 l 位作为输出返回.
如果需要的输出长度小于或等于输入的分组长度， 即 l ≤ r. 这种情况下海绵结构会在吸水阶段完成后直接结束. 如果需要的输出长度超过 b 位, 则需要执行挤压阶段的操作.
Reference
Wang X, Yu H. How to Break MD5 and Other Hash Functions[M]// Advances in Cryptology – EUROCRYPT 2005. DBLP, 2005:19-35.
Wang X, Yin Y L, Yu H. Finding Collisions in the Full SHA-1[J]. Crypto, 2005, 3621:17-36.
Bertoni G, Daemen J, Peeters M, et al. Sponge Functions[J]. Ecrypt Hash Workshop, 2007.
Guido B, Joan D, Micha?l P, et al. Cryptographic sponge functions[J]. 2011.
WilliamStalings. 密码编码学与网络安全:原理与实践[M]. 电子工业出版社, 2001.
- 发表于:
- 原文链接：https://kuaibao.qq.com/s/20180611G10Y5C00?refer=cp_1026
- 腾讯「腾讯云开发者社区」是腾讯内容开放平台帐号（企鹅号）传播渠道之一，根据《腾讯内容开放平台服务协议》转载发布内容。
- 如有侵权，请联系 cloudcommunity@tencent.com 删除。
相关快讯
扫码
添加站长 进交流群
领取专属 10元无门槛券
私享最新 技术干货
腾讯云开发者
