王晓云的著名论文HowtoBreakMD5andOtherHashFunctions资源-CSDN下载

需积分: 17 138 浏览量 2009-07-26 19:34:03 上传评论收藏 311KB PDF 举报

### 知识点一：MD5哈希函数及其安全性的演变 **MD5**（Message-Digest Algorithm 5）是一种广泛使用的密码学哈希函数，由Ron Rivest于1992年设计，作为MD4的改进版本。自从发布以来，MD5的安全性一直受到广泛关注。1993年，B. den Boer和A. Bosselaers发现了MD5的一种伪碰撞现象，即相同的输入消息可以与不同的初始值产生相同的哈希输出。这一发现揭示了MD5在所有链变量的最高位上具有较弱的雪崩效应。1996年的欧洲密码学研讨会上，H. Dobbertin展示了半自由起始碰撞攻击，即两个不同的512位消息可以使用一个特定的非标准初始值产生相同的哈希值。 ### 知识点二：王晓云等人的新攻击方法王晓云等人在《如何破解MD5和其他哈希函数》这篇论文中介绍了一种新的强力攻击方法，能够高效地找到MD5的碰撞。这种攻击在大约15分钟至1小时内即可完成。该攻击属于差分攻击，但与大多数差分攻击不同的是，它没有使用异或运算作为差异度量，而是使用模整数减法来衡量差异。作者们将这种类型的差分称为“模差分”。 ### 知识点三：差分攻击原理及模差分的概念 #### 差分攻击简介：差分攻击是一种常见的密码分析技术，主要用于攻击迭代的加密算法，如块密码和哈希函数。该攻击的基本思想是通过构造特定的输入对，并观察这些输入对经过加密或哈希后的输出差异，从而推断出加密密钥或哈希函数内部的状态。 #### 模差分的概念：传统的差分攻击通常使用异或运算来计算两个输入之间的差异。然而，在王晓云等人的研究中，他们引入了一种新的差异度量方式——模差分。具体来说，对于两个输入\( M_1 \)和\( M_2 \)，其模差分定义为\( (M_1 - M_2) \mod n \)，其中\( n \)通常是哈希函数的输出空间大小或者与之相关的某个数值。通过这种方式，研究者们能够更精确地控制和利用哈希函数内部状态的变化，从而实现高效的碰撞攻击。 ### 知识点四：MD5及其他哈希函数的适用性王晓云等人的这项攻击不仅适用于MD5，还适用于其他一些哈希函数，如**MD4**、**RIPEMD**以及**HAVAL**等。特别是对于MD4，使用这种方法可以在不到一秒的时间内找到碰撞。 ### 知识点五：哈希函数在信息安全中的应用哈希函数在信息安全领域中扮演着至关重要的角色。它们被广泛应用于数字签名、数据完整性检查、群签名、电子现金系统等多种密码学协议中。使用哈希函数不仅可以确保安全性，还能大大提高效率。当前，最广泛使用的哈希函数包括**MD5**和**SHA-1**。 ### 知识点六：王晓云等人研究成果的意义王晓云等人在《如何破解MD5和其他哈希函数》中的研究成果，极大地推动了密码学领域的发展。他们的工作不仅揭示了MD5等哈希函数的潜在弱点，而且为开发更安全的哈希函数提供了理论依据和技术支持。此外，该研究也提醒了业界关注现有哈希函数的安全性问题，促进了新的、更加安全的算法的诞生和发展。王晓云等人的研究不仅对学术界有着深远的影响，也为实际应用中的信息安全提供了重要的参考价值。

资源推荐

资源详情

资源评论

How to Break MD5 and Other Hash Functions

Xiaoyun Wang and Hongbo Yu

Shandong University, Jinan 250100, China

[email protected]

Abstract. MD5 is one of the most widely used cryptographic hash func-

tions nowadays. It was designed in 1992 as an improvement of MD4, and

its security was widely studied since then by several authors. The best

known result so far was a semi free-start collision, in which the initial

value of the hash function is replaced by a non-standard value, which is

the result of the attack. In this paper we present a new powerful attack

on MD5 which allows us to ﬁnd collisions eﬃciently. We used this attack

to ﬁnd collisions of MD5 in about 15 minutes up to an hour computation

time. The attack is a diﬀerential attack, which unlike most diﬀerential

attacks, does not use the exclusive-or as a measure of diﬀerence, but

instead uses modular integer subtraction as the measure. We call this

kind of diﬀerential a modular diﬀerential. An application of this attack

to MD4 can ﬁnd a collision in less than a fraction of a second. This attack

