SHA-1
概述 | |
---|---|
设计者 | 美国国家安全局 |
首次发布 | 1993年(SHA-0) 1995年(SHA-1) |
系列 | 安全散列算法家族 |
认证 | FIPS PUB 180-4,CRYPTREC(监测) |
密码细节 | |
摘要长度 | 160位元 |
分组长度 | 512位元 |
结构 | Merkle–Damgård结构 |
重复回数 | 80 |
最佳公开破解 | |
2011年,Marc Stevens的攻击,可以通过复杂度260.3至265.3的操作产生散列碰撞。[1]2017年2月23日,首次公开碰撞。[2]SHA-1容易受到长度扩展攻击。 |
SHA-1(英语:Secure Hash Algorithm 1,中文名:安全散列算法1)是一种密码散列函数,美国国家安全局设计,并由美国国家标准技术研究所(NIST)发布为联邦资料处理标准(FIPS)[3]。SHA-1可以生成一个被称为消息摘要的160位(20字节)散列值,散列值通常的呈现形式为40个十六进制数。
2005年,密码分析人员发现了对SHA-1的有效攻击方法,这表明该算法可能不够安全,不能继续使用[4],自2010年以来,许多组织建议用SHA-2或SHA-3来替换SHA-1[5][6][7]。Microsoft[8]、Google[9]以及Mozilla[10][11][12]都宣布,它们旗下的浏览器将在2017年停止接受使用SHA-1算法签名的SSL证书。
2017年2月23日,CWI Amsterdam与Google宣布了一个成功的SHA-1碰撞攻击[13][14],发布了两份内容不同但SHA-1散列值相同的PDF文件作为概念证明。[15]
2020年,针对SHA-1的选择前缀冲突攻击已经实际可行。建议尽可能用SHA-2或SHA-3取代SHA-1。[16][17]
SHA-0和SHA-1
[编辑]最初载明的演算法于1993年发布,称做安全杂凑标准(Secure Hash Standard),FIPS PUB 180。这个版本现在常被称为SHA-0。它在发布之后很快就被NSA撤回,并且由1995年发布的修订版本FIPS PUB 180-1(通常称为SHA-1)取代。SHA-1和SHA-0的演算法只在压缩函数的讯息转换部份差了一个位元的循环位移。根据NSA的说法,它修正了一个在原始演算法中会降低杂凑安全性的弱点。然而NSA并没有提供任何进一步的解释或证明该弱点已被修正。而后SHA-0和SHA-1的弱点相继被攻破,SHA-1似乎是显得比SHA-0有抵抗性,这多少证实了NSA当初修正演算法以增进安全性的声明。
SHA-0和SHA-1可将一个最大264位元的讯息,转换成一串160位元的讯息摘要;其设计原理相似于MIT教授Ronald L. Rivest所设计的密码学杂凑演算法MD4和MD5。
SHA-0的破解
[编辑]在CRYPTO 98上,两位法国研究者提出一种对SHA-0的攻击方式[18]:在261的计算复杂度之内,就可以发现一次碰撞(即两个不同的讯息对应到相同的讯息摘要);这个数字小于生日攻击法所需的280,也就是说,存在一种演算法,使其安全性不到一个理想的杂凑函数抵抗攻击所应具备的计算复杂度。
2004年时,Biham和Chen也发现了SHA-0的近似碰撞,也就是两个讯息可以杂凑出几乎相同的数值;其中162位元中有142位元相同。他们也发现了SHA-0的完整碰撞(相对于近似碰撞),将本来需要80次方的复杂度降低到62次方。
2004年8月12日,Joux, Carribault, Lemuet和Jalby宣布找到SHA-0演算法的完整碰撞的方法,这是归纳Chabaud和Joux的攻击所完成的结果。发现一个完整碰撞只需要251的计算复杂度。他们使用的是一台有256颗Itanium2处理器的超级电脑,约耗80,000 CPU工时。
2004年8月17日,在CRYPTO 2004的Rump会议上,王小云,冯登国(Feng)、来学嘉(Lai),和于红波(Yu)宣布了攻击MD5、SHA-0和其他杂凑函数的初步结果。他们攻击SHA-0的计算复杂度是240,这意味的他们的攻击成果比Joux还有其他人所做的更好。请参见MD5安全性。
2005年二月,王小云和殷益群、于红波再度发表了对SHA-0破密的演算法,可在239的计算复杂度内就找到碰撞。
SHA-1的破解
[编辑]鉴于SHA-0的破密成果,专家们建议那些计划利用SHA-1实作密码系统的人们也应重新考虑。在2004年CRYPTO会议结果公布之后,NIST即宣布他们将逐渐减少使用SHA-1,改以SHA-2取而代之。
2005年,Rijmen和Oswald发表了对SHA-1较弱版本(53次的加密回圈而非80次)的攻击:在280的计算复杂度之内找到碰撞。
2005年二月,王小云、殷益群及于红波发表了对完整版SHA-1的攻击,只需少于269的计算复杂度,就能找到一组碰撞。(利用生日攻击法找到碰撞需要280的计算复杂度。)
这篇论文的作者们写道;“我们的破密分析是以对付SHA-0的差分攻击、近似碰撞、多区块碰撞技术、以及从MD5演算法中寻找碰撞的讯息更改技术为基础。没有这些强力的分析工具,SHA-1就无法破解。”此外,作者还展示了一次对58次加密回圈SHA-1的破密,在233个单位操作内就找到一组碰撞。完整攻击方法的论文发表在2005年八月的CRYPTO会议中。
殷益群在一次面谈中如此陈述:“大致上来说,我们找到了两个弱点:其一是前置处理不够复杂;其二是前20个回圈中的某些数学运算会造成不可预期的安全性问题。”
2005年8月17日的CRYPTO会议尾声中王小云、姚期智、姚储枫再度发表更有效率的SHA-1攻击法,能在263个计算复杂度内找到碰撞。
2006年的CRYPTO会议上,Christian Rechberger和Christophe De Cannière宣布他们能在容许攻击者决定部分原讯息的条件之下,找到SHA-1的一个碰撞。
在密码学的学术理论中,任何攻击方式,其计算复杂度若少于暴力搜寻法所需要的计算复杂度,就能被视为针对该密码系统的一种破密法;但这并不表示该破密法已经可以进入实际应用的阶段。
就应用层面的考量而言,一种新的破密法出现,暗示着将来可能会出现更有效率、足以实用的改良版本。虽然这些实用的破密法版本根本还没诞生,但确有必要发展更强的杂凑演算法来取代旧的演算法。在“碰撞”攻击法之外,另有一种反译攻击法(Pre-image attack),就是由杂凑出的字串反推原本的讯息;反译攻击的严重性更在碰撞攻击之上,但也更困难。在许多会应用到密码杂凑的情境(如用户密码的存放、文件的数位签章等)中,碰撞攻击的影响并不是很大。举例来说,一个攻击者可能不会只想要伪造一份一模一样的文件,而会想改造原来的文件,再附上合法的签章,来愚弄持有公钥的验证者。另一方面,如果可以从密文中反推未加密前的使用者密码,攻击者就能利用得到的密码登入其他使用者的帐户,而这种事在密码系统中是不能被允许的。但若存在反译攻击,只要能得到指定使用者密码杂凑过后的字串(通常存在影档中,而且可能不会透露原密码资讯),就有可能得到该使用者的密码。
2017年2月23日,Google公司宣布,他们与CWI Amsterdam合作创建了两个有着相同SHA-1值但内容不同的PDF文件,这代表SHA-1演算法已被正式攻破。[19]
2020年,针对SHA-1的选择前缀冲突攻击已经实际可行。建议尽可能用SHA-2或SHA-3取代SHA-1。在数位签章领域,用更安全的SHA-2或SHA-3替换SHA-1已经变得急迫。[16][17]
SHA-1演算法
[编辑]以下是SHA-1演算法的伪代码:
Note: All variables are unsigned 32 bits and wrap modulo 232 when calculating
Initial variables:
h0 := 0x67452301
h1 := 0xEFCDAB89
h2 := 0x98BADCFE
h3 := 0x10325476
h4 := 0xC3D2E1F0
Pre-processing:
append the bit '1' to the message
append k bits '0', where k is the minimum number >= 0 such that the resulting message
length (in bits) is congruent to 448(mod 512)
append length of message (before pre-processing), in bits, as 64-bit big-endian integer
Process the message in successive 512-bit chunks:
break message into 512-bit chunks
for each chunk
break chunk into sixteen 32-bit big-endian words w[i], 0 ≤ i ≤ 15
Extend the sixteen 32-bit words into eighty 32-bit words:
for i from 16 to 79
w[i] := (w[i-3] xor w[i-8] xor w[i-14] xor w[i-16]) leftrotate 1
Initialize hash value for this chunk:
a := h0
b := h1
c := h2
d := h3
e := h4
Main loop:
for i from 0 to 79
if 0 ≤ i ≤ 19 then
f := (b and c) or ((not b) and d)
k := 0x5A827999
else if 20 ≤ i ≤ 39
f := b xor c xor d
k := 0x6ED9EBA1
else if 40 ≤ i ≤ 59
f := (b and c) or (b and d) or(c and d)
k := 0x8F1BBCDC
else if 60 ≤ i ≤ 79
f := b xor c xor d
k := 0xCA62C1D6
temp := (a leftrotate 5) + f + e + k + w[i] e := d d := c c := b leftrotate 30 b := a a := temp
Add this chunk's hash to result so far:
h0 := h0 + a
h1 := h1 + b
h2 := h2 + c
h3 := h3 + d
h4 := h4 + e
Produce the final hash value (big-endian):
digest = hash = h0 append h1 append h2 append h3 append h4
上述关于f
运算式列于FIPS PUB 180-1中,以下替代运算式也许也能在主要回圈里计算f
:
(0 ≤ i ≤ 19): f := d xor (b and (c xor d)) (alternative) (40 ≤ i ≤ 59): f := (b and c) or (d and (b or c)) (alternative 1) (40 ≤ i ≤ 59): f := (b and c) or (d and (b xor c)) (alternative 2) (40 ≤ i ≤ 59): f := (b and c) + (d and (b xor c)) (alternative 3)
SHA-1示例
[编辑]空文的散列为:
SHA-1("") = da39a3ee5e6b4b0d3255bfef95601890afd80709
参考文献
[编辑]- ^ Stevens, Marc. Attacks on Hash Functions and Applications (PDF) (学位论文). Leiden University. 2012-06-19 [2016-12-15]. ISBN 9789461913173. OCLC 795702954. hdl:1887/19093. (原始内容存档 (PDF)于2017-03-18).
- ^ Stevens, Marc; Bursztein, Elie; Karpman, Pierre; Albertini, Ange; Markov, Yarik. Katz, Jonathan; Shacham, Hovav , 编. The First Collision for Full SHA-1 (PDF). Advances in Cryptology – CRYPTO 2017. Lecture Notes in Computer Science 10401. Springer: 570–596. 2017 [2017-02-23]. ISBN 9783319636870. doi:10.1007/978-3-319-63688-7_19. (原始内容 (PDF)存档于2018-05-15). 简明摘要 – Google Security Blog (2017-02-23).
- ^ 存档副本 (PDF). [2016-12-15]. (原始内容存档 (PDF)于2013-02-17).
- ^ Schneier, Bruce. Schneier on Security: Cryptanalysis of SHA-1. 2005-02-18 [2016-12-15]. (原始内容存档于2017-04-14).
- ^ NIST.gov - Computer Security Division - Computer Security Resource Center. [2016-12-15]. (原始内容存档于2017-04-29).
- ^ Stevens1, Marc; Karpman, Pierre; Peyrin, Thomas. The SHAppening: freestart collisions for SHA-1. [2015-10-09]. (原始内容存档于2017-04-19).
- ^ Bruce Schneier. SHA-1 Freestart Collision. Schneier on Security. 2015-10-08 [2016-12-15]. (原始内容存档于2017-01-28).
- ^ Windows Enforcement of Authenticode Code Signing and Timestamping. Microsoft. 2015-09-24 [2016-08-07]. (原始内容存档于2016-10-05).
- ^ Intent to Deprecate: SHA-1 certificates. Google. 2014-09-03 [2014-09-04].[失效链接]
- ^ Bug 942515 - stop accepting SHA-1-based SSL certificates with notBefore >= 2014-03-01 and notAfter >= 2017-01-01, or any SHA-1-based SSL certificates after 2017-01-01. Mozilla. [2014-09-04]. (原始内容存档于2014-09-07).
- ^ CA:Problematic Practices - MozillaWiki. Mozilla. [2014-09-09]. (原始内容存档于2017-05-06).
- ^ Phasing Out Certificates with SHA-1 based Signature Algorithms | Mozilla Security Blog. Mozilla. 2014-09-23 [2014-09-24]. (原始内容存档于2017-04-25).
- ^ CWI, Google announce first collision for Industry Security Standard SHA-1. [2017-02-23]. (原始内容存档于2017-02-23).
- ^ Announcing the first SHA1 collision. Google Online Security Blog. 2017-02-23. (原始内容存档于2017-04-24).
- ^ SHAttered. [2017-02-23]. (原始内容存档于2017-04-12).
- ^ 16.0 16.1 存档副本 (PDF). [2020-09-09]. (原始内容存档 (PDF)于2020-09-10).
- ^ 17.0 17.1 Critical flaw demonstrated in common digital security algorithm. media.ntu.edu.sg. [2020-09-08]. (原始内容存档于2020-04-19) (美国英语).
- ^ Chabaud and Joux, 1998
- ^ Announcing the first SHA1 collision. Google Online Security Blog. 2017-02-23 [2017-02-24]. (原始内容存档于2017-04-24).