区块链与哈希函数

目录

哈希函数

定义

性质

发展

常见攻击方法

1.穷举攻击

2.生日攻击

3.其他攻击

构造方法

1.利用对称密码体制来设计哈希函数

2.直接设计哈希函数

​编辑

常用哈希函数简介

1.SHA-256算法

​编辑

2.Keccak算法

3.SM3算法

哈希函数在区块链中的应用

1.以太坊用户地址的生成

2.默克尔哈希树

3. 挖矿难度的设置

4. 数字签名

5. 软件发布

哈希函数 定义

哈希函数：是一公开函数。用于将任意长的消息M映射为较短的、固定长度的值H（M），又称为散列函数、杂凑函数。我们称函数值H（M）为哈希值、杂凑值、杂凑码、信息摘要。

杂凑值是信息中所有比特的函数，因此提供了一种错误检测能力，即改变信息中任何一个比特或几个比特都会使杂凑值改变

性质

前三条实用性要求，后三条安全性要求

• H 可以作用于任意一个长度的数据块（实际上不是任意的，比如SHA-1要求不超过2^64）
• H 产生一个固定长度的输出（比如SHA-1的输出是160比特，SHA-256的输出是256比特）
• 对任意给定的x，H（x）计算相对容易，无论是软件还是硬件实现
• 单向性（抗原像）（one-way）：对于任意给定的消息，计算其哈希值容易。但是，对于给定的哈希值H，要找到M使得H（M）=H在计算上是不可行的。即给定消息可以产生一个哈希值，而给定哈希值不可能产生对应的消息；否则, 设传送数据 C =< M,H(M||K)>，K是密钥。攻击者可以截获C，求出哈希函数的逆，从而得出H^-1(C)，然后从M 和M‖K即可得出K
• 弱抗碰撞（抗二次原像）（Weakly Collision-Free）：对于给定的消息x，要发现另一个消息y，满足H（x）=H（y）在计算上是不可行的。是保证一个给定的消息的哈希值不能找到与之相同的另外的消息，即防止伪造。否则，攻击者可以劫获报文M及其哈希值H（M），并找出另一报文M'，使得H（M）=H（M'）。这样攻击者可以用M'去冒充M。
• 强抗碰撞（Strongly Collision-Free）：找任意一对不同的消息x、y，使H（x）=H（y）在计算上是不可行的。是对已知的生日攻击方法的防御能力，强抗碰撞自然包含弱抗碰撞。（？）

 图：哈希函数强碰撞性示意图

发展

 

 图：哈希函数结构示意图

• 1978年，Merkle和Damagad设计MD迭代结构
• 1993年，来学嘉和Messay改进加强MD结构；
• 在90年代初 MIT Laboratory for Computer Science和RSA数据安全公司的Rivest设计了散列算法MD族，MD代表消息摘要.
• MD族中的MD2、MD4和MD5都产生一个 128位的信息摘要
• MD2(1989年)
• MD4(1990年)
• MD5(1991年)：由美国密码学家罗纳德ꞏ李维斯特(Ronald Linn Rivest)设计，经MD2、MD3和 MD4发展而来，输出的是128位固定长度的字符串.
• RIPEMD-128/160/320：国际著名密码学家Hans Dobbertin的在1996年攻破了MD4算法的同时， 也对MD5的安全性产生了质疑，从而促使他设计了一个类MD5的RIPEMD-160. 在结构上， RIPEMD-160可以视为两个并行的类MD5算法，这使得RIPEMD-160的安全性大大提高.
• 值得注意得是，MD4， MD5已经在2004年8月Crypto2004 上，被我国密码学者王小云等破 译，即在有效的时间内找到了它们的大量碰撞

• SHA-0：正式称作为SHA，这个版本在发行后不久被指出存在弱点
• SHA-1：是NIS于1994年发布的，它于MD4与MD5算法非常相似，被认为是MD4和MD5的后继者
• SHA-2：实际上分为SHA-224、SHA-256、SHA384、SHA-512算法

 图：SHA系列哈希函数相关参数比较

