通過細分消息然後聚合結果來並行化 MAC
除 GMAC（和 Poly1305？）之外的大多數 MAC 都不可並行化。範例包括 CMAC 和 HMAC。
這些是否可以通過並行計算多個 MAC 然後合併結果來安全地並行化？這有點學術，但只是好奇。
假設您有一條消息是您分成四個部分，這樣
M==M1|M2|M3|M4. 然後，您對這些中的每一個計算 CMAC，然後對結果計算最終 CMAC。T=CMAC(CMAC(M1)|CMAC(M2)|CMAC(M3)|CMAC(M4))優點是這可以通過利用指令級並行性的方式來實現。您可以通過並行計算四個 CMAC 來實現這一點，而不是將消息分成四個塊，步長為 4*B，其中 B 是密碼的塊大小（例如 AES 的 128 位）。最終的 CMAC 也可以與每個組件 CMAC 的最後一個塊並行完成。
您還可以在支持 AVX-512 的 CPU 上使用那些瘋狂的 4X 並行 AES 指令來真正並行執行四個 CMAC。
顯然，結果與 CMAC(M) 不同，但安全性是否相同？這基本上是一個雜湊列表，所以我認為是的，但是 MAC 案例與普通雜湊案例不同。
編輯：更大膽的事情是只計算四個 CMAC 並對它們進行異或，但由於異或是可交換的，這讓我認為它容易受到選擇明文攻擊。
編輯#2：如果每個 MAC 都是獨立鍵控的，那麼 XOR 情況似乎是安全的，但我想更多地研究它。
編輯＃3：或者，如果上述內容是安全的，它似乎
CMAC(M1|CMAC(M2)|CMAC(M3)|CMAC(M4))應該是安全的。這可以通過在消息的所有四個部分（或條帶）上計算 CMAC 來並行完成，然後對第一個 CMAC 再做三個塊以合併兄弟姐妹。編輯#4：再考慮一下，**我認為最快的算法是使用不同的密鑰執行 N 個並行 HMAC/CMAC，然後將它們異或在一起。**只要 MAC 是安全的，這就是安全的。您不能交換任何東西，因為密鑰不同，例如
CMAC[k1](M1) XOR CMAC[k2](M2)!=CMAC[k1](M2) XOR CMAC[k2](M1)。在啟用 AVX2 的機器上，您可以使用_mm512_aesenc_epi128一次使用不同的密鑰並行執行四個 CMAC。即使沒有這種指令級並行性，如果 CPU 執行它，它也會啟動。所以你會有類似的東西（虛擬碼，使用帶有 16 字節塊的 CMAC-AES）：
K1 = KDF(K,1) K2 = KDF(K,2) K3 = KDF(K,3) K4 = KDF(K,4) while (remaining >= 64) { CMAC_BLOCK(K1,input) CMAC_BLOCK(K2,input + 16) CMAC_BLOCK(K3,input + 32) CMAC_BLOCK(K4,input + 48) remaining -= 64 input += 64 } // ... do final blocks with padding ... MAC = CMAC_FINAL(K1) XOR CMAC_FINAL(K2) XOR ...高度優化的實現將插入每一輪 AES 的指令，以允許 ILP 工作或使用 SIMD AES，如 _mm512_aesenc_epi128（如果可用）。
並行化 MAC 有兩種通用方法：
- 使用通用雜湊，如 GHASH 或 Poly1305，其代數結構基本上允許任意級別的並行性。
對於 GHASH 和 Poly1305，雜湊是多項式計算：
$$ \begin{equation} H_r(m_1 \mathbin| m_2 \mathbin| \dotsb \mathbin| m_n) := m_1 r^n + m_2 r^{n-1} + \dotsb + m_n r. \end{equation} $$
計算這一點的簡單方法是使用霍納規則：
$$ \begin{align} h_0 &:= m_1, \ h_1 &:= h_0 r + m_2, \ h_2 &:= h_1 r + m_3, \ &\vdots \ h_n &:= h_{n-1} r. \end{align} $$
如果您可以同時計算兩個乘法，那麼通過預先計算 $ r^2 $ 您可以一次處理兩個消息塊（處理奇數個消息塊作為練習留給讀者）：
$$ \begin{align} h_0 &:= m_1, \ h_2 &:= h_0 r^2 + m_2 r + m_3, \ h_4 &:= h_2 r^2 + m_4 r + m_5, \ &\vdots \ h_{n-2} &:= h_{n-4} r^2 + m_{n-2} r + m_{n-1}, \ h_n &:= h_{n-2} r^2 + m_n r. \end{align} $$
在不改變您計算的 MAC的*語義的情況下，相同的想法可以擴展到實現*中的任意程度的並行性。** 其他通用散列 MAC 通常具有類似的可並行代數結構，例如UMAC，它使用內積和多項式評估的組合。 2. 在消息的樹結構編碼上使用類似 BLAKE2 的 PRF——Merkle 樹。
如果 $ H $ 是一個均勻隨機（秘密）函式，那麼也是$$ (x, y) \mapsto H(2 \mathbin| H(0 \mathbin| x) \mathbin| H(1 \mathbin| y)) $$在適當的域上，或者至少幾乎如此——這種構造與隨機預言機無異。那麼如果你實例化 $ H = F_k $ 對於均勻隨機 $ k $ 在哪裡 $ F $ 是一個偽隨機函式族，構造的 PRF 安全性$$ (x, y) \mapsto F_k(2 \mathbin| F_k(0 \mathbin| x) \mathbin| F_k(1 \mathbin| y)) $$與原語的 PRF 安全性沒有太大區別 $ F_k $ . 當然，一個統一的隨機函式可以產生一個好的 MAC，所以 PRF $ (x, y) \mapsto F_k(2, F_k(0, x), F_k(1, y)) $ 為固定長度的消息提供良好的 MAC。這裡 $ F_k $ 例如，可能是AES-CMAC 或 HMAC-SHA256。
您必須注意對消息進行唯一編碼。如果你暴露了預言機 $ H $ （僅適用於短消息）和 $ (x, y) \mapsto H(H(x) \mathbin| H(y)) $ （僅在長消息上），那麼攻擊者可以偽造身份驗證器 $ (x, y) $ 通過查詢 $ H $ 神諭 $ x $ ， 為了 $ y $ ，並且對於 $ H(x) \mathbin| H(y) $ . 這個錯誤並不是立即顯而易見的，而是出現在 BitTorrent 和證書透明度日誌等現實世界的協議中，這就是存在BLAKE2 樹散列和Sakura等提議標準的原因。
通常，當我們想要增量驗證或修改樹的一部分時會應用這種技術，但是您可以將基數擴展到您想要最大化並行性的任何扇出。BLAKE2bp 和 BLAKE2sp 並行散列模式本質上是使用 BLAKE2 壓縮函式作為 PRF 來實現這一點的，但是如果由於某種原因您必須使用 AES-CMAC 或 HMAC-SHA256，您可以在此結構中使用它們作為 PRF（相當性能成本），前提是您將本機計算的所有參數唯一地編碼到 BLAKE2 中。
Merkle 樹可以實現基本上任意程度的並行性，但您必須事先同意更改您使用的 MAC。 也許現在您喜歡四個並行 AES-CMAC 的想法；也許明天你寧願選擇八個；也許在星期二，一個只能執行一個順序 AES-CMAC 的小型 ARM 系統的客戶很傷心。
你建議的結構怎麼樣？
T=CMAC(CMAC(M1)|CMAC(M2)|CMAC(M3)|CMAC(M4))如果這是一個固定深度的Merkle 樹，那麼它可能會構成一個安全的 MAC，但關鍵在於您在密鑰下為 CMAC 公開了哪些預言機以及如何將消息編碼為樹結構的詳細資訊。當然，CMAC 沒有像 BLAKE2 壓縮函式那樣對諸如樹位置之類的參數進行編碼的內置空間，因此您必須找到另一種方法來做到這一點。
CMAC(M1|CMAC(M2)|CMAC(M3)|CMAC(M4))與上麵類似，但現在您更有可能在您的密鑰下意外地暴露一個普通 CMAC 的預言機。
編輯#2：如果每個 MAC 都是獨立鍵控的，那麼 XOR 情況似乎是安全的，但我想更多地研究它。
那篇文章討論 $ H_1(m) \oplus H_2(m) \oplus \dotsb \oplus H_n(m) $ , 其中 $ H_i $ 是獨立選擇的應用於整個消息的 MAC $ m $ ，但你認為這是意味著 $ H_1(m_1) \oplus H_2(m_2) \oplus \dotsb \oplus H_n(m_n) $ 分別應用於單獨的塊 $ m_1 \mathbin| m_2 \mathbin| \dotsb \mathbin| m_n $ 的 $ m $ . 你推斷的結論不成立。（當然，您還必須花費額外的時間來獲取子密鑰！）