SHA1isaShambles资源-CSDN文库

需积分: 9 81 浏览量 2021-07-08 15:33:09 上传评论收藏 586KB PDF 举报

根据提供的文件信息，本文档主要聚焦于对SHA-1哈希函数的安全性分析，并报告了针对该算法的首个实际的碰撞攻击的实现，以及攻击对真实世界安全性的潜在影响。文件内容揭示了SHA-1算法由于可利用的碰撞攻击，已经不再安全，尤其是对于PGP/GnuPG这样的网络身份认证和安全通信协议。知识点概述如下： ### SHA-1哈希函数与安全性问题 SHA-1（安全哈希算法1）是在1995年设计的一个加密哈希函数。其设计初衷是为了提供一种安全的数据完整性校验机制。然而，随着时间的推移，SHA-1开始暴露出安全性上的缺陷。 ### 碰撞攻击与SHA-1 碰撞攻击指的是找到两个不同的输入（通常是一段数据或者文件），使得它们具有相同的哈希值。由于哈希函数是单向的，理论上应该很难找到两个不同的输入有相同的输出，如果成功找到这样的碰撞，就可以对哈希算法的安全性造成威胁。 ### 理论与实际攻击的差异虽然在2004年就提出了针对SHA-1的理论上的碰撞攻击，但由于所需计算复杂度过高，实际操作一直未能实现。然而到了2017年，使用大量GPU集群的技术突破，使得这一攻击在实践中得以实现。 ### 近乎实际的选定前缀碰撞攻击攻击者可以通过选定前缀碰撞攻击，构造两个具有任意前缀的碰撞消息，这比仅实现相同前缀的碰撞攻击更具威胁性，因为它可以用于伪造数字签名和破坏加密通信协议的安全握手。 ### 实际攻击的实现和成本本文件报告了首个选定前缀碰撞攻击的实际实现。通过使用900块Nvidia GTX 1060 GPU卡，攻击者能够以较低的成本执行攻击。尽管GPU的价格导致实际成本比理论计算更高，但攻击的总成本仍在学术研究者的可承担范围内。 ### 对PGP/GnuPG的影响研究者通过创建具有不同身份但具有碰撞SHA-1证书的PGP/GnuPG密钥对，展示了这种攻击如何在实践中被利用。这意味着在现实世界中，SHA-1已经无法提供足够的安全性。 ### 应用中的安全建议鉴于攻击的易用性，强烈建议从安全敏感型应用中尽快移除SHA-1。MD5自从2009年以来一直是可攻击的，现在随着SHA-1也变得容易受到攻击，对TLS、SSH等安全通信协议的影响尤其严重。 ### 结论文件中强调了密码学分析的重要性，通过实例展现了理论研究如何转化为现实世界的安全威胁。此外，还指出了GnuPG的遗留分支仍然默认使用SHA-1进行身份认证，尽管SHA-1的安全性已经不复存在。总结来说，文件内容突出了几个关键点：SHA-1已不再安全，选定前缀的碰撞攻击已成为可能，攻击成本已经降低到学术研究者可以承受的水平，因此需要立即从敏感应用中移除SHA-1。对于密码学研究和安全实践者而言，这是一个重要警示，表明即使是广泛部署的算法，也必须随着研究的深入和计算能力的提升而不断地重新评估其安全性。

资源推荐

资源详情

资源评论

SHA-1 is a Shambles

First Chosen-Preﬁx Collision on SHA-1

and Application to the PGP Web of Trust

Gaëtan Leurent

and Thomas Peyrin

2,3

Inria, France

Nanyang Technological University, Singapore

Temasek Laboratories, Singapore

gaetan.leurent@inria.fr, thomas.peyrin@ntu.edu.sg

https://sha-mbles.github.io/

Abstract.

The

SHA-1

hash function was designed in 1995 and has been widely used

