安全雜湊演算法（SHA，Secure Hash Algorithm）系列是 NIST 為美國非軍事聯邦政府機構所定義的標準。它們被視為世界標準，只有少數非美國政府基於主權而非對 SHA 安全性缺乏信任的理由，選擇自己的雜湊演算法（如中國的 SM3、俄羅斯的 Streebog、烏克蘭的 Kupyna）。美國的 SHA 系列受過密碼分析者比非美國演算法更廣泛的檢視。

MD5 處理 512 位元區塊訊息、更新 128 位元內部狀態、產生 128 位元雜湊，因此頂多提供 128 位元原像安全性與 64 位元碰撞安全性。

1996 年密碼分析者就警告 MD5 壓縮函式存在碰撞，但無人理會，直到 2005 年一組中國密碼分析者發現如何為完整的 MD5 雜湊計算碰撞。

本書寫作時，找出一個 MD5 碰撞只需幾秒鐘，然而許多系統仍在使用或支援 MD5，往往是為了向後相容。

SHA-1#

SHA-1 標準源自 NSA 原始 SHA-0 雜湊函式的一次失敗。1993 年 NIST 把 NSA 的 SHA-0 標準化，但 1995 年 NSA 就發布 SHA-1 來修正 SHA-0 中一個未指明的安全問題。

這次調整的原因在 1998 年變得明朗：兩位研究者發現如何用約 2^60 次運算為 SHA-0 找到碰撞——對 SHA-0、SHA-1 這類 160 位元雜湊函式而言，預期應該是 2^80。後來的攻擊把複雜度降到約 2^33 次運算，使得 SHA-0 的實際碰撞可在一小時內找到。

內部結構#

SHA-1 把 Merkle–Damgård 雜湊函式與基於一個特製區塊密碼（有時稱為 SHACAL）的 Davies–Meyer 壓縮函式結合。也就是說，SHA-1 對 512 位元訊息區塊 M 迭代下列操作：

H = E(M, H) + H

這裡用加號 + 而非 XOR 是刻意的。

E(M, H) 與 H 被視為 32 位元整數的陣列，同一位置的兩個字相加：E(M, H) 的第一個 32 位元字加上 H 的第一個 32 位元字，依此類推。

H 的初始值對任何訊息都是常數，接著依上式修改，處理完所有區塊後 H 的最終值就是訊息的雜湊。

壓縮函式：

SHA1-compress(H, M) {
    (a0, b0, c0, d0, e0) = H   // parsing H as five 32-bit big endian words
    (a, b, c, d, e) = SHA1-blockcipher(a0, b0, c0, d0, e0, M)
    return (a + a0, b + b0, c + c0, d + d0, e + e0)
}

區塊密碼：它以 512 位元訊息區塊 M 為金鑰，迭代 80 個步驟的短運算序列來變換五個 32 位元字，用五個字的組合取代字 a，再像移位暫存器一樣位移陣列中的其他字：

SHA1-blockcipher(a, b, c, d, e, M) {
    W = expand(M)
    for i = 0 to 79 {
        new = (a <<< 5) + f(i, b, c, d) + e + K[i] + W[i]
        (a, b, c, d, e) = (new, a, b >>> 2, c, d)
    }
    return (a, b, c, d, e)
}

expand() 函式：從 16 字的訊息區塊建立一個 80 個 32 位元字的陣列 W——前 16 個字設為 M，之後的字設為先前字的 XOR 組合並左旋 1 位元：

expand(M) {
    // the 512-bit M is seen as an array of sixteen 32-bit words
    W = empty array of eighty 32-bit words
    for i = 0 to 79 {
        if i < 16 then W[i] = M[i]
        else
             W[i] = (W[i – 3] ⊕ W[i – 8] ⊕ W[i – 14] ⊕ W[i – 16]) <<< 1
    }
    return W
}

那個 <<< 1 操作，是 SHA-1 與 SHA-0 之間唯一的差別。

f() 函式：一連串基本的逐位元邏輯運算（布林函式），依輪數而定：

f(i, b, c, d) {
    if i < 20 then return ((b & c) ⊕ (~b & d))
    if i < 40 then return (b ⊕ c ⊕ d)
    if i < 60 then return ((b & c) ⊕ (b & d) ⊕ (c & d))
    if i < 80 then return (b ⊕ c ⊕ d)
}

第二與第四個布林函式只是把三個輸入字 XOR 起來，是線性運算。

相對地，第一與第三個函式使用非線性的 &（邏輯 AND）運算子，以防禦差分密碼分析——那種利用逐位元差異之可預測傳播的攻擊。

沒有 & 運算子（例如若 f() 永遠是 b ⊕ c ⊕ d），SHA-1 只要追蹤其內部狀態中的樣式就能輕易攻破。

對 SHA-1 的攻擊#

SHA-1 雖比 SHA-0 安全，但仍然不安全——這就是為什麼 Chrome 瀏覽器把 HTTPS 連線使用 SHA-1 的網站標示為不安全。

