SHA-1

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的操作产生散列碰撞。2017年2月23日，首次公开碰撞。SHA-1容易受到长度扩展攻击。

SHA-1（英语：Secure Hash Algorithm 1，中文名：安全散列算法1）是一种密码散列函数，美国国家安全局设计，并由美国国家标准技术研究所（NIST）发布为联邦资料处理标准（FIPS）。SHA-1可以生成一个被称为消息摘要的160位（20字节）散列值，散列值通常的呈现形式为40个十六进制数。

2005年，密码分析人员发现了对SHA-1的有效攻击方法，这表明该算法可能不够安全，不能继续使用，自2010年以来，许多组织建议用SHA-2或SHA-3来替换SHA-1。Microsoft、Google以及Mozilla都宣布，它们旗下的浏览器将在2017年停止接受使用SHA-1算法签名的SSL证书。

2017年2月23日，CWI Amsterdam与Google宣布了一个成功的SHA-1碰撞攻击，发布了两份内容不同但SHA-1散列值相同的PDF文件作为概念证明。

2020年，针对SHA-1的选择前缀冲突攻击已经实际可行。建议尽可能用SHA-2或SHA-3取代SHA-1。

SHA-0和SHA-1

SHA-1压缩算法中的一个循环。A, B, C, D和E是这个state中的32位文字；F是会变化的非线性函数；<<<_n代表bit向左循环移动n个位置。n因操作而异。田代表modulo 2³²之下的加法。K_t是一个常量。W_t代表经过拓展后的原文。

最初载明的算法于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⁶⁴比特的消息，转换成一串160位的消息摘要；其设计原理相似于MIT教授Ronald L. Rivest所设计的密码学散列算法MD4和MD5。

SHA-0的破解

在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安全性。

2005年二月，王小云和殷益群、于红波再度发表了对SHA-0破密的算法，可在2³⁹的计算复杂度内就找到碰撞。

SHA-1的破解

鉴于SHA-0的破密成果，专家们建议那些计划利用SHA-1实现密码系统的人们也应重新考虑。在2004年CRYPTO会议结果公布之后，NIST即宣布他们将逐渐减少使用SHA-1，改以SHA-2取而代之。

2005年，Rijmen和Oswald发表了对SHA-1较弱版本（53次的加密循环而非80次）的攻击：在2⁸⁰的计算复杂度之内找到碰撞。

2005年二月，王小云、殷益群及于红波发表了对完整版SHA-1的攻击，只需少于2⁶⁹的计算复杂度，就能找到一组碰撞。（利用生日攻击法找到碰撞需要2⁸⁰的计算复杂度。）

这篇论文的作者们写道；“我们的破密分析是以对付SHA-0的差分攻击、近似碰撞、多区块碰撞技术、以及从MD5算法中查找碰撞的消息更改技术为基础。没有这些强力的分析工具，SHA-1就无法破解。”此外，作者还展示了一次对58次加密循环SHA-1的破密，在2³³个单位操作内就找到一组碰撞。完整攻击方法的论文发表在2005年八月的CRYPTO会议中。

殷益群在一次面谈中如此陈述：“大致上来说，我们找到了两个弱点：其一是前置处理不够复杂；其二是前20个循环中的某些数学运算会造成不可预期的安全性问题。”

2005年8月17日的CRYPTO会议尾声中王小云、姚期智、姚储枫再度发表更有效率的SHA-1攻击法，能在2⁶³个计算复杂度内找到碰撞。

2006年的CRYPTO会议上，Christian Rechberger和Christophe De Cannière宣布他们能在容许攻击者决定部分原消息的条件之下，找到SHA-1的一个碰撞。

在密码学的学术理论中，任何攻击方式，其计算复杂度若少于暴力搜索法所需要的计算复杂度，就能被视为针对该密码系统的一种破密法；但这并不表示该破密法已经可以进入实际应用的阶段。

就应用层面的考量而言，一种新的破密法出现，暗示着将来可能会出现更有效率、足以实用的改良版本。虽然这些实用的破密法版本根本还没诞生，但确有必要发展更强的散列算法来取代旧的算法。在“碰撞”攻击法之外，另有一种反译攻击法（Pre-image attack），就是由散列出的字符串反推原本的消息；反译攻击的严重性更在碰撞攻击之上，但也更困难。在许多会应用到密码散列的情境（如用户密码的存放、文件的数字签名等）中，碰撞攻击的影响并不是很大。举例来说，一个攻击者可能不会只想要伪造一份一模一样的文件，而会想改造原来的文件，再附上合法的签名，来愚弄持有公钥的验证者。另一方面，如果可以从密文中反推未加密前的用户密码，攻击者就能利用得到的密码登录其他用户的账户，而这种事在密码系统中是不能被允许的。但若存在反译攻击，只要能得到指定用户密码散列过后的字符串（通常存在影档中，而且可能不会透露原密码信息），就有可能得到该用户的密码。

2017年2月23日，Google公司宣布，他们与CWI Amsterdam合作创建了两个有着相同SHA-1值但内容不同的PDF文件，这代表SHA-1算法已被正式攻破。

2020年，针对SHA-1的选择前缀冲突攻击已经实际可行。建议尽可能用SHA-2或SHA-3取代SHA-1。在数字签名领域，用更安全的SHA-2或SHA-3替换SHA-1已经变得急迫。

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