图：哈希函数碰撞攻击复杂度示意图（单位：年）

常见攻击方法 1.穷举攻击

（a）原像攻击和第二原像攻击（Preimage or Second Preimage attack）

• 对于给定的哈希值h，试图找到满足H（x）=h的x
• 对于m位的哈希值，穷举规模大约是2^m

（b）碰撞攻击（Collision Resistance）

• 找到两个信息x不等于y，满足H(x) = H(y)
• 对于m位的哈希值，平均预计在2^m/2次尝试后就找到两个具有相同哈希值的数据

（c）因此对于m位的哈希值，抗穷举攻击的强度为2^m/2：

• 目前128比特已经不够，需要160比特甚至更多

2.生日攻击

情景：考虑教室有30位同学，定义函数 H: {张三,李四,ꞏꞏꞏꞏꞏꞏ|在教室里的同学}→{1,2, ꞏꞏꞏꞏꞏꞏ,365}， 如果有两个同学的生日相同，则称为一个“碰撞”. 直观看来，产生碰撞的可能性较小. 但是, 对于30个人的人群，这个事情发生的可能性大约为1/2.当人数增加时，这个可能性就增大. 这 个事实与我们的直观相悖, 称为”生日悖论”.

生日悖论是指在不少于 23 个人中至少有两人生日相同的概率大于 50%。例如在一个 30 人的小学班级中，存在两人生日相同的概率为 70%。对于 60 人的大班，这种概率要大于 99%。从引起逻辑矛盾的角度来说，生日悖论是一种 “佯谬”。但这个数学事实十分反直觉，故称之为一个悖论。生日悖论的数学理论被应用于设计密码学攻击方法——生日攻击。

生日悖论普遍的应用于检测哈希函数：N 位长度的哈希表可能发生碰撞测试次数不是 2N 次而是只有 2N/2 次。这一结论被应用到破解密码哈希函数 (cryptographic hash function) 的 “生日攻击” 中。 

总结：对于n位的哈希值，只要尝试2^n/2次，就至少存在一对x和x'，使得H（x）和H（x'）相同

3.其他攻击

• 利用算法的某种特性进行攻击
• 哈希函数的迭代结构：将消息分组后分别进行处理
• 密码分析的攻击集中于压缩函数 f 的碰撞

构造方法 1.利用对称密码体制来设计哈希函数

分组密码的工作模式是：根据不同的数据格式和安全性要求， 以一个具体的分组密码算 法为基础构造一个分组密码系统的方法.基于分组的对称密码算法比如DES/AES算法只是描述 如何根据秘钥对一段固定长度(分组块)的数据进行加密，对于比较长的数据，分组密码工作模 式描述了如何重复应用某种算法安全地转换大于块的数据量.

简单的说就是，DES/AES算法描述怎么加密一个数据块，分组密码工作模式描述了如果 重复加密比较长的多个数据块. 常见的分组密码工作模式有五种：电码本( Electronic Code Book， ECB)模式、密文分组链接(Cipher Block Chaining，CBC)模式、密文反馈(Cipher Feed Back ， CFB)模式、输出反馈(Output Feed Back ，OFB)模式和计数器(Counter, CTR)模式

（1）ECB工作模式

加密：输入的是当前明文分组

解密：每一个密文分组分别解密

公式：，

 （2）CBC工作模式

加密：输入是当前铭文分组和前一次密文分组的异或

解密：每一个密文分组被解密后，再与前一个密文分组异或得明文

公式：

 

 （3）CFB工作模式

•  加密算法的输入是64比特移位寄存器，其 初值为某个初始向量IV.
• 加密算法输出的最左(最高有效位)j比特与 明文的第一个单元P1进行异或，产生出密 文的第1个单元C1，并传送该单元.
• 然后将移位寄存器的内容左移j位并将C1送 入移位寄存器最右边(最低有效位)j位.
• 这一过程继续到明文的所有单元都被加密 为止.

 

 （4）OFB工作模式

• 工作模式类似CFB
• 不同：OFB模式是将加密算法的输出反馈到移位寄存器；CFB模式中是将密文单元反馈到移位寄存器

 （5）CTR工作模式

加密：输入是当前明文分组和计数器密文分组的异或

解密：每一个密文分组被解密后，再与计数器密文分组异或得到明文

公式：

 

5种工作模式的比较 

• ECB模式，简单、高速，但最弱、易受重发攻击，一般不推荐.
• CBC模式适用于文件加密，比ECB模式慢.安全性加强. 当有少量错误时，不会造成同步错误.
• OFB模式和CFB模式较CBC模式慢许多. 每次迭代只有少数比特完成加密. 若可以容忍少量错 误扩展，则可换来恢复同步能力，此时用CFB或OFB模式. 在字符为单元的流密码中多选 CFB模式.
• CTR模式用于高速同步系统，不容忍差错传播.

下面利用对称密码来构造哈希函数，我们规定：

1.1基于分组密码的CBC工作模式杂凑函数

1.2基于分组密码的CFB工作模式杂凑函数

 

 总结：上述两种基于分组密码的杂凑函数中，K可以公开，称为不带密钥的哈希函数；k也可以不公开，称为带密钥的哈希函数（MAC）。在K公开的情况下，上述两种构造杂凑函数的方法是不安全的，容易找到碰撞。这是为什么呢？

2.直接设计哈希函数

• Merkle在1989年提出迭代型哈希函数的一般结构；(另外一个工作是默克尔哈希树)
• Ron Rivest在1990年利用这种结构提出MD4；(另外一个工作是RSA算法)
• 这种结构在几乎所有的哈希函数中使用，具体做法为：
  • 把所有消息M分成一些固定长度的 块Yi；
  • 最后一块padding并使其包含消息 M的长度；
  • 设定初始值CV0；
  • 循环执行压缩函数f，CVi=f(CVi - 1||Yi -1)；
  • 最后一个CVi为哈希值

•  算法中重复使用一个压缩函数f ；
• f 的输入有两项，一项是上一轮输出的n比特值CVi-1，称为链接变量，另一项是算法在本轮 的b比特输入分组Yi-1 ；
• f 的输出为n比特值CVi，CVi又作为下一轮的输入；
• 算法开始时还需对链接变量指定一个初值IV，最后一轮输出的链接变量CVL即为最终产生的 杂凑值；
• 通常有b>n，因此称函数f为压缩函数.
• 算法可表达如下：CV0=IV= n比特长的初值；
• CVi=f(CVi-1,Yi-1)；1≤i≤L；
• H(M)=CVL
• 算法的核心技术是设计难以找到碰撞的压缩函数f，而敌手对算法的攻击重点是f 的内部结构；
• f 和分组密码一样是由若干轮处理过程组成；
• 对f 的分析需要找出f 的碰撞.由于f 是压缩函数，其碰撞是不可避免的，因此在设计f 时就应 保证找出其碰撞在计算上是困难的

常用哈希函数简介 1.SHA-256算法

概况

• SHA系列标准哈希函数是由美国标准与技术研究所(National Institute of Standards and Technology，NIST)组织制定的.
• 1993年公布了SHA-0 (FIPS PUB 180)，后发现不安全.
• 1995年又公布了SHA-1(FIPS PUB 180--1).
• 2002年又公布了SHA-2( FIPS PUB 180--2)，包括 3种算法：SHA-256, SHA-384, SHA-512.
• 2005年王小云院士给出一种攻击SHA-1的方法，用 2^69操作找到一个强碰撞，以前认为是 2^80.
• 2017 年 2 月23日，谷歌宣布找到SHA-1碰撞的算法，需要耗费110 块GPU一年的运算量

图：SHA系列哈希函数的参数比较

注意：所有的长度以比特为单位；安全性是指对输出长度为n比特哈希函数的生日攻击产生碰撞的工作量大约为2^n/2

 算法描述

• 输入数据长度为k比特，1