|
|
目录
- 1 介绍
- 2 SHA-0和SHA-1
- ▪ SHA-0的破解
- ▪ SHA-1的破解
- 3 SHA-1算法
介绍
SHA-1已经不再视为可抵御有充足资金、充足计算资源的攻击者。2005年，密码分析人员发现了对SHA-1的有效攻击方法，这表明该算法可能不够安全，不能继续使用，自2010年以来，许多组织建议用
SHA-2
或
SHA-3
来替换SHA-1。
Microsoft
、
Google
以及
Mozilla
都宣布，它们旗下的浏览器将在2017年前停止接受使用SHA-1算法签名的
SSL证书
。
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可将一个最大2^64比特的消息，转换成一串160位的消息摘要；其设计原理相似于MIT教授
Ronald L. Rivest
所设计的密码学散列算法
MD4
和
MD5
。
[1]
在
CRYPTO
98上，两位法国研究者提出一种对SHA-0的攻击方式：在2的计算复杂度之内，就可以发现一次碰撞（即两个不同的消息对应到相同的消息摘要）；这个数字小于
生日攻击法
所需的2，也就是说，存在一种算法，使其安全性不到一个理想的散列函数抵抗攻击所应具备的计算复杂度。
2004年时，
Biham
和Chen也发现了SHA-0的近似碰撞，也就是两个消息可以散列出几乎相同的数值；其中162比特中有142比特相同。他们也发现了SHA-0的完整碰撞（相对于近似碰撞），将本来需要80次方的复杂度降低到62次方。
2004年8月12日，Joux, Carribault, Lemuet和Jalby宣布找到SHA-0算法的完整碰撞的方法，这是归纳Chabaud和Joux的攻击所完成的结果。发现一个完整碰撞只需要2的计算复杂度。他们使用的是一台有256颗
Itanium2
处理器的超级计算机，约耗80,000 CPU工时。
2004年8月17日，在
CRYPTO
2004的Rump会议上，
王小云
，
冯登国
（Feng）、
来学嘉
（Lai），和于红波（Yu）宣布了攻击
MD5
、SHA-0和其他
散列函数
的初步结果。他们攻击SHA-0的计算复杂度是2，这意味着他们的攻击成果比Joux还有其他人所做的更好。请参见
MD5安全性
。
鉴于SHA-0的破密成果，专家们建议那些计划利用SHA-1实现
密码
系统的人们也应重新考虑。在2004年
CRYPTO
会议结果公布之后，NIST即宣布他们将逐渐减少使用SHA-1，改以SHA-2取而代之。
2005年，
Rijmen
和Oswald发表了对SHA-1较弱版本（53次的加密循环而非80次）的攻击：在2的计算复杂度之内找到碰撞。
这篇论文的作者们写道；“我们的破密分析是以对付SHA-0的
差分攻击
、近似碰撞、多区块碰撞技术、以及从
MD5
算法中查找碰撞的消息更改技术为基础。没有这些强力的分析工具，SHA-1就无法破解。”此外，作者还展示了一次对58次加密循环SHA-1的破密，在2个单位操作内就找到一组碰撞。完整攻击方法的论文发表在2005年八月的
CRYPTO
会议中。
殷益群在一次面谈中如此陈述：“大致上来说，我们找到了两个弱点：其一是前置处理不够复杂；其二是前20个循环中的某些数学运算会造成不可预期的安全性问题。”
2006年的
CRYPTO
会议上，
Christian Rechberger
和
Christophe De Cannière
宣布他们能在容许攻击者决定部分原消息的条件之下，找到SHA-1的一个碰撞。
在密码学的学术理论中，任何攻击方式，其计算复杂度若少于暴力搜索法所需要的计算复杂度，就能被视为针对该密码系统的一种破密法；但这并不表示该破密法已经可以进入实际应用的阶段。
就应用层面的考量而言，一种新的破密法出现，暗示着将来可能会出现更有效率、足以实用的改良版本。虽然这些实用的破密法版本根本还没诞生，但确有必要发展更强的散列算法来取代旧的算法。在“碰撞”攻击法之外，另有一种反译攻击法（Pre-image attack），就是由散列出的字符串反推原本的消息；反译攻击的严重性更在碰撞攻击之上，但也更困难。在许多会应用到密码散列的情境（如用户密码的存放、文件的
数字签名
等）中，碰撞攻击的影响并不是很大。举例来说，一个攻击者可能不会只想要伪造一份一模一样的文件，而会想改造原来的文件，再附上合法的签名，来愚弄持有公钥的验证者。另一方面，如果可以从密文中反推未加密前的用户密码，攻击者就能利用得到的密码登录其他用户的账户，而这种事在密码系统中是不能被允许的。但若存在反译攻击，只要能得到指定用户密码散列过后的字符串（通常存在影档中，而且可能不会透露原密码信息），就有可能得到该用户的密码。
2017年2月23日，Google公司公告宣称他们与CWI Amsterdam合作共同创建了两个有着相同的SHA-1值但内容不同的PDF文件，这代表SHA-1算法已被正式攻破。
SHA-1算法
Note: All variables are unsigned 32 bits and wrap modulo 2
32
when calculating
İniyorlar 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 功能，可以方便的生成字符串文本的 hash 值。
[2]