儘管 160 位元的雜湊應該給予它 80 位元的碰撞抗性，2005 年研究人員在 SHA-1 中發現弱點，估計找到碰撞約需 2^63 次計算（若演算法完美無瑕，該數字應為 2^80）。

真正的 SHA-1 碰撞在十二年後才出現：經過多年密碼分析，Marc Stevens 等研究者與 Google 研究者合作，提出了兩份會碰撞的 PDF 文件（見 https://shattered.io/ ↗）。

瀏覽器現在把 SHA-1 標為不安全，NIST 也不再推薦它。請改用 SHA-2 系列、BLAKE2 或 SHA-3。

SHA-2#

SHA-2 是 SHA-1 的後繼者，由 NSA 設計、NIST 標準化。它是一個包含四個雜湊函式的家族：SHA-224、SHA-256、SHA-384、SHA-512，其中 SHA-256 與 SHA-512 是兩個主要演算法。三位數字代表各自雜湊的位元長度。

SHA-256#

開發 SHA-2 的初衷是產生更長的雜湊，從而提供比 SHA-1 更高的安全等級。SHA-1 有 160 位元的鏈接值，SHA-256 則有 256 位元（八個 32 位元字）。

SHA-1SHA-256
鏈接值160 位元256 位元
訊息區塊512 位元512 位元
輪數8064
每次迭代算術運算數1126

SHA-256 用 expand256() 把 16 字的訊息區塊擴張成 64 字：

expand256(M) {
    // the 512-bit M is seen as an array of sixteen 32-bit words
    W = empty array of sixty-four 32-bit words
    for i = 0 to 63 {
        if i < 16 then W[i] = M[i]
        else {
             // the ">>" shifts instead of a ">>>" rotates and is not a typo
             s0 = (W[i – 15] >>> 7) ⊕ (W[i – 15] >>> 18) ⊕ (W[i – 15] >> 3)
             s1 = (W[i – 2] >>> 17) ⊕ (W[i – 2] >>> 19) ⊕ (W[i – 2] >> 10)
             W[i] = W[i – 16] + s0 + W[i – 7] + s1
        }
    }
    return W
}

注意 SHA-2 的訊息擴張比 SHA-1 的 expand() 複雜得多——後者只做 XOR 與 1 位元旋轉。SHA-256 壓縮函式的主迴圈也比 SHA-1 複雜。這些運算同樣是 XOR、邏輯 AND 與字旋轉。

其他 SHA-2 演算法#

  • SHA-224：演算法與 SHA-256 完全相同，只是初始值是另一組八個 32 位元字，且雜湊值長 224 位元（取最終鏈接值的前 224 位元）。
  • SHA-512：與 SHA-256 相似，但處理 64 位元字而非 32 位元字。因此它使用 512 位元鏈接值（八個 64 位元字）、吃 1024 位元訊息區塊（十六個 64 位元字），並執行 80 輪而非 64 輪。壓縮函式其餘部分幾乎與 SHA-256 相同，但旋轉距離不同以配合更寬的字長（例如 SHA-512 有 a >>> 34 這種操作，對 SHA-256 的 32 位元字就講不通）。
  • SHA-384：之於 SHA-512，就如同 SHA-224 之於 SHA-256——同樣的演算法，但初始值不同、最終雜湊截斷成 384 位元。

安全性#

就安全性而言，四個 SHA-2 版本目前都不負所望：SHA-256 保證 256 位元原像抗性，SHA-512 保證約 256 位元碰撞抗性，依此類推。

不過並沒有真正的證明說 SHA-2 函式是安全的——我們談的是「可能的安全性」。

在 MD5 與 SHA-1 遭到實際攻擊之後，研究者與 NIST 因 SHA-2 與 SHA-1 的相似性而擔心它的長期安全性，許多人相信對 SHA-2 的攻擊只是時間問題。

本書寫作時，我們尚未見到對 SHA-2 的成功攻擊。無論如何，NIST 準備了備案：SHA-3。

SHA-3 競賽#

2007 年宣布的 NIST 雜湊函式競賽（SHA-3 競賽的正式名稱）以徵件與幾項基本要求展開：

  • 提交的雜湊至少要與 SHA-2 一樣安全、一樣快。
  • 至少要能做到 SHA-2 所能做的事。
  • 不該與 SHA-1 和 SHA-2 太像，以免受到那些能攻破 SHA-1、乃至可能攻破 SHA-2 的攻擊。

到 2008 年，NIST 收到來自世界各地的 64 件提交，包括大學與大企業（BT、IBM、微軟、高通、Sony 等）。其中 51 件符合要求，進入第一輪。

競賽最初幾週，密碼分析者無情地攻擊這些提交。2009 年 7 月，NIST 宣布 14 個第二輪候選者。再花 15 個月分析與評估效能後，NIST 選出五個決選者：

  • BLAKE：一個強化版的 Merkle–Damgård 雜湊，其壓縮函式基於一個區塊密碼，而該區塊密碼又基於串流密碼 ChaCha 的核心函式——一連串加法、XOR 與字旋轉。由瑞士與英國的學術研究者團隊設計，包含本書作者。
  • Grøstl：一個強化版的 Merkle–Damgård 雜湊，其壓縮函式使用兩個基於 AES 區塊密碼核心函式的置換（或固定金鑰區塊密碼）。由丹麥與奧地利的七位學術研究者設計。
  • JH：一個調整過的海綿函式建構，訊息區塊在置換前後都注入，而非只在之前。其置換執行類似替換—置換區塊密碼的操作。由新加坡某大學的一位密碼學家設計。
  • Keccak：一個海綿函式，其置換只執行逐位元運算。由一家總部在比利時與義大利的半導體公司的四位密碼學家設計，其中包含 AES 兩位設計者之一。
  • Skein：一個基於不同於 Merkle–Damgård 之運作模式的雜湊函式，其壓縮函式基於一個只使用整數加法、XOR 與字旋轉的新型區塊密碼。由學界與業界的八位密碼學家設計，除一人外全在美國，包含知名的 Bruce Schneier。

深入分析五個決選者後，NIST 宣布優勝者：Keccak。

NIST 的報告嘉許 Keccak「優雅的設計、大的安全邊際、良好的一般效能、在硬體上卓越的效率，以及它的彈性」。

Keccak（SHA-3）#

NIST 選擇 Keccak 的原因之一，是它與 SHA-1、SHA-2 完全不同——首先，它是一個海綿函式。

Keccak 的核心演算法是一個 1600 位元狀態的置換，吃進 1152、1088、832 或 576 位元的區塊，分別產生 224、256、384 或 512 位元的雜湊值——與 SHA-2 系列相同的四種長度。

但與 SHA-2 不同的是，SHA-3 對全部四種雜湊長度只用單一個核心演算法，而非兩個。

不只是雜湊#

另一個原因是 Keccak 不只是雜湊。SHA-3 標準文件 FIPS 202 定義了：

  • 四個雜湊：SHA3-224、SHA3-256、SHA3-384、SHA3-512
  • 兩個演算法：SHAKE128 與 SHAKE256（SHAKE = Secure Hash Algorithm with Keccak）

SHAKE 這兩個是可擴充輸出函式（XOF，extendable-output functions）——能產生可變長度、甚至非常長之雜湊的雜湊函式。128 與 256 代表各自的安全等級。

核心演算法#

FIPS 202 標準本身冗長難讀，但你可以找到相當快、又比規格書更容易理解的開源實作。例如 Markku-Juhani O. Saarinen 的 MIT 授權 tiny_sha3（https://github.com/mjosaarinen/tiny_sha3/ ↗）用 19 行 C 解釋了 Keccak 的核心演算法：

static void sha3_keccakf(uint64_t st[25], int rounds)
{
    for (r = 0; r < rounds; r++) {

        // Theta
        for (i = 0; i < 5; i++)
            bc[i] = st[i] ^ st[i + 5] ^ st[i + 10] ^ st[i + 15] ^ st[i + 20];

        for (i = 0; i < 5; i++) {
            t = bc[(i + 4) % 5] ^ ROTL64(bc[(i + 1) % 5], 1);
            for (j = 0; j < 25; j += 5)
                st[j + i] ^= t;
        }

        // Rho Pi
        t = st[1];
        for (i = 0; i < 24; i++) {
            j = keccakf_piln[i];
            bc[0] = st[j];
            st[j] = ROTL64(t, keccakf_rotc[i]);
            t = bc[0];
        }

        // Chi
        for (j = 0; j < 25; j += 5) {
            for (i = 0; i < 5; i++)
                bc[i] = st[j + i];
            for (i = 0; i < 5; i++)
                st[j + i] ^= (~bc[(i + 1) % 5]) & bc[(i + 2) % 5];
        }

        // Iota
        st[0] ^= keccakf_rndc[r];
    }
}

這段程式實作了 Keccak 的置換 P——一個對「視為二十五個 64 位元字之陣列」的 1600 位元狀態的可逆變換。它迭代一連串輪，每輪由四個主要步驟組成：

  • Theta：包含 64 位元字之間的 XOR，或字的 1 位元旋轉值（ROTL64(w, 1) 把字 w 左旋 1 位元）。
  • Rho Pi：依硬編碼在 keccakf_rotc[] 陣列中的常數旋轉 64 位元字。
  • Chi：包含更多 XOR，也包含 64 位元字之間的邏輯 AND（& 運算子）。這些 AND 是 Keccak 中唯一的非線性運算，也是密碼學強度的來源。
  • Iota：與一個硬編碼在 keccakf_rndc[] 中的 64 位元常數做 XOR。

這些操作為 SHA-3 提供了一個沒有任何偏差或可利用結構的強置換演算法。

SHA-3 是超過十年研究的成果，數百位有能力的密碼分析者都未能攻破它，它短期內不太可能被破解。

Backward 建構雜湊函式 BLAKE2 Forward