Js哈希摘要算法
2020-01-05 15:46

澳门新葡亰553311b 1

前言

澳门新葡亰553311b 2

最近在看一些NPM库的时候总是看到各种哈希签名算法,之前工作中也有用到过签名算法,但并没有深入理解过其中的原理,于是找了点资料稍微了解了一下,总结了这篇文章。

Hash,一般翻译做“散列”,也有直接音译为“哈希”的,就是把任意长度的输入(又叫做预映射, pre-image),通过散列算法,变换成固定长度的输出,该输出就是散列值。这种转换是一种压缩映射,也就是,散列值的空间通常远小于输入的空间,不同的输入可能会散列成相同的输出,所以不可能从散列值来唯一的确定输入值。简单的说就是一种将任意长度的消息压缩到某一固定长度的消息摘要的函数。

澳门新葡亰网站所有平台,哈希摘要算法

哈希长度扩展攻击简单的来讲就是:

哈希函数,是一种根据任意长度数据计算出固定签名长度的算法,比如MD5,SHA系列。

1.知道一个密文(SECRET)的哈希

哈希签名摘要算法特点不是加密算法,而是一种摘要算法不可逆,“单向”函数签名长度固定存在2的N次方种结果,N表示签名长度以MD5为例

2.知道密文的长度(SECRET LENGTH)

MD5是由美国密码学家罗纳德·李维斯特设计一种加密算法。

在不知道密文的情况下可以推算出密文+填充+追加消息(SECRET+PADDING+EXTRA)的哈希,也就是说在只知道密文长度和密文哈希的情况下,可以预测出密文和另一消息拼接后的哈希。

128个bits长度,也就是16个字节输出结果由为“0-F”字符组成,不区分大小写存在2的128次方种输出结果MD5算法一、源数据处理

澳门新葡亰553311b,0x01 理解哈希算法流程

计算原文长度(bits)对512求余的结果,需要填充原文使得原文对512求余的结果等于448, 填充的方法是第一位填充1,其余位填充0。填充完后,信息的长度为512 * N + 448。

易受哈希长度扩展攻击的哈希算法:SHA系列和MD系列。这两个系列的哈希算法都有一个共同点——基于Merkle–Damgård构造。

剩余64bits存储空间用来填充源信息长度,填充在448byte 数据之后。

澳门新葡亰553311b 3

最终经过处理后的数据长度为 512 * N。

上图可以看出,Merkle–Damgård算法的流程如下:

动手画了一张简单的图来说明:

  1. 把消息划分为n个消息块

  2. 对最后一个消息块做长度填充

二、处理数据

3. 每个消息块都会和一个输入向量做一个运算,把这个计算结果当成下个消息块的输入向量

1、数据进行处理前,会定义4个常量,作为初始值这4个常量分别是

0x02 理解MD5算法流程

var a = 0x67452301;var b = 0xEFCDAB89;var c = 0x98BADCFE;var d = 0x10325476;