is also applicable to other hash functions, such as RIPEMD and HAVAL.

1 Introduction

People know that digital signatures are very important in information security.

The security of digital signatures depends on the cryptographic strength of the

underlying hash functions. Hash functions also have many other applications

in cryptography such as data integrity, group signature, e-cash and many other

cryptographic protocols. The use of hash functions in these applications not only

ensure the security, but also greatly improve the eﬃciency. Nowadays, there are

two widely used hash functions – MD5 [18] and SHA-1 [12].

MD5 is a hash function designed by Ron Rivest as a strengthened version of

MD4 [17]. Since its publication, some weaknesses has been found. In 1993, B.

den Boer and A. Bosselaers [3] found a kind of pseudo-collision for MD5 which

consists of the same message with two diﬀerent sets of initial values. This attack

discloses the weak avalanche in the most signiﬁcant bit for all the chaining vari-

ables in MD5. In the rump session of Eurocrypt’96, H. Dobbertin [8] presented

a semi free-start collision which consists of two diﬀerent 512-bit messages with

a chosen initial value IV



= 0x12ac2375,b

= 0x3b341042,c

= 0x5f62b97c,d

= 0x4ba763ed

A general description of this attack was published in [9].

R. Cramer (Ed.): EUROCRYPT 2005, LNCS 3494, pp. 19–35, 2005.

 International Association for Cryptologic Research 2005

转载

http://www.paper.edu.cn

20 X. Wang and H. Yu

Although H. Dobbertin cannot provide a real collision of MD5, his attack

reveals the weak avalanche for the full MD5. This provides a possibility to ﬁnd

a special diﬀerential with one iteration.

In this paper we present a new powerful attack that can eﬃciently ﬁnd a col-

lision of MD5. From H. Dobbertin’s attack, we were motivated to study whether

it is possible to ﬁnd a pair of messages, each consists of two blocks, that pro-

duce collisions after the second block. More speciﬁcally, we want to ﬁnd a pair

) and (M



) such that

