扩展MD4与RIPEMD攻击分析：碰撞与伪原像
49 浏览量
更新于2024-07-15
收藏 369KB PDF 举报
"对完整扩展MD4的碰撞攻击和对RIPEMD的伪原像攻击"
这篇研究论文由王高丽撰写，发表在2013年1月的《计算机科学与技术》期刊上，探讨了对完整扩展MD4（Extended MD4）的碰撞攻击以及对RIPEMD的伪原像攻击。碰撞攻击和伪原像攻击是密码学哈希函数安全性的两个关键测试，这两个函数都是双分支哈希函数，包含两个并行的处理分支。
MD4是由Ron Rivest在1990年提出的一种哈希函数，而RIPEMD则是RACE Integrity Primitives Evaluation项目（1988年至1992年）框架下设计的。这两种函数在密码学中被广泛用于数据完整性验证和数字签名等领域。
论文基于差分分析法和中间相遇攻击原理，提出了针对完整扩展MD4的新碰撞攻击方法，以及对完整RIPEMD的伪原像攻击策略。碰撞攻击是指找到两个不同的输入，它们的哈希值相同，这在理论上破坏了哈希函数的唯一性。而伪原像攻击则是寻找一个输入，其哈希值与给定的哈希值相同，这能暴露哈希函数的安全漏洞。
Wang在文中详细阐述了如何通过分析这些哈希函数的内部工作机制，发现并利用它们的弱点来实施这两种攻击。这些攻击对于理解哈希函数的安全性至关重要，因为它们揭示了这些算法可能存在的潜在风险，并可能导致实际应用中的安全问题。
通过对完整扩展MD4的碰撞攻击，论文展示了MD4的脆弱性，表明在某些情况下，该算法可能不再适合用于安全性要求高的应用。同样，对RIPEMD的伪原像攻击也表明，尽管RIPEMD比MD4稍强，但依然存在可以被利用的安全隐患。
这些发现对于密码学研究者和安全专家来说具有重要意义，他们需要不断更新和改进现有的哈希函数，以应对新的攻击手段。同时，这也提醒了软件开发者和系统管理员，应谨慎选择和使用哈希函数，避免使用已被证明存在安全隐患的算法，如MD4或早期版本的RIPEMD，转而采用更安全的替代方案，如SHA-2或SHA-3系列。
Gao-Li Wang: Collision Extended MD4 Pseudo-Preimage RIPEMD 131
Table 1. Comparison of Our Results with Previous
(Pseudo-)Preimage Attacks
Number of Pseudo-Preimage (Second) Preimage Reference
Steps Attacks Attacks
Complexity Complexity
Time/Memory Time/Memory
26/29
∗
2
110
/2
33
2
115.2
/2
33
[45]
33 2
121
/2
10
2
125.5
/2
10
[44]
35
∗
2
96
/2
35
2
113
/2
35
[44]
47
?
2
119
/2
10.5
2
124.5
/2
10.5
[56]
48 2
125.4
/2
58
Ours
Note: ∗: the attacked steps start from some intermediate
step. ?: the attack is only applicable to find second preim-
ages.
Sections 4 and 5 describe the procedure of our pseudo-
preimage attack on the full RIPEMD compression func-
tion. Finally, Section 6 concludes the paper.
2 Preliminary
2.1 Notations
In order to describe our analysis conveniently, we
introduce some notations, where 0 6 j 6 31.
1) M = (m
0
, m
1
, . . . , m
15
) represents a 512-bit
block, where m
i
(0 6 i 6 15) is a 32-bit word.
2) ¬, ∧, ⊕, ∨ denote bitwise complement, AND, XOR
and OR respectively.
3) ≪ s (≫ s) is circular shift s-bit positions to the
left (right).
4) x k y denotes concatenation of the two bit strings
x and y.
5) +, − denote addition and subtraction modulo 2
32
respectively.
6) The least significant bit is the first bit (0th bit)
and the most significant bit is the last bit (31st bit).
7) x
i,j
denotes the j-th bit of 32-bit word x
i
.
8) ∆x
i
= x
0
i
− x
i
is the modular subtraction diffe-
rence of two words x
0
i
and x
i
.
9) x
0
i
= x
i
[j] is the value obtained by modifying the
j-th bit of x
i
from 0 to 1, i.e., x
i,j
= 0, x
0
i,j
= 1, and the
other bits of x
i
and x
0
i
are all equal. Similarly, x
i
[−j] is
the value obtained by modifying the j-th bit of x
i
from
1 to 0.
10) x
i
[±j
1
, ±j
2
, . . . , ±j
k
] denotes the value obtained
by modifying the bits in positions j
1
, . . . , j
k
of x
i
ac-
cording to the ± signs.
11) In Section 3, (a
i
, b
i
, c
i
, d
i
) and (aa
i
, bb
i
, cc
i
, dd
i
)
(0 6 i 6 12) represent the chaining variables corre-
sponding to the message block M
1
of left branch and
right branch respectively.
12) In Section 3, (a
0
i
, b
0
i
, c
0
i
, d
0
i
) and (aa
0
i
, bb
0
i
, cc
0
i
, dd
0
i
)
(0 6 i 6 12) represent the chaining variables corre-
sponding to the message block M
0
1
of left branch and
right branch respectively.
13) In Sections 4 and 5, (a
i
, b
i
, c
i
, d
i
) and
(aa
i
, bb
i
, cc
i
, dd
i
) (0 6 i 6 48) represent the chaining
variables of left branch and right branch respectively.
14) 0
α∼β
means that the bits from the β-th bit to
the α-th bit are all 0, where α > β.
15) w
α∼β
mean that the bits from the β-th bit to
the α-th bit of the variable w are arbitrary bits.
16) [α ∼ β] means that the bits from the β-th bit
to the α-th bit are known, and all the other bits are
unknown.
17) [α ∼ β, γ ∼ δ] means that the bits from the β-th
bit to the α-th bit and from the δ-th bit to the γ-th bit
are known, and all the other bits are unknown.
Note that the differential definition in Wang’s
method
[24]
is a kind of precise differential which uses
the difference in terms of integer modular subtraction
and the difference in terms of XOR. The combination
of both kinds of differences gives attackers more infor-
mation. For example, the output difference in step 1 of
Table 2 (collision differential path of Extended MD4) is
∆a
1
= a
0
1
− a
1
= 2
19
, for the specific differential path,
we need to expand the one-bit difference in bit 19 into
a three-bit differences in bits 19, 20 and 21. That is,
we expand a
1
[19] to a
1
[−19, −20, 21], which means the
19th and 20th bits of a
1
are 1, and the 21st bit of a
1
is 0, while the 19th and 20th bits of a
0
1
are 0, and the
21st bit of a
0
1
is 1.
2.2 Description of Extended MD4
The hash function Extended MD4 compresses a mes-
sage of length less than 2
64
bits into a 256-bit hash
value. Firstly, the algorithm pads any given message
into a message with the length of 512-bit multiple. We
do not describe the padding process here because it has
little relation with our attack, and the details of the
message padding can refer to [1]. Each 512-bit message
block invokes a compression function of Extended MD4.
The compression function takes a 256-bit chaining value
and a 512-bit message block as input and outputs an-
other 256-bit chaining value. The initial chaining value
is a set of fixed constants. The compression function
consists of two parallel branches named left branch and
right branch. Left branch is the standard MD4 and
right branch is a modified MD4. Each branch has three
rounds, and the nonlinear functions in each round are
as follows:
F (X, Y, Z) = (X ∧ Y ) ∨ (¬X ∧ Z),
G(X, Y, Z) = (X ∧ Y ) ∨ (X ∧ Z) ∨ (Y ∧ Z),
H(X, Y, Z) = X ⊕ Y ⊕ Z.
Here X, Y , Z are 32-bit words. The operations of the
three functions are all bitwise. Each round of the com-
pression function in each branch consists of 16 similar
剩余14页未读，继续阅读
103 浏览量
173 浏览量
点击了解资源详情
239 浏览量
134 浏览量
103 浏览量
236 浏览量
217 浏览量
2021-09-26 上传
weixin_38657115
- 粉丝: 5
- 资源: 905
我的内容管理
展开
