了解 GCM 安全性背後的代數
我想了解 GCM 安全性背後的代數。在我提問之前，讓我陳述一下我對 GCM 背後數學的理解。如果正確，我的問題在最後；如果不正確，請您解釋我的錯誤。
為簡單起見，假設只有一個密文塊 $ c $ . 我們希望我們的標籤有兩個屬性：
- $ tag_k(c) $ 應該是一個通用的統一雜湊 $ c $ : 也就是說，對於所有人 $ c $ ， 如果 $ k $ 是均勻隨機的， $ P[tag_k(c) = y] $ 對所有人都是統一的 $ y $ .
- $ tag_k(c) $ 不應該透露任何資訊 $ k $ ，即使當 $ c $ 是已知的。
乘以非零很容易滿足屬性 1 $ k $ 在 $ GF(2^n) $ , 因為, 在 $ GF(2^n) $ , $ f(x) = ax $ 對所有人來說都是一個獨特的排列 $ a \ne 0 $ ， 和 $ f $ 因此是一個通用的統一雜湊。
然而，屬性 2不會滿足 $ tag_k(c) = kc $ , 因為我們可以計算 $ c{^-1} $ 並解決 $ k = tag_k(c)c^{-1} $ . 為了滿足屬性 2，我們引入了“秘密密文”， $ c_0 $ , 並定義 $ tag_k(c) = kc + c_0 $ （加法是按位異或 $ GF(2^n) $ ). $ c_0 $ 有效地作為一次性墊來加密“根”標籤 $ kc $ .
如果我們想驗證兩個密文塊怎麼辦？我們可以重複該過程，確保使用新的 $ c_0 $ 每一次。在實踐中，AES-GCM 使用
c_0 = AES_k(counter++).但是，當一次驗證多個塊時，這是低效的。相反，我們可以使用以下公式為多個密碼塊使用一個標籤：
$$ tag_k(c_1, c_2,…c_n) = kc_0 + \sum k^nc_n. $$ （為簡單起見，我省略了長度欄位以及經過身份驗證的明文）。 這保留了這兩個屬性。
我們可能會傾向於將其簡化為 $ \sum kc_n $ ，但這失敗了，因為我們可以替換 $ c_a, c_b $ 和 $ fake_a, fake_b $ 只要 $ fake_a + fake_b = c_a + c_b $ . 例如，只要我們翻轉不同塊中的相應位，我們就可以翻轉任何密碼塊中的位。（這種類型的攻擊用於針對 WEP，它使用 CRC 作為其“MAC”）。
- 以上是正確的嗎？
- AES-GCM如何選擇 $ k $ ?
更重要的是，我們如何避免以下明顯的故障模式：
- 如果 $ k = 0 $ , $ tag(any_ciphertext) = 0 $
- 做 $ c_n = 0 $ 造成問題？它似乎沒有破壞任何屬性，但似乎仍然令人擔憂。 （請注意，我們不能簡單地附加零塊，因為這會改變長度欄位。）
- 在我看來，如果每個多塊算法都是正確的 $ k $ 是一個發電機 $ GF(2^n) $ 或者至少是非常高級的。但如果 $ k $ 恰好是低階，該方案將失敗。
例如：想像一下 $ k $ 有訂單 2。然後我們可以翻轉一點 $ c_1 $ 只要我們翻轉相同的位 $ c_3 $ ， 自從$$ \begin{align} k^2c_1 + k^4c_3 &= k^2(c_1 + c_3) \ &= k^2(c_1 + c_3 + d + d) \ &= k^2(c_1 + d) + k^4(c_3 + d)\end{align}. $$ GCM 如何避免這種故障模式？
我想了解 GCM 安全性背後的代數。
好吧，您寫出了 GCM 的身份驗證部分如何工作的機制；但是，要了解這些機制為何起作用，以不同的方式處理它會有所幫助。
GCM 在 $ GF(2^{128}) $ ; 這是一個欄位；重要的一點是，在一個領域中，任何非零多項式至多 $ n $ 最多有 $ n $ 零；也就是說，對於任何方程：
$$ a_n x^n + a_{n-1} x^{n-1} + … + a_0 x^0 = 0 $$
最多有 $ n $ 解決方案 $ x $ （假設至少有一個 $ a_i $ 值不為零）。
為什麼這很重要，稍後會很清楚。
現在，GCM 進行身份驗證的工作是獲取加密數據（和 AAD），並將其轉換為多項式；然後它將隨機數轉換為多項式的常數值，然後以秘密值評估該多項式 $ k $ ，並且該評估的結果是標籤；那是：
$$ tag := a_n k^n + a_{n-1} k^{k-1} + … + a_1 k^1 + \text{hash}(nonce) $$
現在，假設我們對同一個 nonce 有不同的消息/標籤對；如果出現以下情況，該消息/標籤將通過 GCM 完整性檢查：
$$ tag’ := a’n k^n + a’{n-1} k^{k-1} + … + a’_1 k^1 + \text{hash}(nonce) $$
我們可以做的是減去兩個多項式（一個對應於有效加密器生成的好的密文，另一個對應於攻擊者的猜測）；我們得到了
$$ 1 $$: $$ 0 = (a_n-a’n)k^n + (a{n-1} - a’_{n-1})k^{n-1} + … + (a_1 - a’_1)k^1 + (tag - tag’)k^0 $$
該等式僅在第二個密文/標籤對有效時才成立。
現在，我們回到最初的觀察：這至多是一個次數的多項式 $ n $ 所以最多有 $ n $ 不同的價值觀 $ k $ 這個等式是正確的。我們還知道多項式的至少一個係數是非零的（如果“偽造”密文與有效密文完全相同，則全零多項式為真，這不被認為是偽造的）。而如果 $ k $ 被不可預測地選擇，那麼有 $ 2^{128} $ 可能的值，因此它恰好是其中之一的機率 $ n $ 值最多 $ n2^{-128} $ ，這確實很小。
現在，要將這個論點變成一個實際的證明（已經完成），我們需要假設 a) $ k $ 是隨機均勻選擇的，並且 b) $ \text{hash}(nonce) $ 同樣是隨機選擇的（因為如果不是，攻擊者可以推斷出一些關於多項式值的東西，這會很糟糕）；事實證明，我們可以將兩者與 AES 的加密強度聯繫起來。
現在，回答您的問題：
- 以上是正確的嗎？
關; 你確實弄錯了一個細節；使用您的符號，我們將標籤計算為 $ tag_k(c_1, c_2,…c_n) = c_0 + \sum k^nc_n $ （注意 $ c_0 $ 不乘以 $ k $ ):
- AES-GCM如何選擇 $ k $ ?
它使用 GCM 密鑰使用 AES 加密全零塊。
- 如果 $ k=0 $ , $ tag(\text{any_ciphertext})=0 $
不， $ c_0 $ 不會乘以 $ k $ ，所以在這種情況下我們有：
$$ tag(\text{any_ciphertext}) = c_0 $$
這仍然意味著，在這種特定情況下，可以在不修改標籤的情況下任意修改密文，但這並不明顯。
顯而易見的問題是：“這還不是很糟糕嗎？”。好吧，使用 128 位標籤，攻擊者總是有機率 $ 2^{-128} $ 只是盲目猜測有效的密文/標籤對- $ k=0 $ 具有相同的發生機率，因此不會增加偽造機率。
- 做 $ c_n=0 $ 造成問題？
不; 如果你按照上面的邏輯， $ c_n=0 $ 不是特例。
- 但如果 $ k $ 恰好是低階，該方案將失敗。
這種特定的故障情況仍然屬於機率範圍內 $ n2^{-128} $ 如上圖；如果你（說）測試是否 $ k $ 有一個小訂單並拒絕這些值，您實際上不會降低偽造機率。
$$ 1 $$：在偶數特徵場中，例如 $ GF(2^{128}) $ , 加法和減法是同一個運算，所以我們通常都寫成 $ + $ ; 我把它保留為 $ - $ 對於不習慣這種約定的人來說，to make 會更清楚一些。