(a, b, c, d)=MD5(a



)=MD5(a



MD5(a, b, c, d, M

)=MD5(a



where a

, b

, c

, d

are the initial values for MD5. We show that such collisions

of MD5 can be found eﬃciently, where ﬁnding the ﬁrst blocks (M



) takes

about 2

MD5 operations, and ﬁnding the second blocks (M



) takes about

MD5 operations. The application of this attack on IBM P690 takes about

an hour to ﬁnd M

and M



, where in the fastest cases it takes only 15 minutes.

Then, it takes only between 15 seconds to 5 minutes to ﬁnd the second blocks

and M



. Two such collisions of MD5 were made public in the Crypto’04

rump session [19].

This attack is applicable to many other hash functions as well, including MD4,

HAVAL-128 and RIPEMD ([17], [20], [15]). In the case of MD4, the attack can

ﬁnd a collision within less than a second, and can also ﬁnd second pre-images

for many messages.

In Crypto’04 Eli Biham and Raﬁ Chen presented a near-collision attack on

SHA-0 [2], which follows the lines of the technique of [4]. In the rump session they

described their new (and improved) results on SHA-0 and SHA-1 (including a

multi-block technique and collisions of reduced SHA-1). Then, A.

Joux presented

a 4-block full collision of SHA-0 [14], which is a further improvement of these

results. Both these works were made independently of this paper.

This paper is organized as follows: In Section 2 we brieﬂy describe MD5.

Then in Section 3 we give the main ideas of our attack, and in Section 4 we

give a detailed description of the attack. Finally, in Section 5 we summarize the

paper, and discuss the applicability of this attack to other hash functions.

2 Description of MD5

In order to conveniently describe the general structure of MD5, we ﬁrst recall

the iteration process for hash functions.

Generally a hash function is iterated by a compression function X = f (Z)

which compresses l-bit message block Z to s-bit hash value X where l>s.For

MD5, l = 512, and s = 128. The iterating method is usually called the Merkle-

Damgard meta-method (see [6], [16]). For a padded message M with multiples

of l-bit length, the iterating process is as follows:

i+1

= f (H

), 0 ≤ i ≤ t − 1.

中国科技论文在线

http://www.paper.edu.cn

How to Break MD5 and Other Hash Functions 21

Here M =(M

, ···,M

t−1

), and H

= IV

is the initial value for the hash

function.

In the above iterating process, we omit the padding method because it has

no inﬂuence on our attack.

The following is to describe the compression function for MD5. For each

512-bit block M

of the padded message M , divide M

into 32-bit words, M

, ...., m

). The compression algorithm for M

has four rounds, and each

round has 16 operations. Four successive step operations are as follows:

a = b +((a + φ

(b, c, d)+w

+ t

) ≪ s

d = a +((d + φ

i+1

(a, b, c)+w

i+1

+ t

i+1

) ≪ s

i+1

c = d +((c + φ

i+2

(d, a, b)+w

i+2

+ t

i+2

) ≪ s

i+2

b = c +((b + φ

i+3

(c, d, a)+w

i+3

+ t

i+3

) ≪ s

i+3

where the operation + means ADD modulo 2

. t

i+j

and s

i+j

(j =0, 1, 2, 3)

are step-dependent constants. w

i+j

is a message word. ≪ s

i+j

is circularly left-

shift by s

i+j

bit positions. The details of the message order and shift positions

can be seen in Table 3.

Each round employs one nonlinear round function, which is given below.

(X, Y, Z)=(X ∧ Y ) ∨ (¬X ∧ Z), 0 ≤ i ≤ 15,

(X, Y, Z)=(X ∧ Z) ∨ (Y ∧¬Z), 16 ≤ i ≤ 31,

(X, Y, Z)=X ⊕ Y ⊕ Z, 32 ≤ i ≤ 47,

(X, Y, Z)=Y ⊕ (X ∨¬Z), 48 ≤ i ≤ 63,

where X, Y , Z are 32-bit words.

The chaining variables are initialized as:

a = 0x67452301,b= 0xefcdab89,c= 0x98badcfe,d= 0x10325476.

We select a collision diﬀerential with two iterations as follows: Let H

i−1

(aa, bb, cc, dd) be the chaining values for the previous message block. After four

rounds, the compression value H

is obtained by wordwise addition of the chain-

ing variables to H

i−1

3 Diﬀerential Attack for Hash Functions

3.1 The Modular Diﬀerential and the XOR Diﬀerential

The most important analysis method for hash functions is diﬀerential attack

which is also one of most important methods for analyzing block ciphers. In

general, the diﬀerential attack especially in block ciphers is a kind of XOR dif-

ferential attack which uses exclusive-or as the diﬀerence. The diﬀerential attack

was introduced by E. Biham and A. Shamir to analyze the security of DES-like

cryptosystems. E. Biham and A. Shamir [1], described that diﬀerential crypt-

analysis is a method which analyzes the eﬀect of particular diﬀerences in plain

text pairs on the diﬀerences of the resultant cipher text pairs.

中国科技论文在线

http://www.paper.edu.cn

剩余16页未读，继续阅读

评论收藏

内容反馈

adomore

粉丝: 4

王晓云的著名论文How to Break MD5 and Other Hash Functions

最新资源

王晓云的著名论文How to Break MD5 and Other Hash Functions

How to Break MD5 and Other Hash Functions

王晓云：How to Break MD5 and Other Hash Functions

王晓云教授的md5-attack的论文

论文：MD5摘要实现

C语言程序设计大全、课件（保证全，包括课后习题及答案）

ros机械臂开发从入门到实战

机械工程控制基础ppt

软件项目管理模型及其应用研究的开题报告.docx

敦煌莫高窟重点保护区沙化现状分析

任务书-基于JAVA WEB技术的旅行社网站系统设计.docx

敦煌市近15年来生物丰度和植被覆盖指数的变化

安全环保部培训计划.docx

基于Sift特征的服装纸样检索.docx

食品安全检查记录-(1).doc

机械控制工程基础培训课件.pptx

移动无线通信技术智能化发展趋势探讨 (2).pdf

用MATLAB和Visual_C 混合编程及应用.pdf

仿真电路以及操作方法

【纯干货啊】华为IPD流程管理(完整版).pptx

信号与系统——保研复习资料.pdf

python大作业 含爬虫、数据可视化、地图、报告、及源码（整和为一个文件）（2014-2020全国各地区原油加工量）.rar

可编程语言标准IEC61131-3中文版.pdf

Landsat_WRS2.zip

数字信号处理——保研复习资料.pdf

使用STM32F103C8T6+L298N+MG513P30电机使用外部中断法和输入捕获法进行编码器测速

系统规划与管理师全套资料.zip

中国行政区划矢量数据WGS84免费下载

线性代数——保研复习资料.pdf

量子计算：从入门到精通

DeepCamera: 开源AI摄像头解决方案

最新资源

python大作业含爬虫、数据可视化、地图、报告、及源码（整和为一个文件）（2014-2020全国各地区原油加工量）.rar