哈希(Hash)长度拓展攻击

  • A+
所属分类:网络安全文章
阿里代金券


推广者专属福利,新客户无门槛领取总价值高达2775元代金券,每种代金券限量500张,先到先得。

哈希长度拓展攻击 Hash Length Extension Attacks

导语

通过CTF接触到哈希长度扩展攻击,本文将详细分析如何对一些比较弱的Message Authentication codes (MACs)进行这种攻击。

原理

Message authentication codes (MACs)是用于验证信息真实性的。一般的MAC算法是这样的:服务器把secret和message连接到一起,然后用消息摘要算法如MD5或SHA1取摘要。研究发现MD4、MD5、RIPEMD-160、SHA-0、SHA-1、SHA-256、SHA-512、WHIRLPOOL等摘要算法受此攻击,但MD2、SHA-224和SHA-384不受此攻击。

哈希摘要算法,如MD5、SHA1、SHA2等,都是基于Merkle–Damgård结构。这类算法有一个很有意思的问题:当知道hash(secret + message)的值及secret长度的情况下,可以轻松推算出hash(secret + message||padding||m’)。在这里m’是任意数据,||是连接符,可以为空,padding是secret后的填充字节。hash的padding字节包含整个消息的长度,因此,为了能准确计算出padding的值,secret的长度我们也是需要知道的。

当我们填充后,服务器算出的原始hash值,正好与我们添加扩展字符串并覆盖初始链变量所计算出来的一样。这是因为攻击者的哈希计算过程,相当于从服务器计算过程的一半紧接着进行下去。提交此hash值便能通过验证了,这就是所谓的哈希长度拓展攻击(Hash Length Extension Attacks)。

算法简析

要深入理解哈希长度拓展攻击(Hash Length Extension Attacks),就得先了解摘要算法的具体实现过程。本文以MD5为例做简析,其它算法类似。

哈希(Hash)长度拓展攻击

 

这是一张MD5算法的流程图,根据这张图我们可以把MD5算法的流程,简单分为下面几步:

把消息分为n个消息块。

对最后一个消息块进行消息填充。

每个消息块会和一个输入量做运算,把运算结果作为下一个输入量。
下面说说MD5算法的实现:

Append Padding Bits(填充bits)

Append Length(填充长度)

Initialize MD Buffer(初始化向量)

Process Message in 16-Word Blocks(复杂的函数运算)
而要实现我们的攻击,我们只关心前三步,也就是不再再纠结复杂的算法运算。下面用例子来解释前三个流程也便于更加深入的理解哈希长度拓展攻击(Hash Length Extension Attacks):

Append Padding Bits(填充bits)

MD5算法会对消息进行分组,每组64 byte(512bit),不足64 byte 的部分会用padding补位。MD5算法每组最后8 byte 表示的是补充前消息的长度,所以消息补位是使得其长度在对 512 取模后的值为 448(512-8*8)。也就是说,len(message) mod(512) == 448。补位二进制表示是在消息的后面加上一个1,后面跟着 n 个0,直到 len(message) mod (512) == 448。在 16 进制下,我们需要在消息后补80,就是 2 进制的10000000。我们把消息进行补位到 448 bit,也就是 56 byte。

Append Length(填充长度)

补位过后,第 57 个字节开始储存补位之前消息的长度。

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

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

Initialize MD Buffer(初始化向量)

计算消息摘要必须用补位已经补长度完成之后的消息来进行运算,拿出 512 bit 的消息(即64 byte )。 计算消息摘要的时候,有一个初始的链变量,用来参与第一轮的运算。MD5 的初始链变量为:

  1. A=0x67452301
  2. B=0xefcdab89
  3. C=0x98badcfe
  4. D=0x10325476

无需关心计算细节,我们只需要知道经过一次消息再要后,上面的链变量将会被新的值覆盖,而最后一轮产生的链变量经过高低位互换(如:aabbccdd -> ddccbbaa)后就是我们计算出来的 md5 值。

哈希长度拓展攻击(Hash Length Extension Attacks)的实现

哈希长度拓展攻击(Hash Length Extension Attacks)的实现就是基于初始链变量的值被新的覆盖。

危害

只要存在脆弱的(使用此类散列算法)Message authentication codes (MACs)用于验证信息真实性的地方就很可能受此攻击。

那么如何抵御此攻击呢?

可以将消息摘要的值再进行消息摘要,这样就可以避免用户控制message了。也就是HMAC算法。该算法大概来说是这样:MAC =hash(secret + hash(secret + message)),而不是简单的对密钥连接message之后的值进行哈希摘要。具体HMAC的工作原理有些复杂,但你可以有个大概的了解。重点是,由于这种算法进行了双重摘要,密钥不再受本文中的长度扩展攻击影响。HMAC最先是在1996年被发表,之后几乎被添加到每一种编程语言的标准函数库中。

将secret放置在消息末尾也能防止这种攻击。比如 hash(m+secret),希望推导出 hash(m + secret||padding||m'),由于自动附加secret在末尾的关系,会变成hash(m||padding||m'||secret)。现在的附加值可以看作是m'||secret,secret值不知道,从而导致附加字符串不可控,hash值也就不可控,因而防止了这种攻击。

CE安全网

发表评论

您必须登录才能发表评论!