SHA-0

**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

最初載明的演算法於 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 演算法的虛擬碼：

```
_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
```

## 參考文獻