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

<image>

最初载明的算法于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的攻击方式：在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算法已被正式攻破。

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

## SHA-1算法

以下是SHA-1算法的伪代码：

```
<span style="color: green;">''Note: All variables are unsigned 32 bits and wrap modulo 2<sup>32</sup> when calculating''</span>

<span style="color: green;">''Initial variables:''</span>
h0 := 0x67452301
h1 := 0xEFCDAB89
h2 := 0x98BADCFE
h3 := 0x10325476
h4 := 0xC3D2E1F0

<span style="color: green;">''Pre-processing:''</span>
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

<span style="color: green;">''Process the message in successive 512-bit chunks:''</span>
break message into 512-bit chunks
'''for''' each chunk
    break chunk into sixteen 32-bit big-endian words w[i], 0 ≤ i ≤ 15

    <span style="color: green;">''Extend the sixteen 32-bit words into eighty 32-bit words:''</span>
    '''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

    <span style="color: green;">''Initialize hash value for this chunk:''</span>
    a := h0
    b := h1
    c := h2
    d := h3
    e := h4

    <span style="color: green;">''Main loop:''</span>
    '''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

    <span style="color: green;">''Add this chunk's hash to result so far:''</span>
    h0 := h0 + a
    h1 := h1 + b
    h2 := h2 + c
    h3 := h3 + d
    h4 := h4 + e

<span style="color:green;">''Produce the final hash value (big-endian):''</span>
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))         <span style="color: green;">''(alternative)''</span>

(40 ≤ i ≤ 59): f := (b '''and''' c) '''or''' (d '''and''' (b '''or''' c))   <span style="color: green;">''(alternative 1)''</span>
(40 ≤ i ≤ 59): f := (b '''and''' c) '''or''' (d '''and''' (b '''xor''' c))  <span style="color: green;">''(alternative 2)''</span>
(40 ≤ i ≤ 59): f := (b '''and''' c) + (d '''and''' (b '''xor''' c))   <span style="color: green;">''(alternative 3)''</span>
```

## SHA-1示例

空文的散列为：

```
SHA-1("") 
= da39a3ee5e6b4b0d3255bfef95601890afd80709
```

## 基本资料

- 设计者：美国国家安全局
- publish date：1993年（SHA-0）、1995年（SHA-1）
- 系列：安全散列算法家族
- 认证：FIPS PUB 180-4，CRYPTREC（监测）
- 摘要长度：160位元
- 分组长度：512位元
- 结构：Merkle–Damgård结构
- 重复回数：80
- cryptanalysis：2011年，Marc Stevens的攻击，可以通过复杂度260.3至265.3的操作产生散列碰撞。2017年2月23日，首次公开碰撞。SHA-1容易受到长度扩展攻击。