SHA-1安全漏洞：首个选择前缀碰撞攻击实现

sha1

需积分: 9 173 浏览量更新于2024-07-09 收藏 586KB PDF 举报

身份认证购VIP最低享 7 折!

领优惠券(最高得80元）

资源详情

资源推荐

6 SHA-1 is a Shambles

Table 3: Boolean functions and constants of SHA-1

step i f

(B, C, D) K

0 ≤ i < 20 f

= (B ∧ C) ⊕ (B ∧ D) 0x5a827999

20 ≤ i < 40 f

XOR

= B ⊕ C ⊕ D 0x6ed6eba1

40 ≤ i < 60 f

MAJ

= (B ∧ C) ⊕ (B ∧ D) ⊕ (C ∧ D) 0x8fabbcdc

60 ≤ i < 80 f

XOR

= B ⊕ C ⊕ D 0xca62c1d6

32-bit words M

, . . . , M

, and then the W

’s are computed as follows:

(

, for 0 ≤ i ≤ 15

i−3

⊕ W

i−8

⊕ W

i−14

⊕ W

i−16

) ≪ 1, for 16 ≤ i ≤ 79

In the rest of this article, we will use the notation X[j] to refer to bit j of word X.

2.2 Previous Works

Without going into too many details of the very technical

SHA-1

cryptanalysis advances,

we recall here the general state-of-the-art collision search strategies that we will use for

our CP collision attack. Readers only interested by the applications of our CP collision

attack can skip up to Section 6.

2.2.1 Preparing a Collision Attack on SHA-1

The ﬁrst results on

SHA-0

(the predecessor of

SHA-1

) and

SHA-1

were diﬀerential in

nature and obtained by building diﬀerential paths from a linearization of the compression

function: in order to simplify the analysis the attacker assumes that modular additions

and boolean functions

in the

SHA-1

compression function are behaving as an XOR

with regards to diﬀerential propagation. These assumptions are indeed happening with

a certain probability, which will basically consist of the bulk of the ﬁnal attack cost.

Then, in order to further simplify the analysis while trying to minimize the number of

diﬀerences present in the internal state (which will in turn increase the diﬀerential trail

probability and therefore improve the ﬁnal attack cost), these trails are generated with

a succession of so-called local collisions: small message disturbances whose inﬂuence is

immediately corrected with other message diﬀerences inserted in the subsequent

SHA-1

steps, while following the

SHA-1

message expansion. However, in this linearization model,

impossibilities might appear in the ﬁrst 20 steps of

SHA-1

(as in some speciﬁc cases the

boolean function will never behave as an XOR) and the cheapest trail candidates

might not be the ones that start and end with the same diﬀerence (which is a property

required to obtain directly a 1-block collision after the compression function feed-forward).

This strategy could already break the collision resistance of

SHA-0

, but not yet for

SHA-1

(due to a small rotation added in the message expansion of

SHA-1

, that forces disturbances

to spread throughout the rounds).

A huge breakthrough then happened in 2005: a team of researchers [

WYY05

] showed

that by generating non-linear diﬀerential trails for the ﬁrst 10

∼

15 steps of the compression

function, one could potentially connect any incoming input diﬀerence to any ﬁxed diﬀerence

at step 10

∼

15. This ﬂexibility allows to remove completely the impossibility issues one

could face in the ﬁrst steps due to the linearization (since this part is now non-linear). Even

better, taking advantage of the Davies-Meyer construction used inside the compression

function, it actually permits to perform the collision attack on

SHA-1

using only two blocks

containing diﬀerences, while picking the cheapest diﬀerential trail from step 10

∼

15 to 80.

With two successive blocks using the same diﬀerential trails (just ensuring that the output

Gaëtan Leurent and Thomas Peyrin 7

diﬀerence of the two blocks have opposite signs: 0

and

−δ

), one can see in

Figure 1 that a collision is obtained at the end of the second block because the internal

state diﬀerences cancel out.

IV H

hδ

i h−δ

h0i hδ

i hδ

i h−δ

h0i hδ

i h0i

L L

Figure 1:

2-block collision attack using a linear trail

and two non-linear trails

and

−δ

in the ﬁrst 10 15 steps. Green values between bracket represent

diﬀerences in the state.

2.2.2 Computing a Collision for SHA-1 with Amortization Techniques

Once the diﬀerential trail is set, for each successive block the attacker can concentrate

on ﬁnding a pair of messages that follows it. For this, he constructs a large number of

messages that follow the trail up to some predetermined step (using the freedom degrees

available from the message input), and then computes the remaining

SHA-1

steps to test

whether the output diﬀerence is the expected one

(this part is only probabilistic).

Compared to a pure naive search, it can be observed that the computational cost is

reduced by using a simple early-abort strategy for the 16 ﬁrst steps. Yet, more advanced

amortization methods such as neutral bits [

BCJ

], boomerangs [

Kli06

JP07

] or message

modiﬁcation [

WYY05

] can reach a few more steps further. Because of this amortization,

usually the ﬁrst 20 or so steps do not contribute to the ﬁnal complexity of the attack

(which is a good thing because the ﬁrst 10

∼

15 steps of the diﬀerential path are non-linear

and thus will be veriﬁed with quite low probability).

Neutral bits were ﬁrstly introduced for the cryptanalysis of

SHA-0

[

BC04

BCJ

The idea is that once a message pair following the diﬀerential path until a certain step

was found, one could get another message pair valid until step

for free by applying a small

message modiﬁcation (one or a few bits). The hope is basically that such a modiﬁcation

would not interact too much with necessary conditions in the diﬀerential path before step

. The fact that a certain modiﬁcation was neutral or not until a step

with a good

probability could be pre-analysed before running the attack and a key observation was

that any combination of two of more neutral bits until step

was likely to be neutral as

well until step x, which gives an exponential potential amortization.

Boomerangs [

JP07

] or tunnels [

Kli06

] are very similar amortization tools to neutral bits.

Basically, they can be seen as neutral bits that are planned in advance: build from one or

a few local collisions (or relaxed versions of a local collision), one expects this perturbation

to be neutral to the diﬀerential path after a few steps with a certain probability, but

extra conditions are forced in the internal state and message to increase this probability.

Boomerangs are generally more powerful than neutral bits (in the sense that they produce

candidates valid with high probability for later steps than classical neutral bits), but

consume more freedom degrees. For this reason, you can generally only place a few of

them due to a lack of available freedom degrees, but their amortization gain is almost a

factor 2.

Note that a lot of details have to be taken into account when using neutral bits or

boomerangs, as many equations between some internal state bits and potentially message

bits must be fulﬁlled in order for the planned diﬀerential path to be valid. Thus, one can’t

剩余31页未读，继续阅读

jmxuan

粉丝: 3
资源: 7

SHA-1安全漏洞：首个选择前缀碰撞攻击实现

密码学sha1

shambles-website:乱码的网站

2进制3位数过去现在将来输赢公式代码.txt

福州大学在广东2021-2024各专业最低录取分数及位次表.pdf

WordPress 集网址、资源、资讯于一体的导航类主题开心版

【Java学习】activemq消息中间件学习demo.zip

爬取淘宝热销(热门)手机支架商品信息公开透明的数据集

【目标检测数据集】斧子数据集2396张VOC+YOLO格式（含增强60%）.zip

南昌大学科学技术学院在广东2021-2024各专业最低录取分数及位次表.pdf

南京财经大学红山学院在广东2021-2024各专业最低录取分数及位次表.pdf

武昌首义学院在广东2021-2024各专业最低录取分数及位次表.pdf

【2024国赛C题】C 题农作物的种植策略思路+代码+论文V3.rar

基于Java的客户管理系统源码，CRM 带小程序 CRM小程序源码 1. 前端：Vue 2. 后端：Spring boot

某智慧城市社区网格化初步设计方案.doc

苹果CMS泛目录黑帽SEO站群繁殖程序

10米不锈钢输送设备_机械3D图Solidworks设计图.zip

一文了解javascript语言，适合小白想了解什么是JavaScript语言的同学

收藏的电池电量检测的资料技术资料开发设计用的重要资料.zip

武昌理工学院在广东2021-2024各专业最低录取分数及位次表.pdf

西安科技大学在广东2021-2024各专业最低录取分数及位次表.pdf

最新资源