A quantum algorithm for nding collision-inducing disturbance vectors in SHA-1 Jiheng Duan

2025-04-30 0 0 1.08MB 14 页 10玖币

侵权投诉

A quantum algorithm for ﬁnding collision-inducing

disturbance vectors in SHA-1

Jiheng Duan

Department of Physics and Chemistry, Faculty of Science and Technology,

University of Macau, Macau SAR, China

Minghui Li

Institute of Applied Physics and Materials Engineering, University of Macau,

Macau SAR, China

Hou Ian

Institute of Applied Physics and Materials Engineering, University of Macau,

Macau SAR, China

E-mail: houian@um.edu.mo

Abstract. Modern cryptographic protocols rely on sophisticated hash functions

to generate quasi-unique numbers that serve as signatures for user authentication

and other security veriﬁcations. The security could be compromised by ﬁnding

texts hash-mappable to identical numbers, forming so-called collision attack.

Seeding a disturbance vector in the hash mapping to obtain a successful collision

is that a major focus of cryptography study in the past two decades to improve

hash protocols. We propose an algorithm that takes advantage of entangled

quantum states for concurrent seeding of candidate disturbance vectors, out of

which the one entailing collision is selected through a combination of quantum

search, phase gating, diﬀusion gating, and information feedbacks from classical

computing machinery. The complexity reduction is shown to be on the order of

O(2n/2+1) where nis the number of qubits encoding addresses. We demonstrate

the practicality of the proposed by an implementation scheme based on degenerate

optical parametric oscillators.

arXiv:2210.12762v1 [quant-ph] 23 Oct 2022

A quantum algorithm for ﬁnding collision-inducing disturbance vectors in SHA-1 2

1. Introduction

Cryptographic hash functions appeared at the end of the twentieth century and became

one of the most signiﬁcant concepts in key derivation, password hashing, and digital

signatures which were popularized since 1990s [1]. The most ubiquitous cryptographic

hash functions belong to the secure hash algorithm (SHA) family [2], which includes

the variants SHA-0 up to SHA-3. The SHA function converts input messages into

quasi-unique and orderless strings of a ﬁxed length. Since this length is much shorter

than the lengths of original messages, collisions are doomed to occur due to the pigeon-

hole principle, where two or more messages are converted to the same hash value. The

careful design of the SHA family, however, mandates that similar messages lead to

vastly distinct hash values, let alone messages of diﬀerent lengths. It was believed that

hash collisions would never occur such that authentication systems would be protected

from fake signatures from malware. The course took a sudden change in 2005 when the

ﬁrst practical collision attack of SHA-1 was proposed by employing a diﬀerential path

method [3, 4]. Since then, more collision attacks have been found with relatively low

algorithmic complexities. Constructing diﬀerential paths essentially reduces the time

complexity of ﬁnding collision-inducing messages from brute-force method and the

introduction of disturbance vectors (DV) further simpliﬁes this construction [5, 6, 7, 8].

Hence, ﬁnding the DVs becomes the key to ﬁnding the collision attacks on SHA-1 [9].

Despite the reduction in complexity, ﬁnding DV still remains a computationally

daunting task in a practice sense and often seeking a collision relies on heuristic

approaches. Quantum algorithms, nevertheless, poses unparalleled advantage over

classical algorithms in tackling speciﬁc computational problems. The use of quantum

computers would render some classically improbable tasks tangible, granting the

programmer quantum supremacy [10]. Two particularly well-known problems falling

in this category are the factorization of large integers, solved by Shor’s algorithm

[11], and the searching in unsorted list, solved by Grover’s algorithm [12]. The latter

has been applied in numerous works to enhance computation eﬃcacy [13, 14, 15].

Therefore, it is only natural to take advantage of quantum parallelism to improve the

eﬃcacy of seeking SHA-1 collisions but, to our knowledge, scarcely have such quantum

approaches been attempted. A quantum collision search that elevates from classical

semi-free-start collisions [16, 17] on reduced SHA-256 and SHA-512 was proposed last

year [18].

Here, we propose a quantum algorithm for seeding DVs against SHA-1, which

combines diﬀusion and inversion gating from Grover’s algorithm, quantum phase

gating, diﬀusion gating, and information feedback from classical computing machinery,

to greatly reduce the overall computation complexity. The algorithm runs on a

quantum machine of two n= 16λqubit-long registers RCand RW, where λis the

bit weight of the candidate DVs. While the control register RCstores the addresses

of the DVs, the work register RWcarries the hash computation related information.

