赞
踩
哈希算法主要有MD4、MD5、SHA。
MD4 1990年 输出128位 (已经不安全)
MD5 1991年 输出128位 (已经不安全)
SHA-0 1993年 输出160位 (发布之后很快就被NSA撤回,是SHA-1的前身)
SHA-1 1995年 输出160位 (已经不安全)
SHA-2包括SHA-224、SHA-256、SHA-384,和 SHA-512,分别输出224、256、384、512位。 (目前安全)
冲突避免:
2的128次方为340282366920938463463374607431768211456,也就是10的39次方级别
2的160次方为1.4615016373309029182036848327163e+48,也就是10的48次方级别
2的256次方为1.1579208923731619542357098500869 × 10的77次方,也就是10的77次方
宇宙中原子数大约在10的60次方到80次方之间,所以2的256次方有足够的空间容纳所有的可能,算法好的情况下冲突碰撞的概率很低。
第一步:处理原文
首先,我们计算出原文长度(bit)对512求余的结果,如果不等于448,就需要填充原文使得原文对512求余的结果等于448。填充的方法是第一位填充1,其余位填充0。填充完后,信息的长度就是512*N+448。
之后,用剩余的位置(512-448=64位)记录原文的真正长度,把长度的二进制值补在最后。这样处理后的信息长度就是512*(N+1)。
第二步:设置初始值
MD5的哈希结果长度为128位,按每32位分成一组共4组。这4组结果是由4个初始值A、B、C、D经过不断演变得到。MD5的官方实现中,A、B、C、D的初始值如下(16进制):
A=0x01234567
B=0x89ABCDEF
C=0xFEDCBA98
D=0x76543210
第三步:循环加工
这一步是最复杂的一步,我们看看下面这张图,此图代表了单次A,B,C,D值演变的流程。
图中,A,B,C,D就是哈希值的四个分组。每一次循环都会让旧的ABCD产生新ABCD。一共进行多少次循环呢?由处理后的原文长度决定。
假设处理后的原文长度是M
主循环次数 = M / 512
每个主循环中包含 512 / 32 * 4 = 64 次 子循环。
上面这张图所表达的就是单次子循环的流程。
下面对图中其他元素一一解释
1.绿色F
图中的绿色F,代表非线性函数。官方MD5所用到的函数有四种:
F(X, Y, Z) =(X&Y) | ((~X) & Z)
G(X, Y, Z) =(X&Z) | (Y & (~Z))
H(X, Y, Z) =XYZ
I(X, Y, Z)=Y^(X|(~Z))
在主循环下面64次子循环中,F、G、H、I 交替使用,第一个16次使用F,第二个16次使用G,第三个16次使用H,第四个16次使用I。
2.红色“田”字
很简单,红色的田字代表相加的意思。
3.Mi
Mi是第一步处理后的原文。在第一步中,处理后原文的长度是512的整数倍。把原文的每512位再分成16等份,命名为M0 ~ M15,每一等份长度32。在64次子循环中,每16次循环,都会交替用到M1~M16之一。
4.Ki
一个常量,在64次子循环中,每一次用到的常量都是不同的。
5.黄色的<<<S
左移S位,S的值也是常量。
“流水线”的最后,让计算的结果和B相加,取代原先的B。新ABCD的产生可以归纳为:
新A = 原d
新B = b+((a+F(b,c,d)+Mj+Ki)<<<s)
新C = 原b
新D = 原c
第四步:拼接结果
这一步就很简单了,把循环加工最终产生的A,B,C,D四个值拼接在一起,转换成字符串即可。
设MD5的哈希函数是H(X),那么:
H(A) = M
H(B) = M
任意一个B即为破解结果。
B有可能等于A,也可能不等于A。
用一个形象的说法,A和B的MD5结果“殊途同归”。
MD5碰撞通常用于登陆密码的破解。应用系统的数据库中存储的用户密码通常都是原密码的MD5哈希值,每当用户登录时,验签过程如下:
如果我们得到了用户ABC的密码哈希值E10ADC3949BA59ABBE56E057F20F883E,并不需要还原出原密码123456,只需要“ 碰撞”出另一个原文654321(只是举例)即可。登录时,完全可以使用654321作为登陆密码,欺骗过应用系统的验签。
用空间换时间,提前存储好原文和MD5摘要的一一映射的表,这样做需要大量的成本去计算这么一张表。当数字长度为8时,有需要约4PB的空间。
H(X):生成信息摘要的哈希函数,比如MD5,比如SHA256。
R(X):从信息摘要转换成另一个字符串的衰减函数(Reduce)。其中R(X)的定义域是H(X)的值域,R(X)的值域是H(X)的定义域。但要注意的是,R(X)并非H(X)的反函数。
通过交替运算H和R若干次,可以形成一个原文和哈希值的链条。假设原文是aaaaaa,哈希值长度32bit,那么哈希链表就是下面的样子:
这个链条有多长呢?假设H(X)和R(X)的交替重复K次,那么链条长度就是2K+1。同时,我们只需把链表的首段和末端存入哈希表中:
给定信息摘要:920ECF10
如何得到原文呢?只需进行R(X)运算:
R(920ECF10) = kiebgt
查询哈希表可以找到末端kiebgt对应的首端是aaaaaa,因此摘要920ECF10的原文“极有可能”在aaaaaa到kiebgt的这个链条当中。
接下来从aaaaaa开始,重新交替运算R(X)与H(X),看一看摘要值920ECF10是否是其中一次H(X)的结果。从链条看来,答案是肯定的,因此920ECF10的原文就是920ECF10的前置节点sgfnyd。
需要补充的是,如果给定的摘要值经过一次R(X)运算,结果在哈希表中找不到,可以继续交替H(X)R(X)直到第K次为止。
所以只需要存储头尾aaaaa和kiebgt就可以存储链上所有的可能性。
但是这个做法有一个致命的缺陷,就是R (X)函数可能产生碰撞。
给定信息摘要:FB107E70
经过多次R(X),H(X)运算,得到结果kiebgt
通过哈希表查找末端kiebgt,可以找出首端aaaaaa
但是,FB107E70并不在aaaaaa到kiebgt的哈希链条当中,这就是R(X)的碰撞造成的。
这个问题看似没什么影响,既然找不到就重新生成一组首尾映射即可。但是想象一下,当K值较大的时候,哈希链很长,一旦两条不同的哈希链在某个节点出现碰撞。
这样造成的后果就是冗余存储。原本两条哈希链可以存储 2K个映射,由于重复,真正存储的映射数量不足2K。
于是彩虹表产生了
我们将R(X)改进成R1(X)到Rk(X),像彩虹一样,故名彩虹表。
SHA256简介
SHA256是SHA-2下细分出的一种算法
SHA-2,名称来自于安全散列算法2(英语:Secure Hash Algorithm 2)的缩写,一种密码散列函数算法标准,由美国国家安全局研发,属于SHA算法之一,是SHA-1的后继者。
SHA-2下又可再分为六个不同的算法标准
包括了:SHA-224、SHA-256、SHA-384、SHA-512、SHA-512/224、SHA-512/256。
这些变体除了生成摘要的长度 、循环运行的次数等一些微小差异外,算法的基本结构是一致的。
(1)附加填充比特。对报文进行填充使报文长度与448 模512 同余(长度=448 mod 512), 填充的比特数范围是1 到512,填充比特串的最高位为1,其余位为0。
就是先在报文后面加一个 1,再加很多个0,直到长度 满足 mod 512=448。为什么是448,因为448+64=512. 第二步会加上一个 64bit的 原始报文的 长度信息。
(2)附加长度值。将用64-bit 表示的初始报文(填充前)的位长度附加在步骤1 的结果
后(低位字节优先)。
(3)初始化缓存。使用一个256-bit 的缓存来存放该散列函数的中间及最终结果。
该缓存表示为A=0x6A09E667 , B=0xBB67AE85 , C=0x3C6EF372 , D=0xA54FF53A,
E=0x510E527F , F=0x9B05688C , G=0x1F83D9AB , H=0x5BE0CD19 。
(4)处理512-bit(16 个字)报文分组序列。该算法使用了六种基本逻辑函数,由64
步迭代运算组成。每步都以256-bit 缓存值ABCDEFGH 为输入,然后更新缓存内容。
每步使用一个32-bit 常数值Kt 和一个32-bit Wt。
就像上图一样,参与运算的都是 32 bit的数,Wt 是 分组之后的报文,512 bit=32bit*16. 也就是 Wt t=1,2…16 由 该组报文产生。
Wt t=17,18,…,64 由 前面的Wt按递推公式 计算出来。
(5)所有的512-bit分组处理完毕后,对于SHA-256算法最后一个分组产生的输出便是256-bit的报文摘要。
sha256安全的主要原因还是因为算法产生碰撞的可能性小,而且摘要长,这样加大了彩虹表破解的时间复杂度和空间的复杂度,相比MD5更加安全。
参考文献:
https://zhuanlan.zhihu.com/p/37165658
https://juejin.im/entry/59cf56a26fb9a00a4a4ceb64
https://juejin.im/entry/59dc3264f265da431769173a
https://juejin.im/post/5ce6b828f265da1bba58dd9e
https://www.cnblogs.com/foxclever/p/8370712.html
https://www.aboutyun.com/thread-24105-1-1.html
https://www.cnblogs.com/tofixer/p/3498048.html
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。