了解了Merkle–Damgård算法的流程,下面详细了解一下MD5算法的流程,我们可以参考RFC 1321(

翻译成二进制就是

MD5算法包括四大步骤:

var a = 1732584193;var b = -271733879;var c = -1732584194;var d = 271733878;
  •  Append Padding Bits(填充bits)
  •  Append Length(填充长度)
  • Initialize MD Buffer(初始化向量)
  • Process Message in 16-Word Blocks(复杂的函数运算)

2、将处理后的数据,外循环处理N次,N为第一步中512的整数倍。每次外循环处理的会产生新的“a、b、c、d”值,每次新产生的“a、b、c、d”值会再一次提供给下一次外循环使用

我们主要需要了解前三步,也就是MD5算法中的填充和生成初始化向量。首先,我们看一下MD5中填充bits的算法,该算法的流程如下:

3、在每个外循环中又进行内循环处理64次,在这64次数据处理中会不停的将 512 bytes 数据中的 16个小单元不停的通过4个函数进行交叉处理,共计进行64轮计算。

  1. 根据消息的长度确定填充的字节数,即填充后消息长度 mod 512bit = 448bit。举个例子:一个消息是”message”,则这个消息是56bit,所以需要填充392bit。

  2. 最小填充1bit最多填充512bit,即使消息长度 mod 512 = 448bit。也就是说,不管消息长度是多少,都必须进行填充。

  3. 填充信息的第一个字节是0x80,剩余数据用0x00填充。

4、最终生成新的“a、b、c、d”,新的“a、b、c、d”分别是占用32bytes的数据

然后,我们看一下填充长度的流程:

5、最终生成的“a、b、c、d”转换为对应的ascll占用的字节,32 bytes * 4 = 128 bytes, 一个字节占用8个bytes, 也就是16个字节,16个字节转换为ASCII码,再将ASCII码转换为16进制数据,即可得到一个32个字节长度的hash值。

填充长度的大小是64bit

内外循环代码

长度是小端存储的,也就是说高字节放在高地址中

function binl_md5(x, len) { /* append padding */ x[len  5] = x[len  5] | 0x80  (len % 32); x[(((len + 64)  9)  4) + 14] = len; var i, olda, oldb, oldc, oldd, a = 1732584193, b = -271733879, c = -1732584194, d = 271733878; // 每次计算位移值,可以理解为是常量 var ffShift = [7, 12, 17, 22, 7, 12, 17, 22, 7, 12, 17, 22, 7, 12, 17, 22]; var ggShift = [5, 9, 14, 20, 5, 9, 14, 20, 5, 9, 14, 20, 5, 9, 14, 20]; var hhShift = [4, 11, 16, 23, 4, 11, 16, 23, 4, 11, 16, 23, 4, 11, 16, 23]; var iiShift = [6, 10, 15, 21, 6, 10, 15, 21, 6, 10, 15, 21, 6, 10, 15, 21]; // Todo: 四个字节一组,每个组别之间不停的交叉计算,不停的根据已计算出来的值多次计算赋值 // x[i]装的是4个字节的数据 // x.length 为 512 * N / 32 // i += 16 每512bits长度的数据分为了16组,而每次循环的计算单位是以512为一个单元的,所以每次都是+16 for (i = 0; i  x.length; i += 16) { olda = a; oldb = b; oldc = c; oldd = d; // 64轮计算中包含原始“a、b、c、d”值。 // 以及位移值,以及一个计算常量,这两个是MD5规范中所定义的常量 a = md5_ff(a, b, c, d, x[i], ffShift[0], -680876936); d = md5_ff(d, a, b, c, x[i + 1], ffShift[1], -389564586); c = md5_ff(c, d, a, b, x[i + 2], ffShift[2], 606105819); b = md5_ff(b, c, d, a, x[i + 3], ffShift[3], -1044525330); a = md5_ff(a, b, c, d, x[i + 4], ffShift[4], -176418897); d = md5_ff(d, a, b, c, x[i + 5], ffShift[5], 1200080426); c = md5_ff(c, d, a, b, x[i + 6], ffShift[6], -1473231341); b = md5_ff(b, c, d, a, x[i + 7], ffShift[7], -45705983); a = md5_ff(a, b, c, d, x[i + 8], ffShift[8], 1770035416); d = md5_ff(d, a, b, c, x[i + 9], ffShift[9], -1958414417); c = md5_ff(c, d, a, b, x[i + 10], ffShift[10], -42063); b = md5_ff(b, c, d, a, x[i + 11], ffShift[11], -1990404162); a = md5_ff(a, b, c, d, x[i + 12], ffShift[12], 1804603682); d = md5_ff(d, a, b, c, x[i + 13], ffShift[13], -40341101); c = md5_ff(c, d, a, b, x[i + 14], ffShift[14], -1502002290); b = md5_ff(b, c, d, a, x[i + 15], ffShift[15], 1236535329); a = md5_gg(a, b, c, d, x[i + 1], ggShift[0], -165796510); d = md5_gg(d, a, b, c, x[i + 6], ggShift[1], -1069501632); c = md5_gg(c, d, a, b, x[i + 11], ggShift[2], 643717713); b = md5_gg(b, c, d, a, x[i], ggShift[3], -373897302); a = md5_gg(a, b, c, d, x[i + 5], ggShift[4], -701558691); d = md5_gg(d, a, b, c, x[i + 10], ggShift[5], 38016083); c = md5_gg(c, d, a, b, x[i + 15], ggShift[6], -660478335); b = md5_gg(b, c, d, a, x[i + 4], ggShift[7], -405537848); a = md5_gg(a, b, c, d, x[i + 9], ggShift[8], 568446438); d = md5_gg(d, a, b, c, x[i + 14], ggShift[9], -1019803690); c = md5_gg(c, d, a, b, x[i + 3], ggShift[10], -187363961); b = md5_gg(b, c, d, a, x[i + 8], ggShift[11], 1163531501); a = md5_gg(a, b, c, d, x[i + 13], ggShift[12], -1444681467); d = md5_gg(d, a, b, c, x[i + 2], ggShift[13], -51403784); c = md5_gg(c, d, a, b, x[i + 7], ggShift[14], 1735328473); b = md5_gg(b, c, d, a, x[i + 12], ggShift[15], -1926607734); a = md5_hh(a, b, c, d, x[i + 5], hhShift[0], -378558); d = md5_hh(d, a, b, c, x[i + 8], hhShift[1], -2022574463); c = md5_hh(c, d, a, b, x[i + 11], hhShift[2], 1839030562); b = md5_hh(b, c, d, a, x[i + 14], hhShift[3], -35309556); a = md5_hh(a, b, c, d, x[i + 1], hhShift[4], -1530992060); d = md5_hh(d, a, b, c, x[i + 4], hhShift[5], 1272893353); c = md5_hh(c, d, a, b, x[i + 7], hhShift[6], -155497632); b = md5_hh(b, c, d, a, x[i + 10], hhShift[7], -1094730640); a = md5_hh(a, b, c, d, x[i + 13], hhShift[8], 681279174); d = md5_hh(d, a, b, c, x[i], hhShift[9], -358537222); c = md5_hh(c, d, a, b, x[i + 3], hhShift[10], -722521979); b = md5_hh(b, c, d, a, x[i + 6], hhShift[11], 76029189); a = md5_hh(a, b, c, d, x[i + 9], hhShift[12], -640364487); d = md5_hh(d, a, b, c, x[i + 12], hhShift[13], -421815835); c = md5_hh(c, d, a, b, x[i + 15], hhShift[14], 530742520); b = md5_hh(b, c, d, a, x[i + 2], hhShift[15], -995338651); a = md5_ii(a, b, c, d, x[i], iiShift[0], -198630844); d = md5_ii(d, a, b, c, x[i + 7], iiShift[1], 1126891415); c = md5_ii(c, d, a, b, x[i + 14], iiShift[2], -1416354905); b = md5_ii(b, c, d, a, x[i + 5], iiShift[3], -57434055); a = md5_ii(a, b, c, d, x[i + 12], iiShift[4], 1700485571); d = md5_ii(d, a, b, c, x[i + 3], iiShift[5], -1894986606); c = md5_ii(c, d, a, b, x[i + 10], iiShift[6], -1051523); b = md5_ii(b, c, d, a, x[i + 1], iiShift[7], -2054922799); a = md5_ii(a, b, c, d, x[i + 8], iiShift[8], 1873313359); d = md5_ii(d, a, b, c, x[i + 15], iiShift[9], -30611744); c = md5_ii(c, d, a, b, x[i + 6], iiShift[10], -1560198380); b = md5_ii(b, c, d, a, x[i + 13], iiShift[11], 1309151649); a = md5_ii(a, b, c, d, x[i + 4], iiShift[12], -145523070); d = md5_ii(d, a, b, c, x[i + 11], iiShift[13], -1120210379); c = md5_ii(c, d, a, b, x[i + 2], iiShift[14], 718787259); b = md5_ii(b, c, d, a, x[i + 9], iiShift[15], -343485551); a = safe_add(a, olda); b = safe_add(b, oldb); c = safe_add(c, oldc); d = safe_add(d, oldd); } // 最终生成4个占用32 bytes控制的值 return [a, b, c, d];}

如果消息的长度大于2 ^ 64,也就是大于2048PB。那么64bit无法存储消息的长度,则取低64bit。

四轮计算线性函数

下图是补位的示例,要进行哈希运算的消息是字符串”message”,则:

F(X,Y,Z) =(XY)|((~X)Z) G(X,Y,Z) =(XZ)|(Y(~Z)) H(X,Y,Z) =X^Y^Z I(X,Y,Z)=Y^(X|(~Z)) 

澳门新葡亰553311b 4

6、第五点可以解释为什么生成的hash值中只会包含“0-F”,且不区分大小写的原因,长度为16。

最后,初始化向量为固定值:

function rstr2hex(input) { var hex_tab = '0123456789abcdef', output = '', x, i; for (i = 0; i  input.length; i += 1) { x = input.charCodeAt(i); output += hex_tab.charAt((x  4)  0x0F) + hex_tab.charAt(x  0x0F); x:${input.charCodeAt(i)}, output: ${output}`); } return output;}

A 01 23 45 67 0x67452301

以上代码来自,稍有改动。

B 89 AB CD EF 0xEFCDAB89

适用场景:私密数据加密,比如用户密码一般都不会明文存储,而是通过加密后存入数据库赌场开盘前将开票结果公布,开盘后通过签名对比校验是否存在作弊行为检测文件是否下载完成,比如迅雷下载...如何破解

C FE DC BA 98 0x98BADCFE

MD5中,虽然由源文可以推导出签名,反过来,并不能由签名推导出源文。但MD5并不是坚不可摧,目前有两种破解方式

D 76 54 32 10 0x10325476

碰撞法,虽然MD5签名存在2的128次方种输出结果,但每个签名对应的原文并不是唯一的,只要计算机性能够强大,给予充足的时间,总能找到能输出相同签名的数据源。映射法,把常规字符串对应的签名存储,比如常用的“123456”,“abcdefg”等。当得到MD5签名时,就可以映射出源数据。如何防范:使用安全性更高的SHA256,并不是说SHA256不能被破解,只是相对于MD5来说算法步骤更多,也更复杂,破解难度更大。源数据 + KEY,比如“123456”加上KEY就变成了“123456@#DFF23DS”,其中“@#DFF23DS”就是服务端存储的KEY。“源数据

然后,用初始化向量和补位后的消息进行复杂的函数运算,最终得到消息”message”的MD5值为78e731027d8fd50ed642340b7c9a63b3。

上一篇:只有 90 年代的 Web 开发者才记得这些 下一篇:没有了