The principles of the algorithm apply to other SHA and MD5 hashing protocols as

well, only that the qubit length would vary. The concurrency of searching permitted

by the entanglement between R1and R2signiﬁcantly reduces the query complexity

to O(2n/2), translating to a total temporal complexity of O(2n/2+1). Beginning with

qubit initialization, the algorithm ﬁrst uses Hadamard gates to equally distribute

probability among all DV addresses on R1. It is followed by phase gating, diﬀusion

gating, and data for DV validation to store corresponding entangled computation

states on R2. Grover search then follows by performing the “inversion about average”

A quantum algorithm for ﬁnding collision-inducing disturbance vectors in SHA-1 3

BC2

PPLN

(PSA)

DOPO Pulse FPC

BC1

PPLN

(SHG)

PBS

BC3 BS

PD1

PD2

FPGA

BC4

Feedback Pulse

Input Pulse

BC5

EOS

Output

Figure 1. Experimental schematic of a optical implementation of SHA-1 DV

search algorithm. FPGA: ﬁeld-programmable gate array; PM: phase modulator;

IM: intensity modulator; EOS: electro-optical switch; FPC: ﬁber polarization

controller; FS: ﬁber stretcher; PD: photon diode; BS: beam splitter; PBS:

polarizing beam splitter.

to elicit the address states with the greatest magnitude of probability, which associate

with valid DV states leading to collisions in R2. An algorithmic simulation based

on pure-state quantum evolution simulation package [19] veriﬁes the validity of the

algorithm on 27space.

The proposed algorithm is optically implementable on degenerate optical

parametric oscillators (DOPOs). These parametric oscillators are coherent laser pulses

running in a ring optical cavity. The carrier phase and the polarization direction

of each such pulse are inseparable in a sense equivalent to the inseparability of

two quantum entangled states [20]. The coherence of these pulsed DOPOs can be

maintained by phase-sensitive ampliﬁcation (PSA) in nonlinear optical crystals. The

scale of pulse width being as short as picosecond, a suﬃciently long ring cavity can

store arbitrarily qubit-long information on a train of DOPOs, where the entangled R1

and R2data are encoded on the phases and directions of the DOPOs, respectively.

By virtue of their coherent scalability, these special pulses have been employed to

realize graph-theoretic algorithms on the so-called coherent Ising machine [21, 22, 23]

as well as Shor’s factoring algorithm [24]. We show here that all the quantum

gating and feedback machinery involved in DV searching described above are entirely

implementable via optical means and auxiliary classical computation. In other words,

the proposed algorithm is immediately accessible, where a viable experimental setup

is illustrated in Fig. 1. Before we describe the setup in details in Sec. 5, we explain the

SHA-1 hashing and its valid attacks in Sec. 2, which is followed by the descriptions of

the quantum algorithm and its simulated veriﬁcation in Sec. 3. The conclusions are

given in Sec. 6.

2. Classical collision attacks of SHA-1

The cryptographic hash function takes an input of a 512-bit block and converts it into a

160-bit hash value output. Messages of lengths less than 264 bits long are ﬁrst chopped

文档加载中……请稍候！
如果长时间未打开，您也可以点击刷新试试。

下载文档到电脑，查找使用更方便

10 玖币 0人已下载

立即下载

摘要：

Aquantumalgorithmforndingcollision-inducingdisturbancevectorsinSHA-1JihengDuanDepartmentofPhysicsandChemistry,FacultyofScienceandTechnology,UniversityofMacau,MacauSAR,ChinaMinghuiLiInstituteofAppliedPhysicsandMaterialsEngineering,UniversityofMacau,MacauSAR,ChinaHouIanInstituteofAppliedPhysicsandMat...

展开>> 收起<<

A quantum algorithm for nding collision-inducing disturbance vectors in SHA-1 Jiheng Duan.pdf

共14页,预览3页

还剩页未读，继续阅读

声明：本站为文档C2C交易模式，即用户上传的文档直接被用户下载，本站只是中间服务平台，本站所有文档下载所得的收益归上传人(含作者)所有。玖贝云文库仅提供信息存储空间，仅对用户上传内容的表现方式做保护处理，对上载内容本身不做任何修改或编辑。若文档所含内容侵犯了您的版权或隐私，请立即通知玖贝云文库，我们立即给予删除！

A quantum algorithm for nding collision-inducing disturbance vectors in SHA-1 Jiheng Duan

相关推荐

开通VIP享超值会员特权

作者详情

相关内容

热门标签

举报选择: