ChaCha20-Poly1305 加密演算法介紹

簡介

ChaCha20 是一種對稱加密演算法，由 Daniel J. Bernstein 在 2008 年提出。它是基於 Salsa20 的改進版本。

而ChaCha20-Poly1305 是一種 AEAD（Authenticated Encryption with Associated Data）加密模式，結合了 ChaCha20 加密演算法與 Poly1305 認證碼(Message Authenticate Code)，用於提供機密性和完整性保護。

ChaCha20-Poly1305 的特性

ChaCha20-Poly1305 有以下的特性：

• 高效能：在軟體中，ChaCha20-Poly1305 的速度比 AES-GCM 更快，尤其在沒有硬體加速的環境下。
• 常數時間操作：ChaCha20-Poly1305 的操作是常數時間的，這有助於防止時序攻擊。
• 串流加密：ChaCha20 是一種串流加密演算法(stream cipher)，適合用於加密大量資料，而不需要填充。

ChaCha20-Poly1305 的應用

目前，ChaCha20-Poly1305 已被廣泛應用於網路協議中，例如：

• TLS 1.3：在 TLS 1.3 中，ChaCha20-Poly1305 是一種可選的加密套件。
• OpenSSH：OpenSSH 使用 ChaCha20-Poly1305 作為加密演算法之一。
• WireGuard：WireGuard VPN 使用 ChaCha20-Poly1305 作為其加密演算法。
• Google QUIC：Google 的 QUIC 也使用 ChaCha20-Poly1305 作為加密演算法。
• 高效能應用：ChaCha20-Poly1305 在高效能應用中也表現良好，尤其是在移動設備和嵌入式系統中。

ChaCha20-Poly1305 的運作原理可以分為兩個部分：加密和認證。
首先我們先來看加密的部分:

ChaCha20 的運作原理

1. 初始化狀態矩陣

ChaCha20 使用一個 4x4 的狀態矩陣（共 16 個 32-bit 的 word），初始化如下：

其中：

• $c_0, c_1, c_2, c_3$ 是常數，分別為 “expand 32-byte k” 的 ASCII code。
• $k_0 - k_7$ 是 256-bit 的金鑰，分成 8 個 32-bit 的word。
• $b$ 是 block counter，初始值為 0。
• $n_0, n_1, n_2$ 是 96-bit 的 nonce（隨機數），用於確保每次加密的唯一性。(不是秘密)

我們接下來將這個矩陣的元素位置用以下的方式標記：

2. Quarter Round 函數

我們定義一個Quarter Round 函數($QR$)，它接受四個 32-bit 的字作為輸入，並對他們進行混合/混淆操作:

圖片說明如下:

C語言實現如下:

void QuarterRound(uint32_t *a, uint32_t *b, uint32_t *c, uint32_t *d) {
    *a += *b; *d ^= *a; *d = (*d << 16) | (*d >> (32 - 16));
    *c += *d; *b ^= *c; *b = (*b << 12) | (*b >> (32 - 12));
    *a += *b; *d ^= *a; *d = (*d << 8) | (*d >> (32 - 8));
    *c += *d; *b ^= *c; *b = (*b << 7) | (*b >> (32 - 7));
}

3. 20 輪變換

ChaCha20 名字中的 “20” 代表它會對狀態矩陣進行 20 輪的變換，每一輪包含四個 Quarter Round 操作，分別作用於不同的列和對角線。

奇數輪作直行變換(Column Round)

偶數輪作對角線變換(Diagonal Round)

4. 最終輸出

最後把 20 輪變換後的狀態與初始狀態逐 word 相加，得到 ChaCha20 的輸出。

之後將最終狀態矩陣轉換為 64 個Bytes的 Keystream，並與明文進行 XOR 運算，產生密文。

• 如果明文的長度大於 64 Bytes，則會將 block counter 加 1，重新生成新的 Keystream，直到整個明文都被加密完成。
• 若是明文長度不是 64 Bytes 的整數倍，那會截斷 Keystream 來加密剩餘的明文。

Poly1305 的運作原理

Poly1305 是一種訊息認證碼（MAC）演算法，由 Daniel J. Bernstein 在 2005 年提出。它的主要目的是確保訊息的完整性和來源的真實性。

Poly1305 的運作原理可以分為兩個部分：生成認證碼和驗證認證碼。

生成認證碼

Poly1305 是在一個有限域(finite field) 上運作的，使用一個 130-bit 的質數 $p = 2^{130} - 5$。它接受兩個輸入：訊息 $M$ 和一個 256-bit 的金鑰 $K$，其中 $K$ 被分成兩個部分：$r$ 和 $s$。兩個部分都是128-bit 的數字:

分割訊息

將訊息分成最多 16 Bytes 的區塊。每個區塊以 little-endian 方式視為整數，並在每個區塊的資料末端上附加一個 0x01，因此每個區塊會被視為一個最多 129-bit 的整數。

多項式求值

設訊息被切成 $q$ 個區塊，對應整數為 $n_1, n_2, \dots, n_q$。Poly1305 會維護一個累加器 $a$（初始為 0），每次處理一個區塊：

全部區塊處理完後，再把 $s$ 加上去並截成 128-bit：

也就是說，Poly1305 本質上是在有限域上計算一個多項式：

驗證認證碼

接收端拿到訊息 $M$ 與 $\text{tag}$ 後，會用同一把一次性金鑰（同一組 $r,s$）重新計算一次 Poly1305：

1. 對 $M$ 做同樣的分塊與附加 0x01。
2. 依序更新累加器並得到新的 $\text{tag}'$。
3. 以常數時間比較 $\text{tag}'$ 與收到的 $\text{tag}$。

若相同則驗證成功；否則代表資料可能被竄改或金鑰不正確。

ChaCha20-Poly1305 的整合運作 (RFC 8439)

根據 RFC 8439，ChaCha20-Poly1305 的運作流程如下：

加密與生成tag

1. 生成金鑰與 nonce：
   • 使用 256-bit 的金鑰 $K$。
   • 使用 96-bit 的 nonce $N$（不可重複）。
2. 生成 Poly1305 金鑰：
   • 使用 ChaCha20 以 nonce $N$ 和 block counter = 0 生成第一個 32 Bytes 的 keystream，前 16 Bytes 作為 $r$，後 16 Bytes 作為 $s$。後面32 Bytes 不使用。

4. 加密明文：
   • 使用 ChaCha20 以 nonce $N$ 和 block counter = 1 開始生成 keystream，與明文進行 XOR 運算，產生密文。
5. 組裝AAD:
   • AAD（Associated Data）是額外的資料，會被 Poly1305 認證，但不會被加密。AAD 可以是任何長度的資料。

6. 計算 Poly1305 認證碼：
   • 將 AAD、密文以及它們的長度組裝成一個訊息，使用 Poly1305 計算認證碼。

解密與驗證tag

1. 生成 Poly1305 金鑰：
   • 與加密時相同，使用 ChaCha20 以 nonce $N$ 和 block counter = 0 生成 Poly1305 金鑰。
2. 驗證 Poly1305 認證碼：
   • 將收到的 AAD、密文以及它們的長度組裝成訊息，使用 Poly1305 計算認證碼，並與收到的 tag 比較。
   • 若驗證失敗，則拒絕解密並丟棄資料。
3. 解密密文：
   • 若驗證成功，使用 ChaCha20 以 nonce $N$ 和 block counter = 1 生成 keystream，與密文進行 XOR 運算，還原出明文。

tag 的偽造成功率

Poly1305 的 tag 是 128-bit，所以如果攻擊者只是隨機猜一個 tag，單次猜中的機率大約是：

這代表在不知道金鑰的情況下，要直接偽造出一個可通過驗證的 tag 幾乎是不可能的。不過在真實安全分析裡，這個數字通常還要考慮訊息長度與查詢次數。對於長度為 $q$ 個區塊的訊息，RFC 8439 給出的偽造成功率上界大致可寫成：

這個上界比 $2^{-128}$ 大，原因是 Poly1305 的 $r$ 會經過 clamp，而訊息越長，攻擊者可利用的結構也越多。因此，Poly1305 的安全性不是依賴完全不能偽造，而是依賴偽造成本高到可以忽略

參考資料

• ChaCha20 and Poly1305 for IETF Protocols
• ChaCha20
• Poly1305
• ChaCha20流加密算法原理与C语言实现
• ChaCha20的C語言實現