during two decades. A theoretical collision attack was ﬁrst proposed in 2004 [

WYY05

but due to its high complexity it was only implemented in practice in 2017, using

a large GPU cluster [

SBK

]. More recently, an almost practical chosen-preﬁx

collision attack against

SHA-1

has been proposed [

LP19

]. This more powerful attack

allows to build colliding messages with two arbitrary preﬁxes, which is much more

threatening for real protocols.

In this paper, we report the ﬁrst practical implementation of this attack, and its

impact on real-world security with a PGP/GnuPG impersonation attack. We managed

to signiﬁcantly reduce the complexity of collisions attack against

SHA-1

: on an Nvidia

GTX 970, identical-preﬁx collisions can now be computed with a complexity of 2

61.2

rather than 2

64.7

, and chosen-preﬁx collisions with a complexity of 2

63.4

rather than

67.1

. When renting cheap GPUs, this translates to a cost of 11k US$ for a collision,

and 45k US$ for a chosen-preﬁx collision, within the means of academic researchers.

Our actual attack required two months of computations using 900 Nvidia GTX 1060

GPUs (we paid 75k US$ because GPU prices were higher, and we wasted some time

preparing the attack).

Therefore, the same attacks that have been practical on

MD5

since 2009 are now

practical on

SHA-1

. In particular, chosen-preﬁx collisions can break signature schemes

and handshake security in secure channel protocols (TLS, SSH). We strongly advise

to remove SHA-1 from those type of applications as soon as possible.

We exemplify our cryptanalysis by creating a pair of PGP/GnuPG keys with diﬀerent

identities, but colliding

SHA-1

certiﬁcates. A

SHA-1

certiﬁcation of the ﬁrst key can

therefore be transferred to the second key, leading to a forgery. This proves that

SHA-1

signatures now oﬀers virtually no security in practice. The legacy branch of

GnuPG still uses SHA-1 by default for identity certiﬁcations, but after notifying the

authors, the modern branch now rejects

SHA-1

signatures (the issue is tracked as

CVE-2019-14855).

Keywords:

SHA-1

Cryptanalysis

Chosen-preﬁx collision

HPC

GPU

PGP

GnuPG

1 Introduction

Cryptographic hash functions are present in countless security applications and protocols,

used for various purposes such as building digital signature schemes, message authentication

codes or password hashing functions. In the key application of digital signatures for example,

2 SHA-1 is a Shambles

hash functions are classically applied on the message before signing it, in order to improve

eﬃciency and provide security guarantees. Informally, a cryptographic hash function

is a function that maps an arbitrarily long message

to a ﬁxed-length hash value (we

denote

its bit size). Collision resistance is the main security property expected from a

hash function: it should be hard for an adversary to compute a collision, aka two distinct

messages

and

that map to the same hash value

(

) =

(

), where by “hard”

one means not faster than the generic 2

n/2

computations birthday attack.

A cryptanalyst will try to ﬁnd a collision for the hash function at a reduced cost, but

ad-hoc collision attacks are hard to exploit in practice, because the attacker has then

usually little control over the value of the actual colliding messages (in particular where the

diﬀerences are inserted, which are the interesting parts when attacking a digital signature

scheme for example). Thus, one can consider stronger and more relevant variants of the

collision attack in practice, such as the so-called chosen-preﬁx collision [

SLdW07

] or CP

collision: two message preﬁxes

and

are ﬁrst given as challenge to the adversary,

and his goal is to compute two messages

and

such that

(

P k M

) =

(

k M

where

denotes concatenation. With such ability, the attacker can obtain a collision even

though preﬁxes can be chosen arbitrarily (and thus potentially contain some meaningful

information). A CP collision can also be found generically with 2

n/2

computations (thus

for a 160-bit hash function like

SHA-1

), but ad-hoc CP collision attacks are much

more diﬃcult to ﬁnd than plain collision attacks, because of the random and completely

uncontrolled internal diﬀerences created by the preﬁxes. Yet, a CP collision attack was

found for the

MD5

hash function [

SLdW07

], eventually leading to the creation of colliding

X.509 certiﬁcates, and later of a rogue Certiﬁcate Authority (CA) [

SSA

]. CP collisions

have also been shown to break important internet protocols, including TLS, IKE, and

SSH [BL16], because they allow forgeries of the handshake messages.

Largely inspired by

MD4

[

Riv91

] and then

MD5

[

Riv92

SHA-1

is one the most famous

cryptographic hash functions in the world, having been the NIST and de-facto worldwide

hash function standard for nearly two decades. It remained a NIST standard until its

deprecation in 2011 (and disallowed to be used for digital signatures at the end of 2013).

Indeed, even though his successors

SHA-2

SHA-3

are believed to be secure,

SHA-1

has

been broken by a theoretical collision attack in 2004 [

WYY05

]. Due to its high technicality

and computational complexity (originally estimated to about 2

hash function calls), this

attack was only implemented in practice in 2017, using a large GPU cluster [

SBK

Because it took more than a decade to compute an actual collision and because plain

collisions are diﬃcult to use directly to attack a protocol, the on-ﬁeld

SHA-1

deprecation

process has been quite slow in practice and one can still observe many uses of

SHA-1

the wild unfortunately, migration being expensive. Web browsers have recently started to

reject certiﬁcates with

SHA-1

signatures, but there are still many users with older browsers,

and many protocols and software that allow

SHA-1

signatures. As observed in [

LP19

], it is

still possible to buy a

SHA-1

certiﬁcate from a trusted CA, many email clients accept a

SHA-1

certiﬁcate when opening a TLS connection, and

SHA-1

is also widely supported to

authenticate TLS handshake messages.

Very recently, a CP collision attack against

SHA-1

has been published [

LP19

], which

requires an estimated complexity between 2

66.9

and 2

69.4

SHA-1

computations. It works

with a two-phase strategy: given the challenge preﬁx and the random diﬀerences on the

internal state it will induce, the ﬁrst part of the attack uses a birthday approach to limit

the internal state diﬀerences to a not-too-big subset (as done in [

SLdW07

Ste13b

]). From

this subset, reusing basic principles of the various collision search advances on

SHA-1

, one

slowly adds successive message blocks to come closer to a collision, eventually reaching

the goal after a dozen blocks. Even though these advances put the CP collisions within

practical reach for very well-funded entities, it remains very expensive to conduct and also

very diﬃcult to deploy as the attack contains many very technical parts.

Gaëtan Leurent and Thomas Peyrin 3

Table 1:

Comparison of previous and new cryptanalysis results on

SHA-1

. A free-start

collision is a collision or the compression function only, where the attacker has full control

on all the primitive’s inputs. Complexities in the table are given in terms of

SHA-1

equivalents on a GTX-970 GPU (when possible).

Function Collision type Complexity Ref.

SHA-1 free-start collision 2

57.5

[SKP16]

collision 2

[WYY05]

64.7

[Ste13b, SBK

17]

61.2

New

chosen-preﬁx collision 2

77.1

[Ste13b]

67.1

[LP19]

63.4

New

The attack has a complexity of 2

on CPU, and 2

64.7

on GPU

1.1 Our Contributions

In this article, we exhibit the very ﬁrst chosen-preﬁx collision against the

SHA-1

hash

function, with a direct application to PGP/GnuPG security. Our contributions are

threefold.

Complexity improvements.

While the work of [

LP19

] was mostly about high-level tech-

niques to turn a collision attack into a chosen-preﬁx collision attack, we have to look at

the low-level details to actually implement the attack. This gave us a better understanding

of the complexity of the attack, and we managed to signiﬁcantly improve several parts of

the attacks (See Table 1).

First, we improved the use of neutral bits [

BCJ

] and boomerangs [

JP07

] on state-

of-the-art collision attacks for

SHA-1

(focusing on the near-collision block search). This

reduces the computational complexity for both plain and chosen-preﬁx collision attacks,

leading to important savings: on an Nvidia GTX 970, plain collisions can now be computed

with a complexity of 2

61.2

rather than 2

64.7

. We note that the general ideas underlying

these improvements might be interesting for other cryptanalysis than SHA-1 one.

Second, we improved the graph-based technique of [

LP19

] to compute a chosen-preﬁx

collision. Using a larger graph and more heuristic techniques, we can signiﬁcantly reduce the

complexity of the chosen-preﬁx collision attack, taking full advantage of the improvements

on the near-collision block search. This results in a chosen-preﬁx collision attack with a

complexity of 2

63.4

rather than 2

67.1

Record computation.

We implemented the entire chosen-preﬁx collision attack from [

LP19

with those improvements. This attack is extremely technical, contains many details, various

steps, and requires a lot of engineering work. Performing such a large-scale computation is

still quite expensive, but is accessible with an academic budget. More precisely, we can

can rent cheap GPUs from providers that use gaming or mining cards in consumer-grade

PCs, rather that the datacenter-grade hardware used by big cloud providers. This gives a

total cost signiﬁcantly smaller than 100k US$ to compute a chosen-preﬁx collision. We

give more detailed complexity and cost estimates in Table 2.

We have successfully run the computation during two months last summer, using 900

GPUs (Nvidia GTX 1060). Our attack uses one partial block for the birthday stage,

and 9 near-collision blocks. We paid 75k US$ to rent the GPUs from GPUserversrental,

but actual price could be smaller because we lost some time tuning the attack. There is

4 SHA-1 is a Shambles

Table 2:

Complexity of the attacks against

SHA-1

reported in this paper on several GPUs.

The complexity is given in

SHA-1

equivalents (using hashcat benchmarks). For the cost

evaluation we assume that one GTX 1060 GPU can be rented for a price of 35 US$/month.

To attack

MD5 k SHA-1

, we use the multicollision attack of Joux [

Jou04

] with three phase:

(i) a CPC on SHA-1, (ii) 64 collisions on SHA-1, and (iii) 2

evaluations of MD5.

Function Collision type GPU Time Complexity Cost

SHA-1 collision GTX 970 22 years 2

61.2

GTX 1060 27 years 2

61.6

11k US$

GTX 1080 Ti 8 years 2

61.6

chosen-preﬁx GTX 970 99 years 2

63.4

GTX 1060 107 years 2

63.5

45k US$

GTX 1080 Ti 34 years 2

63.6

MD5 k SHA-1 both (plain or CP) GTX 970 1400 years 2

67.2

GTX 1060 1700 years 2

67.6

720k US$

GTX 1080 Ti 540 years 2

67.6

also a large variability depending on luck, and GPU rental prices ﬂuctuate together with

cryptocurrencies prices.

PGP/GnuPG impersonation.

Finally, in order to demonstrate the practical impact of

chosen-preﬁx collisions, we used our CP collision for a PGP/GnuPG impersonation attack.

The chosen preﬁxes correspond to headers of two PGP identity certiﬁcates with keys of

diﬀerent sizes, an RSA-8192 key and an RSA-6144 key. By exploiting properties of the

the OpenPGP and JPEG format, we can create two public keys: key A with the victim

name, and key B with the attacker name and picture, such that the identity certiﬁcate

containing the attacker key and picture has the same

SHA-1

hash as the identity certiﬁcate

containing the victim key and name. Therefore, the attacker can request a signature of his

key and picture from a third party (from the Web of Trust or from a CA) and transfer

the signature to key A. The signature will still be valid because of the collision, while

the attacker controls key A with the name of the victim, and signed by the third party.

Therefore, he can impersonate the victim and sign any document in her name.

1.2 SHA-1 Usage and Impact

Our work show that

SHA-1

is now fully and practically broken for use in digital signatures.

GPU technology improvements and general computation cost decrease will quickly render

our attack even cheaper, making it basically possible for any ill-intentioned attacker in the

very near future.

SHA-1

usage has signiﬁcantly decreased in the last years; in particular web browsers

now reject certiﬁcates signed with

SHA-1

. However,

SHA-1

signatures are still supported

in a large number of applications.

SHA-1

is the default hash function used for certifying

PGP keys in the legacy branch of GnuPG (v 1.4), and those signatures were accepted by

the modern branch of GnuPG (v 2.2) before we reported our results. Many non-web TLS

clients also accept

SHA-1

certiﬁcates, and

SHA-1

is still allowed for in-protocol signatures

in TLS and SSH. Even if actual usage is low (a few percent), the fact that

SHA-1

allowed threatens the security because a man-in-the-middle attacker will downgrade the

connection to

SHA-1

is also the foundation of the GIT versioning system, and there

are probably a lot of less known or proprietary protocols that still use

SHA-1

, but this is

more diﬃcult to evaluate.

Gaëtan Leurent and Thomas Peyrin 5

1.3 Outline

We ﬁrst recall

SHA-1

inner workings and previous cryptanalysis on this hash function

in Section 2. We then provide improvements over the state-of-the-art

SHA-1

collision

attacks in Section 3 and Section 4, and we describe the details of the

SHA-1

chosen-preﬁx

collision computation in Section 5. Finally, we show a direct application of our CP collision

attack with a PGP/GnuPG impersonation (together with discussions on other possible

applications) in Section 6. We discuss

SHA-1

usage and the impact of our results in

Section 7. Eventually, we conclude and propose future works in Section 8.

2 Preliminaries

In this section, we describe the

SHA-1

hash function (we refer to [

Nat95

] for all the complete

details) and summarize the previous cryptanalysis work relevant to our new ﬁndings.

2.1 Description of SHA-1

SHA-1

is a 160-bit hash function that follows the well-known Merkle-Damgård paradigm [

Dam89

Mer89

]. A padding is ﬁrst applied to the message input (with message length encoded) so

that we obtain a multiple of 512 bits, and this bit string is divided into blocks

of 512

bits each. Then, each block

is processed via the

SHA-1

compression function (denoted

) to update a 160-bit chaining variable (denoted

) that is initialised to a constant and

public initial value (denoted IV):

. More precisely, we have

i+1

(

, m

i+1

When all blocks have eventually been processed, the last chaining variable is the ﬁnal hash

output.

The

SHA-1

compression function resembles other members of the

SHA

family of

hash functions. It uses the Davies-Meyer construction, that turns a block cipher

into

a compression function:

i+1

(

) +

, where

(

) is the encryption of the

plaintext y with the key k, and + is a word-wise modular addition.

The internal block cipher is composed of 4 rounds of 20 steps each (for a total of 80

steps), where one step follows a generalised Feistel network. More precisely, the internal

state is divided into ﬁve registers (

, B

, C

, D

, E

) of 32-bit each and at each step, an

extended message word W

updates the registers as follows:











i+1

= A

i+1

= (A

≪ 5) + f

, C

, D

) + E

+ K

+ W

i+1

= A

i+1

= B

≫ 2

i+1

= C

i+1

= D

where

are predetermined constants and

are boolean functions (in short: IF function

for the ﬁrst round, XOR for the second and fourth round, MAJ for the third round, see

Table 3). Since only a single register value is updated (

i+1

), the other registers being

only rotated copies, we can express the SHA-1 step function using a single variable:

i+1

= (A

≪ 5) + f

i−1

, A

i−2

≫ 2, A

i−3

≫ 2)

+ (A

i−4

≫ 2) + K

+ W

For this reason, the diﬀerential trails ﬁgures in this article will only represent

, the

other register values at a certain point of time can be deduced directly.

The extended message words

are computed linearly from the incoming 512-bit

message block

, the process being called message extension. One ﬁrst splits

into 16

剩余31页未读，继续阅读

评论收藏

内容反馈

jmxuan

粉丝: 3
资源: 7

SHA1 is a Shambles

最新资源

SHA1 is a Shambles

sha1加密

shambles-website:乱码的网站

Dungeon-Shambles

Auto-Photo-Colorizer:Python GUI使黑白照片轻松着色

内蒙古第一机械制造集团有限公司第一中学2018_2019学年高二英语10月月考试题

BurpLoaderKeygen.jar.zip

最新版ISO/IEC 27001:2022、ISO 27002:2022中英文合集

Chrome Header Editor 插件

Goby红队版-win-x64-2.4.7版本

软件工程导论(第六版)课后习题答案1

OpenVAS GVM 中文翻译补丁

安全认证cisp教材全套

STM32F103C8T6核心板-电路原理图1.PDF

通达信股票行情接口C#版API手册

第四届网鼎杯赛前训练(20241019)

OpenVAS离线资源

现代永磁同步电机控制原理及MATLAB仿真__袁雷编著1

2023年最全最精简wifi密码字典(2.6G)

小迪安全笔记，详细版本

hackbar2.1.3-master安装包

无法定位程序输入点于动态链接库上的问题1

关于STM32F103C8T6芯片的一些重要引脚功能的整理1

Kali安装burpsuite专业版

goby红队&社区版-win-64-2.4.7

全面的安全基线核查清单

2021年11月更新的哥斯拉4.0.1 免费

LiqunKit-1.6.2

14.视觉SLAM十四讲(高翔第二版)1

最新资源